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: shrink map as elements are deleted #20135

Open
genez opened this issue Apr 26, 2017 · 45 comments
Open

runtime: shrink map as elements are deleted #20135

genez opened this issue Apr 26, 2017 · 45 comments

Comments

@genez
Copy link

@genez genez commented Apr 26, 2017

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 bradfitz changed the title maps do not shrink after elements removal (delete) runtime: maps do not shrink after elements removal (delete) Apr 26, 2017
@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Apr 26, 2017

@bradfitz bradfitz added this to the Unplanned milestone Apr 26, 2017
@josharian
Copy link
Contributor

@josharian josharian commented Apr 26, 2017

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
Copy link

@tandr tandr commented Sep 4, 2018

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
Copy link

@hixichen hixichen commented Sep 24, 2018

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
Copy link
Member

@mvdan mvdan commented Sep 24, 2018

@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
Copy link

@voltrue2 voltrue2 commented Jan 17, 2019

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
Copy link
Contributor

@as as commented Jan 17, 2019

@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
Copy link
Contributor

@randall77 randall77 commented Jan 17, 2019

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
Copy link

@hixichen hixichen commented Jan 17, 2019

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

@rohanil

This comment was marked as off-topic.

@mvdan

This comment was marked as off-topic.

@4nte
Copy link

@4nte 4nte commented Dec 5, 2019

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
Copy link

@hunterhug hunterhug commented Apr 16, 2020

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
Copy link
Contributor

@randall77 randall77 commented Apr 16, 2020

	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

This comment was marked as off-topic.

@mangatmodi
Copy link

@mangatmodi mangatmodi commented Apr 20, 2020

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.

@golang golang deleted a comment from naveenkak Apr 26, 2020
@golang golang deleted a comment from naveenkak Apr 26, 2020
@networkimprov
Copy link

@networkimprov networkimprov commented Apr 27, 2020

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
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented Apr 27, 2020

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

@josharian
Copy link
Contributor

@josharian josharian commented Apr 27, 2020

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
Copy link

@jandos jandos commented Jul 1, 2020

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
Copy link
Contributor

@randall77 randall77 commented Jul 1, 2020

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.

