8 ms·

Maps and Memory Leaks in Go

133 points by minaandrawos 4y ago

cglong 4y ago
I was going to complain that a bug should be filed for this, but one of the blog comments says this issue could be fixed by [1]. [1]: https://github.com/golang/go/issues/54766 https://github.com/golang/go/issues/54766
- deleted 4y ago
  [deleted]
masklinn 4y ago
> Also, in this case, the amount of required memory is less significant during peak times due to some optimizations to reduce the memory consumed. Pretty sure it’s the same: because of collisions, maps always have a certain fraction of empty slots (much more so than vectors). I’ve not heard of Go maps being very high load factors, so they probably resize around 50% or so full. I didn’t check any of the numbers, I’ll assume 50% load factor, doubling on resize, and entries of {hash, key, value} with a word-sized (8 bytes) hash, but some and likely all of those are likely off. Anyway with a load factor of 50% and doubling at any point you’d have 2n to 4n slots in the map total (depending whether you’re nearing resize or just went through one). And thus if you make entries smaller, you make all those overhead slots smaller as well. hash + int + blob would be 8+8+128 144 bytes, a million of those is 144MB, x2 is 288 and x4 is 576, so the observed bounds are pretty close: IIRC Go maps use some form of separate chaining (though not “trivial” linked lists), I assume those do get reclaimed as entries are removed even if the map itself does not get shrunk, which would explain why memory consumption goes down as elements are removed from the initial map. With a pointer each “entry” is 24 bytes instead, for a map overhead of 48~96MB (so clearly Go maps use either a higher load factor or a more efficient storage than the trivial scheme being assumed here, possibly both). The actual data accounts for 128M plus some, there’s a 144M difference between the full and the emptied pointer-maps, which would account for some chain links being removed, and maybe some object headers / allocator overhead for the on-heap arrays.
- morelisp 4y ago
  50% load factor would be incredibly low for any hash table. Go uses 6.5/8 per bucket right now I believe, or 81% if you want to be crass about it.
  - masklinn 4y ago
    > 50% load factor would be incredibly low for any hash table. Might be that I’m more used to open addressing maps? IIRC circa 50 is a pretty good starting point for open addressing unless the collision resolution is specifically designed for that (e.g. swisstable). Not to say it can’t get higher, but for some the that’s where the performance starts going down (e.g. non-bucketed cuckoo hashing).
    - morelisp 4y ago
      Sure, if you grab an algorithms 101 textbook and implement its example of an open addressing table, 50% is a performance inflection point, but nobody is really using such things. And even then I recall seeing numbers more like 70% before actually doubling due to the high cost of rehash; 50% was only for the initial allocation.
- LukeShu 4y ago
  > I've not heard of Go maps being very high load factors, so they probably resize around 50% or so full. Go uses a load factor of 6.5 (expressed as average load of a bucket; where buckets have a maximum load of 8; i.e. 81% full) (ref: https://github.com/golang/go/blob/go1.19.3/src/runtime/map.go#L33-L72 https://github.com/golang/go/blob/go1.19.3/src/runtime/map.g... ) > I’ll assume … doubling on resize Indeed (ref: https://github.com/golang/go/blob/go1.19.3/src/runtime/map.go#L19-L20 https://github.com/golang/go/blob/go1.19.3/src/runtime/map.g...)
hknmtt 4y ago
i don't see any issue here. same behavior can be achieved with slices: foo := make([]int, 0, 1000) for { for k := range bar { foo = append(foo, k) } foo = foo[:0] } the slice will grow as much as the largest dataset. map will be the same. you need to let go of it to be GCd and create a new one.
- olliej 4y ago
  The point is that you can remove the entries from the map, and the map won't ever shrink. If you're using large value type in the map[1], the map's dead storage will be large - by a functionally unbound amount. Most sane collection libraries shrink their backing store after some sufficiently large portion becomes dead. [1] I would argue a general purpose hash table/map should really switch to using a hash code=>index mapping automatically if the value type size is sufficiently large.
  - rob74 4y ago
    The map will shrink, just not by as much as you might expect. You could also argue that they have picked a pathological case for their example because they use 128 byte entries ("If a key or a value is over 128 bytes, Go won’t store it directly in the map bucket. Instead, Go stores a pointer to reference the key or the value" - which probably leads to less memory consumption).
  - morelisp 4y ago
    > Most sane collection libraries shrink their backing store after some sufficiently large portion becomes dead. If you exclude Java, and C++ and C# I think, stdlibs from being sane, sure.
    - olliej 4y ago
      womp womp, you are indeed correct. I'd swear that Java and .NET's did, but I assume that's bad memory at fault :( I will say though that I don't consider C++'s various maps to be sane :D
