Skip to content

Max & Min on BTreeMap are unexpectedly slow #59947

Closed
@jeremycochoy

Description

@jeremycochoy

Hello,

The use of iterator's max and min function do not seams to take advantage of the specific ordering of BTreeMap and looks like it is browsing the whole container.
Although it is still possible to have fast access to minimum and maximum element by using first and first_back, this is not semantically explicite and you can expect that developers may not know the subtilities regarding BTreeMap's implementation and could assume the complexity should be the same.

Here is the benchmark result

running 4 tests
test bench_first ... bench:           9 ns/iter (+/- 0)
test bench_last  ... bench:           8 ns/iter (+/- 0)
test bench_max   ... bench:       3,603 ns/iter (+/- 536)
test bench_min   ... bench:       3,755 ns/iter (+/- 328)

and here is the benchmark code:

#![feature(test)]

extern crate test;
#[macro_use]
extern crate lazy_static;

use test::Bencher;
use std::collections::BTreeMap;

lazy_static! {
    static ref MAP: BTreeMap<i32, i32> = {
        let mut map = BTreeMap::new();

        for i in 0..1000 {map.insert(i, i);}

        map
    };
}
#[bench]
fn bench_max(b: &mut Bencher) {

    b.iter(|| {MAP.iter().max()});
}

#[bench]
fn bench_first(b: &mut Bencher) {

    b.iter(|| {MAP.iter().next()});
}

#[bench]
fn bench_last(b: &mut Bencher) {
    b.iter(|| {MAP.iter().next_back()});
}

#[bench]
fn bench_min(b: &mut Bencher) {
    b.iter(|| {MAP.iter().min()});
}

I don't know the details of the trait implementation, but I think it would be very nice for the community if you can make std::collections::btree_map::Iter take advantage of the ordering. :)

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-collectionsArea: `std::collections`I-slowIssue: Problems and improvements with respect to performance of generated code.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions