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

maps: make Clone more efficient by adding support in the runtime package #58740

Closed
cuiweixie opened this issue Feb 26, 2023 · 19 comments
Closed
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@cuiweixie
Copy link
Contributor

in golang, we copy a map by step as follow:

  1. make a new map.
  2. iter map and copy k,v to new map.

map is hmap struct in runtime internally.
copy by range keys and values is inefficent.
a better way is copy map by deep copy a hmap which represent a map in runtime.

I proposal to make copy the bultin func to support copy map, and impilement it by deep copy hmap.

@gopherbot gopherbot added this to the Proposal milestone Feb 26, 2023
@cuiweixie
Copy link
Contributor Author

when this proposal is accepted, I will send a cl to implement it.

@seankhliao
Copy link
Member

Is this necessary with the new maps.Copy and maps.Clone ?

Where does the assertion that it's inefficient come from?

@cuiweixie
Copy link
Contributor Author

cuiweixie commented Feb 26, 2023

Is this necessary with the new maps.Copy and maps.Clone ?

Where does the assertion that it's inefficient come from?

using copy which implement by me that i will send it later to clone a new map is faster than for range copy like implement in maps.Clone.

here is the benchmark output and benchmark code:

goos: darwin
goarch: arm64
pkg: github.com/cuiweixie/go_compiler/mapcopy
BenchmarkMapCopyGenernal-10           15          68152461 ns/op        40236508 B/op         20 allocs/op
BenchmarkMapCopyNew-10               370           3172743 ns/op        40236386 B/op         20 allocs/op
PASS
ok      github.com/cuiweixie/go_compiler/mapcopy        2.800s

package mapcopy

import "testing"

var m = make(map[int]int)

func init() {
	for i :=0; i<1000000; i++ {
		m[i] = i
	}
}

func OldCopy(m map[int]int)map[int]int{
	nm := make(map[int]int, len(m))
	for k,v := range m {
		nm[k] =v
	}
	return nm
}

var n map[int]int
func BenchmarkMapCopyGenernal(b *testing.B) {
	for i := 0; i < b.N; i++ {
		n = OldCopy(m)
	}
}

func BenchmarkMapCopyNew(b *testing.B) {
	for i := 0; i < b.N; i++ {
		n = copy(m, len(m))
	}
}

@ianlancetaylor
Copy link
Contributor

Whatever you are doing in your version of copy, we can do in a compiler implementation of maps.Clone if that seems to be desirable.

@gopherbot
Copy link

Change https://go.dev/cl/471400 mentions this issue: maps,runtime: improve maps.Clone

@cuiweixie
Copy link
Contributor Author

Whatever you are doing in your version of copy, we can do in a compiler implementation of maps.Clone if that seems to be desirable.

@ianlancetaylor please help to check whether the cl is ok.

@earthboundkid
Copy link
Contributor

I proposed this years and years ago on the Go Nuts mailing list, but it seems totally moot now that maps.Clone has been accepted into Go 1.21.

@cuiweixie
Copy link
Contributor Author

I proposed this years and years ago on the Go Nuts mailing list, but it seems totally moot now that maps.Clone has been accepted into Go 1.21.

this cl reduce the cost of time that clone a one million kv(map[int]int) from 60ms to 3ms.

cuiweixie added a commit to cuiweixie/go that referenced this issue Feb 27, 2023
name         old time/op    new time/op    delta
MapClone-10    66.0ms ± 1%     3.2ms ± 4%  -95.13%  (p=0.000 n=9+10)

name         old alloc/op   new alloc/op   delta
MapClone-10    40.2MB ± 0%    40.2MB ± 0%   +0.00%  (p=0.000 n=10+8)

name         old allocs/op  new allocs/op  delta
MapClone-10      20.0 ± 0%      21.0 ± 0%   +5.00%  (p=0.000 n=10+10)

Updates golang#58740.

Change-Id: I148501e723cb2124f02045400e7ceb36af0871c8
@EbenezerJesuraj
Copy link

From the developments of this proposal, i understand you people want to make the map-copy function to have built-in deep-copy support/feature to improve efficiency..

A similar discussion where myself stated the importance of such deep-copy feature happened during the reflect library proposals and a prototype for deep-copy has been generated if i am not wrong.

That prototype's purpose was not restricted to in-built data-types but more of a generic template for user-defined templates as well..

Linking the Proposal discussion here, hoping it serves some importance: reflect.deepcopy()

@cuiweixie cuiweixie changed the title proposal: make copy support map copy proposal: improve maps.Clone Mar 2, 2023
@cuiweixie
Copy link
Contributor Author

Is this proposal ok?

@ianlancetaylor
Copy link
Contributor

@cuiweixie I see that you've changed the title, and now I'm not sure what the proposal is. Can you clarify? Thanks.

@cuiweixie
Copy link
Contributor Author

@cuiweixie I see that you've changed the title, and now I'm not sure what the proposal is. Can you clarify? Thanks.

change the proposal to improve map.Clone.

@ianlancetaylor
Copy link
Contributor

Thanks. Improving maps.Clone doesn't have to be a proposal, so taking it out of the proposal process.

