Trie: Simplify findPath()

[holgerd77]

This is re-taken from the trie refactor from #2785 which turned out to be too extensive to get completed, there is a a lot of stuff in there which likely can be extracted and integrated via separate and independent PRs.

This specific PR takes on simplifying the over-complicated findPath() logic and call chaining, which makes it pretty hard to follow on what findPath() is doing.

Goal of this PR would be to get the existing tests back to working, then replace the findPath() implementation with the adopted findPath2() entrypoint and remove the old functionality.

I might take on this but can also be taken on by @ScottyPoi or someone else.

One deeper description on what this is doing: so this is bascially going down the call-chain of the existing findPath() method and renames a lot of things, also takes in functionality from separate unnecessary methods over since the old call chain was unnecessarily re-instantiating stuff and the like on methods with just a one-line logic thing, all a bit insane. This made it close to impossible to follow the call-chain.

So while a bit hard to see since there is no code diff, this PR does not refactor the findPath() logic at all (and is not intended to do so). This is simply about simplification and streamlining and should remain in this scope.

[codecov[bot]]

Codecov Report

Merging #2962 (6ce72ff) into master (bae3740) will decrease coverage by 0.04%. The diff coverage is 93.75%.

Additional details and impacted files

Flag	Coverage Δ
block	88.73% <ø> (ø)
blockchain	92.58% <ø> (ø)
client	87.28% <ø> (-0.04%)	:arrow_down:
common	98.18% <ø> (ø)
ethash	∅ <ø> (∅)
evm	69.85% <ø> (ø)
rlp	∅ <ø> (?)
statemanager	84.46% <ø> (ø)
trie	89.76% <93.75%> (-0.51%)	:arrow_down:
tx	96.38% <ø> (ø)
util	86.78% <ø> (ø)
vm	75.97% <ø> (ø)

Flags with carried forward coverage won't be shown. Click here to find out more.

[holgerd77]

Side note: we likely want to run the reactivated trie benchmarks on this from #2969 with before and after results once we have this ready and the tests going.

[ScottyPoi]

One of the trie/test/proof.spec.ts failed when everything else passed.

This tested a valid proof with an invalid key, which should return null. The failure may have been a vitest issue, or something. It seemed like a try/catch was not catching an error during a test that expected a specific error message. so the test ended in failure, when the failure should have been caught, and the error message compared to the expected error.

I tweaked some things so all of the Trie tests would pass, but a few downstream tests fail now. Will comb through it this weekend to find out why

[holgerd77]

Cool 🙏, seems pretty close already! 🙂 Can you do an in-between benchmarks run before and after and paste the results here?

[ScottyPoi]

Benchmarks:

master:

-------
Benchmarking
-------
Benchmarking
1k-3-32-ran x 3 ops/sec @ 296ms/op
1k-5-32-ran x 3 ops/sec @ 292ms/op
1k-9-32-ran x 3 ops/sec @ 287ms/op
1k-1k-32-ran x 3 ops/sec @ 308ms/op
1k-1k-32-mir x 3 ops/sec @ 311ms/op
Checkpointing: 100 iterations x 4,628 ops/sec @ 216μs/op ± 29.65% (min: 75μs, max: 2ms)
Checkpointing: 500 iterations x 3,753 ops/sec @ 266μs/op ± 10.09% (min: 143μs, max: 3ms)
Checkpointing: 1000 iterations x 3,513 ops/sec @ 284μs/op ± 7.02% (min: 170μs, max: 4ms)
Checkpointing: 5000 iterations x 2,689 ops/sec @ 371μs/op ± 4.10% (min: 182μs, max: 6ms)
RAM: rss=646.5mb heap=549.8mb used=520.2mb ext=7.2mb arr=4.7mb
1k-3-32-ran x 0 ops/sec @ 4080ms/op
1k-5-32-ran x 3 ops/sec @ 300ms/op
1k-9-32-ran x 3 ops/sec @ 320ms/op
1k-1k-32-ran x 2 ops/sec @ 337ms/op
1k-1k-32-mir x 2 ops/sec @ 349ms/op
Checkpointing: 100 iterations x 4,075 ops/sec @ 245μs/op ± 20.76% (min: 81μs, max: 2ms)
Checkpointing: 500 iterations x 3,324 ops/sec @ 300μs/op ± 6.15% (min: 167μs, max: 1ms)
Checkpointing: 1000 iterations x 3,125 ops/sec @ 319μs/op ± 4.02% (min: 197μs, max: 2ms)
Checkpointing: 5000 iterations x 2,673 ops/sec @ 374μs/op ± 1.66% (min: 206μs, max: 4ms)
RAM: rss=411.6mb heap=261.3mb used=190.5mb ext=60.1mb arr=57.7mb

