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

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

Open
AsterDY opened this issue Apr 1, 2021 · 13 comments
Open

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

AsterDY opened this issue Apr 1, 2021 · 13 comments
Projects
Milestone

Comments

@AsterDY
Copy link

@AsterDY AsterDY commented Apr 1, 2021

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

@randall77 randall77 commented Apr 1, 2021

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

@AsterDY AsterDY commented Apr 1, 2021

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

@martisch martisch commented Apr 1, 2021

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.

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

@AsterDY AsterDY changed the title Why not supports memory reuse for map? Why not supports more efficient memory reuse for map? Apr 1, 2021
@AsterDY
Copy link
Author

@AsterDY AsterDY commented Apr 1, 2021

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.

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

@randall77 randall77 commented Apr 1, 2021

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

@OneOfOne OneOfOne commented Apr 1, 2021

@randall77

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

@randall77
Copy link
Contributor

@randall77 randall77 commented Apr 1, 2021

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

@AsterDY AsterDY commented Apr 2, 2021

@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

@dr2chase 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 gopherbot added this to the Proposal milestone Apr 2, 2021
@ianlancetaylor 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 ianlancetaylor added this to Incoming in Proposals Apr 7, 2021
@rsc
Copy link
Contributor

@rsc rsc commented Apr 7, 2021

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

@randall77 randall77 commented Apr 7, 2021

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 rsc moved this from Incoming to Active in Proposals Apr 7, 2021
@rsc
Copy link
Contributor

@rsc rsc commented Apr 7, 2021

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

@OneOfOne OneOfOne commented Apr 7, 2021

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

@CAFxX CAFxX commented Apr 8, 2021

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?

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

Successfully merging a pull request may close this issue.

None yet
8 participants