ilyt 4y ago
Huh, I didn't knew that... that might explain one slow "leak" I've been noticing in one of my apps. Shame that quirk wasn't documented
mjpa86 4y ago
what happened to a memory leak being some memory that was allocated but had no reference to it so couldn't be freed? If you can copy the map and release it and the memory usage drops, there is no leak?
- rob74 4y ago
  Yeah, that makes the title pretty much clickbait, because a memory leak in a memory-safe language would really be a big deal...
  - TheDong 4y ago
    > a memory leak in a memory-safe language would really be a big deal... It is not. Let me show you a memory leak in the memory safe language, rust: let vec: Vec<u8> = Vec::with_capacity(1024); std::mem::forget(vec); Let me show you a memory leak in the memory safe language, go: _ = time.Tick(1 * time.Second) See the docs for time.Tick in the stdlib, which documents that calling it is a memory leak: https://pkg.go.dev/time@go1.19.3#Tick https://pkg.go.dev/time@go1.19.3#Tick You can also, if you want to leak memory in go, set the environment variable GOGC=off, and there you go, instant memory leak. Practically any language, memory safe or otherwise, will let you create a memory leak.
  - sigg3 4y ago
    Go is just memory safe until you have a race, or so I have heard.
    - pclmulqdq 4y ago
      The same goes for Rust and most other "safe" languages. They all have synchronization primitives that make it safe, but you need to use them - the compiler won't always tell you.
      - suremarc 4y ago
        I have no idea what you mean here. Data races are next to impossible in safe Rust.
twic 4y ago
FWIW i am pretty sure Java's HashMap has the same behaviour - it grows the table, but never shrinks it. Even if you call .clear(), it just clears out the table, rather than throwing the table away. I imagine there are lots of scenarios in which this is what you want, because after emptying the map, you're going to re-fill it, and it saves reallocating the table. But it would be frustrating in a scenario when that isn't what you want. If a map has this behaviour, i would say that the most important thing is that it should be clearly documented (Java's isn't). The second most important thing is that there should be a way to get round it - either a .clearHarder() method which throws away the table, or a .compact() method which downsizes it while retaining the content.
- eptcyka 4y ago
  Wouldn't reallocating the map be very cheap when running in a JVM? Yes, it isn't something to do in the hot path, but surely it should be faster than a direct malloc(), right? I'm being very naive and ready to be proven wrong.
- Gwypaas 4y ago
  Rust uses "shrink_to_fit()". Personally never had to use it, but you always end up scrolling by the backing allocation management for all the standard collections when looking through the docs. > Shrinks the capacity of the map as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy. https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.shrink_to_fit https://doc.rust-lang.org/std/collections/struct.HashMap.htm... And the docs makes it clear that "clear()" only removes the elements. Giving a hint of where to go next if you stumble upon the issue in the OP. > "Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse." https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.clear https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
- creata 4y ago
  > If a map has this behaviour, i would say that the most important thing is that it should be clearly documented Iirc, most hash table implementations don't automatically shrink. More documentation is always nice, but isn't not automatically shrinking kind of the expected "default" behavior?
