Hashmap cleaning should be more thorough

[ikeydoherty]

Due to our use of hashmap, we still show a large amount of memory reachable upon program exit.
Whilst some may argue it's not the biggest issue as its indeed not directly lost memory, it would seem
to indicate that the existing hashmap implementation is too fast and loose with allocation.

==3701== 28,672 bytes in 1 blocks are still reachable in loss record 1 of 2
==3701==    at 0x4C2B6A6: calloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==3701==    by 0x40722F: allocate_tile.part.1 (hashmap.c:94)
==3701==    by 0x4075C6: hashmap_put (hashmap.c:446)
==3701==    by 0x404100: main (main.c:120)
==3701== 
==3701== 159,744 bytes in 1 blocks are still reachable in loss record 2 of 2
==3701==    at 0x4C2B6A6: calloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==3701==    by 0x40722F: allocate_tile.part.1 (hashmap.c:94)
==3701==    by 0x407380: hashmap_new (hashmap.c:189)
==3701==    by 0x404099: main (main.c:112)
==3701== 
==3701== LEAK SUMMARY:
==3701==    definitely lost: 0 bytes in 0 blocks
==3701==    indirectly lost: 0 bytes in 0 blocks
==3701==      possibly lost: 0 bytes in 0 blocks
==3701==    still reachable: 188,416 bytes in 2 blocks
==3701==         suppressed: 0 bytes in 0 blocks

I'll follow up with a solution should I find one, simply tracking this here.

[ikeydoherty]

Note from a create-group operation with buxtonctl (above was just running and doing noop):

4-linux.so)
==3746==    by 0x40722F: allocate_tile.part.1 (hashmap.c:94)
==3746==    by 0x407380: hashmap_new (hashmap.c:189)
==3746==    by 0x404099: main (main.c:112)
==3746== 
==3746== 159,744 bytes in 1 blocks are still reachable in loss record 4 of 4
==3746==    at 0x4C2B6A6: calloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==3746==    by 0x4E3800F: allocate_tile.part.1 (hashmap.c:94)
==3746==    by 0x4E38160: hashmap_new (hashmap.c:189)
==3746==    by 0x4E39150: setup_callbacks (protocol.c:66)
==3746==    by 0x4E351B4: buxton_open (lbuxton.c:97)
==3746==    by 0x404A4E: main (main.c:291)
==3746== 
==3746== LEAK SUMMARY:
==3746==    definitely lost: 0 bytes in 0 blocks
==3746==    indirectly lost: 0 bytes in 0 blocks
==3746==      possibly lost: 0 bytes in 0 blocks
==3746==    still reachable: 376,832 bytes in 4 blocks
==3746==         suppressed: 0 bytes in 0 blocks
==3746== 

[bryteise]

It is allocating quite large blocks to improve speed of use, avoiding hitting allocation early (remember it is from systemd's implementation so they'll not want to impact startup speed due to reallocs because they use hashmap everywhere).

[bryteise]

Switching over to your hashmap would be the goal though I imagine. Is that in the TODO?

[ikeydoherty]

Eventual switch over or ensure correct alignment throughout the lifetime of this hashmap. Tbh I'd prefer a new one :) It's not in the TODO, want me to open up a quick change?

[ikeydoherty]

Added just in case ^^

[bryteise]

You are welcome to push the TODO =).

[ikeydoherty]

Hah, you'd think I would remember I had push privs xD

[ikeydoherty]

So currently working on my resize code but I've gone with an aggressive cache hashmap implementation.
Now obv. there are going to be doubling resizes in between, but I've checked with 5 million keys (ints) on an initial 75% capacity hashmap. As its aggressive with cache in mind its slightly heavier in terms of memory but very very fast (this will slow down a small bit when I introduce resizes though :P)

Loop-int tests
==28153== 
==28153== HEAP SUMMARY:
==28153==     in use at exit: 0 bytes in 0 blocks
==28153==   total heap usage: 1,250,002 allocs, 1,250,002 frees, 160,000,024 bytes allocated
==28153== 
==28153== All heap blocks were freed -- no leaks are possible
==28153== 
==28153== For counts of detected and suppressed errors, rerun with: -v
==28153== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
ikey@evolveos ~l/hashmap
$ time ./run.sh 
Test #1: 99/110
Returned: 110
Test #2: 98/136
Returned: 136
Test #3: 99/110
Returned: 110


Loop-int tests

real    0m0.497s
user    0m0.337s
sys 0m0.151s

[bryteise]

On Sep 24, 2014 9:24 AM, "Ikey Doherty" notifications@github.com wrote:

So currently working on my resize code but I've gone with an aggressive
cache hashmap implementation.
Now obv. there are going to be doubling resizes in between, but I've
checked with 5 million keys (ints) on an initial 75% capacity hashmap. As
its aggressive with cache in mind its slightly heavier in terms of memory
but very very fast (this will slow down a small bit when I introduce
resizes though :P)

