Poor use of memory / too many allocations in HashLeaf, leading to GC to work in overdrive

[musalbas]

More time is spent in HashLeaf allocating, than hashing:

https://github.com/celestiaorg/nmt/blob/master/hasher.go#L190
https://flamegraph.com/share/a54e891a-1114-11ee-b13f-de9431916b05

---

Possibly related:

In celestia-node, min and max namespace take up 200MB (20%) of RAM

[musalbas]

If the same allocation is reused in HashLeaf--would that make it not threadsafe? If so, should be considered, I believe trees are often computed in parallel.

[liamsi]

I would try the folllwing fwiw. Change these appends

nmt/hasher.go

Lines 190 to 192 in 564300a

	minMaxNIDs := make([]byte, 0, resLen)
	minMaxNIDs = append(minMaxNIDs, nID...) // nID
	minMaxNIDs = append(minMaxNIDs, nID...) // nID || nID

to

minMaxNIDs :=  append(append(make([]byte, 0, resLen), nID...), nID...) 

and see if that removes the need for additional allocs. Similar for the other appends:

nmt/hasher.go

Lines 195 to 197 in 564300a

	leafPrefixedNData := make([]byte, 0, len(ndata)+1)
	leafPrefixedNData = append(leafPrefixedNData, LeafPrefix)
	leafPrefixedNData = append(leafPrefixedNData, ndata...)

[liamsi]

Also, it is important to use benchstat for any related changes (since we disabled go-bencher recently): https://pkg.go.dev/golang.org/x/perf/cmd/benchstat

Should include both mem and CPU.

[liamsi]

This could be somewhat related: #212