Why is Mojo's dictionary (or for loop) slower than Python's?

[ekbrown]

I used Mojo's (v. 0.7.0) dictionary data structure to calculate the frequency of words in a file with 230+ million words, and did the same with Python. Surprisingly, Python was 7x times faster than Mojo. I imagine I did something wrong, as I was expecting "the usability of Python with the performance of C". Anyone have an idea? I'll link to my Mojo and Python scripts below.

My Mojo script:
https://github.com/ekbrown/scripting_for_linguists/blob/main/Script_populate_dict.mojo

My Python script:
https://github.com/ekbrown/scripting_for_linguists/blob/main/Script_populate_dict.py

A video in which I test the above two scripts:
https://youtu.be/mB_1SQlS_B0

[wiseaidev]

Thank you for sharing your insights. This is precisely what I was looking for; A detailed comparison of the identical implementation in both languages. It's important not to make unsubstantiated claims about Mojo being faster than Rust without a thorough examination. Now, Imagine if we could contrast that with Rust; it would make Mojo significantly slower, with a performance difference like ~100X.

[soraros]

What do you mean by identical implementation?

[wiseaidev]

The layout of the examples in both languages is identical, as outlined by the code provided by Lord Brown for what he is measuring:

# Mojo or whatever the stolen Rust syntax is called
fn get_freqs(in_path: String) raises -> String:
	let txt: String = get_text(in_path)
	let wds: DynamicVector[String] = txt.split(" ")
	let t0 = now()
	var freqs = Dict[StringKey, Int]()
	for i in range(len(wds)):
		let wd: String = wds[i]
		if freqs.__contains__(wd):
			freqs[wd] = freqs.__getitem__(wd) + 1
		else:
			freqs.__setitem__(wd, 1)
	let t1 = now()
	print((t1-t0)/1_000_000_000)
	
	return freqs.__getitem__("THE")

# Python
def get_freqs(in_path):
    txt = get_text(in_path)
    wds = txt.split(" ")
    t0 = time()
    freqs = {}
    for i in range(len(wds)):
        wd = wds[i]
        if wd in freqs:
            freqs[wd] = freqs[wd] + 1
        else:
            freqs[wd] = 1
    t1 = time()
    print(t1 - t0)
    return freqs["THE"]

[soraros]

Ah, I thought you mean the implementation of Mojo Dict vs Python dict are identical, which is what the code is meant to test. The benchmark does show that the Mojo implementation is inferior, but your point is rather moot. This is an important point for one can't improve the Python dict by using Python (you have to write C), but people can just improve the Mojo Dict by, say, porting absl::flat_hash_map to Mojo in Mojo, which is exactly what Rust did.

[soraros]

In your case, my guess is that it is memory allocation that takes the most time, because String doesn't have small string optimisation.

Notice large part of Mojo's standard library is still WIP. Dict for one, is only introduced in 0.7.0 (the latest version), and it's more "place holder" to make sure things mash together than being fully optimised implementation. Introduce them early helps getting the API right, and can serve to replace the many hand rolled implementation by the community. There are both minimal hand-rolled hash map and hash function that perform better than the standard library ones, which proves my point. Notice Mojo is a system programming language like C++ and Rust. Its standard library types are not builtins like Python, but just ordinary structs. It's only a matter of (of course that's a lot of work) implementing the needed optimisations.

To be honest, you could make Mojo look even worse, for your Python implementation is not optimal. It could be shorter and faster by using collections.Counter.

[ekbrown]

@soraros Thanks for the tip! My script is now 9x faster! Here's my updated script:
https://github.com/ekbrown/scripting_for_linguists/blob/main/Script_populate_hashmapdict.mojo

And thanks to Maxim Zaks (is that you?) for the mojo-hash github repo here:
https://github.com/mzaks/mojo-hash

[ekbrown]

With the improvements with v24.4, Mojo’s Dict is 4x faster:
https://youtu.be/ZpEZ5zMV1Xs

[rd4com]

Hello @ekbrown , nice !
Subscript [] and __getitem__ don't returns references yet,
this is why the current version of your scripts are doing a lot of __copyinit__;

➡️ Here is how you could use references, with 🔥 mojo nightly 2024.6.1912 (f72bd5ea):

# mojo nightly 2024.6.1912 (f72bd5ea)
fn get_freqs(in_path: String) raises -> String:
    var txt: String = get_text(in_path)
    var wds: List[String] = txt.split(" ")
    var t0 = now()
    var freqs = Dict[String, UInt64]()
    for i in wds:
        if i[] in freqs:
            freqs.__get_ref(i[]) +=  1
        else:
            freqs[i[]] = 1
    var t1 = now()
    print((t1-t0)/1_000_000_000)

🥳 This should at least double the performances ! (1.98x here )

 

Mojo now support auto dereference, which reduce the amount of empty [].

It is just a question of time before they turn into a new 🐍 Python experience 👍

(a lot of thoughts are devoted to design theses API's)