eschneider 4y ago
This all looks like reasonable implementation behavior which will give optimal runtime performance in most "common" cases. If one really wants or needs a map that'll free memory as it shrinks (and sure, for some folks, that'd be super useful) one's always free to just implement your own.
- eptcyka 4y ago
  Go doesn't really allow you to create a hashmap with the same generic possibilities as the built in one.
  - ironick09 4y ago
    Why is it? Or rather what limitations are there to enforced by go compiler that won’t allow someone to implement their own hash map that can free memory with the same generic possibilities, even with the recent introduction of generics?
    - eptcyka 4y ago
      Seems like I was wrong about my assumptions about Go's generics - it does seem like they're specialized at build time and it is possible to operate over generic values rather than fat pointers. So it is possible to implement a fully featured hash map without extra pointer hopping now. I stand corrected.
  - jimbokun 4y ago
    Is that still true with the support Go added for generics?
    - morelisp 4y ago
      You probably won't be able to match the built-in's performance without a similarly large surface area of unsafe usage. And Go's maintainers won't maintain your unsafe code for you as they do the default, nor consider the impact of other language changes on your micro-optimizations. https://github.com/golang/go/blob/master/src/runtime/map.go https://github.com/golang/go/blob/master/src/runtime/map.go You also won't have `for k, v := range` iteration, but that is also likely being addressed within the next few versions. But - no, there's not really any major ergonomic issues to basic lookups given generics these days.
tapirl 4y ago
Yes, Go maps never shrink. This is good for most use cases in practice. Because in practice, map entry deletions happen seldom. And when map entry deletions are needed, users often hope maps don't shrink, to avoid potential later unnecessary memory allocations and entry moves. For example, I only do map entry deletions in one of my projects, In the project, I clear all entries of a map and re-use the map to avoid making new allocations. The current design satisfies my need well. This is more an optimization than a memory leak. To avoid the kind-of memory leak, just make a new map and discard the old one.
- jimbokun 4y ago
  The article gives a common place example where this could be an issue, so I don’t know what you mean by “in practice” here.
  - throwaway894345 4y ago
    The parent said “most” so both can be true: most maps don’t need to shrink and the example in the article is a valid case where shrinking a map would be desirable. This seems obvious so I’m confused by your confusion. :)
    - Someone 4y ago
      I think you’re referring to > However, let’s say we want to store one hour of data. Meanwhile, our company has decided to have a big promotion for Black Friday: in one hour, we may have millions of customers connected to our system. But a few days after Black Friday, our map will contain the same number of buckets as during the peak time. This explains why we can experience high memory consumption that doesn’t significantly decrease in such a scenario. > What are the solutions if we don’t want to manually restart our service to clean the amount of memory consumed by the map? I don’t see that as a strong argument for making the implementation of maps more complex by adding some auto- shrinking. If your process survived Black Friday with a map full of items, why would it run out of memory after it with a map that’s mostly empty but didn’t return bookkeeping memory to the heap? Your process likely will keep running. There may be a slight performance drop because cache lookups become more likely to lead to cache misses, but otherwise, the typical system won’t care much about the use of virtual memory space.
SeanLuke 4y ago
< 293 MB <-- After we remove 1 million elements Let's be kind and assume that prior to removal, the map has just trebled in size and the extra space wasn't used. Doesn't this imply that a map has an overhead of about 100 bytes per key/value pair? How can this be so?
- skywhopper 4y ago
  There's some some waste involved in not pre-allocating the map to begin with. Check the output of this variation (https://go.dev/play/p/vQwg3GajzXx https://go.dev/play/p/vQwg3GajzXx -- n shrunk to 1,000 to stay within the playground's memory constraints) which fills the map again after the GC. You'll see the map doesn't grow back to the max size. And if you specify the size of the map up front in the `make()` function, it never grows or shrinks (or not significantly): https://go.dev/play/p/AGW35kMMOc5 https://go.dev/play/p/AGW35kMMOc5 IIRC, what's happening is that whenever the map hits what was pre-allocated, it expands by a certain growth factor of the current size. So at some point between 1 and 1,000,000 a big chunk was allocated that went over what was necessary for 1,000,000 entries. In my testing it happened around i == 851_500: i == 851000: 258507 KB i == 852000: 479212 KB
  - SeanLuke 4y ago
    Hashtables often treble when they reach 50% utilization. I think I'm already factoring that in. It's still 100 bytes overhead!
- EdiX 4y ago
  If you are referring to the change from 461 MB to 293 MB that's because he didn't call runtime.GC right after the insertion loop.
sys_64738 4y ago
I thought GO had garbage collection or is that just trash talk?
- avianlyric 4y ago
  It does, and as the article mentions, it’ll collect the map elements. But it doesn’t collect the map infrastructure that grew to accommodate the elements, and doesn’t shrink when the elements are removed, because the map never stops referencing them.

