Performance Improvement

[yancyribbens]

I made a rather serious error which resulted in poor performance in the initial implementation. I've made a fork of the project and added a benchmark to measure performance. By removing the redundant for loop here the time to search through a utxo space of 10,000 with cargo bench:

time: [315.80 ms 316.59 ms 317.32 ms]

to the improved:

time: [438.80 µs 441.28 µs 443.84 µs] change: [-99.861% -99.860% -99.859%] (p = 0.00 < 0.05)

The search performance is now measured in nano-seconds instead of micro-seconds, an increase of 1000x.

My apologies for the initial oversight.

[murchandamus]

Nice, that's a solid improvement

[yancyribbens]

fyi: I made some minor improvements to the readability of theses commits (here and here).

[yancyribbens]

I've added a few more performance improvements, most notably this one here:. I think the commit simplifies the code as well as a 20% reduction in run-time. Overall, I've managed to reduce the time down to ~250 nano-seconds for a search space of 10,000 utxos:

time: [254.42 µs 254.53 µs 254.64 µs] change: [-22.062% -21.645% -21.349%] (p = 0.00 < 0.05)

[yancyribbens]

@Xekyo thanks for taking a look at my previous improvement btw. Please let me know if you have any suggestions.

[yancyribbens]

I just noticed that while the commit improves performance, it actually precludes more optimal solutions, and so while I thought I had made a mistake, the second for loop is actually required.

The test here fails on the "performance improved" version however the original solution is correct.

Long story short, false alarm.