trie-find-path-simplified-new

-------
Benchmarking
-------
Benchmarking
1k-3-32-ran x 2 ops/sec @ 349ms/op
1k-5-32-ran x 2 ops/sec @ 334ms/op
1k-9-32-ran x 2 ops/sec @ 357ms/op
1k-1k-32-ran x 2 ops/sec @ 386ms/op
1k-1k-32-mir x 2 ops/sec @ 402ms/op
Checkpointing: 100 iterations x 4,918 ops/sec @ 203μs/op ± 20.82% (min: 80μs, max: 2ms)
Checkpointing: 500 iterations x 3,395 ops/sec @ 294μs/op ± 11.15% (min: 167μs, max: 3ms)
Checkpointing: 1000 iterations x 3,054 ops/sec @ 327μs/op ± 6.59% (min: 197μs, max: 4ms)
Checkpointing: 5000 iterations x 2,356 ops/sec @ 424μs/op ± 3.87% (min: 203μs, max: 17ms)
RAM: rss=642.3mb heap=544.3mb used=515.8mb ext=7.5mb arr=5.0mb
1k-3-32-ran x 0 ops/sec @ 4826ms/op
1k-5-32-ran x 2 ops/sec @ 381ms/op
1k-9-32-ran x 2 ops/sec @ 401ms/op
1k-1k-32-ran x 2 ops/sec @ 427ms/op
1k-1k-32-mir x 2 ops/sec @ 443ms/op
Checkpointing: 100 iterations x 3,958 ops/sec @ 252μs/op ± 18.34% (min: 95μs, max: 1ms)
Checkpointing: 500 iterations x 3,168 ops/sec @ 315μs/op ± 5.86% (min: 189μs, max: 1ms)
Checkpointing: 1000 iterations x 2,803 ops/sec @ 356μs/op ± 3.83% (min: 225μs, max: 2ms)
Checkpointing: 5000 iterations x 2,342 ops/sec @ 426μs/op ± 1.58% (min: 235μs, max: 6ms)
RAM: rss=468.4mb heap=316.9mb used=182.5mb ext=61.0mb arr=58.5mb

[ScottyPoi]

