Go: runtime: maps do not shrink after elements removal (delete)

[genez]

What version of Go are you using (go version)?

go version go1.8 windows/amd64

What operating system and processor architecture are you using (go env)?

set GOARCH=amd64
set GOBIN=
set GOEXE=.exe
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOOS=windows
set GOPATH=C:\dev\Go
set GORACE=
set GOROOT=C:\Go
set GOTOOLDIR=C:\Go\pkg\tool\windows_amd64
set GCCGO=gccgo
set CC=gcc
set GOGCCFLAGS=-m64 -mthreads -fmessage-length=0
set CXX=g++
set CGO_ENABLED=1
set PKG_CONFIG=pkg-config
set CGO_CFLAGS=-g -O2
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-g -O2
set CGO_FFLAGS=-g -O2
set CGO_LDFLAGS=-g -O2

What did you do?

See example on playground: https://play.golang.org/p/odsk9F1UH1
(edit: forgot to remove sleeps and changed the number of elements)

What did you expect to see?

removing elements from m1 map should release memory.

What did you see instead?

total allocated memory is always increasing

In the example the issue is not so relevant, but in my production scenario (several maps with more than 1million elements each) I can easily get OOM error, and the process is being killed.
Also I don't know if memstats.Alloc is the right counter to expose here, but I can observe the issue with regular process management tools in linux (e.g. top or htop)

[bradfitz]

/cc @randall77, @josharian

[josharian]

I'm surprised there isn't a dup of this already in the issue tracker.

Yes, maps that shrink permanently currently never get cleaned up after. As usual, the implementation challenge is with iterators.

Maps that shrink and grow repeatedly used to also cause leaks. That was #16070, fixed by CL 25049. I remember hoping when I started on that CL that the same mechanism would be useful for shrinking maps as well, but deciding it wouldn't. Sadly, I no longer remember why. If anyone wants to investigate this issue, I'd start by looking at that CL and thinking about whether that approach could be extended to shrinking maps.

The only available workaround is to make a new map and copy in elements from the old.

[tandr]

just an observation - adding runtime.GC() after last loop of copy/delete brings memory down to about the same size (well, lower actually) as at "Alloc After M1" point

[hixichen]

Any update on this issue?

we load 1 Million entry into map. No matter we try to delete the value or set the map nil, seems the memory is always increasing until OOM.

[mvdan]

@hixichen: see @josharian's workaround above:

The only available workaround is to make a new map and copy in elements from the old.

That is, you have to let the entire map be garbage-collected. Then all its memory will eventually be made available again, and you can start using a new and smaller map. If this doesn't work, please provide a small Go program to reproduce the problem.

As for progress - if there was any, you'd see it in this thread.

[voltrue2]

The only available workaround is to make a new map and copy in elements from the old.

Is this really an efficient way to handle this issue?
If you have a very large map, you'd have to loop a large map every time you delete an element or two, right?

[as]

@hixichen what happens if you set the map to nil (or any cleanup action you mentioned previously) and then run debug.FreeOSMemory()?

This may help differentiate between a "GC-issue" and a "returning memory to the OS" issue.

Edit: It seems you're using Go itself to gauge memory allocation so this message can be ignored (perhaps it will be useful to someone else so I'll post it anyway).

[randall77]

Is this really an efficient way to handle this issue? If you have a very large map, you'd have to loop a large map every time you delete an element or two, right?

You can do it efficiently by delaying shrinking until you've done O(n) deletes.
That's what a built-in mechanism would do.
The map growing mechanism works similarly.

[hixichen]

@as yes, I am using Go itself to gauge memory allocation, and, personally I think Go should handle it by itself.

[rohanil]

any updates on this issue here?

[mvdan]

@rohanil you'd see it in this thread if there was any update. The issue is unplanned, so I don't think anyone plans on looking at it in the near future. I'll label it as NeedsFix, since there seems to be consensus that it should work better.

Also, please stop asking for progress updates. I'll start marking such comments as off-topic in the future.

[4nte]

I'd expect GO to handle memory both ways here. This is unintuitive behavior and should be noted in the map docs until resolved. I just realized we have multiple eventual OOM's in our system.
cc @marco-hrlic data-handler affected

[hunterhug]

go version go1.13.1 darwin/amd64

I have a question:

package main

import (
    "fmt"
    "runtime"
)

