# BTreeMap constant time first/last iterators

**URL:** <https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101>\
**Category:** libs\
**Created:** [April 7, 2020, 7:12am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101 "2020-04-07T07:12:59Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 7, 2020, 7:12am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/1 "2020-04-07T07:12:59Z")

</div>

One of the common operations for sorted maps/sets is looking at first or last few elements. C++ std::map has constant time complexity for begin() and end(). While BTreeMap might be better in many ways I cannot even use it because getting the first and last iterator is 2\*log(n). And this isn't something easily fixed by making a wrapper with my needs because on new inserts to front or back of the collection, I would need to do another log(n) probe to get the first/last iter.

As it stands, two log(n) probes to get a front of tree iterator is way too expensive for my use. Can a constant time version be made?

(This isn't unique btreemap, i've also had re-implement my down doubly linked list because of similar issues where the idea sounds nice, but it just lacks some basic functionality to make it useful in more complex cases.)

---

<div class="post-metadata">

**Author:** ![jschievink](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jschievink/32/3063_2.png) [@jschievink](https://internals.rust-lang.org/u/jschievink)\
**Post date:** [April 7, 2020, 10:33am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/2 "2020-04-07T10:33:11Z")

</div>

Nightly has `first_key_value` and `last_key_value` for this, but I think they're `O(log n)` (how would a constant-time version be implemented?). [This PR](https://github.com/rust-lang/rust/pull/70850) improves them a bit and adds `pop_first` and `pop_last` methods.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [April 7, 2020, 12:38pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/3 "2020-04-07T12:38:51Z")

</div>

> [@jschievink](#):
>
> how would a constant-time version be implemented?

Potentially it could always keep pointers to the first/last element around? Updating those also has a cost, though...

Cc @ssomers

---

<div class="post-metadata">

**Author:** ![Amanieu](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/amanieu/32/4095_2.png) [@Amanieu](https://internals.rust-lang.org/u/Amanieu)\
**Post date:** [April 7, 2020, 12:41pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/4 "2020-04-07T12:41:14Z")

</div>

Actually due to the way B-Trees are structured, the pointer to the first node never needs to be updated. The pointer to the last node will need to be updated when splitting and merging nodes however.

---

<div class="post-metadata">

**Author:** ![ssomers](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ssomers/32/6150_2.png) [@ssomers](https://internals.rust-lang.org/u/ssomers)\
**Post date:** [April 7, 2020, 1:09pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/5 "2020-04-07T13:09:38Z")

</div>

That PR just changes looks, not performance.

---

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 7, 2020, 3:28pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/6 "2020-04-07T15:28:22Z")

</div>

The actual iterators are needed, not just the first value. And I am using nightly so I've already seen that, and it is still 2\*log n to get an iterator. And I don't want to pop anything.

---

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 7, 2020, 3:35pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/7 "2020-04-07T15:35:12Z")

</div>

> Updating those also has a cost, though...

That mostly properly predicted branch (even if not) on every insert and removal is a hell of a lot cheaper than all the cache misses running down both side of the tree.

---

<div class="post-metadata">

**Author:** ![jschievink](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jschievink/32/3063_2.png) [@jschievink](https://internals.rust-lang.org/u/jschievink)\
**Post date:** [April 7, 2020, 4:02pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/8 "2020-04-07T16:02:34Z")

</div>

Don't forget the size increase of `2 * size_of::<usize>()` for every `BTreeMap` and `BTreeSet` though

---

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 7, 2020, 4:44pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/9 "2020-04-07T16:44:00Z")

</div>

I'd consider that more than acceptable - the gain is constant time iterator creation, min, max, left most, right most, etc.

Iterator creation is horribly expensive in the current implementation. With 10k elements, even wtih an avg branching factor of 5, you're expecting 10+ cache misses to create an iterator.

---

<div class="post-metadata">

**Author:** ![RalfJung](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/ralfjung/32/2415_2.png) [@RalfJung](https://internals.rust-lang.org/u/RalfJung)\
**Post date:** [April 7, 2020, 9:46pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/10 "2020-04-07T21:46:59Z")

</div>

> [@jnordwick](#):
>
> I'd consider that more than acceptable - the gain is constant time iterator creation, min, max, left most, right most, etc.

_You_ would consider that acceptable, yes -- but I am sure there are usecases where duplicating the size of a `BTreeMap` would be a disaster, but the tiny cost of 10 cache misses every now and then is entirely irrelevant.

---

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 7, 2020, 11:08pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/11 "2020-04-07T23:08:53Z")

</div>

You would literally be adding to pointers to the top level structures, not to every node. That is dwarfed by the size of the data held by those structures. Far more people will be impacted by a 2\*log(n) iterator creation that 16 more byes on a one time hit.

If they are that memory constrained they aren't going to be using btreemap (especially when there isnt any way to control the allocation strategy).

This argument is a huge reach.

---

<div class="post-metadata">

**Author:** ![kornel](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kornel/32/2711_2.png) [@kornel](https://internals.rust-lang.org/u/kornel)\
**Post date:** [April 7, 2020, 11:44pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/12 "2020-04-07T23:44:48Z")

</div>

> [@RalfJung](#):
>
> there are usecases where duplicating the size of a `BTreeMap` would be a disaster, but the tiny cost of 10 cache misses every now and then is entirely irrelevant.

I'm having hard time imagining such case. It would require _lots_ of mostly empty `BTreeMap`s, and then my worry would be not that it would take too much memory overall (these are just a couple of pointers), but that it would not fit in the cache — causing more cache misses. Cache misses are the major cost to worry about.

---

<div class="post-metadata">

**Author:** ![Tom-Phinney](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tom-phinney/32/3299_2.png) [@Tom-Phinney](https://internals.rust-lang.org/u/Tom-Phinney)\
**Post date:** [April 8, 2020, 12:23am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/13 "2020-04-08T00:23:13Z")

</div>

So @jnordwick, why not create a modified version of BTreeMap that does what you want and benchmark it in various scenarios? Without any hard comparative data this discussion is really just hypothetical.

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steffahn/32/13288_2.png) [@steffahn](https://internals.rust-lang.org/u/steffahn)\
**Post date:** [April 8, 2020, 12:24am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/14 "2020-04-08T00:24:14Z")

</div>

> [@kornel](#):
>
> I'm having hard time imagining such case.

I’m guessing a better comparison might be between:

the 2\*log\_5(n/11) _[i.e. practically always a TINY constant]_ time overhead that you might only encounter in the occasional moments when you create an iterator, where in common use cases this overhead is _dwarfed_ by the time that the actual _iteration_ over a decent part of the whole structure takes

vs.

a _repeated_ constant time overhead in potentially almost every operation that updates the map to keep those two pointers up to date.

I mean, I don’t know the data structure too well, the best approach would probably be to implement a different version and just benchmark. If there’s no noticeable performance regressions anywhere then, sure, maybe it is a good idea to change the implementation. _Ah, and now @Tom-Phinney said the exact same thing before I finished xD_

---

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 8, 2020, 5:31am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/15 "2020-04-08T05:31:11Z")

</div>

> [@steffahn](#):
>
> the 2\*log\_5(n/11) _[i.e. practically always a TINY constant]_

First of all, that is log time overhead, not constant and when you 10k-100k elements, it matters. but second, cache misses are how you evaluate high performance, latency sensitive run time costs. Cache hit rates are your deciding factor. You would rather do hundreds to thousands of useless operations than make a trip to memory. This it the reason bteemap was chosen over red-black or avl trees. And this is also the reason for rust going with a quadratic probe hash table. You're basically arguing against the decision criteria used for choosing these version the data structures.

Literally, cache is king.

A dozen cache misses vs. one (maybe be 2 at times) comparisons that are mostly going to be properly predicted (so 1 cycle plus the instruction slot) is such a no-brainier trade off.

Iterators are the largest reason you use a tree over a hash - you need ordering and some for of traveral (prev and next values).

I don't have the rust skills to implement this at this time. I tried to read the bteemap code and it is incredibly complex rust code (the btree algorithms aren't that complex, just all the rust-ism is beyond my level.

---

<div class="post-metadata">

**Author:** ![PoignardAzur](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/poignardazur/32/6464_2.png) [@PoignardAzur](https://internals.rust-lang.org/u/PoignardAzur)\
**Post date:** [April 8, 2020, 8:57am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/16 "2020-04-08T08:57:03Z")

</div>

> [@jnordwick](#):
>
> You're basically arguing against the decision criteria used for choosing these version the data structures.

I'm not saying you're wrong, but this is a little more confrontational than necessary.

---

<div class="post-metadata">

**Author:** ![pcpthm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/pcpthm/32/4952_2.png) [@pcpthm](https://internals.rust-lang.org/u/pcpthm)\
**Post date:** [April 8, 2020, 11:16am UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/17 "2020-04-08T11:16:08Z")

</div>

This is not what OP is asking but I think there is a way to improve the time complexity in OP's use-case by adding data structure without modifying `BTreeMap` itself.

For the simplicity, I only describe one-way implementation (`first` only). It can be extended to two-way but it will be slightly more complex.

You maintain a sorted array of length `P` in addition to the main B-tree data structure where `P` is a constant `P ∊ Θ(log N)` that can be tuned. For a sorted sequence of `n` elements, the array always contains the prefix of sequence of size `min(n, P)` and the remaining suffix of is maintained by the B-tree.

It can be implemented so the time complexity is `O(log N)` for insert/remove/find, and iterating first `k` elements runs in `O(k)` time (in particular, the first element can be accessed in `O(1)` time). It believe it is also fast in practice because it is just an array access. Implementation: [https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2c63d0fa5dc188fc5f0e8ea0650e7227](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2c63d0fa5dc188fc5f0e8ea0650e7227). Probably it can be improved by using SIMD instructions or some other techniques.

---

<div class="post-metadata">

**Author:** ![Tom-Phinney](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/tom-phinney/32/3299_2.png) [@Tom-Phinney](https://internals.rust-lang.org/u/Tom-Phinney)\
**Post date:** [April 8, 2020, 3:02pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/18 "2020-04-08T15:02:45Z")

</div>

> [@jnordwick](#):
>
> I don't have the rust skills to implement this at this time. I tried to read the bteemap code and it is incredibly complex rust code (the btree algorithms aren't that complex, just all the rust-ism is beyond my level.

To paraphrase, you haven't found a crate in the Rust ecosystem that offers a version of BTreeMap that meets your needs, and you yourself don't have the needed skill with Rust to create such a derivative version. Perhaps a query for help on the [Rust Users Forum](https://users.rust-lang.org/) might locate someone able to make the changes you want, resulting in a [crates.io](http://crates.io) contribution with a new variant of BTreeMap.

---

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 8, 2020, 3:28pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/19 "2020-04-08T15:28:02Z")

</div>

> resulting in a [crates.io](http://crates.io/) contribution with a new variant of BTreeMap

Splitting the BTreeMap on such a small change would be counterproductive the the rust ecosystem. It is already balkanized enough. The point of bringing this up herre was to stay in the bound the current one. If my view was "screw you I'm going to write my own " I wouldn't have posted here and would have just written my own (in a very C-like style because that is about where my rust knowledge is). It is a no-brainer for 90% of performance-sensitive cases.

---

<div class="post-metadata">

**Author:** ![jnordwick](https://avatars.discourse-cdn.com/v4/letter/j/aca169/32.png) [@jnordwick](https://internals.rust-lang.org/u/jnordwick)\
**Post date:** [April 8, 2020, 3:32pm UTC](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101/21 "2020-04-08T15:32:28Z")

</div>

> [@pcpthm](#):
>
> For the simplicity, I only describe one-way implementatio

All that work to avoid two pointer and an extra cmp? This is a horrible idea. This is basically building your own copy of the first and last node in the tree. Why not just keep pointers to them in the structure?

I'm getting the feeling here that most people in this discussion don't have strong performance requirements in the software they write - which is fine - but it creates a very different mindset. Asymptotic complexity isn't what matters most here (although my original post wasn't very clear on that) - it is the dozen cache misses that kill things. You get rid of that, but now I have to do way more work that the BTreeMap would be doing if it was keeping track of the first land last node itself.

[Next page](https://internals.rust-lang.org/t/btreemap-constant-time-first-last-iterators/12101.md?page=2)
