SUMMARY While profiling the memory usage of git-cinnabar, heaptrack_interpret, at some point, instantly goes from using 500MB of memory to ... 45GB. STEPS TO REPRODUCE 1. `git clone https://github.com/glandium/git-cinnabar -b next && cd git-cinnabar` 2. `CARGO_PROFILE_RELEASE_DEBUG=true cargo build --release` 3. `git init mozilla-central && cd mozilla-central` 4. `heaptrack ../target/release/git-cinnabar unbundle --clonebundle https://hg.mozilla.org/mozilla-central` OBSERVED RESULT When reaching around 289K manifests imported, the memory usage of heaptrack_interpret jumps from 500MB to 45GB EXPECTED RESULT Not such a jump in memory usage. SOFTWARE/OS VERSIONS Debian 12
I've also reproduced with 1.5.0, which uses memory more slowly at first, allowing to go up to around 410K manifests imported before jumping above 40GB usage.
Attaching heaptrack to heaptrack_interpret, it's telling me that the huge memory use comes from: `std::__new_allocator<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true> >::allocate(unsigned long, void const*)` in very few allocations, apparently. Following that, I attached gdb to heaptrack_interpret and added a breakpoint to malloc with a size larger than 1GB, and was stopped at an allocation for 1.6GB, from which I continued, reaching another allocation for 3.2GB. The full stack trace: ``` #0 __GI___libc_malloc (bytes=3221225472) at ./malloc/malloc.c:3288 #1 0x00007f2d558a958c in operator new (sz=sz@entry=3221225472) at ../../../../src/libstdc++-v3/libsupc++/new_op.cc:50 #2 0x000055c194388e4b in std::__new_allocator<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true> >::allocate (this=<optimized out>, __n=134217728) at /usr/include/c++/12/bits/new_allocator.h:112 #3 std::allocator_traits<std::allocator<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true> > >::allocate (__n=134217728, __a=...) at /usr/include/c++/12/bits/alloc_traits.h:464 #4 std::_Vector_base<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true>, std::allocator<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true> > >::_M_allocate ( __n=134217728, this=<optimized out>) at /usr/include/c++/12/bits/stl_vector.h:378 #5 std::_Vector_base<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true>, std::allocator<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true> > >::_M_create_storage ( __n=134217728, this=<optimized out>) at /usr/include/c++/12/bits/stl_vector.h:395 #6 std::_Vector_base<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true>, std::allocator<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true> > >::_Vector_base ( __a=..., __n=134217728, this=<optimized out>) at /usr/include/c++/12/bits/stl_vector.h:332 #7 std::vector<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true>, std::allocator<tsl::detail_robin_hash::bucket_entry<IndexedAllocationInfo, true> > >::vector (__a=..., __n=134217728, this=0x7ffdf21cd478) at /usr/include/c++/12/bits/stl_vector.h:552 #8 tsl::detail_robin_hash::robin_hash<IndexedAllocationInfo, tsl::robin_set<IndexedAllocationInfo, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::KeySelect, void, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::robin_hash (this=0x7ffdf21cd470, bucket_count=134217728, hash=..., equal=..., alloc=..., min_load_factor=0, max_load_factor=0.5) at /tmp/heaptrack-v1.5.0/3rdparty/robin-map/include/tsl/robin_hash.h:550 #9 0x000055c194389eb0 in tsl::detail_robin_hash::robin_hash<IndexedAllocationInfo, tsl::robin_set<IndexedAllocationInfo, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::KeySelect, void, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::rehash_impl ( this=0x7ffdf21cd730, count_=<optimized out>) at /tmp/heaptrack-v1.5.0/3rdparty/robin-map/include/tsl/robin_hash.h:1318 #10 0x000055c19438a1ac in tsl::detail_robin_hash::robin_hash<IndexedAllocationInfo, tsl::robin_set<IndexedAllocationInfo, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::KeySelect, void, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::rehash_on_extreme_load ( curr_dist_from_ideal_bucket=<optimized out>, this=0x7ffdf21cd730) at /tmp/heaptrack-v1.5.0/3rdparty/robin-map/include/tsl/robin_hash.h:1387 #11 tsl::detail_robin_hash::robin_hash<IndexedAllocationInfo, tsl::robin_set<IndexedAllocationInfo, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::KeySelect, void, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::insert_impl<IndexedAllocationInfo, IndexedAllocationInfo const&> (this=0x7ffdf21cd730, this@entry=0x1000, key=...) at /tmp/heaptrack-v1.5.0/3rdparty/robin-map/include/tsl/robin_hash.h:1234 #12 0x000055c19438a543 in tsl::detail_robin_hash::robin_hash<IndexedAllocationInfo, tsl::robin_set<IndexedAllocationInfo, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::KeySelect, void, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::insert<IndexedAllocationInfo const&> (value=..., this=0x1000) at /tmp/heaptrack-v1.5.0/3rdparty/robin-map/include/tsl/robin_hash.h:740 #13 tsl::detail_robin_hash::robin_hash<IndexedAllocationInfo, tsl::robin_set<IndexedAllocationInfo, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::KeySelect, void, std::hash<IndexedA--Type <RET> for more, q to quit, c to continue without paging--c llocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::insert_hint<IndexedAllocationInfo const&> ( value=..., hint=..., this=0x1000) at /tmp/heaptrack-v1.5.0/3rdparty/robin-map/include/tsl/robin_hash.h:750 #14 tsl::robin_set<IndexedAllocationInfo, std::hash<IndexedAllocationInfo>, std::equal_to<IndexedAllocationInfo>, std::allocator<IndexedAllocationInfo>, false, tsl::rh::power_of_two_growth_policy<2ul> >::insert (value=..., hint=..., this=0x1000) at /tmp/heaptrack-v1.5.0/3rdparty/robin-map/include/tsl/robin_set.h:219 #15 AllocationInfoSet::add (this=this@entry=0x7ffdf21cd730, size=size@entry=748, traceIndex=..., traceIndex@entry=..., allocationIndex=allocationIndex@entry=0x7ffdf21cd630) at /tmp/heaptrack-v1.5.0/src/util/pointermap.h:74 #16 0x000055c1943805dd in main () at /tmp/heaptrack-v1.5.0/src/interpret/heaptrack_interpret.cpp:584 ``` The most notable in there is that the robin hash has this: - m_nb_elements = 470664 (not that many) - m_bucket_count = 67108864 (this seems excessive: 2 orders of magnitude more than the number of elements!)
Replacing robin_set with std::unordered_set in AllocationInfoSet makes the problem go away. We seem to be hitting some corner case where robin_set goes awry.
I filed https://github.com/Tessil/robin-map/issues/71. It could be argued that the hashCombine function in src/util/pointermap.h doesn't do a good enough job to spread the values. Things go better with `seed ^= hasher(v) + 0x9e3779b97f4a7c15 + (seed << 12) + (seed >> 4);`.
Opened PR: https://github.com/KDE/heaptrack/pull/49
Thank you for this report and investigation, quite the nasty corner case! commit f1f59da06211632da92d77fce461bc8ccee7b4c2 (HEAD -> master, origin/master, origin/HEAD) Author: Milian Wolff <mail@milianw.de> Date: Wed Nov 15 07:56:08 2023 +0100 Use boost::hash_combine to prevent collisions in tsl pointermap Apparently the hash combine I copied from stackoverflow all these years ago is simply broken - it can trigger a worst-case scenario in the tsl::set leading to excessive memory consumption. Using boost::hash_combine the example given at [1] we get back to a load factor of ~0.25 at the end, instead of going all the way to 0.00... and gigabytes of memory consumed for the buckets. We use boost already elsewhere so it's fine to use it here too. [1]: https://github.com/Tessil/robin-map/issues/71