map very slow with larger composite keys

[anuraaga]

When integrating a cache in an attempt to improve performance by reducing allocations, I found it to severely reduce performance, with map operations adding milliseconds of overhead. I tried making a simple benchmark to simulate similar behavior (notably, a large-ish composite key). It's hard to isolate processing vs FFI but I added a 100-iteration loop within wasm to try to help. I had originally hoped to make it larger, but it was too slow to complete in meaningful time.

https://github.com/corazawaf/coraza-proxy-wasm/compare/main...anuraaga:coraza-1225?expand=1#diff-173fbfd8d8844658344b121461b4290d0a85230caae9825240705df8130e8b75

goos: darwin
goarch: arm64
pkg: github.com/corazawaf/coraza-proxy-wasm/mapbench
BenchmarkMapBench
BenchmarkMapBench-10        	      28	  40528976 ns/op
BenchmarkMapBenchWasm
BenchmarkMapBenchWasm-10    	       1	26306643833 ns/op
PASS

There are of course many variables here, such as performance of the wasm runtime (wazero), though I noticed slow map performance in a real world usage with Envoy (v8) too. Even assuming wasm is slower than native code, this seems like many more orders of magnitude than I would expect in general.

Is this known performance behavior? I saw in #1553 that growing logic was added so hashmaps shouldn't end up with quadratic performance without an appropriate size hint, but in this benchmark the number of keys is about 2400 vs a size hint of 10000 so growing or load factor shouldn't be much of an issue either way.

I tried setting runtime_memhash_tsip but no real change.

For reference, the real-world code the benchmark attemps to reflect

corazawaf/coraza#537

[anuraaga]

Realized it may not be specific to maps, with adding some debug logging I found that the key is allocated on the heap each iteration. The intent for this sort of cache is to reduce allocations and it's important for the key to be on the stack. The size of the struct is 20 bytes, not tiny but still would expect it to stick to the stack.

Any pointer on where TinyGo decides to allocate a struct on the stack or heap. Or could it be that it always allocates them on the heap?

[anuraaga]

For reference, these seem to be the allocation sizes for a single k := key{...}; m[k] in this benchmark. Intuitively, I'd expect no allocations but there is the key struct, and then several other small ones

0x00000014
0x00000008
0x00000004
0x00000004
0x00000004
0x00000004
0x00000004

[anuraaga]

Ah found this, it probably is map specific

https://github.com/tinygo-org/tinygo/blob/release/compiler/map.go#L99

Conversion to interface would allocate.

Has there ever been any thought put into generating code to compute the hashcode for a struct inline instead of converting to interface? Do we not have runtime information available for a struct like Go does in structtype, without using reflect interfaces?

[anuraaga]

BTW JFYI I tried switching the string field to a pointer field (of course this is only a valid change in certain circumstances), and could confirm all allocations are gone, the ones shown before must indeed been of converting the key to an interface, and allocating some other helper objects during reflection presumably. Then Wasm is about 5-10x slower than native, while I wish Wasm is faster this looks much closer than what I'd expect and is workable :) Hoping there is a path towards supporting string fields in struct map keys more efficiently

[aykevl]

The map type has seen very little optimization effort, as you can see. In this case, it seems like the interface should have been stack allocated (by the heap-to-stack optimization) but apparently it wasn't.

Conversion to interface would allocate.

Not necessarily, but it may be hard for the compiler to prove it is safe to allocate on the stack.

Have you tried -print-allocs=. to print all heap allocations? (the . is a regex you can use to filter the output).

[anuraaga]

Ah thanks hadn't tried that flag before, looks pretty useful. Unfortunately I guess it's not able to introspect the code generated by the compiler, e.g. createMakeInterface and is just showing the allocations in the runtime code which all look appropriate.

❯ ~/go/bin/tinygo build -scheduler=none -target=wasi -opt=2 -o mapbench.wasm -print-allocs=.
/Users/anuraag/git/tinygo/src/runtime/string.go:62:15: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/arch_tinygowasm_malloc.go:51:13: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:245:19: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:244:17: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:239:19: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:215:20: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/arch_tinygowasm_malloc.go:18:13: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:76:17: object allocated on the heap: escapes at line 76
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:71:18: object allocated on the heap: size is not constant

[aykevl]

Unfortunately I guess it's not able to introspect the code generated by the compiler, e.g. createMakeInterface and is just showing the allocations in the runtime code which all look appropriate.

Yeah createMakeInterface is part of the compiler, not part of the resulting binary. Of course it won't be able to inspect it.