func main() {
    v := struct{}{}

    a := make(map[int]struct{})

    for i := 0; i < 10000; i++ {
        a[i] = v
    }

    runtime.GC()
    printMemStats("After Map Add 100000")

    for i := 0; i < 10000-1; i++ {
        delete(a, i)
    }

    runtime.GC()
    printMemStats("After Map Delete 9999")

    for i := 0; i < 10000-1; i++ {
        a[i] = v
    }

    runtime.GC()
    printMemStats("After Map Add 9999 again")

    a = nil
    runtime.GC()
    printMemStats("After Map Set nil")
}

func printMemStats(mag string) {
    var m runtime.MemStats
    runtime.ReadMemStats(&m)
    fmt.Printf("%v：memory = %vKB, GC Times = %v\n", mag, m.Alloc/1024, m.NumGC)
}

output:

After Map Add 100000：memory = 241KB, GC Times = 1
After Map Delete 9999：memory = 242KB, GC Times = 2
After Map Add 9999 again：memory = 65KB, GC Times = 3
After Map Set nil：memory = 65KB, GC Times = 4

Why a local var map a Delete 9999, it's memory not change, but Add 9999 again, it's memory reduce?

[randall77]

    for i := 0; i < 10000-1; i++ {
        a[i] = v
    }

    runtime.GC()
    printMemStats("After Map Add 9999 again")

The map will be garbage collected at this runtime.GC. The compiler knows that the map will not be used again. Your later a==nil does nothing - the compiler is way ahead of you.

Try adding fmt.printf("%d\n", len(m)) at various places above to introduce another use of m. If you put it after the runtime.GC, you will see the behavior you are expecting.

[hunterhug]

the compiler is way ahead of you

So amazing!

[mangatmodi]

Isn't the issue is that the GC is not triggered at the right point? GC process is able to recognize that the map has some deleted keys, that's why runtime.GC() helps. I guess it needs some tuning.

Also, I believe it is a pretty serious issue. Allocating a new map should be documented as best practices when using go.

[bradfitz]

@mangatmodi, this issue is about the map's internal representation, not GC.

[mangatmodi]

@bradfitz Thanks for the reply. However, I was reading map code of go and would really love to understand this issue. Is it that, overflow buckets are never deallocated when we delete keys?

I simplified OP's example and added GC - https://play.golang.org/p/pdZls3ljYb9

Here GC is able to collect some deleted keys, which means that the map is not keeping the reference to deleted keys as live. Go GC is able to visit and collect memory available after deleted keys.
But in OPs case the app was killed with OOM, which looks like to me that Go's GC was not able to trigger(otherwise it would have freed space as manually triggered GC)

[randall77]

This issue is about map buckets, both the standard ones and the overflow buckets. We do not shrink the main buckets array or deallocate the overflow buckets when elements are deleted from the map.

We do zero the slots in the buckets when elements are deleted, so the individual keys and values (if they contain pointers) will be collected by GC correctly.

[mangatmodi]

Thanks @randall77 . That explains why the map was still taking 9MB after delete and GC. If we linearly scale what means 36MB allocated space for zeroes buckets for 1M keys.

Also your comment for if they contain pointers caught my eye. Is it because of this fix - https://go-review.googlesource.com/c/go/+/3288?

Does that means if we are going to keep a big map in the app(with many deletes) as live, we have to choose between memory leaks(non pointer kv) or long GC pauses (pointers)?

Or we keep tracks of number of deletes and copy to a new map after O(n) deletes

[randall77]

Also your comment for if they contain pointers caught my eye. Is it because of this fix - https://go-review.googlesource.com/c/go/+/3288?

No, I just mean the space for the keys and values themselves won't be reclaimed, as that space is part of the buckets. Only the things referenced by the keys and values will be collected. CL 3288 is only about optimizing GC work - it does not affect what is collected.

Does that means if we are going to keep a big map in the app(with many deletes) as live, we have to choose between memory leaks(non pointer kv) or long GC pauses (pointers)?

Not really. The only situation I see where that choice is relevant is if you're deciding between using string or [100]byte as the key. The former has a pointer in it, so the text of your strings will be collected, but then the GC has to scan the map. With the latter the GC doesn't have to scan the map, but then the space for your keys will not be collected because it is part of the buckets themselves.

Or we keep tracks of number of deletes and copy to a new map after O(n) deletes

That would work fine.

[mangatmodi]

@randall77 Thanks It becomes much clear to me. However, I still fail to reproduce the behavior. I used [640]byte array as the key and value type - https://play.golang.org/p/t5_y_WY1Hc9

GC successfully claims the space allocated to the array. If I understood correctly, GC will zero the slots and zero of an array will still use the same space. Am I hitting some compiler optimisations?

[bradfitz]

