bad Dict performance for small integers, strings

[binarybana]

In playing with dictionaries, I boiled down my code to a microbenchmark of simply filling a Dict{Int,Float64} with a million elements. Compared to Python, the results are disappointing. Here's the gist of the gist:

function stress0(N::Int)
    x = Dict{Int,Float64}()
    for i = 1:N
        x[i] = 0.0
    end
    return x
end

Full Julia and Python code

julia> load("test.jl")

julia> for i=1:5 @time stress0(10^6); end
elapsed time: 3.6805942058563232 seconds
elapsed time: 4.042525053024292 seconds
elapsed time: 4.042686939239502 seconds
elapsed time: 4.022021055221558 seconds
elapsed time: 4.173625946044922 seconds

In [1]: %run test.py

In [4]: %time stress0(10**6);
CPU times: user 0.17 s, sys: 0.08 s, total: 0.25 s
Wall time: 0.23 s

In [5]: %time stress0(10**6);
CPU times: user 0.15 s, sys: 0.07 s, total: 0.22 s
Wall time: 0.21 s

In [6]: %time stress0(10**6);
CPU times: user 0.18 s, sys: 0.08 s, total: 0.27 s
Wall time: 0.20 s

So roughly a 20x difference. And even if we preallocate the dictionary to a more appropriate size:

julia> for i=1:5 @time stress0prime(10^6); end
elapsed time: 0.8082170486450195 seconds
elapsed time: 0.9532439708709717 seconds
elapsed time: 0.9672729969024658 seconds
elapsed time: 0.9541919231414795 seconds
elapsed time: 0.9703891277313232 seconds

We are still around 5x. I heard somewhere that Julia has a much better hashing algorithm than Python (in terms of distribution), and if that's the cause of this, is it worth the 20x?

And to make sure this wasn't a read/write tradeoff, reading is not as bad, but still 5x slower:

julia> x = stress0(10^6);

julia> for i=1:5 @time stress2(x,10^6); end
elapsed time: 1.0894720554351807 seconds
elapsed time: 1.150738000869751 seconds
elapsed time: 1.089750051498413 seconds
elapsed time: 1.116157054901123 seconds
elapsed time: 1.0949499607086182 seconds

In [8]: x = stress0(10**6)

In [12]: %time stress2(x,10**6);
CPU times: user 0.26 s, sys: 0.03 s, total: 0.28 s
Wall time: 0.26 s

[nolta]