Is this with the fix to avoid strings in the struct, that you mentioned? Because in that case you won't see the allocation - you just avoided it. If you undo it, you should be able to see the allocation again (I'm guessing somewhere in your main package).

[anuraaga]

Oops duh thanks for noticing that. Not sure but looks like it's saying unsafe.Pointer(&key) causes an escape

/Users/anuraag/git/coraza-proxy-wasm/mapbench/mapbench.go:18:11: object allocated on the heap: escapes at line 18
/Users/anuraag/git/coraza-proxy-wasm/mapbench/mapbench.go:18:11: object allocated on the heap: escapes at line 18
/Users/anuraag/git/coraza-proxy-wasm/mapbench/mapbench.go:22:10: object allocated on the heap: escapes at line 22
/Users/anuraag/git/tinygo/src/runtime/string.go:62:15: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:591:41: object allocated on the heap: escapes at line 596
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:582:38: object allocated on the heap: escapes at line 588
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:574:38: object allocated on the heap: escapes at line 579
/Users/anuraag/git/tinygo/src/runtime/arch_tinygowasm_malloc.go:51:13: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:245:19: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:244:17: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:239:19: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:215:20: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/arch_tinygowasm_malloc.go:18:13: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:490:2: object allocated on the heap: escapes at line 495
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:499:2: object allocated on the heap: escapes at line 504
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:513:2: object allocated on the heap: escapes at line 514
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:567:30: object allocated on the heap: escapes at line 567
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:76:17: object allocated on the heap: escapes at line 76
/Users/anuraag/git/tinygo/src/runtime/hashmap.go:71:18: object allocated on the heap: size is not constant
/Users/anuraag/git/tinygo/src/reflect/type.go:440:19: object allocated on the heap: escapes at line 440
/Users/anuraag/git/tinygo/src/reflect/type.go:541:19: object allocated on the heap: escapes at line 541
/Users/anuraag/git/tinygo/src/reflect/type.go:525:18: object allocated on the heap: escapes at line 525
/Users/anuraag/git/tinygo/src/reflect/value.go:461:20: object allocated on the heap: escapes at line 461
/Users/anuraag/git/tinygo/src/reflect/value.go:194:20: object allocated on the heap: escapes at line 194
/Users/anuraag/git/tinygo/src/reflect/value.go:609:20: object allocated on the heap: escapes at line 609
/Users/anuraag/git/tinygo/src/reflect/value.go:413:20: object allocated on the heap: escapes at line 413
/Users/anuraag/git/tinygo/src/reflect/value.go:236:20: object allocated on the heap: escapes at line 236
/Users/anuraag/git/tinygo/src/reflect/value.go:364:20: object allocated on the heap: escapes at line 364
/Users/anuraag/git/tinygo/src/reflect/value.go:342:20: object allocated on the heap: escapes at line 342
/Users/anuraag/git/tinygo/src/reflect/value.go:273:20: object allocated on the heap: escapes at line 273
/Users/anuraag/git/tinygo/src/reflect/value.go:316:20: object allocated on the heap: escapes at line 316

[dgryski]

Taking ownership of map related issues.

[dgryski]

The escape logic is being confused by the function pointers in the hashmap struct type. Neither keyEqual or keyHash cause the value to escape, but because they're function pointers the compiler doesn't know that and so conservatively assumes that they do. We need to either special-case them in the compiler explicitly or figure out how to add //go:noescape annotations to them.

[dgryski]

Hmm.. can we even apply noescape in the interface case for the hashing logic that goes through reflect ?

[aykevl]

Hmm.. can we even apply noescape in the interface case for the hashing logic that goes through reflect ?

Yes, I think so. I don't see where reflection would keep the pointer alive after return (it certainly shouldn't).

[dgryski]

Oh right, I was thinking noescape == no allocations.

[dgryski]

I think the fix here is to tag more of these runtime hashmap methods as noescape for the keys.

For example, in

func hashmapStringSet(m *hashmap, key string, value unsafe.Pointer) {
	if m == nil {
		nilMapPanic()
	}
	hash := hashmapStringHash(key, m.seed)
	hashmapSet(m, unsafe.Pointer(&key), value, hash)
}

the compiler doesn't know that unsafe.Pointer(&key) is safe to allocate on stack, and so causes a heap allocation. The rest of the hashmap methods need similar noescape tags to indicate that the keys are always nocapture/readonly.

I just did this for stringFromBytes; adding the rest of the hashmapString* functions is reasonble (although yes we do need to be careful with interfaces to make sure we get that correct...)

[aykevl]

@dgryski yes sounds reasonable!