@mangatmodi, when you write:

    //Here we delete all the keys.
    for k, _ := range m1 {
        delete(m1, k)
    }

... that's recognized by the compiler and rewritten to be a runtime.mapclear call. See test/codegen/maps.go and src/cmd/compile/internal/gc/range.go from issue #20138 (aee71dd70b3779c66950ce6a952deca13d48e55e).

Perhaps that indirectly fixes this issue, but this issue remains for other slower map clearing techniques.

I think you'd want to adjust your repro to not use that map clearing idiom. Perhaps something like:

    for len(m) > 0 {
        for k := range m {
            delete(m, k)
            break
       }
    }

[mangatmodi]

@bradfitz interesting. However, I changed to keep a set of keys and used that to browse. Still, GC is able to collect - https://play.golang.org/p/7mMcOruxuG_t

[randall77]

Ah, looks like you're hitting our large key optimization - if a key or value is over 128 bytes, we allocate it on the heap and store a pointer to it in the map bucket. Those allocations will get collected when the key is deleted (because we zero the pointer in the map bucket when deleting).

[mangatmodi]

@randall77 Yes, it worked with [120] bytes. GC was not able to collect. Anyways I think its really hard to hit this issue of OOM. Atleast for my use case. But it is good to understand.

[naveenkak]

I use golang map to store a huge amount of data. I get lot of Add/Delete for the entries on the map. To me looks like same issue I believe that even after deleting entry from the map memory is not getting freed. What is the solution..calling runtime.GC() after every delete, will that force memory to be freed.
Setting whole map to nil for every delete operation looks very crude.
Also i have recursive maps, map containing an element which is another map.
I was under the impression that once i delete the entry from the top level map, I don,t need to bother about the inner map at all. But I am running into high memory issues if system is left running for a long time.

[nightlyone]

The major underlying issue seems to be, that there is no way in Go to express "I am done adding/deleting, please finalise the map" which doesn't involve using more memory.

This becomes a concern for applications where the RSS is dominated by a few of such maps, especially wihh multiple levels (think distributed, in-app cache for a parsed elements in a document storage).

[mangatmodi]

Theoretically, the map is always growing. With pointers we are able to collect the space pointed to, but the buckets are never resized and to the users, it is not clear by reading just documentation.

It is genuine to think that delete(k) will reclaim space for me after GC.

[naveenkak]

Theoretically, the map is always growing. With pointers we are able to collect the space pointed to, but the buckets are never resized and to the users, it is not clear by reading just documentation.

It is genuine to think that delete(k) will reclaim space for me after GC.

Are you saying delete an element from map should reclaim the memory occupied by element?

[naveenkak]

Theoretically, the map is always growing. With pointers we are able to collect the space pointed to, but the buckets are never resized and to the users, it is not clear by reading just documentation.

It is genuine to think that delete(k) will reclaim space for me after GC.

The major underlying issue seems to be, that there is no way in Go to express "I am done adding/deleting, please finalise the map" which doesn't involve using more memory.

This becomes a concern for applications where the RSS is dominated by a few of such maps, especially wihh multiple levels (think distributed, in-app cache for a parsed elements in a document storage).
Once delete of an element is called it should call the GC to reclaim the memory occupied by that element?
What is the solution in this case, an explicit call to GC ( runtime.GC() post every element delete would work?)...I was expecting delete to free up the memory as I run a model where add/delete operations keep going continuously and run into memory leaks because of this.
Appreciate a response.

[randall77]

calling runtime.GC() after every delete, will that force memory to be freed.

runtime.GC won't collect anything that isn't collectable with the automatic GC. So it's a no-op with regards to this issue. (It's a hint to collect things more promptly, but does not affect the set of collectable things.)

I was under the impression that once i delete the entry from the top level map, I don,t need to bother about the inner map at all.

Your impression is correct. Maps are implemented as pointers, so once you delete an entry from the top map, the inner map will be unreachable and be eligible for garbage collection.

The major underlying issue seems to be, that there is no way in Go to express "I am done adding/deleting, please finalise the map" which doesn't involve using more memory.

The major underlying issue is that someone has to implement shrink on delete.
There's no reason the runtime can't do this (within a constant factor of) optimally, without hints.

[naveenkak]

Ok So you mean there is no memory leak issue here, deleting a map entry should clean up the memory used by the underlying map element?

[randall77]

space for the keys and values themselves won't be reclaimed, as that space is part of the buckets. Only the things referenced by the keys and values will be collected.

Maps are reference types (they are implemented as pointers). For a map of type map[int]map[int]int, deleting an entry from the top-level map should make the entire inner map collectable. Only the pointer slot in the top-level map will be uncollectable.

