Add smalloc to mimalloc-bench

[mjp41]

There is an allocator written in Rust called smalloc that looks interesting:
https://github.com/zooko/smalloc

We should add it to mimalloc-bench.

[mjp41]

@zooko could you add slightly more build instructions to your repo, it didn't build directly with my Rust installation. I think it needs nightly rather than a stable build? Is that essential?

[mjp41]

Running it locally, it is pretty reasonable performance, and does very well on redis. I think its Realloc Growers optimisation might improve its performance there.

[zooko]

Hi! Sorry I didn't see your message until just now. How did you discover smalloc?! I haven't announced it yet. :-) I think the current version is pretty stable/correct, but I'm still experimenting with optimizations and extensions (like a couple of hours ago I added alloc_zeroed for the first time, and I'm experimenting with a Windows HeapAlloc API interposition).

Yes, I've been using rustc nightly instead of stable, and I've been using a few nightly-only features. They are not essential though -- pretty simple things that would not be difficult to remove. The two that come to mind are: 1. profile-rustflags so you can pass flags like "-C target-cpu=native" depending on the build profile. You can remove that just by not passing such flags. 2. #![feature(likely_unlikely)] for branch prediction hints.

Here is a stupid patch just to demonstrate that it is easy to make it buildable on stable. This patch makes it pass its own tests with stable rust:

diff --git a/Cargo.toml b/Cargo.toml
index f615953..9a78527 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,5 +1,3 @@
-cargo-features = ["profile-rustflags"]
-
 [workspace]
 members = ["smalloc", "smalloc-ffi", "hellosmalloc", "bench", "find_max_vm_addresses_reservable"]
 default-members = ["smalloc"]
@@ -25,7 +23,6 @@ codegen-units = 1
 lto = "fat"
 debug-assertions = false
 overflow-checks = false
-rustflags = ["-C", "target-cpu=native"]
 
 [profile.profiling]
 inherits = "release"
@@ -33,4 +30,3 @@ debug = 2
 opt-level = 2
 lto = "thin"
 codegen-units = 16
-rustflags = ["-C", "force-frame-pointers=yes", "-C", "target-cpu=native"]
diff --git a/bench/src/bin/bench.rs b/bench/src/bin/bench.rs
index db0352a..ac9dc64 100644
--- a/bench/src/bin/bench.rs
+++ b/bench/src/bin/bench.rs
@@ -1,4 +1,4 @@
-#![feature(rustc_private)]
+//xx!![feature(rustc_private)]
 #![allow(unused_imports)]
 
 use bench::{st_bench, mt_bench, compare_st_bench, compare_mt_bench, compare_fh_bench, multithread_hotspot, multithread_free_hotspot, compare_hs_bench};
diff --git a/devutils/src/lib.rs b/devutils/src/lib.rs
index 5026a49..ca96471 100644
--- a/devutils/src/lib.rs
+++ b/devutils/src/lib.rs
@@ -1,8 +1,16 @@
-#![feature(likely_unlikely)]
+//xxx#![feature(likely_unlikely)]
 // This file contains things used by both tests and benchmarks.
 
 // xxx consider removing some of these "helper"/utility functions in favor of standard/idiomatic things...
 
+const fn unlikely(b: bool) -> bool {
+    b
+}
+
+const fn likely(b: bool) -> bool {
+    b
+}
+
 const BYTES1: [u8; 8] = [1, 2, 4, 3, 5, 6, 7, 8];
 const BYTES2: [u8; 8] = [9, 8, 7, 6, 5, 4, 3, 2];
 const BYTES3: [u8; 8] = [0xA, 0xB, 0xC, 0xD, 0xE, 0xF, 0x10, 0x11];
@@ -12,7 +20,7 @@ const BYTES5: [u8; 8] = [0xFE, 0xFD, 0xFC, 0xFB, 0xFA, 0xF9, 0xF8, 0xF7];
 
 use std::alloc::GlobalAlloc;
 use std::cmp::min;
-use std::hint::unlikely;
+//xxxuse std::hint::unlikely;
 use std::thread;
 use std::alloc::Layout;
 
@@ -421,7 +429,7 @@ impl std::hash::BuildHasher for WyHashBuilder {
     }
 }
 
