HashSet[uint64] slow insertion depending on values

[cwpearson]

The rate of inserting uint64s into a hash set varies wildly with the order and the range of integers inserted

Example

# slow_set.nim
import sets
import times

when isMainModule:
    var hs1: HashSet[uint64]
    var hs2: HashSet[uint64]
    var hs3: HashSet[uint64]

    # insert 0..200k
    var time = cpuTime()
    for i in 0..200_000:
        let k1 = uint64(i)
        hs1.incl(k1)
    echo "time ", (cpuTime() - time)

    # interleave insert 0..100k and 100k..200k
    time = cpuTime()
    for i in 0..100_000:
        let k1 = uint64(i)
        let k2 = uint64(i + 100_000)
        hs2.incl(k1)
        hs2.incl(k2)
    echo "time ", (cpuTime() - time)

    # interleave insert 0..100k and 1.0M..1.1M
    time = cpuTime()
    for i in 0..100_000:
        let k1 = uint64(i)
        let k2 = uint64(i + 1_000_000)
        hs3.incl(k1)
        hs3.incl(k2)
    echo "time ", (cpuTime() - time)

Current Output

Compiled with nim c -d:release -r slow_set.nim.

time 0.016778
time 1.01831
time 14.043752

Expected Output

I would expect the three different insertion loops to take roughly the same amount of time.
They are all inserting the same amount of unique values.
In the second loop, I just interleave the insertion order, and in the third loop, I insert some larger numbers.

Possible Solution

Additional Information

This issues #10097 talks about integer hashing and collisions, but all of my uint64s are well below the max uint32.

This also happens with hashTable keys, presumably for similar reasons?

In my actual project I am deduplicating an edge list for a graph where the source and destination vertex for a node are sort of similar to loop 3, so the performance is not good.

$ nim -v
Nim Compiler Version 0.20.2 [MacOSX: amd64]
Compiled at 2019-07-17
Copyright (c) 2006-2019 by Andreas Rumpf

git hash: 88a0edba4b1a3d535b54336fd589746add54e937
active boot switches: -d:release

[krux02]

In general I have to say that you can always construct a sequence of keys that works very bad for the hash set implementation no matter what the hashing function does. But this does indeed look strange, as these keys don't look like as if they would cause particularly many collisions. Did you measure what part exactly causes this slowdown?

EDIT: I did the benchmark, this loop here is where all the time is wasted:

Nim/lib/pure/collections/hashcommon.nim

Line 40 in 210988c

while isFilled(t.data[h].hcode):

[cwpearson]

I added 3 more experiments, with resizing the hashSet first:

import sets
import times

when isMainModule:
    var hs1: HashSet[uint64]
    var hs2: HashSet[uint64]
    var hs3: HashSet[uint64]
    var hs4 = initHashSet[uint64](rightSize(100_000))
    var hs5 = initHashSet[uint64](rightSize(200_000))
    var hs6 = initHashSet[uint64](rightSize(1_100_000))

    # insert 0..200k
    var time = cpuTime()
    for i in 0..200_000:
        let k1 = uint64(i)
        hs1.incl(k1)
    echo "time ", (cpuTime() - time)

    # interleave insert 0..100k and 100k..200k
    time = cpuTime()
    for i in 0..100_000:
        let k1 = uint64(i)
        let k2 = uint64(i + 100_000)
        hs2.incl(k1)
        hs2.incl(k2)
    echo "time ", (cpuTime() - time)

    # interleave insert 0..100k and 1.0M..1.1M
    time = cpuTime()
    for i in 0..100_000:
        let k1 = uint64(i)
        let k2 = uint64(i + 1_000_000)
        hs3.incl(k1)
        hs3.incl(k2)
    echo "time ", (cpuTime() - time)

    # interleave insert 0..100k and 1.0M..1.1M
    # but insert into a hashSet with space for100k
    time = cpuTime()
    for i in 0..100_000:
        let k1 = uint64(i)
        let k2 = uint64(i + 1_000_000)
        hs4.incl(k1)
        hs4.incl(k2)
    echo "time ", (cpuTime() - time)

    # interleave insert 0..100k and 1.0M..1.1M
    # but insert into a hashSet with space for 200K
    time = cpuTime()
    for i in 0..100_000:
        let k1 = uint64(i)
        let k2 = uint64(i + 1_000_000)
        hs5.incl(k1)
        hs5.incl(k2)
    echo "time ", (cpuTime() - time)

    # interleave insert 0..100k and 1.0M..1.1M
    # but insert into a hashSet with space for 1.1M
    time = cpuTime()
    for i in 0..100_000:
        let k1 = uint64(i)
        let k2 = uint64(i + 1_000_000)
        hs6.incl(k1)
        hs6.incl(k2)
    echo "time ", (cpuTime() - time)