bench	master	PR	compare
1k-3-32-ran	x 3 ops/sec @ 296ms/op	x 2 ops/sec @ 356ms/op	+60 ms/op
1k-5-32-ran	x 3 ops/sec @ 292ms/op	x 2 ops/sec @ 348ms/op	+56 ms/op
1k-9-32-ran	x 3 ops/sec @ 287ms/op	x 2 ops/sec @ 379ms/op	+92 ms/op
1k-1k-32-ran	x 3 ops/sec @ 308ms/op	x 2 ops/sec @ 418ms/op	+110 ms/op
1k-1k-32-mir	x 3 ops/sec @ 311ms/op	x 2 ops/sec @ 430ms/op	+119 ms/op
Checkpointing: 100 iterations	x 4,628 ops/sec @ 216μs/op ± 29.65% (min: 75μs, max: 2ms)	x 4,043 ops/sec @ 247μs/op ± 19.40% (min: 127μs, max: 2ms)	-1585 ops/sec { min: +52μs, max: +0ms }
Checkpointing: 500 iterations	x 3,753 ops/sec @ 266μs/op ± 10.09% (min: 143μs, max: 3ms)	x 2,884 ops/sec @ 346μs/op ± 11.56% (min: 194μs, max: 5ms)	-869 ops/sec { min: +51μs, max: +2ms }
Checkpointing: 1000 iterations	x 3,513 ops/sec @ 284μs/op ± 7.02% (min: 170μs, max: 4ms)	x 2,704 ops/sec @ 369μs/op ± 7.16% (min: 199μs, max: 5ms)	-809 ops/sec { min: +29μs, max: +1ms }
Checkpointing: 5000 iterations	x 2,689 ops/sec @ 371μs/op ± 4.10% (min: 182μs, max: 6ms)	x 2,313 ops/sec @ 432μs/op ± 3.31% (min: 210μs, max: 5ms)	-376 ops/sec { min: +28μs, max: +1ms }
RAM:	rss=646.5mb heap=549.8mb used=520.2mb ext=7.2mb arr=4.7mb	rss=643.2mb heap=545.3mb used=505.2mb ext=7.4mb arr=4.2mb	rss: -3.3mb heap: -4.5mb, used: -15mb, ext: +0.2mb, arr: -0.5mb
1k-3-32-ran	x 0 ops/sec @ 4080ms/op	x 0 ops/sec @ 5024ms/op	+956 ms/op
1k-5-32-ran	x 3 ops/sec @ 300ms/op	x 2 ops/sec @ 420ms/op	+120 ms/op
1k-9-32-ran	x 3 ops/sec @ 320ms/op	x 2 ops/sec @ 422ms/op	+102 ms/op
1k-1k-32-ran	x 2 ops/sec @ 337ms/op	x 2 ops/sec @ 446ms/op	+109 ms/op
1k-1k-32-mir	x 2 ops/sec @ 349ms/op	x 2 ops/sec @ 462ms/op	+113 ms/op
Checkpointing: 100 iterations	x 4,075 ops/sec @ 245μs/op ± 20.76% (min: 81μs, max: 2ms)	x 3,862 ops/sec @ 258μs/op ± 15.35% (min: 96μs, max: 1ms)	-213 ops/sec { min: +15μs, max: +1ms }
Checkpointing: 500 iterations	x 3,324 ops/sec @ 300μs/op ± 6.15% (min: 167μs, max: 1ms)	x 3,046 ops/sec @ 328μs/op ± 5.84% (min: 203μs, max: 2ms)	-222 ops/sec { min: +36μs, max: +1ms }
Checkpointing: 1000 iterations	x 3,125 ops/sec @ 319μs/op ± 4.02% (min: 197μs, max: 2ms)	x 2,604 ops/sec @ 383μs/op ± 3.78% (min: 231μs, max: 2ms)	-519 ops/sec { min: +34μs, max: +0ms }
Checkpointing: 5000 iterations	x 2,673 ops/sec @ 374μs/op ± 1.66% (min: 206μs, max: 4ms)	x 2,234 ops/sec @ 447μs/op ± 1.55% (min: 242μs, max: 5ms)	-439 ops/sec { min +36μs, max: +1ms }
RAM:	rss=411.6mb heap=261.3mb used=190.5mb ext=60.1mb arr=57.7mb	rss=456.6mb heap=304.1mb used=187.1mb ext=61.1mb arr=58.7mb	rss: +44mb, heap: +42.78mb, used: -3.4mb, ext: +1mb, arr: +1mb

[holgerd77]

Guess we need to put this on hold due to the performance results. Will give this a "blocked" label for now.

[ScottyPoi]

@holgerd77

I pared this down to as few lines of code as I could manage.
hope this is closer to what you were looking for. :pray:

the benchmark performance is the same, though.