Rust: Finding minimum/maximum element in BTreeMap does twice the required amount of computation

[nexplor]

The standard way of finding the minimum element in BTreeMap is tree_map.iter().next()

The iter() function creates a btree_map::Iter, which finds both the minimum and maximum element to create its internal instance of btree_map::Range.

This is unnecessary, and a BTreeMap::get_min or similar function could be provided, which would just internally call the first_leaf_edge private function, without needing to call last_leaf_edge.

Ditto for finding the maximum element.

[cuviper]

Here are what the other collections call similar methods:

• [T] slices (and Vec via deref) have first/first_mut and last/last_mut.
• VecDeque and LinkedList have front/front_mut and back/back_mut.
• BinaryHeap has peek and peek_mut, i.e. only from the front.
• HashMap and HashSet are unordered, and have no such methods.
• str and String have no such methods.

[cuviper]

59947 is related -- Iterator::min/max are even worse since they naively walk everything.

[ssomers]

64820 is also related - BTreeSet is_subset, intersection and difference now always do this double work (they actually want both min and max at the same time, but requesting both next and next_back from the same iterator that may only see one element is not the most straightforward code).

I naively thought the redundant data (the other end and iterator length) and code would all get optimized away from an expression like tree_map.iter().next(), but after writing out code to avoid the double work in BTreeSet::is_subset, benchmarks report a 20 to 40% speed boost, for the cases where it can quickly bail out after getting min and max either side and comparing them. I'm going to measure the effect by adding the desired functions to map, and if successful I can put them in a pull request, but I have no idea what the procedure is for adding APIs. I vote for first and last as names.

[ssomers]

According to a raw benchmark, the specialized functions are about 3 times faster than .iter().next(). By the way, .range(..).next() is a little slower for small sets, despite not bothering with iterator length, presumably because iter() has access to internals to construct its unbounded range.

Details: benchmark code in liballoc/benches/btree/map.rs:

fn bench_first_and_last(b: &mut Bencher, size: i32) {
    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
    b.iter(|| {
        for _ in 0..10 {
            black_box(map.first_key_value());
            black_box(map.last_key_value());
        }
    });
}

#[bench]
pub fn first_and_last_0(b: &mut Bencher) {
    bench_first_and_last(b, 0);
}

#[bench]
pub fn first_and_last_100(b: &mut Bencher) {
    bench_first_and_last(b, 100);
}

#[bench]
pub fn first_and_last_10k(b: &mut Bencher) {
    bench_first_and_last(b, 10_000);
}

Results using the new functions:

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          37 ns/iter (+/- 2)
test btree::map::first_and_last_10k                      ... bench:          54 ns/iter (+/- 3)

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          42 ns/iter (+/- 1)
test btree::map::first_and_last_10k                      ... bench:          56 ns/iter (+/- 2)

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          37 ns/iter (+/- 1)
test btree::map::first_and_last_10k                      ... bench:          54 ns/iter (+/- 2)

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          37 ns/iter (+/- 0)
test btree::map::first_and_last_10k                      ... bench:          55 ns/iter (+/- 1)

Results using .iter().next() / .iter().next_back():

test btree::map::first_and_last_0                        ... bench:          65 ns/iter (+/- 1)
test btree::map::first_and_last_100                      ... bench:          97 ns/iter (+/- 3)
test btree::map::first_and_last_10k                      ... bench:         141 ns/iter (+/- 0)

test btree::map::first_and_last_0                        ... bench:          64 ns/iter (+/- 1)
test btree::map::first_and_last_100                      ... bench:          97 ns/iter (+/- 3)
test btree::map::first_and_last_10k                      ... bench:         131 ns/iter (+/- 4)

test btree::map::first_and_last_0                        ... bench:          65 ns/iter (+/- 2)
test btree::map::first_and_last_100                      ... bench:          96 ns/iter (+/- 3)
test btree::map::first_and_last_10k                      ... bench:         131 ns/iter (+/- 7)

test btree::map::first_and_last_0                        ... bench:          65 ns/iter (+/- 2)
test btree::map::first_and_last_100                      ... bench:          99 ns/iter (+/- 2)
test btree::map::first_and_last_10k                      ... bench:         131 ns/iter (+/- 15)

Results using .range(..).next() / .range(..).next_back():

test btree::map::first_and_last_0                        ... bench:          66 ns/iter (+/- 3)
test btree::map::first_and_last_100                      ... bench:         100 ns/iter (+/- 1)
test btree::map::first_and_last_10k                      ... bench:         123 ns/iter (+/- 2)

