Swap `IndexedMap` implementation for a `HashMap`+B-Tree
authorMatt Corallo <git@bluematt.me>
Thu, 19 Jan 2023 17:59:10 +0000 (17:59 +0000)
committerMatt Corallo <git@bluematt.me>
Wed, 25 Jan 2023 18:58:51 +0000 (18:58 +0000)
commit039fa5255da65cd84c42af93e720e3db57a09b38
treeeb4f935acdd382179a8ce6300252c8f5cc6f4b9c
parent1bd35367d8495d9a8b90f5de0f02b68014523e3b
Swap `IndexedMap` implementation for a `HashMap`+B-Tree

Our network graph has to be iterable in a deterministic order and
with the ability to iterate over a specific range. Thus,
historically, we've used a `BTreeMap` to do the iteration. This is
fine, except our map needs to also provide high performance lookups
in order to make route-finding fast. Sadly, `BTreeMap`s are quite
slow due to the branching penalty.

Here we replace the implementation of our `IndexedMap` with a
`HashMap` to store the elements itself and a `BTreeSet` to store
the keys set in sorted order for iteration.

As of this commit on the same hardware as the above few commits,
the benchmark results are:

```
test routing::router::benches::generate_mpp_routes_with_probabilistic_scorer ... bench: 109,544,993 ns/iter (+/- 27,553,574)
test routing::router::benches::generate_mpp_routes_with_zero_penalty_scorer  ... bench:  81,164,590 ns/iter (+/- 55,422,930)
test routing::router::benches::generate_routes_with_probabilistic_scorer     ... bench:  34,726,569 ns/iter (+/- 9,646,345)
test routing::router::benches::generate_routes_with_zero_penalty_scorer      ... bench:  22,772,355 ns/iter (+/- 9,574,418)
```
lightning/src/util/indexed_map.rs