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: performance of map[string(bytes)]++ #45021

Open
egonelbre opened this issue Mar 15, 2021 · 8 comments
Open

runtime: performance of map[string(bytes)]++ #45021

egonelbre opened this issue Mar 15, 2021 · 8 comments

Comments

@egonelbre
Copy link
Contributor

@egonelbre egonelbre commented Mar 15, 2021

Currently using map[string]*int to count []byte values is significantly faster than using map[string]int. This came up in https://benhoyt.com/writings/count-words/ post. It would be nicer if map[string]int was as fast or faster.

To demonstrate the issue:

var testBytesValues = func() (xs [][]byte) {
	for i := 0; i < 1000; i++ {
		xs = append(xs, []byte(strconv.Itoa(i)+"-"+strconv.Itoa(i)))
	}
	return xs
}()

func BenchmarkByteInt(b *testing.B) {
	count := map[string]int{}
	for i := 0; i < b.N; i++ {
		for _, v := range testBytesValues {
			count[string(v)]++
		}
	}
}

func BenchmarkBytePointer(b *testing.B) {
	count := map[string]*int{}
	for i := 0; i < b.N; i++ {
		for _, v := range testBytesValues {
			if p, ok := count[string(v)]; ok {
				*p++
				continue
			}
			p := new(int)
			*p = 1
			count[string(v)] = p
		}
	}
}

Outputs:

BenchmarkByteInt-32                18928             63314 ns/op
BenchmarkBytePointer-32            38485             32200 ns/op

The underlying issue seems to be that, in the map[string]*int case the code ends up calling first mapaccess2_faststr (for the common case) and then mapassign_faststr. Whereas map[string]int only calls mapassign_faststr. See https://go.godbolt.org/z/j6PY77.

mapaccess2_faststr currently does not cause a call to slicebytetostring, however mapassign_faststr does, which means that with map[string]int it ends up doing bunch of conversions that are unnecessary.

@egonelbre
Copy link
Contributor Author

@egonelbre egonelbre commented Mar 15, 2021

One option would also be to avoid slicebytetostring when writing the longer form of the assignment:

func Increment(x map[string]int, v []byte) {
    if c, ok := x[string(v)]; ok {
        x[string(v)] = c + 1 // <---- avoid slicebytetostring
        return
    }
    x[string(v)] = 1
}

While this is not as convenient, it still would allow to write the code without the conversion.

@martisch
Copy link
Contributor

@martisch martisch commented Mar 15, 2021

The map functions themselfs do not make calls to slicebytetostring but that is done before passing the string to them.
Map functions are not aware themselfs whether the passed in key was created by a string conversion from a byte slice that avoided the allocation of a new string or a string was passed in directly with no conversion. Therefore count[string(v)]++ that can create a new key needs to allocate before calling map functions and just reading a value for a key e.g. count[string(v)] does not need to currently.

If this is really important for optimisation I see two possible improvements:

  1. add an extra bit of information to map*_faststr versions (for which it is advantageous) that conveys that for new entries a copy needs to be made of the string (might be bearable in performance with register calling convention)
  2. add new copies of map*_faststr that e.g. mapassign_faststrneedscopy that are used when the key was directly created from a byte slice and needs a copy when creating a new entry in the map.

Personally I am not a fan of adding even more copies of map functions to the runtime for special string variants. Maybe it would at that point be better to allow byte slices as map keys (not using cap for key comparison and hashes) and making byte slice copies on demand in specialised byte slice map runtime functions.

@cherrymui cherrymui added this to the Unplanned milestone Mar 15, 2021
@cherrymui
Copy link
Contributor

@cherrymui cherrymui commented Mar 15, 2021

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Mar 15, 2021

Dup of #5147 ?

@martisch
Copy link
Contributor

@martisch martisch commented Mar 15, 2021

While #5147 if implemented would give one option to avoid an allocation (for existing keys) by rewriting count[string(v)]++ with an explicit check for key and then assignment there are other options to solve this specific case that do not require a rewrite by making the compiler and runtime do some optimisations and special casing. Therefore it might be worth to keep this issue open independently.

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Mar 15, 2021

add an extra bit of information to map*_faststr versions (for which it is advantageous) that conveys that for new entries a copy needs to be made of the string (might be bearable in performance with register calling convention)

This seems reasonable to me. We can have mapassign_faststr and mapassign_faststrtmp that use a common implementation routine, and we only need to worry about the extra temp-or-not bool in the "store new key at insert position" point.

(Incidentally, I thought we used to have the semantics that if we overwrote a string key in a map, we retained the new string instead of the old one? It doesn't look like that's currently the case. Am I misremembering that and/or misreading the current code?)

@randall77
Copy link
Contributor

@randall77 randall77 commented Mar 15, 2021

(Incidentally, I thought we used to have the semantics that if we overwrote a string key in a map, we retained the new string instead of the old one? It doesn't look like that's currently the case. Am I misremembering that and/or misreading the current code?)

That sounds right. I think the current code does that, look for needkeyupdate.
But maybe the _fast versions don't?

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Mar 15, 2021

But maybe the _fast versions don't?

Looks like it: https://play.golang.org/p/M6JXPe8-EH4

On the upside, that means we can be assured that this optimization won't break anyone expecting m[string(bytes)]++ to overwrite existing keys.

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
6 participants