2026-09-26
PR available at rust-lang/rust#161791 - Merged 26th Sept. 2026.
My first PR merged into the Rust compiler, and my first open-source contribution ever, was rust#155132. It added a help message to the --target option that suggests the closest matching built-in target when the one provided isn’t found. Once it merged, I started looking for my next issue: something doable, but with enough new ground to learn from. That’s how I found #161375, which pointed out that creating and dropping an empty BTreeMap isn’t free: the compiled code still executes instructions when it could do nothing at all.
In the issue the reporter linked a godbolt showing a small code snippet of this issue:
pub fn drop_btree() {
std::collections::BTreeMap::<(), ()>::new();
}
BTreeMap’s Drop impl turns the map into an IntoIter and then drops that, which walks the tree with dying_next to free every node:
fn drop(&mut self) {
drop(unsafe { ptr::read(self) }.into_iter())
}
But when there is an empty map and thus no nodes, the code still builds out this iterator and calls dying_next. Godbolt shows on the right what this compiles to in x86-64 assembly:
; godbolt, rustc 1.56 (after the regression)
example[7a9efb3d937417e2]::drop_btree:
push r14
push rbx
sub rsp, 104
mov qword ptr [rsp + 32], 0
mov qword ptr [rsp + 64], 0
mov qword ptr [rsp + 96], 0
lea rdi, [rsp + 8]
lea rsi, [rsp + 32]
call <alloc[c00562a4ff4db933]::collections::btree::map::IntoIter<(), ()>>::dying_next
cmp qword ptr [rsp + 8], 0
je .LBB0_3
lea rbx, [rsp + 8]
lea r14, [rsp + 32]
.LBB0_2:
mov rdi, rbx
mov rsi, r14
call <alloc[c00562a4ff4db933]::collections::btree::map::IntoIter<(), ()>>::dying_next
cmp qword ptr [rsp + 8], 0
jne .LBB0_2
.LBB0_3:
add rsp, 104
pop rbx
pop r14
ret
but a simple ret was expected, so we are executing 43 extra instructions (including the call into dying_next not shown above).
Using godbolt’s version comparison, I stepped back through compiler versions until the drop compiled to nothing, and narrowed it down to commit 7b28036 which landed in 1.56.0.
Before that commit, Drop only did work if let Some(root) = self.root.take(), so an empty map returned straight away. The commit routed everything through IntoIter instead, which dropped that early-out. My fix effectively puts it back.
If the map has no root then we have nothing to walk, so only the allocator needs dropping. The allocator field is ManuallyDrop so the compiler never drops it automatically. The code has to do it exactly once.
fn drop(&mut self) {
if self.root.is_some() {
// SAFETY: `self` is not used after this and none of its fields are dropped again:
// `alloc` is `ManuallyDrop` and `root` has no drop glue.
drop(unsafe { ptr::read(self) }.into_iter())
} else {
// SAFETY: With no root there are no nodes to free, so only the allocator needs
// dropping. `self` is not used after this, and `alloc` is dropped only here.
unsafe { ManuallyDrop::drop(&mut self.alloc) }
}
}
My first codegen test checked that dying_next no longer appears in drop_btree:
// CHECK-LABEL: @drop_btree
// CHECK-NOT: dying_next
// CHECK: ret void
The reviewer suggested checking for calls to dealloc instead since this test would silently stop working if dying_next were ever renamed. So I made the change and then put the old Drop impl back and ran it:
$ git checkout upstream/main -- library/alloc/src/collections/btree/map.rs # Old Drop impl
$ ./x test tests/codegen-llvm/btree-empty-drop.rs # CHECK-NOT: dealloc
running 1 tests
.
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 1247 filtered out
This new codegen passed on the old code, so it wasn’t actually testing anything. The generated LLVM IR explained why: the old drop_btree calls dying_next out of line, and every __rust_dealloc call lives inside that separate function. FileCheck only looks between the @drop_btree label and the first ret void, so it never saw a dealloc.
So I switched to checking that the function body is nothing but a return:
// CHECK-LABEL: @drop_btree(
// CHECK-NEXT: {{.*}}:
// CHECK-NEXT: ret void
{{.*}}: matches the entry block’s label, whose name comes from inlined mangled function names and changes between builds, and the next line must be ret void. Against the old code it now fails, pointing straight at the stack allocation:
$ ./x test tests/codegen-llvm/btree-empty-drop.rs # CHECK-NEXT: ret void
[codegen] tests/codegen-llvm/btree-empty-drop.rs ... F
btree-empty-drop.rs:11:16: error: CHECK-NEXT: is not on the line after the previous match
// CHECK-NEXT: ret void
^
btree-empty-drop.ll:454:1: note: non-matching line after previous match is here
%_2.i.i.i.i = alloca [24 x i8], align 8
^
test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 1247 filtered out
And with the fix back in place, it passes:
$ git checkout HEAD -- library/alloc/src/collections/btree/map.rs # with the fix
$ ./x test tests/codegen-llvm/btree-empty-drop.rs
running 1 tests
.
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 1247 filtered out
This now doesn’t depend on any function name, which was the reviewer’s original concern with the dying_next check-not.
After I pushed the fix, the reviewer asked why this was needed at all - they expected this to be inlined and reduced to ret void. So to find out, I restored the old Drop impl and wrote a simple x.rs test:
// x.rs
use std::collections::BTreeMap;
#[no_mangle]
pub fn drop_btree() {
let _ = BTreeMap::<(), ()>::new();
}
Inlining is when the compiler copies a function’s body into its caller instead of calling it. Once dying_next is inside drop_btree, LLVM can see that on an empty map it does nothing, and delete it. LLVM gives each function an estimated cost and only inlines it if that cost is under a threshold, and -C remark=inline prints each of those decisions:
$ git checkout upstream/main -- library/alloc/src/collections/btree/map.rs # Bringing back the Drop impl
$ R=build/x86_64-unknown-linux-gnu/stage1/bin/rustc
$ $R -Copt-level=3 --crate-type=lib --emit=asm -C debuginfo=1 -C remark=inline -o /dev/null x.rs
note: .../library/alloc/src/collections/btree/map.rs:1921:45 inline (missed): '...IntoIter...dying_next...'
not inlined into '...IntoIter...drop...DropGuard...' because too costly to inline (cost=850, threshold=250)
So the answer is that dying_next costs 850 against a threshold of 250 and so it never gets inlined. Now we can raise this threshold to see if it does get inlined:
$ $R -Copt-level=3 --crate-type=lib --emit=llvm-ir -C llvm-args=-inline-threshold=2000 -o old-x-2000.ll x.rs
Opening old-x-2000.ll and searching for drop_btree shows the whole function:
; old-x-2000.ll
define void @drop_btree() unnamed_addr #0 personality ptr @rust_eh_personality !guid !4 {
start:
ret void
}
Same old code, and it’s just ret void. So the code was always correct, it was just too big for LLVM to look inside.
The reviewer then asked whether #[inline(always)] would get around the need for my change - this is an attribute that inlines regardless of the cost, so I tried it on dying_next:
impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> {
/// Core of a `next` method returning a dying KV handle,
/// invalidated by further calls to this function and some others.
#[inline(always)] // ADDED
fn dying_next(
&mut self,
) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
$ ./x build library --stage 1
$ ./x test tests/codegen-llvm/btree-empty-drop.rs
running 1 tests
.
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 1247 filtered out
It works, with no root check. But “always” means always, and dying_next isn’t only called when dropping. Looking through map.rs, IntoIter::next calls it too, so to see what that costs, I wrote a function that just iterates a map:
// sum.rs
use std::collections::BTreeMap;
#[no_mangle]
pub fn sum(m: BTreeMap<u64, u64>) -> u64 {
m.into_iter().map(|(k, v)| k + v).sum()
}
and compiled it with and without the attribute.
$ $R -Copt-level=3 --crate-type=lib --emit=llvm-ir -o sum-always.ll sum.rs # with inline(always)
$ ./x build library --stage 1 # after removing it
$ $R -Copt-level=3 --crate-type=lib --emit=llvm-ir -o sum-default.ll sum.rs
This outputs two LLVM IR files. Each function in the IR runs from its define line to a closing }, so counting the lines of @sum gives its size:
sum-default.ll : 165
sum-always.ll : 429
sum goes from 165 to 429 lines of IR. That’s a lot of extra code in every loop over a map which happens far more often than an empty drop case. The root check only touches drop, so I kept it as it’s isolated to one function and has no impact elsewhere.
Bigger code is only a problem if it costs something, so I checked whether it at least made sum faster. Timing it was too noisy to tell the two apart, so I counted instructions instead with cachegrind, which gives the exact number of instructions executed, the same every run:
// count.rs
use std::collections::BTreeMap;
use std::hint::black_box;
// from sum.rs
fn sum(m: BTreeMap<u64, u64>) -> u64 {
m.into_iter().map(|(k, v)| k + v).sum()
}
fn main() {
let n: u64 = std::env::args().nth(1).unwrap().parse().unwrap();
let m: BTreeMap<u64, u64> = (0..n).map(|i| (i, i)).collect();
for _ in 0..100_000 {
black_box(sum(black_box(m.clone())));
}
}
$ valgrind --tool=cachegrind --cache-sim=yes --cachegrind-out-file=/dev/null ./count-always 1000
==3149065== I refs: 8,973,644,786
==3149065== I1 misses: 1,806
$ valgrind --tool=cachegrind --cache-sim=yes --cachegrind-out-file=/dev/null ./count-default 1000
==3149243== I refs: 8,971,064,729
==3149243== I1 misses: 1,809
With inline(always), each call executed about 26 more instructions (+0.03%), with no change in instruction cache misses. So it made sum 2.6× bigger for nothing. That extra code would land in every loop over a map, just to save a few instructions when dropping an empty one. The root check only touches drop, so I kept it.
For the resulting x86_64 assembly, dropping an empty map went from 43 executed instructions to a single ret, which will disappear once inlined.
; stage1 rustc, with the fix
example::drop_btree::h605893958e2aa49c:
ret