[naveenkak]

Thanks randall77. I have another problem below.

I am initialising the same slice variable in a loop, why is the memory going up?
Since I am making the same variable point to a different memory every time, earlier memory should be cleaned up.
https://play.golang.org/p/fVKI7Nr6g6j

package main

package main

import (
"fmt"
"runtime"
//"time"
)
var testslice [] byte
var m runtime.MemStats

func main() {
for i := 0; i < 100; i++{
testslice = make([]byte, 100000)
fmt.Printf("test slice length %d", len(testslice))
runtime.ReadMemStats(&m)
fmt.Printf(" memory allocated %d \n", m.Alloc)
}

}

[randall77]

It is cleaned up. Change your print line to

    fmt.Printf(" memory allocated %d %d\n",  m.Alloc, m.NumGC)

And then run again you'll get something like:

test slice length 100000 memory allocated 225856 0
test slice length 100000 memory allocated 332368 0
test slice length 100000 memory allocated 438880 0
test slice length 100000 memory allocated 545392 0
test slice length 100000 memory allocated 651904 0
test slice length 100000 memory allocated 758416 0
test slice length 100000 memory allocated 864928 0
test slice length 100000 memory allocated 971440 0
test slice length 100000 memory allocated 1077952 0
test slice length 100000 memory allocated 1184464 0
test slice length 100000 memory allocated 1290976 0
test slice length 100000 memory allocated 1397488 0
test slice length 100000 memory allocated 1504000 0
test slice length 100000 memory allocated 1610512 0
test slice length 100000 memory allocated 1717024 0
test slice length 100000 memory allocated 1823536 0
test slice length 100000 memory allocated 1930048 0
test slice length 100000 memory allocated 2036560 0
test slice length 100000 memory allocated 2143072 0
test slice length 100000 memory allocated 2249584 0
test slice length 100000 memory allocated 2356096 0
test slice length 100000 memory allocated 2462608 0
test slice length 100000 memory allocated 2569120 0
test slice length 100000 memory allocated 2675632 0
test slice length 100000 memory allocated 2782144 0
test slice length 100000 memory allocated 2888656 0
test slice length 100000 memory allocated 2995168 0
test slice length 100000 memory allocated 3101680 0
test slice length 100000 memory allocated 3208192 0
test slice length 100000 memory allocated 3314704 0
test slice length 100000 memory allocated 3421216 0
test slice length 100000 memory allocated 3527728 0
test slice length 100000 memory allocated 3634240 0
test slice length 100000 memory allocated 3740752 0
test slice length 100000 memory allocated 3847264 0
test slice length 100000 memory allocated 3953776 0
test slice length 100000 memory allocated 4060288 0
test slice length 100000 memory allocated 4166800 0
test slice length 100000 memory allocated 326080 1
test slice length 100000 memory allocated 432608 1
test slice length 100000 memory allocated 539136 1
test slice length 100000 memory allocated 645664 1
test slice length 100000 memory allocated 752192 1
test slice length 100000 memory allocated 858720 1
test slice length 100000 memory allocated 965248 1
test slice length 100000 memory allocated 1071776 1
test slice length 100000 memory allocated 1178304 1
test slice length 100000 memory allocated 1284832 1
test slice length 100000 memory allocated 1391360 1
test slice length 100000 memory allocated 1497888 1
test slice length 100000 memory allocated 1604416 1
test slice length 100000 memory allocated 1710944 1
test slice length 100000 memory allocated 1817472 1
test slice length 100000 memory allocated 1924000 1
test slice length 100000 memory allocated 2030528 1
test slice length 100000 memory allocated 2137056 1
test slice length 100000 memory allocated 2243584 1
test slice length 100000 memory allocated 2350112 1
test slice length 100000 memory allocated 2456640 1
test slice length 100000 memory allocated 2563168 1
test slice length 100000 memory allocated 2669696 1
test slice length 100000 memory allocated 2776224 1
test slice length 100000 memory allocated 2882752 1
test slice length 100000 memory allocated 2989280 1
test slice length 100000 memory allocated 3095808 1
test slice length 100000 memory allocated 3202336 1
test slice length 100000 memory allocated 3308864 1
test slice length 100000 memory allocated 3415392 1
test slice length 100000 memory allocated 3521920 1
test slice length 100000 memory allocated 3628448 1
test slice length 100000 memory allocated 3734976 1
test slice length 100000 memory allocated 3841504 1
test slice length 100000 memory allocated 3948032 1
test slice length 100000 memory allocated 4054560 1
test slice length 100000 memory allocated 4161088 1
test slice length 100000 memory allocated 4266432 2
test slice length 100000 memory allocated 432856 2
test slice length 100000 memory allocated 539384 2
test slice length 100000 memory allocated 645912 2
test slice length 100000 memory allocated 752440 2
test slice length 100000 memory allocated 858968 2
test slice length 100000 memory allocated 965496 2
test slice length 100000 memory allocated 1072024 2
test slice length 100000 memory allocated 1178552 2
test slice length 100000 memory allocated 1285080 2
test slice length 100000 memory allocated 1391608 2
test slice length 100000 memory allocated 1498136 2
test slice length 100000 memory allocated 1604664 2
test slice length 100000 memory allocated 1711192 2
test slice length 100000 memory allocated 1817720 2
test slice length 100000 memory allocated 1924248 2
test slice length 100000 memory allocated 2030776 2
test slice length 100000 memory allocated 2137304 2
test slice length 100000 memory allocated 2243832 2
test slice length 100000 memory allocated 2350360 2
test slice length 100000 memory allocated 2456888 2
test slice length 100000 memory allocated 2563416 2
test slice length 100000 memory allocated 2669944 2
test slice length 100000 memory allocated 2776472 2
test slice length 100000 memory allocated 2883000 2

