gnosis / dex-services / 5381

31%

push

travis-pro

Get rid of dynamic dispatch in bellman ford algorithm (#1499)

Follow up on #1494 to remove performance regression. This PR was mostly @e00E's idea and replaces the dynamic dispatch that was required in the bellman_ford method (e.g. `update_distance` and `find_cycle`) with a direct invocation by turning the `Box<dyn PreprocessorStoring>` into a flat generic type (`P: PreprocessorStoring`).

There is still dynamic dispatch happening on the object returned from the create_new_shortest_graph method, however interactions seems to be limited enough to not affect the current performance metrics. 

### Test Plan
Benchmark between master (before 1494) and this branch:

No change in performance detected.

<details>

```
   Compiling pricegraph v0.1.0 (/Users/felixleupold/Gnosis/dex-services/pricegraph)
   Compiling pricegraph-bench v0.0.0 (/Users/felixleupold/Gnosis/dex-services/pricegraph/bench)
    Finished bench [optimized] target(s) in 5.87s
     Running /Users/felixleupold/Gnosis/dex-services/target/release/deps/pricegraph-3f4e763559a6a78d
Pricegraph::read        time:   [7.8050 ms 7.8283 ms 7.8568 ms]                             
                        change: [+0.7851% +1.5803% +2.3877%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe

Pricegraph::transitive_orderbook/5298183                                                                            
                        time:   [7.6825 ms 7.6974 ms 7.7135 ms]
                        change: [-2.1038% -1.5656% -1.1004%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 100 measurements (2.00%)
  2 (2.00%) high severe

Pricegraph::estimate_limit_price/100000000000000000                                                                             
                        time:   [101.28 us 101.73 us 102.20 us]
   ... (continued)

13729 of 54952 branches covered (24.98%)

Branch coverage included in aggregate %.

3728 of 5796 relevant lines covered (64.32%)

40844.86 hits per line