search

celestiaorg / nmt

Namespaced Merkle Tree
Apache License 2.0
107 stars 39 forks source link

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

Open musalbas opened 1 year ago

musalbas commented 1 year ago

More time is spent in HashLeaf allocating, than hashing:

image 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

image

musalbas commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

This could be somewhat related: https://github.com/celestiaorg/nmt/issues/212