The memory gets cleaned up, but only when the garbage collector runs (and even then, only around when NumGC goes up, because the garbage collector is asynchronous).

[naveenkak]

Ok but the last o/p line shows
test slice length 100000 memory allocated 2883000 2
means 2.8 MB of memory used.

At beginning of program , first line of o/p.

test slice length 100000 memory allocated 225856 0
means 225k of memory.

Why hasn't memory come back to original size ?

[bradfitz]

Can we bring this discussion elsewhere? This is off topic noise for people subscribed to this issue.

[RalphCorderoy]

Hi @naveenkak, you're seeking general help about garbage collection and maps on an issue which is about one precise situation and so those of us who have no interest in your general problem are being hit by GitHub emails. Please seek help elsewhere. I suggest Go Nuts, see https://golang.org/help/.  Point them at this issue, but be sure to give a code sample which shows the problem you're experiencing. Thanks.

[networkimprov]

Has letting copy() support map[k]v been considered?

That would support updating/extending one map with the contents of another, or recreating a map in a "packed" state when the destination is empty.

[ianlancetaylor]

@networkimprov Let's see if we can implement generics first, since would permit a generic maps.Copy.

[josharian]

I've been thinking about this again. I think we might be able to use the same mechanism as we use for "same size" map growth for shrinking maps. Most of what we need is there. The main sticking point I see is that we need to guarantee that one "growth" (going from smaller to bigger, going from a size to the same size, going from bigger to smaller) completes before the next one starts. I think we can accomplish that if (1) we do more work per evacuation when shrinking and (2) we shrink to 1/2 half the buckets, but only when the map has shrunk to a 1/4 of its size, so that if the user immediately starts filling the map again, their newly doubled buckets still fit before we have to begin growing again. I'm not 100% sure those are necessary/sufficient, but trying that out would be a place to start.

[jandos]

Also your comment for if they contain pointers caught my eye. Is it because of this fix - https://go-review.googlesource.com/c/go/+/3288?

No, I just mean the space for the keys and values themselves won't be reclaimed, as that space is part of the buckets. Only the things _referenced_ by the keys and values will be collected. CL 3288 is only about optimizing GC work - it does not affect what is collected.

Does that means if we are going to keep a big map in the app(with many deletes) as live, we have to choose between memory leaks(non pointer kv) or long GC pauses (pointers)?

Not really. The only situation I see where that choice is relevant is if you're deciding between using string or [100]byte as the key. The former has a pointer in it, so the text of your strings will be collected, but then the GC has to scan the map. With the latter the GC doesn't have to scan the map, but then the space for your keys will not be collected because it is part of the buckets themselves.

Or we keep tracks of number of deletes and copy to a new map after O(n) deletes

That would work fine.

Thanks @randall77, your answer was just what I was looking for.
Also, could you please help me with following questions.

In a case when the key does not contain any pointers, and it's size is less than 128 bytes (not large key),
Will that memory for the key be reused when the same key is again added to the map after a deletion ?
Or will that memory be reused by any other different key which will be added later on ?

[randall77]

In a case when the key does not contain any pointers, and it's size is less than 128 bytes (not large key),
Will that memory for the key be reused when the same key is again added to the map after a deletion ?
Or will that memory be reused by any other different key which will be added later on ?

Both.