unicode-org / icu4x / 14317629463

73%

Build Type

push

github

Committed by web-flow

Commit Message

Impl Extend for LiteMap and avoid quadratic behavior in from_iter and deserialize (#6132)

Adds `lm_extend` to the `StoreMut` trait. The Vec implementation is
optimized to have O(N) performance on sorted inputs and an asymptotic
worst case of O(NLog(N)), effectively avoiding quadratic worst cases.

This PR takes advantage of the new `extend` optimization and changes the
`FromIterator` and `Deserialize` implementations to also avoid quadratic
worst-case.

Before
```
litemap/from_iter_rand/small
                        time:   [916.60 ns 941.77 ns 965.82 ns]
litemap/from_iter_rand/large
                        time:   [2.3779 s 2.3863 s 2.3946 s]
litemap/from_iter_sorted/small
                        time:   [84.010 ns 84.084 ns 84.155 ns]
litemap/from_iter_sorted/large
                        time:   [725.31 µs 739.88 µs 755.20 µs]
```

After

```
litemap/from_iter_rand/small
                        time:   [354.62 ns 365.31 ns 376.02 ns]
litemap/from_iter_rand/large
                        time:   [25.129 ms 25.415 ms 25.704 ms]
litemap/from_iter_sorted/small
                        time:   [76.593 ns 76.767 ns 76.938 ns]
litemap/from_iter_sorted/large
                        time:   [662.70 µs 673.66 µs 686.83 µs]
litemap/extend_rand/large
                        time:   [66.221 ms 67.467 ms 68.814 ms]
litemap/extend_rand_dups/large
                        time:   [190.24 ms 196.05 ms 202.13 ms]
litemap/extend_from_litemap_rand/large
                        time:   [2.0401 s 2.0488 s 2.0575 s]
```

This is a followup of #6068

Run Details

154 of 159 new or added lines in 5 files covered. (96.86%)

3 existing lines in 3 files now uncovered.

57867 of 79256 relevant lines covered (73.01%)

804924.87 hits per line