`BTreeMap::split_off` has suboptimal asymptotic performance

オープン
#165,975 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
35/100
issue の種類
リファクタリング
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
rust
領域
performance

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

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));
    }
}
主要言語
Rust
スター
122k
フォーク
16.7k
平均マージ
2日 16時間
マージ済み PR(30日)
515

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

rust-lang/rust のほかの issue

rust-lang/rust の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。