@rsc rsc changed the title runtime: maps do not shrink after elements removal (delete) runtime: shrink map as elements are deleted Apr 7, 2021
rfjakob added a commit to rfjakob/go-fuse that referenced this issue May 31, 2021
Maps do not free all memory when elements get deleted
( golang/go#20135 ).

As a workaround, we recreate our two big maps (kernelNodeIds & stableAttrs)
when they have shrunk dramatically (100 x smaller).

Benchmarkung with loopback (go version go1.16.2 linux/amd64) shows:

Before this change:

State              VmRSS (kiB)
-----              -----------
Fresh mount          4000
ls -R 500k files   271100
after drop_cache   336448
wait ~ 3 minutes   101588

After:

State              VmRSS (kiB)
-----              -----------
Fresh mount          4012
ls -R 500k files   271100
after drop_cache    31528

Results for gocryptfs are similar.

Change-Id: Idcae1ab953270516735839a034d586717647b8db
rfjakob added a commit to rfjakob/go-fuse that referenced this issue May 31, 2021
Maps do not free all memory when elements get deleted
( golang/go#20135 ).

As a workaround, we recreate our two big maps (kernelNodeIds & stableAttrs)
when they have shrunk dramatically (100 x smaller).

Benchmarkung with loopback (go version go1.16.2 linux/amd64) shows:

Before this change:

State              VmRSS (kiB)
-----              -----------
Fresh mount          4000
ls -R 500k files   271100
after drop_cache   336448
wait ~ 3 minutes   101588

After:

State              VmRSS (kiB)
-----              -----------
Fresh mount          4012
ls -R 500k files   271100
after drop_cache    31528

Results for gocryptfs are similar.

Fixes: rfjakob/gocryptfs#569
Change-Id: Idcae1ab953270516735839a034d586717647b8db
rfjakob added a commit to rfjakob/go-fuse that referenced this issue Jun 1, 2021
Maps do not free all memory when elements get deleted
( golang/go#20135 ).

As a workaround, we recreate our two big maps (kernelNodeIds & stableAttrs)
when they have shrunk dramatically (100 x smaller).

Benchmarkung with loopback (go version go1.16.2 linux/amd64) shows:

Before this change:

State              VmRSS (kiB)
-----              -----------
Fresh mount          4000
ls -R 500k files   271100
after drop_cache   336448
wait ~ 3 minutes   101588

After:

State              VmRSS (kiB)
-----              -----------
Fresh mount          4012
ls -R 500k files   271100
after drop_cache    31528

Results for gocryptfs are similar.

Fixes: rfjakob/gocryptfs#569
Change-Id: Idcae1ab953270516735839a034d586717647b8db
rfjakob added a commit to rfjakob/go-fuse that referenced this issue Jun 10, 2021
Maps do not free all memory when elements get deleted
( golang/go#20135 ).

As a workaround, we recreate our two big maps (kernelNodeIds & stableAttrs)
when they have shrunk dramatically (100 x smaller).

Benchmarkung with loopback (go version go1.16.2 linux/amd64) shows:

Before this change:

Step               VmRSS (kiB)
-----              -----------
Fresh mount          4000
ls -R 500k files   271100
after drop_cache   336448
wait ~ 3 minutes   101588

After:

Step               VmRSS (kiB)
-----              -----------
Fresh mount          4012
ls -R 500k files   271100
after drop_cache    31528

Results for gocryptfs are similar.

Fixes: rfjakob/gocryptfs#569
Change-Id: Idcae1ab953270516735839a034d586717647b8db
rfjakob added a commit to rfjakob/go-fuse that referenced this issue Jun 11, 2021
Maps do not free all memory when elements get deleted
( golang/go#20135 ).

As a workaround, we recreate our two big maps (kernelNodeIds & stableAttrs)
when they have shrunk dramatically (100 x smaller).

Benchmarkung with loopback (go version go1.16.2 linux/amd64) shows:

Before this change:

Step               VmRSS (kiB)
-----              -----------
Fresh mount          4000
ls -R 500k files   271100
after drop_cache   336448
wait ~ 3 minutes   101588

After:

Step               VmRSS (kiB)
-----              -----------
Fresh mount          4012
ls -R 500k files   271100
after drop_cache    31528

Results for gocryptfs are similar.

Has survived xfstests via gocryptfs.

Fixes: rfjakob/gocryptfs#569
Change-Id: Idcae1ab953270516735839a034d586717647b8db
hanwen added a commit to hanwen/go-fuse that referenced this issue Jun 11, 2021
Maps do not free all memory when elements get deleted
( golang/go#20135 ).

As a workaround, we recreate our two big maps (kernelNodeIds & stableAttrs)
when they have shrunk dramatically (100 x smaller).

Benchmarkung with loopback (go version go1.16.2 linux/amd64) shows:

Before this change:

Step               VmRSS (kiB)
-----              -----------
Fresh mount          4000
ls -R 500k files   271100
after drop_cache   336448
wait ~ 3 minutes   101588

After:

Step               VmRSS (kiB)
-----              -----------
Fresh mount          4012
ls -R 500k files   271100
after drop_cache    31528

Results for gocryptfs are similar.

Has survived xfstests via gocryptfs.

Fixes: rfjakob/gocryptfs#569
Change-Id: Idcae1ab953270516735839a034d586717647b8db
@Yanwenjiepy
Copy link

@Yanwenjiepy Yanwenjiepy commented Jul 14, 2021

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.

It is only possible to reuse this part of memory if the hash result of other different key also fall into the same bucket.
In general, this does not happen very often, so memory will still grow slowly.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet