Why is BTreeMap consuming much memory per InternalNode?

help
1

Some oss-fuzz issue shows that the target is running out of memory in part because of the use of BTreeMap

The report contains

331482048 byte(s) (21%) in 16728 allocation(s)
    #0 0x556c5fb3048e in malloc /rustc/llvm/src/llvm-project/compiler-rt/lib/asan/asan_malloc_linux.cpp:69:3
    #1 0x556c5fcbade9 in alloc::alloc::alloc::h5269ce07bb10c902 /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/alloc.rs:95:14
    #2 0x556c5fcbade9 in alloc::alloc::Global::alloc_impl::h77c01dfca3f18465 /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/alloc.rs:177:73
    #3 0x556c5fcbade9 in _$LT$alloc..alloc..Global$u20$as$u20$core..alloc..Allocator$GT$::allocate::hfa51f6d5533f308a /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/alloc.rs:237:9
    #4 0x556c5fcbade9 in alloc::boxed::Box$LT$T$C$A$GT$::try_new_uninit_in::h993a1d521e98ccbe /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/boxed.rs:492:19
    #5 0x556c5fcbade9 in alloc::boxed::Box$LT$T$C$A$GT$::new_uninit_in::h742bf80ef83b0a4e /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/boxed.rs:456:15
    #6 0x556c5fcbade9 in alloc::collections::btree::node::LeafNode$LT$K$C$V$GT$::new::h3e371920f9f6162a /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/collections/btree/node.rs:83:28
    #7 0x556c5fcbade9 in alloc::collections::btree::node::Handle$LT$alloc..collections..btree..node..NodeRef$LT$alloc..collections..btree..node..marker..Mut$C$K$C$V$C$alloc..collections..btree..node..marker..Leaf$GT$$C$alloc..collections..btree..node..marker..KV$GT$::split::hf207001a8e092812 /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/collections/btree/node.rs:1138:28
    #8 0x556c5fcbce87 in alloc::collections::btree::node::Handle$LT$alloc..collections..btree..node..NodeRef$LT$alloc..collections..btree..node..marker..Mut$C$K$C$V$C$alloc..collections..btree..node..marker..Leaf$GT$$C$alloc..collections..btree..node..marker..Edge$GT$::insert::h70813019c4cb31f0 /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/collections/btree/node.rs:887:30
    #9 0x556c5fcbbee2 in alloc::collections::btree::node::Handle$LT$alloc..collections..btree..node..NodeRef$LT$alloc..collections..btree..node..marker..Mut$C$K$C$V$C$alloc..collections..btree..node..marker..Leaf$GT$$C$alloc..collections..btree..node..marker..Edge$GT$::insert_recursing::h63a282aee479afcf /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/collections/btree/node.rs:980:42
    #10 0x556c5fcb20bf in alloc::collections::btree::map::entry::VacantEntry$LT$K$C$V$C$A$GT$::insert::ha982e045fe40fb84 /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/collections/btree/map/entry.rs:361:35
    #11 0x556c5fe2419a in alloc::collections::btree::map::entry::Entry$LT$K$C$V$C$A$GT$::or_insert_with::h3876bc2a76fdf2a2 /rustc/c8e6a9e8b6251bbc8276cb78cabe1998deecbed7/library/alloc/src/collections/btree/map/entry.rs:187:30

That is 19816 bytes per InternalNode from rust/node.rs at 338cfd3cce448f576dbac48438018fc65cef8982 · rust-lang/rust · GitHub

The size of the structure used in this BTreeMap does not seem to impact much the InternalNode size

Dividing the size by approximately 2, It went down to 19288 bytes per InternalNode

2

It looks like my BTreeMap internal node contains 11 elements at one time...

3

Remember that BTreeMap isn't a classic binary tree. It holds many values per internal node -- that's why it can be much faster and has better memory locality than an AVL or Red-Black tree.

What's the per-item memory use of your maps? Do you have lots of tiny maps?

2 Likes
4

It does -- in the same node.rs, notice that B = 6, and CAPACITY = 2 * B - 1.

1 Like
5

Are you calculating the total memory use and dividing by the number of InternalNodes?

Most of the nodes and most of the keys are in LeafNodes rather than InternalNodes

2 Likes
6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.