toffaletti / flat_map

A compact map stored as a vector of key, value pairs.
Apache License 2.0
12 stars 7 forks source link

Add benchmarks, faster batch_insert. #7

Closed Pratyush closed 7 years ago

Pratyush commented 7 years ago

Hi,

This is a PR for some perf improvements:

  1. A new FromIterator impl that collects the iterator into a Vec, sorts it by the key, dedups by the key, and constructs a new FlatMap from this. This is much faster for large inputs than inserting each pair one by one because the latter requires moving elements down the vector whenever an insertion occurs.

  2. I added #[inline] attributes to small functions.

I also added some benchmarks comparing the map to BTreeMap from the stdlib, and added myself to the contributors list.

Pratyush commented 7 years ago

I pushed some updates:

  1. Fixed the benchmark code and added a new from_iter benchmark.
  2. Removed #[inline] attributes because they weren't giving any speed-ups on the benchmarks. Perhaps the compiler is smart enough to know when to inline function calls in our case.