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 https://github.com/celestiaorg/nmt/blob/564300aaa2125d5881ecf62f024a22db190db17c/hasher.go#L190-L192 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: https://github.com/celestiaorg/nmt/blob/564300aaa2125d5881ecf62f024a22db190db17c/hasher.go#L195-L197

[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: https://github.com/celestiaorg/nmt/issues/212