Poor cache space utilization with "sequential" keys / multithreaded about freecache

[anton-povarov]

tested with https://github.com/spaolacci/murmur3

result

entries: 12417, evacuated: 0, overwritten: 0
avg_value_len: 43.480773
bytes per item: 84.44680679713296 - 43.480773 - 16 = 24.966033797132965

and is about (non-scientifically) 20% faster than md5

[anton-povarov]

Hm... actually tested it some more. And while a better hash function does solve the issue in single-threaded case, it's still very bad in multithreaded case.
With 10 goroutines, all inserting same keys, but slightly different values (so a zillion of evacuates happens) - overhead per item still grows to ridiculous values.

for example:
same code as above gist, but changed the following params

const cache_size = 10 * 1024 * 1024 // was 1 megabyte
n_keys := 10 * 1000 * 1000 // was 1 million

here's the result with: const n_routines = 10

entries: 42078, evacuated: 120957842, overwritten: 77988935
avg_value_len: 43.49973858
bytes per item: 249.1981558058843 - 43.49973858 - 16 = 189.69841722588433

vs const n_routines = 1

entries: 125323, evacuated: 0, overwritten: 0
avg_value_len: 43.4929523
bytes per item: 83.6698770377345 - 43.4929523 - 16 = 24.176924737734495

[coocood]

Thank you for your intensive testing on it.
So it seems like the memory utilization issue is not caused by hash function.
The difference of entry overhead seems too big for the difference of hash function distribution quality.

[coocood]

I think this is normal.

If you set n_routines to one, then every key is new, there is no overwrites, the entry length is exactly (24+keyLen+valueLen).

If you set n_routines to 10, the entry can be overwritten.

If the new value is larger than the old entry's capacity, it won't be updated in place, then the old entry's space is not utilized.

If the new value is smaller than the old entry's capacity, then there would be an in-place update, (capacity - valueLen) of space is not utilized.

Whenever the capacity is smaller than the new value, the capacity is doubled, so when you keep increasing the size of the new value, it won't keep writing new entries, most of the update would be in place update.

[anton-povarov]

Even in single threaded case with fnvhash - utilization is poor. With zero overwrites/evictions. might be wrong stats i guess ? since with avg value of 43 bytes and key 16 bytes, we should be able to fit all the values into 1 meg.

[coocood]

I will try to find the answer tomorrow, you can print out every segment's entry count to see how it is distributed .

[anton-povarov]

hacked it together for 1 mil items, 1 goroutine, 1 meg cache
data gathered with

        n := atomic.LoadInt64(&cache.segments[i].entryCount)
        fmt.Printf("%d %d\n", i, n)

fnvhash

antoxa@antoxa-suse:~/_Dev/go/src/antoxa> cat 1.txt | awk '{ print $2 }' | sort -n | uniq -c
    384 0
      2 470
      4 479
      6 480
      4 481
      2 482
     10 483
      2 484
      6 485
      4 486
      6 487
     14 488
     12 489
      6 490
     12 491
      2 492
      8 494
      4 495
      4 496
      6 497
      4 499
      4 501
      4 503
      2 508

murmur3

antoxa@antoxa-suse:~/_Dev/go/src/antoxa> cat 1.txt | awk '{ print $2 }' | sort -n | uniq -c
      4 471
      2 473
      2 475
      6 477
      8 478
     12 479
     12 480
     20 481
      6 482
     26 483
     14 484
     20 485
     24 486
     24 487
     18 488
     40 489
     30 490
     24 491
     18 492
     44 493
     44 494
     18 495
     18 496
     14 497
     20 498
     10 499
     12 500
      2 501
     10 502
      4 503
      2 504
      2 505
      2 508

[coocood]

Thank you for the great work to address this issue. The hash function definitely need to change.

[coocood]

Changed to MD5 in the latest commit 28070c0