`BTreeMap::split_off` has suboptimal asymptotic performance
メンテナーはふだん 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 の本文から書いたものです。
説明
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
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートあり
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
rust-lang/rust のほかの issue
-
Remove unnecessary parentheses when suggesting to remove '&' from a pattern対応中かも @BartSimpson001 が 1 日前に担当しました。 オープンA-diagnostics D-invalid-suggestion T-compiler
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
メンテナーはふだん 1 日以内に返信
-
Windows `File::set_permissions` silently does nothing when clearing `readonly` leaves `FileAttributes == 0`対応中かも @ChrisDenton が 11 日前に担当しました。 オープンA-filesystem C-bug O-windows T-libs
難易度 2/5 1〜3時間 初心者へのやさしさ 62/100
メンテナーはふだん 1 日以内に返信
-
A-run-make relnotes relnotes-needs-review relnotes-tracking-issue T-lang T-libs
難易度 1/5 1時間未満 初心者へのやさしさ 72/100
メンテナーはふだん 1 日以内に返信
-
A-LLVM O-Arm O-UEFI O-x86_64 relnotes relnotes-needs-review relnotes-tracking-issue T-compiler
難易度 1/5 1時間未満 初心者へのやさしさ 72/100
rust-lang/rust#165504 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
relnotes relnotes-tracking-issue T-libs
難易度 1/5 1時間未満 初心者へのやさしさ 72/100
メンテナーはふだん 1 日以内に返信
似ている issue
-
難易度 1/5 1時間未満 初心者へのやさしさ 88/100
bytecodealliance/wrpc#1785 ·
メンテナーはふだん 1 日以内に返信
-
2 advisory ignore entries no longer match anything (`quick-xml` already patched in `Cargo.lock`)オープン
難易度 1/5 1時間未満 初心者へのやさしさ 85/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
longbridge/nsh#2758 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 84/100
antithesishq/bombadil#473 ·
メンテナーはふだん 2 日以内に返信
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
libracoder/kiri#669 ·
メンテナーはふだん 1 日以内に返信