133 points by minaandrawos 4y ago

I was going to complain that a bug should be filed for this, but one of the blog comments says this issue could be fixed by [1]. [1]: https://github.com/golang/go/issues/54766 https://github.com/golang/go/issues/54766

deleted 4y ago
[deleted]

masklinn 4y ago

> Also, in this case, the amount of required memory is less significant during peak times due to some optimizations to reduce the memory consumed. Pretty sure it’s the same: because of collisions, maps always have a certain fraction of empty slots (much more so than vectors). I’ve not heard of Go maps being very high load factors, so they probably resize around 50% or so full. I didn’t check any of the numbers, I’ll assume 50% load factor, doubling on resize, and entries of {hash, key, value} with a word-sized (8 bytes) hash, but some and likely all of those are likely off. Anyway with a load factor of 50% and doubling at any point you’d have 2n to 4n slots in the map total (depending whether you’re nearing resize or just went through one). And thus if you make entries smaller, you make all those overhead slots smaller as well. hash + int + blob would be 8+8+128 144 bytes, a million of those is 144MB, x2 is 288 and x4 is 576, so the observed bounds are pretty close: IIRC Go maps use some form of separate chaining (though not “trivial” linked lists), I assume those do get reclaimed as entries are removed even if the map itself does not get shrunk, which would explain why memory consumption goes down as elements are removed from the initial map. With a pointer each “entry” is 24 bytes instead, for a map overhead of 48~96MB (so clearly Go maps use either a higher load factor or a more efficient storage than the trivial scheme being assumed here, possibly both). The actual data accounts for 128M plus some, there’s a 144M difference between the full and the emptied pointer-maps, which would account for some chain links being removed, and maybe some object headers / allocator overhead for the on-heap arrays.

morelisp 4y ago
50% load factor would be incredibly low for any hash table. Go uses 6.5/8 per bucket right now I believe, or 81% if you want to be crass about it.
- masklinn 4y ago
  > 50% load factor would be incredibly low for any hash table. Might be that I’m more used to open addressing maps? IIRC circa 50 is a pretty good starting point for open addressing unless the collision resolution is specifically designed for that (e.g. swisstable). Not to say it can’t get higher, but for some the that’s where the performance starts going down (e.g. non-bucketed cuckoo hashing).
  - morelisp 4y ago
    Sure, if you grab an algorithms 101 textbook and implement its example of an open addressing table, 50% is a performance inflection point, but nobody is really using such things. And even then I recall seeing numbers more like 70% before actually doubling due to the high cost of rehash; 50% was only for the initial allocation.
LukeShu 4y ago
> I've not heard of Go maps being very high load factors, so they probably resize around 50% or so full. Go uses a load factor of 6.5 (expressed as average load of a bucket; where buckets have a maximum load of 8; i.e. 81% full) (ref: https://github.com/golang/go/blob/go1.19.3/src/runtime/map.go#L33-L72 https://github.com/golang/go/blob/go1.19.3/src/runtime/map.g... ) > I’ll assume … doubling on resize Indeed (ref: https://github.com/golang/go/blob/go1.19.3/src/runtime/map.go#L19-L20 https://github.com/golang/go/blob/go1.19.3/src/runtime/map.g...)

hknmtt 4y ago

i don't see any issue here. same behavior can be achieved with slices: foo := make([]int, 0, 1000) for { for k := range bar { foo = append(foo, k) } foo = foo[:0] } the slice will grow as much as the largest dataset. map will be the same. you need to let go of it to be GCd and create a new one.

olliej 4y ago
The point is that you can remove the entries from the map, and the map won't ever shrink. If you're using large value type in the map[1], the map's dead storage will be large - by a functionally unbound amount. Most sane collection libraries shrink their backing store after some sufficiently large portion becomes dead. [1] I would argue a general purpose hash table/map should really switch to using a hash code=>index mapping automatically if the value type size is sufficiently large.
- rob74 4y ago
  The map will shrink, just not by as much as you might expect. You could also argue that they have picked a pathological case for their example because they use 128 byte entries ("If a key or a value is over 128 bytes, Go won’t store it directly in the map bucket. Instead, Go stores a pointer to reference the key or the value" - which probably leads to less memory consumption).