By resizing the hashSet large enough to cover the largest expected integer, we recover all the performance (loop 6) and then some.
Making it big enough to just probably hold all of the integers recovers some of the performance (loop 5).
Making it large but still too small doesn't have much impact (loop 4).

time 0.017222
time 1.267755
time 16.218246
time 15.879905            # initHashSet(rightSize(100k))
time 9.667273999999999.   # initHashSet(rightSize(200k))
time 0.003250000000001307 # initHashSet(rightSize(1.1M))

It's been a while since I took my CS algorithms course, but is it possible that the logic which controls when to resize the HashSet as it grows has some problems?

[cwpearson]

Just in case

https://github.com/cwpearson/nim-issue-11764

[cwpearson]

Hi, now that 1.0.0 has come out I re-ran this https://github.com/cwpearson/nim-issue-11764:

Nim Compiler Version 1.0.0 [Linux: amd64]
Compiled at 2019-09-23
Copyright (c) 2006-2019 by Andreas Rumpf

git hash: f7a8fc46c0012033917582eb740dc0343c093e35
active boot switches: -d:release

(1) time 0.015417049
(2) time 0.952415456
(3) time 12.335662364
(4) time 12.212460556
(5) time 7.530930397999999
(6) time 0.003257626999996432

• (1): insert 0.200k into set in order
• (2): insert 0..100k and 100k..200k interleaved
• (3): insert 0..100k and 1M..1.1M interleaved
• (4): (3), but hashset is sized for 100k insertions
• (5): (3), but hashset is sized for 200k insertions
• (6): (3), but hashset is sized for 1.1M insertions

I'd expect 1-3 to be roughly the same performance, and 4-6 to be somewhat better than 1-3 due to the pre-allocation. In practice, that is still not what we see.

[Araq]

Looks like you crafted the numbers to produce collisions, that is always a danger when using hashing.

[cwpearson]

Thanks!

It looks like the hash for int is just that int value:

Nim/lib/pure/hashes.nim

Lines 115 to 117 in e9f7455

	proc hash*(x: int): Hash {.inline.} =
	## Efficient hashing of integers.
	result = x

.

It seems like the hashset implementation tries the next consecutive bucket when there is a collision:

Nim/lib/pure/collections/hashcommon.nim

Lines 29 to 30 in e9f7455

	proc nextTry(h, maxHash: Hash): Hash {.inline.} =
	result = (h + 1) and maxHash

The general wisdom for open addressing sets seems to be that the hash function needs to avoid placing consecutive values in consecutive buckets (wikipedia). "Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent."

1. I agree that collisions are always possible with a hash function, but this choice of hash function seems like it has collisions in a common scenario, where other choices of hash functions would only have collisions in a pathological case. The "efficient" hash implementation for ints is actually causing a big performance issue.
2. Even if you don't agree with 1), I think the concern about clustering summarized in Wikipedia may argue for a redesign of the hash/hashset implementation in the context of integers. When folks are hashing they probably want to avoid collisions, so it might be worth considering using the MurmurHash that is used for other data on ints as well, even if the cost of each hash is higher.

As an aside, I gave IntSet from the Nim lib a try and the performance is much better (case (8) in https://github.com/cpwearson/nim-issue-11764).

[Araq]

But my point is that

   let k1 = uint64(i)
   let k2 = uint64(i + 1_000_000)

is not common. Usually IDs are mostly consecutive. May I ask where your integers come from?