Lovely. How does the time compare to systemd's time?

Loop-int tests
==28153==
==28153== HEAP SUMMARY:
==28153== in use at exit: 0 bytes in 0 blocks
==28153== total heap usage: 1,250,002 allocs, 1,250,002 frees,
160,000,024 bytes allocated
==28153==
==28153== All heap blocks were freed -- no leaks are possible
==28153==
==28153== For counts of detected and suppressed errors, rerun with: -v
==28153== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
ikey@evolveos ~l/hashmap
$ time ./run.sh
Test #1: 99/110
Returned: 110
Test #2: 98/136
Returned: 136
Test #3: 99/110
Returned: 110

Loop-int tests

real 0m0.497s
user 0m0.337s
sys 0m0.151s

—
Reply to this email directly or view it on GitHub.

[ikeydoherty]

Putting appropriate tests together :) To be fair I need to do one where systemd's hashmap is initially resized the same, and then one with my implementation doing resizes, which is why there aren't more numbers yet :D

[ikeydoherty]

Simple test, systemd hashmap vs ikey-hashmap

Store 5 million integers in one loop. In next loop assert i == value restored. Highly trivial

systemd valgrind:

==1864== Command: ./a.out
==1864== 
==1864== 
==1864== HEAP SUMMARY:
==1864==     in use at exit: 469,893,120 bytes in 15 blocks
==1864==   total heap usage: 27 allocs, 12 frees, 686,720,352 bytes allocated
==1864== 
==1864== 159,744 bytes in 1 blocks are still reachable in loss record 1 of 2
==1864==    at 0x4C2B6A6: calloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1864==    by 0x4E34AE7: allocate_tile (hashmap.c:94)
==1864==    by 0x4E34CBD: hashmap_new (hashmap.c:184)
==1864==    by 0x4008FF: main (main.c:5)
==1864== 
==1864== 469,733,376 bytes in 14 blocks are still reachable in loss record 2 of 2
==1864==    at 0x4C2B6A6: calloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==1864==    by 0x4E34AE7: allocate_tile (hashmap.c:94)
==1864==    by 0x4E3574C: hashmap_put (hashmap.c:442)
==1864==    by 0x400927: main (main.c:9)
==1864== 
==1864== LEAK SUMMARY:
==1864==    definitely lost: 0 bytes in 0 blocks
==1864==    indirectly lost: 0 bytes in 0 blocks
==1864==      possibly lost: 0 bytes in 0 blocks
==1864==    still reachable: 469,893,120 bytes in 15 blocks
==1864==         suppressed: 0 bytes in 0 blocks
==1864== 
==1864== For counts of detected and suppressed errors, rerun with: -v
==1864== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

ikeymap valgrind:

==1958== HEAP SUMMARY:
==1958==     in use at exit: 0 bytes in 0 blocks
==1958==   total heap usage: 22 allocs, 22 frees, 346,730,056 bytes allocated
==1958== 
==1958== All heap blocks were freed -- no leaks are possible
==1958== 
==1958== For counts of detected and suppressed errors, rerun with: -v
==1958== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

systemd hashmap time (put/get)

ikey@evolveos ~/Intel/hashmap/systemd
$ time ./run.sh 

real    0m1.158s
user    0m0.878s
sys 0m0.275s

ikeymap time (put/get):

ikey@evolveos ~/Intel/hashmap
$ time ./run.sh 
Test #1: 99/110
Returned: 110
Test #2: 98/136
Returned: 136
Test #3: 99/110
Returned: 110


Loop-int tests

real    0m0.570s
user    0m0.343s
sys 0m0.225s

Basically mine wins :D I set them both to an initial capacity of 31 as found in systemd, though I prefer 61. Mine auto-resizes at 75%, and instead of memmove/memcpy voodoo we just reinsert into a fresh bigger map.

Tomorrow I'll do tests for strings (which will be slower due to different hash and strncmp, though to be fair I'll likely just use a simple DJB hash like systemd, meaning by nature I should win this one too :)

I also have some check-style asserts at the beginning of my own test, so mine is technically doing more get/puts for assurances, and we free that map and create a new one after =)

[bryteise]

Looks good =).

[ikeydoherty]

Forgot to note; I switched to 4x not 2x, as systemd does, to be fair. I've also now added hash/compare functions for both string+"simple" operations. To make it dead-for-dead fair, I restricted the tests to the 5m comparisons of ints between both (identical now) and using the function pointers for comparison and hashing...

ikey@evolveos ~/Intel/hashmap
$ time ./run.sh 

real    0m0.608s
user    0m0.410s
sys 0m0.197s

So, still not bad =)

[bryteise]

Woo! Now just need to run it under perf and find out where these spend most of their time =).