`BTreeMap::split_off` has suboptimal asymptotic performance

Abierto
#165,975 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
4/5
Tiempo estimado
3-5 días
Aptitud para principiantes
35/100
Tipo de issue
Refactorización
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
rust
Área
performance

Línea de trabajo

The cost is in calc_split_length in library/alloc/src/collections/btree/split.rs, which walks one of the two trees to count entries. Start by reading that function and the split path, then run the repro program from the issue at n = 1,000,000 for both at = n/2 and at = n - 10. Done means a middle split no longer grows with the larger half, so its timings track the tail-split numbers.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

A-btree C-optimization I-slow T-libs

Splitting a BTreeMap<u64, u64> in the middle takes about 4.5 us at 100k entries, 130 to 160 us at 1M and 1.4 to 1.9 ms at 10M. Splitting ten entries before the end stays around 1 us at every size.

The split only touches one path from the root to a leaf. What costs is calc_split_length in library/alloc/src/collections/btree/split.rs, which afterwards walks one of the two trees to count its entries. It picks the lower tree, so a small tail is cheap, but in the middle both halves are equally high and every node of one half gets visited.

Repro:

use std::collections::BTreeMap;
use std::hint::black_box;
use std::time::Instant;

fn split_micros(n: u64, at: u64) -> f64 {
    let mut best = f64::MAX;
    for _ in 0..5 {
        let mut map: BTreeMap<u64, u64> = (0..n).map(|i| (i, i)).collect();
        let t = Instant::now();
        let tail = black_box(map.split_off(black_box(&at)));
        best = best.min(t.elapsed().as_secs_f64());
        assert_eq!(tail.len() as u64, n - at);
    }
    best * 1e6
}

fn main() {
    println!("{:>10} {:>16} {:>18}", "entries", "at n/2 (us)", "at n - 10 (us)");
    for n in [10_000, 100_000, 1_000_000, 10_000_000] {
        println!("{n:>10} {:>16.2} {:>18.2}", split_micros(n, n / 2), split_micros(n, n - 10));
    }
}
Lenguaje dominante
Rust
Estrellas
122k
Forks
16.7k
Merge medio
2 d 16 h
PR fusionados (30 d)
515

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de rust-lang/rust

Todos los issues de rust-lang/rust

Issues similares

Más issues de Rust

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.