Agreed, this is disappointing. I fooled around w/ the implementation for about 20mins, and sped up your write benchmarks by 2x (https://github.com/JuliaLang/julia/compare/mn/fasterdict).

[nolta]

Python's hash function for integers is the identity, e.g., hash(5) = 5. If i make the same change to julia, i.e.,

-hash(x::Integer) = _jl_hash64(uint64(x))
+hash(x::Integer) = uint64(x)

then julia is much more competitive:

                    stress0 stress2
------------------------------------
 julia               1.85s   0.63s
 julia w/ hashfix    0.27s   0.14s
 python              0.15s   0.26s

[StefanKarpinski]

Here's a very thorough answer on StackExchange regarding quality of hashing algorithms:

http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633

The conclusion is basically that Murmur – which is the algorithm we are using – is the best overall hashing algorithm. The stress tests in this issue are all contrived (unintentionally) to penalize any hashing algorithm that doesn't do what Python's identity hashing for integers does. Most real-world test cases, however, don't resemble this at all, because if you want to use the integers 1-N as keys, the obvious and natural data structure is an array, not a hash. If you don't care that much about speed, either one will work fine. If you do care a lot about speed you can take the time to use the appropriate data structure. In other use cases where a hash really is the appropriate data structure, non-identity hashing for integers is a big win. We're already doing the right thing here, imo.

[nolta]

Can we come up w/ an example for which our integer hashing is superior to python's? I tried randomizing the keys, but python still smokes us:

                    stress0 stress0-rand
-----------------------------------------
 julia               1.45s     1.42s
 python              0.15s     0.32s

[JeffBezanson]

To see it you have to "attack" the hash function with a set of keys
designed to cause collisions. I'm sure the python implementers decided not
to worry about such a case, and perhaps we should follow.
On Oct 28, 2012 1:11 PM, "Mike Nolta" notifications@github.com wrote:

Can we come up w/ an example for which our integer hashing is superior to
python's? I tried randomizing the keys, but python still smokes us:

                stress0 stress0-rand

---

julia 1.45s 1.42s
python 0.15s 0.32s

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/1423#issuecomment-9847789.

[StefanKarpinski]

Randomizing the keys how? By using a different insertion order? That doesn't really slow down identity hashing at all. Here's a case where Julia is 2x faster for string keys:

function stress_strings(n::Int)
    d = Dict{String,Int}()
    for i = 1:n
        d[string(i)] = i
    end
    return d
end

julia> [@elapsed stress_strings(10^5) for i=1:5]
5-element Float64 :Array:
 0.545406
 0.499304
 0.50927 
 0.576306
 0.454787

In [1]: %paste
def stress_strings(n):
    d = {}
    for i in xrange(1,n):
        d[str(i)] = i
    return d

In [2]: %time stress_strings(10**6);
CPU times: user 0.84 s, sys: 0.12 s, total: 0.95 s
Wall time: 0.99 s

In [3]: %time stress_strings(10**6);
CPU times: user 0.88 s, sys: 0.11 s, total: 1.00 s
Wall time: 1.01 s

In [4]: %time stress_strings(10**6);
CPU times: user 0.92 s, sys: 0.12 s, total: 1.04 s
Wall time: 1.13 s

In [13]: %time stress_strings(10**6);
CPU times: user 0.94 s, sys: 0.12 s, total: 1.05 s
Wall time: 1.07 s

In [5]: %time stress_strings(10**6);
CPU times: user 0.97 s, sys: 0.14 s, total: 1.10 s
Wall time: 1.12 s

[nolta]

Yeah, i shuffled the insert order.

Here are the gory details, adding a couple of tests where i choose keys at random:

def stress1(keys):
    x = {}
    for i in keys:
        x[i] = 0.0
    return x

$ python -m timeit -s 'import test,random; n = range(10**6)' 'test.stress1(n)'
10 loops, best of 3: 143 msec per loop
$ python -m timeit -s 'import test,random; n = range(10**6); random.shuffle(n)' 'test.stress1(n)'
10 loops, best of 3: 322 msec per loop
$ python -m timeit -s 'import test,random; n = [random.randint(0,100) for i in range(10**6)]' 'test.stress1(n)'
10 loops, best of 3: 80.5 msec per loop
$ python -m timeit -s 'import test,random; n = [random.randint(0,100000000) for i in range(10**6)]' 'test.stress1(n)'
10 loops, best of 3: 300 msec per loop

function stress1(keys::Array{Int,1})
    x = Dict{Int,Float64}()
    for i in keys
        x[i] = 0.0
    end
    return x
end

julia> n = [1:10^6]; mean([@elapsed stress1(n) for i=1:5])
1.434598159790039

julia> n = shuffle([1:10^6]); mean([@elapsed stress1(n) for i=1:5])
1.0441438198089599

julia> n = randi((0,100),10^6); mean([@elapsed stress1(n) for i=1:5])
0.03199162483215332

julia> n = randi((0,100000000),10^6); mean([@elapsed stress1(n) for i=1:5])
1.1499474048614502

And here's julia w/ identity int hashing (hash(x::Integer) = uint(x)):

julia> n = [1:10^6]; mean([@elapsed stress1(n) for i=1:5])
0.25340638160705564

julia> n = shuffle([1:10^6]); mean([@elapsed stress1(n) for i=1:5])
0.8471670150756836

julia> n = randi((0,100),10^6); mean([@elapsed stress1(n) for i=1:5])
0.021085405349731447

julia> n = randi((0,100000000),10^6); mean([@elapsed stress1(n) for i=1:5])
1.0878849983215333

Summary:

                 A      B      C      D
------------------------------------------
 julia         1.43s  1.04s  0.03s  1.15s
 julia w/ IIH  0.25s  0.85s  0.02s  1.09s
 python        0.14s  0.32s  0.08s  0.30s
------------------------------------------
IIH = "identity int hashing"

So python's advantage isn't solely due to IIH. There's an interesting discussion in the python dict source code.

[binarybana]

Most real-world test cases, however, don't resemble this at all, because if you want to use the integers 1-N as keys, > the obvious and natural data structure is an array, not a hash.

My primary use case is sparse arrays (such as case D in nolta's previous post) specifically in representing probability tables where the amount of filled values will typically be many orders of magnitude less than the total integer key space. So I need speed with integer keys as the memory needs of dense arrays are unfeasible.

Unfortunately, IIH does not appear to greatly improve case D, but everything else looks nice.

It is interesting how 'stock' julia is actually improved with a shuffled key insertion and IIH is harmed. Perhaps this is due to the number of collisions over the entire lifecycle of the Dict throughout the expansions?

[pao]

Would it make sense to generalize the native sparse arrays (in sparse.jl) to 1D?

[nolta]

@StefanKarpinski, looks like you ran stress_strings 10^5 times for julia, but 10**6 for python?

[StefanKarpinski]

You are correct, sir! I meant to run the Julia one 10^6 times too but was using 10^5 until I got things right. Corrected:

julia> [@elapsed stress_strings(10^6) for i=1:5]
5-element Float64 :Array:
 27.0971
 30.2122
 31.2654
 32.599 
 30.7837

So we're getting our asses handed to us here. Especially note the worse than linear slow-down: the hash isn't scaling. This definitely needs a lot of improvement.

[JeffBezanson]

I can get a 3-4x speedup just by growing by a factor of 4 each time instead of 2.

[nolta]

                         A      B      C      D      E
---------------------------------------------------------
 julia@099936a         1.49s  1.31s  0.05s  1.35s 15.27s
 julia@0a67d86         0.70s  0.88s  0.06s  1.09s  3.71s

"E" is Stefan's string test, and the numbers in the first row have shifted a bit because i upped the iterations to 50.

[ViralBShah]

@pao Can you elaborate a bit more on your comment about 1D sparse?