test btree::map::first_and_last_0                        ... bench:          67 ns/iter (+/- 5)
test btree::map::first_and_last_100                      ... bench:         100 ns/iter (+/- 4)
test btree::map::first_and_last_10k                      ... bench:         127 ns/iter (+/- 4)

test btree::map::first_and_last_0                        ... bench:          66 ns/iter (+/- 1)
test btree::map::first_and_last_100                      ... bench:         101 ns/iter (+/- 6)
test btree::map::first_and_last_10k                      ... bench:         123 ns/iter (+/- 5)

[matklad]

I vote for min/max rather than first/last terminology. Rationale: I’ve recently had a bad bug when I used Rust’s BinaryHeap and assumed that pop yields a minimal item. If the API had used max in the method name, I wouldn’t have made the bug.

This case is similar: first is ambiguous, min is precise (and shorter ^^).

[ssomers]

I'm slightly in favour of min/max at the moment, having faced reverse iteration in (other) code with first/last names. It's a close call; min/max is ambiguous about performance, because many min/max functions out there are in fact linear searches. PS then again, that argument makes last double ambiguous, because last on an iterator can be sluggish (meticulously consume an iterator) or instant (on a well-behaved implementation of DoubleEndedIterator).

[matklad]

Correctness is more important than performance, and the performance ambiguity is an a safe direction (operation is faster than it might seem)

[jmlMetaswitch]

Can we also get pop forms that remove the entry at the same time? (I think that's probably better than take or other synonyms, especially as BTreeSet has pop_last.) They are particularly useful in algorithms that repeatedly process the max/min and may add entries during that processing (e.g A*). I think that suggests (from the above) max_key_value, max_entry, pop_max_key_value and the equivalent for min.

[ssomers]

I didn't add those back then because I thought they were intended to be used through the entry API. But using that in practice seems more complicated than I would want. There's no entry concept in BTreeSet, so pop_X seemed the only option there.

I wouldn't start mixing the naming scheme though. First/last or min/max (or something else) all the way.

I don't remember any discussion on whether it should be pop or take (or poll, anyone?) but there are lots of similar pops in Rust's standard library, the existing takes on sets work with a particular key, and the other takes seem to grab the entire contents.

[ssomers]

In the rust code base, there's only one use of this new API: last_entry. But anyone could have a feature(map_first_last), so not something I'd want to change without blessing.

By the way, that use would be slightly simpler if we had a last_key too. Should we? Is last_key trivial while pop_last would be worth while?

[ssomers]

And then there's the "_key_value" suffix. In a different line of development, get_key_value was added next to get (which returns only the value), and it obviously needed some different name. Plain last or max returning key and value, next to the mutable last_entry or max_entry, seemed overly terse and somewhat inconsistent, so it got the same "_key_value" suffix.

But pop_last or pop_max doesn't have that terseness nor inconsistency in my mind. On the contrary, pop_max_key_value makes me wonder if I could pop only a key or only a value. pop_max_key does sound better than pop_max, because it makes it clear what maximum we're talking about.

That means max_key_value sounds ambiguous to me now. What is the maximum of key,value pairs? Or maybe does it return the value of the max key? last_key_value doesn't raise that first question so you don't stray into the second question. max_key_with_value?

[pipehappy1]

randomly come across this. pop_first and pop_last are more appropriate than min/max since this is an iteration and an iteration comes with the first and ends with the last.

[ssomers]

@pipehappy1, I don't understand what you mean. Which "this" is an iteration?

Of course first and last correspond to the various forms of forward iteration on maps, but that doesn't imply first/last is any clearer than min/max.

I think both naming schemes are reasonable. Min/max when the caller can have a good notion of how keys are ordered, and really wants the minimum or maximum. As it stands, almost all members have an Ord bound, meaning the caller must indeed know that there is an intrinsic order on the key type, and since it's the only order around, min/max is rather clear. But many of methods don't need this bound, like BTreeMap::new and the methods discussed here. And funnily enough, the iterators that expose the order don't have this Ord bound, it's just documented in the methods ("sorted by key" or "in ascending order"). I don't think it was a conscious design decision.

Therefore, the first/last case is also reasonable, when the caller has no notion of key order and just wants to follow whatever order the container chooses, regardless of whether the container is a map or a vector (of pairs). But then it should not have the Ord bound.

[pipehappy1]

@ssomers That's quite clear and an insight. Both naming schemes get their reason. Thx

[ssomers]

Point made in internals: the fact that first/last_entry are not constant time is the real problem. The "twice" in the title of this issue is just peanuts, the "required amount of computation" matters more.

PS But if it's not feasible to reduce the required amount of computation, the "twice" are still tasty peanuts.