Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: map memory usage grows as it changes even though number of entries does not grow #16070

Closed
druminski opened this issue Jun 15, 2016 · 3 comments

Comments

Projects
None yet
4 participants
@druminski
Copy link

commented Jun 15, 2016

Hi,

I have an issue with growing memory usage for a simple map without pointers. The map contains not small amount of entries, keys are fully random. Entries to the map are added and removed but the number of entries is on the same high level. Here is a gist reproducing the issue: Gist

When provided example is run then at the beginning heap size is less than 500MB and memory in use looks like this:

ROUTINE ======================== main.main in /map_leak.go
  350.48MB   350.98MB (flat, cum)   100% of Total
         .          .     20:func main() {
         .          .     21:   go func () {
         .          .     22:       log.Println(http.ListenAndServe("localhost:6060", nil))
         .          .     23:   }()
         .          .     24:
     176MB      176MB     25:   hashmap := make(map[uint64]bool, entries)
   76.30MB    76.30MB     26:   hashes := make([]uint64, entries)
         .          .     27:
         .          .     28:   for repeat := 0; repeat < repeats; repeat++ {
         .          .     29:       fmt.Printf("==== \nRepeat: %6d \n", repeat)
         .          .     30:       fmt.Printf("Number of elements: %6d \n", len(hashmap))
         .          .     31:       printAllocs()
         .          .     32:       for index := 0; index < entries - 1; index++ {
         .   512.03kB     33:           key := generateKey()
         .          .     34:           hashes[index] = key
   98.18MB    98.18MB     35:           hashmap[key] = true
         .          .     36:           delete(hashmap, hashes[index + 1])
         .          .     37:       }
         .          .     38:       key := generateKey()
         .          .     39:       hashes[entries - 1] = key
         .          .     40:       hashmap[entries - 1] = true

After few hours of run (~ 700 repeats) heap size is around 1GB and memory in use looks like this

ROUTINE ======================== main.main in /map_leak.go
     483MB      483MB (flat, cum)   100% of Total
         .          .     20:func main() {
         .          .     21:   go func () {
         .          .     22:       log.Println(http.ListenAndServe("localhost:6060", nil))
         .          .     23:   }()
         .          .     24:
     176MB      176MB     25:   hashmap := make(map[uint64]bool, entries)
   76.30MB    76.30MB     26:   hashes := make([]uint64, entries)
         .          .     27:
         .          .     28:   for repeat := 0; repeat < repeats; repeat++ {
         .          .     29:       fmt.Printf("==== \nRepeat: %6d \n", repeat)
         .          .     30:       fmt.Printf("Number of elements: %6d \n", len(hashmap))
         .          .     31:       printAllocs()
         .          .     32:       for index := 0; index < entries - 1; index++ {
         .          .     33:           key := generateKey()
         .          .     34:           hashes[index] = key
  230.71MB   230.71MB     35:           hashmap[key] = true
         .          .     36:           delete(hashmap, hashes[index + 1])
         .          .     37:       }
         .          .     38:       key := generateKey()
         .          .     39:       hashes[entries - 1] = key
         .          .     40:       hashmap[entries - 1] = true

As you can see memory usage grows in line 35 where entry is added to the map (https://golang.org/src/runtime/hashmap.go line 429). This is because of how map works under the hood.
I am aware that map in Go is an implementation of hash table. Basing on a hash(key), bucket and cell is picked. If it doesn't exist it is created.
However I am wondering why memory usage in the map grows (and how can I prevent it, fully random keys are one of my requirement), because I assume that unussed cells/buckets should be removed. Also I am expecting rather stable and predictable memory usage when number of entries is known.

Before I start study and debug how exaclty map works under the hood I decided to describe my issue here. Maybe you are already familiar with it and can provide some hints on it. This issue was produced on go1.6.2 darwin/amd64.

Thanks,
Luke

@randall77

This comment has been minimized.

Copy link
Contributor

commented Jun 15, 2016

Yes, this is a known limitation of maps. Once overflow buckets are allocated, they are not freed (until the map grows, which doesn't happen in your test). Given lots of inserts and deletes, you'll eventually get an overflow bucket or two for each main bucket.

It would be great to figure out a way to fix this. Deleting overflow buckets is tricky in the presence of iterators.

@randall77 randall77 added this to the Unplanned milestone Jun 15, 2016

@ianlancetaylor ianlancetaylor changed the title Growing memory usage for a simple map runtime: map memory usage grows as it changes even though number of entries does not grow Jun 15, 2016

@josharian josharian self-assigned this Jul 19, 2016

@josharian

This comment has been minimized.

Copy link
Contributor

commented Jul 19, 2016

I'm working on this now. Expect an R=go1.8 early feedback CL soon.

I'm using a slightly modified version of the original code that generates less irrelevant garbage and runs runtime.GC before printing mem stats to provide more stable output.

@rhysh some folks vaguely remembered that you might have expressed an interest in working on this problem at GopherCon. If so, I'd be interested to get your take on the CL. If not, apologies for the noise.

@gopherbot

This comment has been minimized.

Copy link

commented Jul 19, 2016

CL https://golang.org/cl/25049 mentions this issue.

josharian added a commit to josharian/go that referenced this issue Jul 21, 2016

runtime: limit the number of map overflow buckets
DO NOT SUBMIT

[code freeze]

Consider repeatedly adding many items to a map
and then deleting them all, as in golang#16070. The map
itself doesn't need to grow above the high water
mark of number of items. However, due to random
collisions, the map can accumulate overflow
buckets.

Prior to this CL, those overflow buckets were
never removed, which led to a slow memory leak.

The problem with removing overflow buckets is
iterators. The obvious approach is to repack
keys and values and eliminate unused overflow
buckets. However, keys, values, and overflow
buckets cannot be manipulated without disrupting
iterators.

This CL takes a different approach, which is to
reuse the existing map growth mechanism,
which is well established, well tested, and
safe in the presence of iterators.
When a map has accumulated enough overflow buckets
we trigger map growth, but grow into a map of the
same size as before. The old overflow buckets will
be left behind for garbage collection.

For the code in golang#16070, instead of climbing
(very slowly) forever, memory usage now cycles
between 264mb and 483mb every 15 minutes or so.

This CL changes the size of maps on 64 bit systems
from 48 bytes to 56 bytes, which moves its
alloc class from 48 bytes to 64 bytes.

Fixes golang#16070

Change-Id: If551d77613ec6836907efca58bda3deee304297e

josharian added a commit to josharian/go that referenced this issue Aug 31, 2016

runtime: limit the number of map overflow buckets
DO NOT SUBMIT

[code freeze]

Consider repeatedly adding many items to a map
and then deleting them all, as in golang#16070. The map
itself doesn't need to grow above the high water
mark of number of items. However, due to random
collisions, the map can accumulate overflow
buckets.

Prior to this CL, those overflow buckets were
never removed, which led to a slow memory leak.

The problem with removing overflow buckets is
iterators. The obvious approach is to repack
keys and values and eliminate unused overflow
buckets. However, keys, values, and overflow
buckets cannot be manipulated without disrupting
iterators.

This CL takes a different approach, which is to
reuse the existing map growth mechanism,
which is well established, well tested, and
safe in the presence of iterators.
When a map has accumulated enough overflow buckets
we trigger map growth, but grow into a map of the
same size as before. The old overflow buckets will
be left behind for garbage collection.

For the code in golang#16070, instead of climbing
(very slowly) forever, memory usage now cycles
between 264mb and 483mb every 15 minutes or so.

This CL changes the size of maps on 64 bit systems
from 48 bytes to 56 bytes, which moves its
alloc class from 48 bytes to 64 bytes.

Fixes golang#16070

Change-Id: If551d77613ec6836907efca58bda3deee304297e

josharian added a commit to josharian/go that referenced this issue Sep 13, 2016

runtime: limit the number of map overflow buckets
Consider repeatedly adding many items to a map
and then deleting them all, as in golang#16070. The map
itself doesn't need to grow above the high water
mark of number of items. However, due to random
collisions, the map can accumulate overflow
buckets.

Prior to this CL, those overflow buckets were
never removed, which led to a slow memory leak.

The problem with removing overflow buckets is
iterators. The obvious approach is to repack
keys and values and eliminate unused overflow
buckets. However, keys, values, and overflow
buckets cannot be manipulated without disrupting
iterators.

This CL takes a different approach, which is to
reuse the existing map growth mechanism,
which is well established, well tested, and
safe in the presence of iterators.
When a map has accumulated enough overflow buckets
we trigger map growth, but grow into a map of the
same size as before. The old overflow buckets will
be left behind for garbage collection.

For the code in golang#16070, instead of climbing
(very slowly) forever, memory usage now cycles
between 264mb and 483mb every 15 minutes or so.

To avoid increasing the size of maps,
the overflow bucket counter is only 16 bits.
For large maps, the counter is incremented
stochastically.

Fixes golang#16070

Change-Id: If551d77613ec6836907efca58bda3deee304297e

@gopherbot gopherbot closed this in 9980b70 Sep 13, 2016

@golang golang locked and limited conversation to collaborators Sep 13, 2017

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.