@ianlancetaylor ianlancetaylor changed the title proposal: improve maps.Clone maps: make Clone more efficient by adding support in the runtime package Mar 3, 2023
@ianlancetaylor ianlancetaylor added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. and removed Proposal labels Mar 3, 2023
@ianlancetaylor ianlancetaylor modified the milestones: Proposal, Unplanned Mar 3, 2023
@cuiweixie
Copy link
Contributor Author

ping

@ianlancetaylor
Copy link
Contributor

@cuiweixie Sorry, what are you pinging? Are you asking whether it is OK for maps.Clone to call into the runtime? I think that that is OK in principle, and that we should use benchmarks to decide whether to actually do it.

@gophun
Copy link

gophun commented Mar 7, 2023

@ianlancetaylor: @cuiweixie posted a CL (471400) with benchmarks.

gopherbot pushed a commit that referenced this issue Apr 13, 2023
name         old time/op    new time/op    delta
MapClone-10    65.8ms ± 7%    10.3ms ± 2%  -84.30%  (p=0.000 n=10+9)

name         old alloc/op   new alloc/op   delta
MapClone-10    40.2MB ± 0%    40.5MB ± 0%   +0.57%  (p=0.000 n=10+9)

name         old allocs/op  new allocs/op  delta
MapClone-10      20.0 ± 0%      23.0 ± 0%  +15.00%  (p=0.000 n=10+10)

Updates #58740.

Change-Id: I148501e723cb2124f02045400e7ceb36af0871c8
Reviewed-on: https://go-review.googlesource.com/c/go/+/471400
Reviewed-by: Heschi Kreinick <heschi@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: xie cui <523516579@qq.com>
Reviewed-by: Keith Randall <khr@google.com>
@qiulaidongfeng
Copy link
Contributor

CL has been merged, why not close this issue?

@thepudds
Copy link
Contributor

CL has been merged, why not close this issue?

Hi @cuiweixie, it looks like the commit message in the CL might have said Updates #58740.

If you want a CL to close a issue, you usually would write Fixes #58740 instead. (There are a few other variations that are treated similarly, but Fixes is the most common).

There are some more details in the Commit Message section of the Contribution Guide, including:

The special notation Fixes #12345 associates the change with issue 12345 in the Go issue tracker. When this change is eventually applied, the issue tracker will automatically mark the issue as fixed.

If the change is a partial step towards the resolution of the issue, write Updates #12345 instead. This will leave a comment in the issue linking back to the change in Gerrit, but it will not close the issue when the change is applied.

Separately -- this is a great change! 🚀

@cuiweixie
Copy link
Contributor Author

CL has been merged, why not close this issue?

Hi @cuiweixie, it looks like the commit message in the CL might have said Updates #58740.

If you want a CL to close a issue, you usually would write Fixes #58740 instead. (There are a few other variations that are treated similarly, but Fixes is the most common).

There are some more details in the Commit Message section of the Contribution Guide, including:

The special notation Fixes #12345 associates the change with issue 12345 in the Go issue tracker. When this change is eventually applied, the issue tracker will automatically mark the issue as fixed.

If the change is a partial step towards the resolution of the issue, write Updates #12345 instead. This will leave a comment in the issue linking back to the change in Gerrit, but it will not close the issue when the change is applied.

Separately -- this is a great change! 🚀

got it. thanks!

eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
name         old time/op    new time/op    delta
MapClone-10    65.8ms ± 7%    10.3ms ± 2%  -84.30%  (p=0.000 n=10+9)

name         old alloc/op   new alloc/op   delta
MapClone-10    40.2MB ± 0%    40.5MB ± 0%   +0.57%  (p=0.000 n=10+9)

name         old allocs/op  new allocs/op  delta
MapClone-10      20.0 ± 0%      23.0 ± 0%  +15.00%  (p=0.000 n=10+10)

Updates golang#58740.

Change-Id: I148501e723cb2124f02045400e7ceb36af0871c8
Reviewed-on: https://go-review.googlesource.com/c/go/+/471400
Reviewed-by: Heschi Kreinick <heschi@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: xie cui <523516579@qq.com>
Reviewed-by: Keith Randall <khr@google.com>
eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
name         old time/op    new time/op    delta
MapClone-10    65.8ms ± 7%    10.3ms ± 2%  -84.30%  (p=0.000 n=10+9)

name         old alloc/op   new alloc/op   delta
MapClone-10    40.2MB ± 0%    40.5MB ± 0%   +0.57%  (p=0.000 n=10+9)

name         old allocs/op  new allocs/op  delta
MapClone-10      20.0 ± 0%      23.0 ± 0%  +15.00%  (p=0.000 n=10+10)

Updates golang#58740.

Change-Id: I148501e723cb2124f02045400e7ceb36af0871c8
Reviewed-on: https://go-review.googlesource.com/c/go/+/471400
Reviewed-by: Heschi Kreinick <heschi@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Run-TryBot: xie cui <523516579@qq.com>
Reviewed-by: Keith Randall <khr@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Development

No branches or pull requests

9 participants