Conversation

libdivide lets you set up compiler-like optimizations for division when the number you’re dividing by isn’t known at compile time. It’s amazing that it makes such a big difference for a malloc! //

@ridiculous_fish

Quote Tweet

Daniel Micay

@DanielMicay

Aug 18, 2019

I love libdivide. Moving to libdivide-2.0 in hardened_malloc is an easy win. 16 byte malloc microbenchmark on Broadwell-E: Hardware division: 1s libdivide-1.1: 0.74s libdivide-2.0: 0.71s In a lightweight build: Hardware division: 1s libdivide-1.1: 0.62s libdivide-2.0: 0.59s

Show this thread

Replying to

and

Delta will also likely grow a bit as I optimize since there's a lot of low-hanging fruit. Using division to find out-of-line metadata for slab allocations in the dedicated metadata region is fundamental to the design. Can't use only powers of 2 since it'd waste lots of memory.

Replying to

and

Fine-grained size classes are also an important part of hardening since each slab allocation size class has an isolated memory region. Using only power of 2 sizes and slab sizes isn't something that's on the table so libdivide ended up being crucial. I'd have had to reinvent it.

Replying to

and

I expanded github.com/GrapheneOS/har with a description of how a slab allocation gets freed. There's a division to find the arena if arenas are enabled and then another to find the size class, but these are both division by a compile-time constant so those don't need libdivide.

Replying to

and

Use case for libdivide is to find the index of a slab within the size class region and the slot index within the slab, since slab size and size vary at runtime. If I really wanted, I could generate the libdivide divisors with a script at compile-time, but compilers can't do this.

Replying to

and

Since I know all the sizes that I need to deal with, I had started down the path of manually optimizing each case... which was going to be a lot of pain before finding libdivide. There are not many libraries that do exactly what I want them to do so incredibly well. It's great.

10:16 AM · Aug 19, 2019Twitter Web App

Replying to

and

Very cool!