- morelisp 4y ago
  > Most sane collection libraries shrink their backing store after some sufficiently large portion becomes dead. If you exclude Java, and C++ and C# I think, stdlibs from being sane, sure.
  - olliej 4y ago
    womp womp, you are indeed correct. I'd swear that Java and .NET's did, but I assume that's bad memory at fault :( I will say though that I don't consider C++'s various maps to be sane :D

ilyt 4y ago

Huh, I didn't knew that... that might explain one slow "leak" I've been noticing in one of my apps. Shame that quirk wasn't documented

mjpa86 4y ago

what happened to a memory leak being some memory that was allocated but had no reference to it so couldn't be freed? If you can copy the map and release it and the memory usage drops, there is no leak?

rob74 4y ago
Yeah, that makes the title pretty much clickbait, because a memory leak in a memory-safe language would really be a big deal...
- TheDong 4y ago
  > a memory leak in a memory-safe language would really be a big deal... It is not. Let me show you a memory leak in the memory safe language, rust: let vec: Vec<u8> = Vec::with_capacity(1024); std::mem::forget(vec); Let me show you a memory leak in the memory safe language, go: _ = time.Tick(1 * time.Second) See the docs for time.Tick in the stdlib, which documents that calling it is a memory leak: https://pkg.go.dev/time@go1.19.3#Tick https://pkg.go.dev/time@go1.19.3#Tick You can also, if you want to leak memory in go, set the environment variable GOGC=off, and there you go, instant memory leak. Practically any language, memory safe or otherwise, will let you create a memory leak.
- sigg3 4y ago
  Go is just memory safe until you have a race, or so I have heard.
  - pclmulqdq 4y ago
    The same goes for Rust and most other "safe" languages. They all have synchronization primitives that make it safe, but you need to use them - the compiler won't always tell you.
    - suremarc 4y ago
      I have no idea what you mean here. Data races are next to impossible in safe Rust.

twic 4y ago

FWIW i am pretty sure Java's HashMap has the same behaviour - it grows the table, but never shrinks it. Even if you call .clear(), it just clears out the table, rather than throwing the table away. I imagine there are lots of scenarios in which this is what you want, because after emptying the map, you're going to re-fill it, and it saves reallocating the table. But it would be frustrating in a scenario when that isn't what you want. If a map has this behaviour, i would say that the most important thing is that it should be clearly documented (Java's isn't). The second most important thing is that there should be a way to get round it - either a .clearHarder() method which throws away the table, or a .compact() method which downsizes it while retaining the content.

eptcyka 4y ago
Wouldn't reallocating the map be very cheap when running in a JVM? Yes, it isn't something to do in the hot path, but surely it should be faster than a direct malloc(), right? I'm being very naive and ready to be proven wrong.
Gwypaas 4y ago
Rust uses "shrink_to_fit()". Personally never had to use it, but you always end up scrolling by the backing allocation management for all the standard collections when looking through the docs. > Shrinks the capacity of the map as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy. https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.shrink_to_fit https://doc.rust-lang.org/std/collections/struct.HashMap.htm... And the docs makes it clear that "clear()" only removes the elements. Giving a hint of where to go next if you stumble upon the issue in the OP. > "Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse." https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.clear https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
creata 4y ago
> If a map has this behaviour, i would say that the most important thing is that it should be clearly documented Iirc, most hash table implementations don't automatically shrink. More documentation is always nice, but isn't not automatically shrinking kind of the expected "default" behavior?

eschneider 4y ago

This all looks like reasonable implementation behavior which will give optimal runtime performance in most "common" cases. If one really wants or needs a map that'll free memory as it shrinks (and sure, for some folks, that'd be super useful) one's always free to just implement your own.

eptcyka 4y ago
Go doesn't really allow you to create a hashmap with the same generic possibilities as the built in one.
- ironick09 4y ago
  Why is it? Or rather what limitations are there to enforced by go compiler that won’t allow someone to implement their own hash map that can free memory with the same generic possibilities, even with the recent introduction of generics?
  - eptcyka 4y ago
    Seems like I was wrong about my assumptions about Go's generics - it does seem like they're specialized at build time and it is possible to operate over generic values rather than fat pointers. So it is possible to implement a fully featured hash map without extra pointer hopping now. I stand corrected.
