runtime: reduce duplicate work by merging map operations

[prattmic]

default := ...
v, ok := m[k]
if !ok {
  m[k] = default
  v = default
}
// Use v

This is a mapaccess2 followed (conditionally) by a mapassign. The beginning of mapassign is identical to mapaccess2: hashing the key and looking for an existing entry (which won't be found).

In theory, the compiler could detect this pattern and use a special call for the map assignment that avoids the duplicate work (this would effectively be internal/runtime/maps.(*table).uncheckedPutSlot in today's implementation).

Another pattern is iteration plus delete:

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

It could be optimized in a similar way. This is also maps.DeleteFunc which could be directly specialized more easily than adding new compiler optimizations.

[prattmic]

The paper Representing Data Collections in an SSA Form describes adding high-level collection operations to compiler SSA to aid in optimizations, which I find a fascinating direction.

[mvdan]

I would be very happy if this were implemented! Previously, see #5147, and in particular, #5147 (comment) which describes how this would speed up declaring flags.

[mateusz834]

In theory, the compiler could detect this pattern and use a special call for the map assignment that avoids the duplicate work (this would effectively be internal/runtime/maps.(*table).uncheckedPutSlot in today's implementation).

It does not have to be internal/runtime/maps.(*table).uncheckedPutSlot. It can be even smarter. Want to point to Zig std lib hash map implementation, zig is a low level language (we don't want obviously to expose this kind of low level stuff), but the optimizations can be made even further, see:

https://ziglang.org/documentation/master/std/#std.hash_map.HashMap.getOrPut

If key exists this function cannot fail. If there is an existing item with key, then the result's Entry pointers point to it, and found_existing is true. Otherwise, puts a new item with undefined value, and the Entry pointers point to it. Caller should then initialize the value (but not the key).

It returns a struct https://ziglang.org/documentation/master/std/#std.hash_map.HashMapUnmanaged.GetOrPutResult

In Go land it would look something like:

type GetOrPutResult[K comparable, V any] struct {
	Key   *K
	Val   *V
	Found bool
}

func GetOrPut[K comparable, V any](m map[K]V, key K) GetOrPutResult[K, V] {
	return GetOrPutResult[K, V]{ /*....*/ }
}

func main() {
	m := make(map[string]string)
	r := GetOrPut(m, "somekey")
	if !r.Found {
		*r.Val = "val"
	}
}

With GetOrPut the caller is responsible to set the value in case r.Found == false.

This works because while scanning for a given key in a swisstable, we also know the place where we would have inserted the element with the same key (at least in Zig, not sure whether this would be possible in Go), thus we can return a pointer to it and there is no need to do that work again in uncheckedPutSlot.

[mknyszek]

Related: #5147

[mateusz834]

FYI I have a WIP (seems to work) implementation of GetOrPut operation in CL 662995 currently only for faststr and fast64.

Shows ~15% speedup for get or put operations (when key does not exist in the map).

v, ok := m[key]
if !ok {
	m[key] = value
}

With a 4.5% slowdown of only get operations (key is already inserted).

[thepudds]

With a 4.5% slowdown of only get operations.

Hi @mateusz834, could you expand slightly on what you mean by that?

(I would have thought an optimization like this could be implemented without slowing down a normal get operation, but maybe you mean "GetOrPut" is only ~4.5% slower than a normal get, but that a normal get is unaffected by this change?)

I have a couple of comments on the implementation, but I will comment on the CL.

[mateusz834]

With a 4.5% slowdown of only get operations.

In cases where the if !ok branch is not reached, so the key already exists in the map. It is ~4.5% slower than mapaccess and mapinsert separately.

maybe you mean "GetOrPut" is only ~4.5% slower than a normal get, but that a normal get is unaffected by this change?

Yes.

[gopherbot]

Change https://go.dev/cl/664918 mentions this issue: cmd/compile: combine access/assign map operations