On 6/22/22 9:26 PM, John Fastabend wrote:
> Martin KaFai Lau wrote:
>> On Tue, Jun 21, 2022 at 10:49:46PM -0700, John Fastabend wrote:
>>> Martin KaFai Lau wrote:
>>>> On Tue, Jun 21, 2022 at 12:17:54PM -0700, John Fastabend wrote:
>>>>>> Hashmap Control
>>>>>> ===============
>>>>>> num keys: 10
>>>>>> hashmap (control) sequential get: hits throughput: 20.900 ± 0.334 M ops/s, hits latency: 47.847 ns/op, important_hits throughput: 20.900 ± 0.334 M ops/s
>>>>>>
>>>>>> num keys: 1000
>>>>>> hashmap (control) sequential get: hits throughput: 13.758 ± 0.219 M ops/s, hits latency: 72.683 ns/op, important_hits throughput: 13.758 ± 0.219 M ops/s
>>>>>>
>>>>>> num keys: 10000
>>>>>> hashmap (control) sequential get: hits throughput: 6.995 ± 0.034 M ops/s, hits latency: 142.959 ns/op, important_hits throughput: 6.995 ± 0.034 M ops/s
>>>>>>
>>>>>> num keys: 100000
>>>>>> hashmap (control) sequential get: hits throughput: 4.452 ± 0.371 M ops/s, hits latency: 224.635 ns/op, important_hits throughput: 4.452 ± 0.371 M ops/s
>>>>>>
>>>>>> num keys: 4194304
>>>>>> hashmap (control) sequential get: hits throughput: 3.043 ± 0.033 M ops/s, hits latency: 328.587 ns/op, important_hits throughput: 3.043 ± 0.033 M ops/s
>>>>>>
>>>>>
>>>>> Why is the hashmap lookup not constant with the number of keys? It looks
>>>>> like its prepopulated without collisions so I wouldn't expect any
>>>>> extra ops on the lookup side after looking at the code quickly.
>>>> It may be due to the cpu-cache misses as the map grows.
>>>
>>> Maybe but, values are just ints so even 1k * 4B = 4kB should be
>>> inside an otherwise unused server class system. Would be more
>>> believable (to me at least) if the drop off happened at 100k or
>>> more.
>> It is not only value (and key) size. There is overhead.
>> htab_elem alone is 48bytes. key and value need to 8bytes align also.
>>
>
> Right late night math didn't add up. Now I'm wondering if we can make
> hashmap behave much better, that drop off is looking really ugly.
>
>> From a random machine:
>> lscpu -C
>> NAME ONE-SIZE ALL-SIZE WAYS TYPE LEVEL SETS PHY-LINE COHERENCY-SIZE
>> L1d 32K 576K 8 Data 1 64 1 64
>> L1i 32K 576K 8 Instruction 1 64 1 64
>> L2 1M 18M 16 Unified 2 1024 1 64
>> L3 24.8M 24.8M 11 Unified 3 36864 1 64
>
> Could you do a couple more data point then, num keys=100,200,400? I would
> expect those to fit in the cache and be same as 10 by the cache theory. I
> could try as well but looking like Friday before I have a spare moment.
>
> Thanks,
> John
Here's a benchmark run with those num_keys.
Hashmap Control
===============
num keys: 10
hashmap (control) sequential get: hits throughput: 23.072 ± 0.208 M ops/s, hits latency: 43.343 ns/op, important_hits throughput: 23.072 ± 0.208 M ops/s
num keys: 100
hashmap (control) sequential get: hits throughput: 17.967 ± 0.236 M ops/s, hits latency: 55.659 ns/op, important_hits throughput: 17.967 ± 0.236 M ops/s
num keys: 200
hashmap (control) sequential get: hits throughput: 17.812 ± 0.428 M ops/s, hits latency: 56.143 ns/op, important_hits throughput: 17.812 ± 0.428 M ops/s
num keys: 300
hashmap (control) sequential get: hits throughput: 17.070 ± 0.293 M ops/s, hits latency: 58.582 ns/op, important_hits throughput: 17.070 ± 0.293 M ops/s
num keys: 400
hashmap (control) sequential get: hits throughput: 17.667 ± 0.316 M ops/s, hits latency: 56.604 ns/op, important_hits throughput: 17.667 ± 0.316 M ops/s
num keys: 500
hashmap (control) sequential get: hits throughput: 17.010 ± 0.409 M ops/s, hits latency: 58.789 ns/op, important_hits throughput: 17.010 ± 0.409 M ops/s
num keys: 1000
hashmap (control) sequential get: hits throughput: 14.330 ± 0.172 M ops/s, hits latency: 69.784 ns/op, important_hits throughput: 14.330 ± 0.172 M ops/s
num keys: 10000
hashmap (control) sequential get: hits throughput: 6.047 ± 0.024 M ops/s, hits latency: 165.380 ns/op, important_hits throughput: 6.047 ± 0.024 M ops/s
num keys: 100000
hashmap (control) sequential get: hits throughput: 4.472 ± 0.163 M ops/s, hits latency: 223.630 ns/op, important_hits throughput: 4.472 ± 0.163 M ops/s
num keys: 4194304
hashmap (control) sequential get: hits throughput: 2.785 ± 0.024 M ops/s, hits latency: 359.066 ns/op, important_hits throughput: 2.785 ± 0.024 M ops/s