-use std::hint::likely;
+//xxxuse std::hint::likely;
 use wyrand::WyRand;
 impl TestState {
     pub fn new(iters: u64, seed: u64) -> Self {
diff --git a/smalloc/src/lib.rs b/smalloc/src/lib.rs
index 2703dc0..8896469 100644
--- a/smalloc/src/lib.rs
+++ b/smalloc/src/lib.rs
@@ -1,4 +1,12 @@
-#![feature(likely_unlikely)]
+//xxx #![feature(likely_unlikely)]
+
+const fn unlikely(b: bool) -> bool {
+    b
+}
+
+const fn likely(b: bool) -> bool {
+    b
+}
 
 // Table of contents of this file:
 //
@@ -552,7 +560,7 @@ const fn reqali_to_sc(siz: usize, ali: usize) -> u8 {
 #[cfg(test)]
 mod tests;
 
-use core::hint::{likely, unlikely};
+//xxxuse core::hint::{likely, unlikely};
 use core::sync::atomic::{AtomicU16, AtomicU64, AtomicUsize, AtomicBool};
 use core::sync::atomic::Ordering::{Acquire, Relaxed, Release};
 use core::cell::{Cell, UnsafeCell};

Also, I just ran its own bench tool and it seems to indicate it is faster (still being built with nightly rustc) with this patch than without? 🧐 I guess I should investigate that.

Sorry about the incorrect build instructions and crate name. Someone else also reported that . I'll fix it right away.

By the way, I've already been using mimalloc-bench to benchmark smalloc! Here's the instructions and a link to my fork of mimalloc-bench: https://github.com/zooko/smalloc/blob/main/bench/README.md#mimalloc-bench Thanks for contributing to this great benchmarking tool!

By the way, I stopped using the redis benchmarks to evaluate smalloc because it was failing tests due to "memory usage" issues. One of them was that the redis benchmarks instructed redis to reduce the memory it used, and then expected a certain number of redis clients to get evicted, and it failed that test when using smalloc. I didn't figure out how it is measuring "memory usage", and then at some point while investigating I found out that redis is apparently no longer open source?

If you happen to know how the redis tests measure memory usage, I'd be curious.

[zooko]

Also, I just ran its own bench tool and it seems to indicate it is faster (still being built with nightly rustc) with this patch than without? 🧐 I guess I should investigate that.

Update, I experimented with smalloc's builtin benchmarks, and it is, as I would expect, usually slightly faster with "-C target-cpu=native", and usually slightly faster with the likely/unlikely hints. One detail (which might have been what made me momentarily think it was slower) is that the likely/unlikely hints tell it to predict the branch that a slot has been allocated before, but some of the builtin benchmarks are testing the case of all allocations and no deallocations, in which case every slot has never been touched before. As I would expect the likely/unlikely hints usually make those benchmarks slightly slower.

[zooko]

Oh, I see that you work on snmalloc! Thank you for that. It seems like a real contribution to humanity's toolchest. I've enjoyed reading about security hardening ideas and enjoyed most of all reading about the Cheri integration work.

[mjp41]

How did you discover smalloc?! I haven't announced it yet. :-)

An issue or PR mentioned snmalloc, so I noticed that. I was very interested in the realloc grow ideas. That seems like something many allocators could pick up heuristically.

Oh, I see that you work on snmalloc! Thank you for that. It seems like a real contribution to humanity's toolchest. I've enjoyed reading about security hardening ideas and enjoyed most of all reading about the Cheri integration work.

Thanks

I was wondering about the speed up you observed in Rust. How much can be attributed to being in Rust, so enabling inlining of the allocator code, versus the particular design.

I also notice in my experiments on Intel the atomics were harming your performance, but I imagine that on Apple's silicon those costs would be much lower.

I'm experimenting with a Windows HeapAlloc API interposition

Cool. That is something I have been experimenting with when I get time: microsoft/snmalloc#775

[zooko]

An issue or PR mentioned snmalloc, so I noticed that. I was very interested in the realloc grow ideas. That seems like something many allocators could pick up heuristically.

Yes, the realloc grower idea seems like it could be easily added to any allocator, if desired. But I haven't actually found a reproducible benchmark that shows that it helps. I've actually removed it because I can't demonstrate that it helps, and then put it back because it makes sense and I guess there must be some app out there that it would help, at least twice. 😂

I was wondering about the speed up you observed in Rust. How much can be attributed to being in Rust, so enabling inlining of the allocator code, versus the particular design.

Great question. I don't know. Also, I haven't looked into the implementation of the Rust wrapper code for snmalloc, rpmalloc or mimalloc that are used in these benchmarks. It's possible those Rust wrappers are slowing things down unnecessarily.

I also notice in my experiments on Intel the atomics were harming your performance,

Can you tell me more of what you noticed? The main thing I've noticed is that when there is heavy multithreading contention, the compare-and-swap instructions show up as by far the hottest parts, using perf on linux/x86-64. Have you noticed anything else about the way smalloc uses atomics, or do you have any ideas about how to optimize any of that? Thanks!

but I imagine that on Apple's silicon those costs would be much lower.

This Apple M4 Max chip is truly a thing of beauty.

I'm experimenting with a Windows HeapAlloc API interposition

Cool. That is something I have been experimenting with when I get time: microsoft/snmalloc#775

Oh! This looks potentially very helpful to my Windows support experimentation, thank you.

[mjp41]

An issue or PR mentioned snmalloc, so I noticed that. I was very interested in the realloc grow ideas. That seems like something many allocators could pick up heuristically.

Yes, the realloc grower idea seems like it could be easily added to any allocator, if desired. But I haven't actually found a reproducible benchmark that shows that it helps. I've actually removed it because I can't demonstrate that it helps, and then put it back because it makes sense and I guess there must be some app out there that it would help, at least twice. 😂

I tried it in snmalloc, but I couldn't find a benchmark that it actually sped up. I had initially thought it had, but I hadn't run enough tests to overcome my noisy dev machine, when I moved to a less noisy machine. It didn't seem to matter.

I also notice in my experiments on Intel the atomics were harming your performance,

Can you tell me more of what you noticed? The main thing I've noticed is that when there is heavy multithreading contention, the compare-and-swap instructions show up as by far the hottest parts, using perf on linux/x86-64. Have you noticed anything else about the way smalloc uses atomics, or do you have any ideas about how to optimize any of that? Thanks!

I probably overstated my observation. I noticed the performance profile was similar to when I experimenting with adding a single atomic increment on the fast path of snmalloc, which for allocation intensive benchmark regress perf quite a bit. I didn't actually check the profiles. I think getting a fast path that doesn't require any atomic increment/exchange/CAS is pretty important even in a sequential case to get really good perf.

I think the boundary between what doesn't require atomics and what does it really important for throughput/footprint tradeoff. I think both snmalloc and mimalloc initially pushed them very far from the fast path. In snmalloc, I have moved things around a bit to allow more sharing between threads and reducing the size required per thread. Based on @daanx's recent comments on mimalloc, I think he is also fine tuning that trade-off.

I am afraid I haven't studied your design enough, yet, to provide more than this superficial feedback.

[zooko]

No, I really appreciate the feedback based on your experience, even though I don't think smalloc can easily take advantage of it. smalloc's overriding focus on simplicity means that the fast path and the other paths all share the same code and data structures, and eat the runtime cost of an atomic CAS on every alloc or free.

What I find most surprising and delightful about smalloc is that it seems to have performance that is competitive in some cases with the best, most sophisticated allocators (snmalloc, mimalloc, and rpmalloc) while being so damn simple! The complete allocation function—handling all allocation cases—is currently about 150 lines of Rust code: Smalloc::inner_alloc(). The "How It Works" section of the README, which is pretty thorough, is about 3000 words.

The data structures are quite minimal:

• the base pointer (i.e. basically the return value from mmap),
• one singly-linked intrusive free list per slab, and
• one thread-local word per thread.

There are no other bits of memory that smalloc ever reads or writes!

(Well, okay, for completeness, there are two other pieces of information, but they are both embedded into the linked list so you don't need to read or write any other memory locations to access them. They are an update counter (embedded into the free list head) and a 1-bit flag about the next free list entry (embedded into each free list entry). Annnnnnd there's a global static count of threads, which does the same thing as the Rust standard ThreadId and could perhaps be replaced with the Rust standard ThreadId.)

Your comment makes me wonder if there would be any way to make smalloc a little bit more complex to enable a faster fast path. I kind of doubt there's much useful design space laying between smalloc minimalism and snmalloc et al sophistication.

By the way, this conversation makes me want to explore experiments in eliminating that one thread-local word per thread, and that ThreadId-like global static. Then the smalloc data structures would truly be just about the most minimal thing possible. :-)