rust-lang/rust — pull request #15399 by kballard (2014-07-04 05:28:24+00:00)
Title: Rewrite the local_data implementation

**WIP**: not quite ready. net tests are failing locally, but I'm suspicious of them on my machine in general, so I'm running it on try right now. Also, @huonw has expressed a desire to benchmark this new implementation using `Vec` again instead of `TreeMap`.

---

This was motivated by a desire to remove allocation in the common
pattern of

let old = key.replace(None)
do_something();
key.replace(old);

While doing this, I also thought it was a good idea to remove the
failure case from replace() if the value is borrowed. Because the TLD
map has to store boxed values with a loan count anyway, there's very
little overhead to switching to using Rc internally, thus allowing
replace() to work even if there's an extant Ref (because the Ref will
still keep its referenced value alive).

The downside is the return value of replace() is now more complicated,
because it can only return the value unboxed if it's uniquely-owned.
This complication can be ameliorated by calling .unwrap() on the return
value, thus providing the same unwrapped-value-or-failure behavior as
the old replace().

Finally, this also switched the map representation from a Vec to a
TreeMap. A Vec may be reasonble if there's only a couple TLD keys, but a
TreeMap provides better behavior as the number of keys increases.

Like the Vec, this TreeMap implementatino does not shrink the container
when a value is removed. Unlike Vec, this TreeMap implementation cannot
reuse an empty node for a different key. Therefore any key that has been
inserted into the TLD at least once will continue to take up space in
the Map until the task ends. The expectation is that the majority of
keys that are inserted into TLD will be expected to have a value for
most of the rest of the task's lifetime. If this assumption is wrong,
there are two reasonable ways to fix this that could be implemented in
the future:

1. Provide an API call to either remove a specific key from the TLD and
destruct its node (e.g. `remove()`), or instead to explicitly clean
up all currently-empty nodes in the map (e.g. `compact()`). This is
simple, but requires the user to explicitly call it.
2. Keep track of the number of empty nodes in the map and when the map
is mutated (via `replace()`), if the number of empty nodes passes
some threshold, compact it automatically. Alternatively, whenever a
new key is inserted that hasn't been used before, compact the map at
that point.

---

Benchmarks:

I ran 3 benchmarks. tld_replace_none just replaces the tld key with None
repeatedly. tld_replace_some replaces it with Some repeatedly. And
tld_replace_none_some simulates the common behavior of replacing with
None, then replacing with the previous value again (which was a Some).

Old implementation:

test tld_replace_none ... bench: 20 ns/iter (+/- 0)
test tld_replace_none_some ... bench: 77 ns/iter (+/- 4)
test tld_replace_some ... bench: 57 ns/iter (+/- 2)

New implementation:

test tld_replace_none ... bench: 13 ns/iter (+/- 1)
test tld_replace_none_some ... bench: 29 ns/iter (+/- 1)
test tld_replace_some ... bench: 17 ns/iter (+/- 1)

[breaking-change]