- jimbokun 4y ago
  Is that still true with the support Go added for generics?
  - morelisp 4y ago
    You probably won't be able to match the built-in's performance without a similarly large surface area of unsafe usage. And Go's maintainers won't maintain your unsafe code for you as they do the default, nor consider the impact of other language changes on your micro-optimizations. https://github.com/golang/go/blob/master/src/runtime/map.go https://github.com/golang/go/blob/master/src/runtime/map.go You also won't have `for k, v := range` iteration, but that is also likely being addressed within the next few versions. But - no, there's not really any major ergonomic issues to basic lookups given generics these days.

tapirl 4y ago

Yes, Go maps never shrink. This is good for most use cases in practice. Because in practice, map entry deletions happen seldom. And when map entry deletions are needed, users often hope maps don't shrink, to avoid potential later unnecessary memory allocations and entry moves. For example, I only do map entry deletions in one of my projects, In the project, I clear all entries of a map and re-use the map to avoid making new allocations. The current design satisfies my need well. This is more an optimization than a memory leak. To avoid the kind-of memory leak, just make a new map and discard the old one.

jimbokun 4y ago
The article gives a common place example where this could be an issue, so I don’t know what you mean by “in practice” here.
- throwaway894345 4y ago
  The parent said “most” so both can be true: most maps don’t need to shrink and the example in the article is a valid case where shrinking a map would be desirable. This seems obvious so I’m confused by your confusion. :)
  - Someone 4y ago
    I think you’re referring to > However, let’s say we want to store one hour of data. Meanwhile, our company has decided to have a big promotion for Black Friday: in one hour, we may have millions of customers connected to our system. But a few days after Black Friday, our map will contain the same number of buckets as during the peak time. This explains why we can experience high memory consumption that doesn’t significantly decrease in such a scenario. > What are the solutions if we don’t want to manually restart our service to clean the amount of memory consumed by the map? I don’t see that as a strong argument for making the implementation of maps more complex by adding some auto- shrinking. If your process survived Black Friday with a map full of items, why would it run out of memory after it with a map that’s mostly empty but didn’t return bookkeeping memory to the heap? Your process likely will keep running. There may be a slight performance drop because cache lookups become more likely to lead to cache misses, but otherwise, the typical system won’t care much about the use of virtual memory space.

SeanLuke 4y ago

< 293 MB <-- After we remove 1 million elements Let's be kind and assume that prior to removal, the map has just trebled in size and the extra space wasn't used. Doesn't this imply that a map has an overhead of about 100 bytes per key/value pair? How can this be so?

skywhopper 4y ago
There's some some waste involved in not pre-allocating the map to begin with. Check the output of this variation (https://go.dev/play/p/vQwg3GajzXx https://go.dev/play/p/vQwg3GajzXx -- n shrunk to 1,000 to stay within the playground's memory constraints) which fills the map again after the GC. You'll see the map doesn't grow back to the max size. And if you specify the size of the map up front in the `make()` function, it never grows or shrinks (or not significantly): https://go.dev/play/p/AGW35kMMOc5 https://go.dev/play/p/AGW35kMMOc5 IIRC, what's happening is that whenever the map hits what was pre-allocated, it expands by a certain growth factor of the current size. So at some point between 1 and 1,000,000 a big chunk was allocated that went over what was necessary for 1,000,000 entries. In my testing it happened around i == 851_500: i == 851000: 258507 KB i == 852000: 479212 KB
- SeanLuke 4y ago
  Hashtables often treble when they reach 50% utilization. I think I'm already factoring that in. It's still 100 bytes overhead!
EdiX 4y ago
If you are referring to the change from 461 MB to 293 MB that's because he didn't call runtime.GC right after the insertion loop.

sys_64738 4y ago

I thought GO had garbage collection or is that just trash talk?

avianlyric 4y ago
It does, and as the article mentions, it’ll collect the map elements. But it doesn’t collect the map infrastructure that grew to accommodate the elements, and doesn’t shrink when the elements are removed, because the map never stops referencing them.