proposal: runtime: add way to clear and reuse a map's working storage #45328

AsterDY · 2021-04-01T12:37:51Z

Line 303 in db8142f

func makemap(t *maptype, hint int, h *hmap) *hmap {

I see runtime.makemap() gives a way to reuse old hmap's buckets, but it is only used when mallocating small maps on stack at present. Why not open this shortcut to users for memory reusing? Actually I only need exporting runtime.makemap() and runtime.clearmap() to achieve this goal:

func resetMap(mtyp *mapType, ptr unsafe.Pointer) {
	m := *(*unsafe.Pointer)(ptr)
	if m == nil {
		return
	}

	hm := (*hmap)(m)
	old := hm.B
	mapclear(mtyp, hm)

	hm = makemap(mtyp, 0, hm)
	hm.B = old
	*(*unsafe.Pointer)(ptr) = m
}

It works fine and benefits much on big maps. This is the benchmark results I got on operating a 1000-keys map (one op includes make(map[int]interface{}), set 1000 keys and get 1000 keys):

func BenchmarkMap1000_ResetAndSet(b *testing.B) {
	var pool = sync.Pool{
		New: func() interface{} {
			m := make(map[int]interface{}, 0)
			return &m
		},
	}

	for n := 0; n < b.N; n++ {
		x := pool.Get()
		obj, _ := x.(*map[int]interface{})
		m := *obj
		for i := 0; i < 1000; i++ {
			m[i] = i
			if ni, ok := m[i]; !ok || ni != i {
				b.Fatalf("exp:%v, got:%v", i, ni)
			}
		}
		resetMap(mtype(unpackEface(m).typ), unsafe.Pointer(obj))
		pool.Put(obj)
	}
}

func BenchmarkMap1000_MallocAndSet(b *testing.B) {
	var obj map[int]interface{}

	for n := 0; n < b.N; n++ {
		obj = make(map[int]interface{})
		for i := 0; i < 1000; i++ {
			obj[i] = i
			if ni, ok := obj[i]; !ok || ni != i {
				b.Fatalf("exp:%v, got:%v", i, ni)
			}
		}
	}

	obj[1] = 1
}

//-------------RESULTS----------------
goos: darwin
goarch: amd64
pkg: code.byted.org/gopkg/memset
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkMap1000_ResetAndSet-16     	   23750	     47376 ns/op	    5957 B/op	     744 allocs/op
BenchmarkMap1000_MallocAndSet-16    	    9390	    119347 ns/op	  128288 B/op	     785 allocs/op

The text was updated successfully, but these errors were encountered:

randall77 · 2021-04-01T15:31:25Z

What's wrong with

for k := range m {
  delete(m, k)
}

?
That gives you an empty map with the bucket array of the starting m. At least, until #20135 is implemented.

AsterDY · 2021-04-01T16:01:23Z

What's wrong with
for k := range m {
  delete(m, k)
}
?
That gives you an empty map with the bucket array of the starting m. At least, until #20135 is implemented.

Actually I bench this scenario too, and it loss %2~%8 cpu performance since runtime.memclr() is more effecient than foreach iteration...

martisch · 2021-04-01T16:05:01Z

since runtime.memclr() is more effecient than foreach iteration...

there is no iteration in the generated code. Newer go compilers optimise the above to a single call to runtime.mapclear which uses memclr.
https://godbolt.org/z/vxKGzb639

Note that this doesnt work for key types that are not reflexive for ==.

A simple memclear allone doesnt suffice and other data in the map needs to be reset too to make it reusable.

go/src/runtime/map.go

Line 978 in db8142f

func mapclear(t *maptype, h *hmap) {

AsterDY · 2021-04-01T16:37:36Z

since runtime.memclr() is more effecient than foreach iteration...

there is no iteration in the generated code. Newer go compilers optimise the above to a single call to runtime.mapclear which uses memclr.
https://godbolt.org/z/vxKGzb639

Note that this doesnt work for key types that are not reflexive for ==.

A simple memclear allone doesnt suffice and other data in the map needs to be reset too to make it reusable.

go/src/runtime/map.go

Line 978 in db8142f

func mapclear(t *maptype, h *hmap) {

I got it. As you mentioned, if the key type is complex like interface{}, this compiling-time optimization doesn't work. So my way still gets advantage?

randall77 · 2021-04-01T20:23:58Z

So my way still gets advantage?

Sure. So the question is, is it worth complicating the API? And what would that API look like? How easy is it to use and/or how easy is it to avoid misusing it?

We tend to come down on the side of a cleaner API.

OneOfOne · 2021-04-01T20:59:11Z

@randall77

Since we have delete(m, k), can't we make k optional?
So basically delete(m) would internally call ~~mapclear~~ resetMap(m).

randall77 · 2021-04-01T21:18:35Z

Having delete(m) clear the whole map is possible. I don't think it is worth complicating the language spec for it, though. I think we'd need a stronger motivation than I've seen so far. Sure, every proposal is useful, but changes to the language need to pass a very high bar. Possible evidence could be that this problem is pervasive (e.g. find lots of instances where people would have used this feature, but had to resort to some lower-quality solution instead).

I'm not sure I understand the distinction between mapclear and resetMap. What different does the latter do?
(If it allows you to change the type of the keys or values, then it gets significantly more complicated.)

AsterDY · 2021-04-02T03:54:36Z

@randall77

Since we have delete(m, k), can't we make k optional?
So basically delete(m) would internally call ~~mapclear~~ resetMap(m).

I agree with your proposal . delete(m) is more definitive and concise for users who even don't know the compiler's trick（including me 👀), therefore them can remind themselves to reuse the map as required

rsc · 2021-04-07T17:25:43Z

We already recognize and optimize

for i := range x {
   x[i] = 0
}

as memset. Whatever fast implementation of map clearing we might come up with could be triggered just as easily by

for k := range m {
   delete(m, k)
}

right?

The question is really whether the optimization of that is "zero all the storage" or "shrink".

randall77 · 2021-04-07T17:53:10Z

Whatever fast implementation of map clearing we might come up with could be triggered just as easily by

for k := range m {
delete(m, k)
}
right?

We already do exactly that, at least for reflexive keys (it's trickier for things like NaN keys, where after this loop we might still have len(m)>0).

The question is really whether the optimization of that is "zero all the storage" or "shrink".

We currently don't shrink, just zero. I think shrink should be implemented in general (#20135) before we do anything like that for this optimization in particular. The tricky part here is that I don't see an easy way to tell the runtime "Keep the storage, I'm going to reuse it ~immediately", and "Release the storage, this map is going to be much smaller from here on out". Hopefully the automatic shrink mechanism, once we have it, will be good enough.

rsc · 2021-04-07T18:02:28Z

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

OneOfOne · 2021-04-07T18:08:12Z

Whatever fast implementation of map clearing we might come up with could be triggered just as easily by
for k := range m {
delete(m, k)
}
right?

We already do exactly that, at least for reflexive keys (it's trickier for things like NaN keys, where after this loop we might still have len(m)>0).

The question is really whether the optimization of that is "zero all the storage" or "shrink".

We currently don't shrink, just zero. I think shrink should be implemented in general (#20135) before we do anything like that for this optimization in particular. The tricky part here is that I don't see an easy way to tell the runtime "Keep the storage, I'm going to reuse it ~immediately", and "Release the storage, this map is going to be much smaller from here on out". Hopefully the automatic shrink mechanism, once we have it, will be good enough.

For my personal use case (where I do the for k := range m { delete(m, k) }, I don't really care about shrinking, this is used for maps in a pool that are usually pre-allocated with make(map[X]Y, 4096).

CAFxX · 2021-04-08T00:52:56Z

The question is really whether the optimization of that is "zero all the storage" or "shrink".

If I want to empty+shrink we can simply create a new map, so maybe we don't need to focus on that possibility?

rsc · 2021-04-14T17:29:54Z

For my personal use case (where I do the for k := range m { delete(m, k) }, I don't really care about shrinking, this is used for maps in a pool that are usually pre-allocated with make(map[X]Y, 4096).

Maybe the signal is to not shrink below the initial capacity.

In any event, it sounds like we don't need "a way to clear and reuse a map's working storage" because the straightforward delete loop does exactly that and does it efficiently.

rsc · 2021-04-14T18:03:16Z

Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group

rsc · 2021-04-21T18:02:13Z

No change in consensus, so declined.
— rsc for the proposal review group

ianlancetaylor · 2022-10-20T17:43:25Z

This has been reopened in #56351, based on further thought about NaNs.

AsterDY changed the title ~~Why not supports memory reuse for map?~~ Why not supports more efficient memory reuse for map? Apr 1, 2021

dr2chase added Performance Proposal labels Apr 2, 2021

dr2chase changed the title ~~Why not supports more efficient memory reuse for map?~~ proposal: add way to clear and reuse a map's working storage Apr 2, 2021

gopherbot added this to the Proposal milestone Apr 2, 2021

ianlancetaylor changed the title ~~proposal: add way to clear and reuse a map's working storage~~ proposal: runtime: add way to clear and reuse a map's working storage Apr 7, 2021

ianlancetaylor added this to Incoming in Proposals (old) Apr 7, 2021

rsc moved this from Incoming to Active in Proposals (old) Apr 7, 2021

rsc mentioned this issue Apr 7, 2021

proposal: review meeting minutes #33502

Open

rsc moved this from Active to Likely Decline in Proposals (old) Apr 14, 2021

rsc added the Proposal-FinalCommentPeriod label Apr 14, 2021

rsc moved this from Likely Decline to Declined in Proposals (old) Apr 21, 2021

rsc removed the Proposal-FinalCommentPeriod label Apr 21, 2021

rsc closed this as completed Apr 21, 2021

golang locked and limited conversation to collaborators Apr 21, 2022

gopherbot added the FrozenDueToAge label Apr 21, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

proposal: runtime: add way to clear and reuse a map's working storage #45328

proposal: runtime: add way to clear and reuse a map's working storage #45328

AsterDY commented Apr 1, 2021 •

edited

randall77 commented Apr 1, 2021

AsterDY commented Apr 1, 2021 •

edited

martisch commented Apr 1, 2021 •

edited

AsterDY commented Apr 1, 2021

randall77 commented Apr 1, 2021

OneOfOne commented Apr 1, 2021 •

edited

randall77 commented Apr 1, 2021

AsterDY commented Apr 2, 2021

rsc commented Apr 7, 2021

randall77 commented Apr 7, 2021

rsc commented Apr 7, 2021

OneOfOne commented Apr 7, 2021

CAFxX commented Apr 8, 2021

rsc commented Apr 14, 2021 •

edited

rsc commented Apr 14, 2021

rsc commented Apr 21, 2021

ianlancetaylor commented Oct 20, 2022

proposal: runtime: add way to clear and reuse a map's working storage #45328

proposal: runtime: add way to clear and reuse a map's working storage #45328

Comments

AsterDY commented Apr 1, 2021 • edited

randall77 commented Apr 1, 2021

AsterDY commented Apr 1, 2021 • edited

martisch commented Apr 1, 2021 • edited

AsterDY commented Apr 1, 2021

randall77 commented Apr 1, 2021

OneOfOne commented Apr 1, 2021 • edited

randall77 commented Apr 1, 2021

AsterDY commented Apr 2, 2021

rsc commented Apr 7, 2021

randall77 commented Apr 7, 2021

rsc commented Apr 7, 2021

OneOfOne commented Apr 7, 2021

CAFxX commented Apr 8, 2021

rsc commented Apr 14, 2021 • edited

rsc commented Apr 14, 2021

rsc commented Apr 21, 2021

ianlancetaylor commented Oct 20, 2022

AsterDY commented Apr 1, 2021 •

edited

AsterDY commented Apr 1, 2021 •

edited

martisch commented Apr 1, 2021 •

edited

OneOfOne commented Apr 1, 2021 •

edited

rsc commented Apr 14, 2021 •

edited