real world test

[Licenser]

Heya it's friday so I had some time to toy around. For giggles I replaced snmalloc with smalloc in a allocation heavy service - largely parsing grcp data with prost (yay the allocations ...)

The results were not great. Compared to snmalloc time spend in the allocator and allocated memory went up 10 fold.

over all change:

top cpu usage (snmalloc left, smalloc right)

and graphic representation of that snmallco:

and smalloc:

[Licenser]

update after some more time running:

It's interesting that memory goes down but cpu keeps going up massively

[zooko]

Thank you so much for doing this and posting the results! How can I reproduce this experiment?

[Licenser]

I think the simplest thing is a service parsing metrics using the tremor-otelapi going over it and just doing some simple allocations after that (might not even be needed) should the main load seems to be in the parsing of the protobuf structure.

the Otel demo will probably do the trick on generating enough load to measure

[zooko]

Hm, okay I looked at https://github.com/tremor-rs/tremor-otelapis and https://opentelemetry.io/docs/demo/ and I don't immediately see how to set up this experiment that you ran. Could you show me a series of command-lines that do it?

[zooko]

I also didn't see any mention of benchmarks in either of those two repos that I could use.

[zooko]

Update: I found that https://github.com/tokio-rs/prost comes with benchmarks so I’ll try those.

[zooko]

Update: the benchmarks in https://github.com/tokio-rs/prost do not include allocations. :-)

GITCOMMIT: fb3994b0f3cdb0b95f86b331fcdf42a95ec35d3d
GITCLEANSTATUS: "Uncommitted changes"
CPUTYPE:                           AMD EPYC 9754 128-Core Processor
OSTYPE: linux-gnu
CPUCOUNT: 256

                                                        default           jemalloc          snmalloc          mimalloc          rpmalloc          smalloc
                                                    ----------------  ----------------  ----------------  ----------------  ----------------  ----------------
test                                        weight   time ms (diff%)   time ms (diff%)   time ms (diff%)   time ms (diff%)   time ms (diff%)   time ms (diff%)
----                                        ------  -------- -------  -------- -------  -------- -------  -------- -------  -------- -------  -------- -------
dataset/google_message1_proto2/encode          100      16.5 ( base)      16.7 (  +1%)      16.9 (  +2%)      15.9 (  -4%)      16.6 (   0%)      16.2 (  -2%)
dataset/google_message1_proto2/encoded_len     100       2.8 ( base)       2.8 (   0%)       2.8 (   0%)       2.8 (  -1%)       2.8 (   0%)       2.8 (  -1%)
dataset/google_message1_proto2/merge           100      26.7 ( base)      26.0 (  -3%)      25.7 (  -4%)      25.5 (  -5%)      28.1 (  +5%)      27.2 (  +2%)
dataset/google_message1_proto3/encode          100      13.1 ( base)      13.0 (   0%)      13.5 (  +3%)      13.3 (  +2%)      13.4 (  +2%)      13.2 (   0%)
dataset/google_message1_proto3/encoded_len     100       2.3 ( base)       2.2 (  -1%)       2.3 (   0%)       2.3 (  +1%)       2.3 (  +1%)       2.2 (  -1%)
dataset/google_message1_proto3/merge           100      20.2 ( base)      20.4 (  +1%)      20.6 (  +2%)      20.2 (   0%)      21.3 (  +5%)      20.4 (  +1%)
varint/large/decode                            100      52.6 ( base)      52.6 (   0%)      52.6 (   0%)      52.6 (   0%)      52.6 (   0%)      52.6 (   0%)
varint/large/encode                            100      65.6 ( base)      64.8 (  -1%)      65.5 (   0%)      64.9 (  -1%)      64.8 (  -1%)      64.8 (  -1%)
varint/large/encoded_len                       100       6.1 ( base)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.1 (  -1%)
varint/medium/decode                           100      30.0 ( base)      30.0 (   0%)      30.0 (   0%)      30.0 (   0%)      30.0 (   0%)      33.1 ( +10%)
varint/medium/encode                           100      32.5 ( base)      32.5 (   0%)      32.5 (   0%)      32.5 (   0%)      32.5 (   0%)      33.0 (  +2%)
varint/medium/encoded_len                      100       6.1 ( base)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.1 (  -1%)
varint/mixed/decode                            100      32.5 ( base)      32.5 (   0%)      32.5 (   0%)      32.5 (   0%)      32.5 (   0%)      34.1 (  +5%)
varint/mixed/encode                            100      35.7 ( base)      35.7 (   0%)      35.7 (   0%)      35.7 (   0%)      35.7 (   0%)      35.7 (   0%)
varint/mixed/encoded_len                       100       6.1 ( base)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.0 (  -2%)
varint/small/decode                            100      16.6 ( base)      16.5 (  -1%)      16.5 (   0%)      16.6 (   0%)      16.6 (   0%)      16.4 (  -1%)
varint/small/encode                            100       6.5 ( base)       6.6 (   0%)       6.5 (   0%)       6.5 (   0%)       6.5 (   0%)       6.5 (   0%)
varint/small/encoded_len                       100       6.1 ( base)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.1 (   0%)       6.0 (  -1%)
dataset/google_message2/encode                   1      71.6 ( base)      70.4 (  -2%)      71.2 (   0%)      70.2 (  -2%)      70.3 (  -2%)      69.6 (  -3%)
dataset/google_message2/encoded_len              1      10.3 ( base)      10.3 (   0%)      10.3 (   0%)      10.3 (   0%)      10.3 (   0%)      10.3 (   0%)
dataset/google_message2/merge                    1     128.3 ( base)     124.5 (  -3%)     128.1 (   0%)     106.5 ( -17%)     114.4 ( -11%)     117.3 (  -9%)
--------------------------------------------------------------------------------------------------------------------------------------------------------------
SUM                                                    588.3 ( base)     582.1 (  -1%)     587.8 (   0%)     562.7 (  -4%)     575.3 (  -2%)     579.6 (  -1%)
--------------------------------------------------------------------------------------------------------------------------------------------------------------

Tests compared: 21

Allocator       Weighted Sum vs Baseline
--------------- ------------ -----------
default                588.3    baseline
jemalloc               582.1     (  -1%)
snmalloc               587.8     (   0%)
mimalloc               562.7     (  -4%)
rpmalloc               575.3     (  -2%)
smalloc                579.6     (  -1%)

Graph saved to: ./benchmark-results/AMDEPYC9754128CoreProcessor.linuxgnu/prost.graph.svg

You can reproduce this with https://github.com/zooko/prost/blob/fb3994b0f3cdb0b95f86b331fcdf42a95ec35d3d/bench-allocators.sh

So, I'm back to square one on how to reproduce your experiment.

[Licenser]

Heya,

I've tried to synthetically reproduce this behavior today and[ I too have failed, for every test I put together with a synthetic consumer & producer smalloc and snmalloc are pretty much tied.

But there is a dragon hidden somewhere and I'm not sure where 😭

[zooko]

Huh! Okay, well there are only two ways that an allocator can affect performance. One is how long it takes to execute malloc, dealloc, and realloc, and the other is how well the allocator's arrangement of space aligns with the user code's use of that space over time.

The first one is what smalloc's micro-benchmarks measure and where smalloc really shines.

The second one is hard to analyze or optimize. The better those space and time patterns line up, the more cache and swap will help run your program efficiently. There could be some edge cases where those two things line up so badly that the process ends up waiting for the kernel to page memory in from swap space over and over. That's the only scenario I can think of, at the moment, where the difference of allocator could cause a 15X slowdown, and I think it would likely be rare, hard to reproduce, and may not even depend on which allocator.

One thing you can try is, if you're on linux put this before the command, and then after the command exits you'll get a nice printout of some statistics that might be a clue:

$ /usr/bin/time -f "Max RSS: %M KB\nMajor faults: %F\nMinor faults: %R" cargo build --quiet
Max RSS: 26624 KB
Major faults: 0
Minor faults: 6093

[mjp41]

I'd be really interested in a synthetic benchmark that highlights this. My thought is that it is typically where there is a very asymmetrical producer/consumer workload, where there is contention on the return slab so the batching of snmalloc works well.

I thought that xmalloc-test in mimalloc-bench would be the closest to representing tremors workload.

[zooko]

Me, too! In the smalloc self-test benchmarks there is a synthetic test of many threads free’ing allocations that require touching the same metadata as each other. Like all the smalloc self-test benchmarks, you can also run it against snmalloc, mimalloc, rpmalloc, and jemalloc. It’s the one named “fh” for “free hotspot”. To run it, pass the —thorough flag to smalloc’s bench executable from its bench package. Here’s the source code of it:

smalloc/bench/src/lib.rs

Line 121 in 76275af

/// This is to stress test the case that many threads are simultaneously free'ing slots in the same

[mjp41]

That benchmark is relatively short lived and the longer lived you make it the less contention you will have. The ones where snmalloc works really well are where there is a pipeline of allocation deallocation. We have one we used for some experiments:

https://github.com/microsoft/snmalloc/blob/main/src/test/perf/msgpass/msgpass.cc

This was designed to stretch that specific use case. We thought it might represent many pipelines for processing data (in a similar way to Tremor). Perhaps you can get Claude to rewrite it into Rust?

We had intended to add this to mimalloc-bench, but I can't remember where @nwf got to on that.

[zooko]

That benchmark is relatively short lived and the longer lived you make it the less contention you will have. The ones where snmalloc works really well are where there is a pipeline of allocation deallocation. We have one we used for some experiments:

Hm, I'm not sure I follow. The "free hotspot" benchmark I linked to above exercises a certain "worst-case scenario" from the perspective of smalloc, a scenario where every free has to touch the same word of metadata (the free list head link for a certain slab), and a large number of threads are simultaneously trying to free at the same time as each other. For smalloc, it isn't the case that the contention will resolve over time if the benchmark runs longer—instead the contention level will remain constant as long as the benchmark runs, because as long as it is running then the threads are trying to free their pointers as fast as they can. Does that make sense?

We can make the "free hotspot" benchmark run longer just by turning up the TOT_ITERS and numthreads arguments in

smalloc/bench/src/bin/bench.rs

Line 104 in 76275af

// multithread_free_hotspot simulates a somewhat plausible worst-case-scenario, which is

.

I briefly looked at https://github.com/microsoft/snmalloc/blob/6dbf08a6f1146d8c87af930840abd7496821d28a/src/test/perf/msgpass/msgpass.cc . It says there are N producer threads that allocate and pass their pointers to N random consumer threads, and then the consumer threads deallocate. Is that right? The "free hotspot" benchmark is very similar to that except that there is only 1 producer thread. This makes it a more difficult scenario for smalloc—having N producer threads would just allow smalloc to distribute those producer threads over N slabs (as long as N < 64) which would just make it much easier.

What I'd love to see is code or at least a spec from you explaining what are some "worst-case scenarios" from the perspective of snmalloc. I'd love for the smalloc builtin benchmarks to test worst-case-scenarios for various allocators. But it sounds like this N-producer, N-consumer scenario might not actually be too difficult for snmalloc. :-)

[mjp41]

Sorry, you are right the short lived nature is not what makes me think that is not like Tremor.

I think the difference would be to have something doing allocation at the same time as it being a free hot spot. The contention then causes the producer to slow down as well. I was mostly proposing the msg pass benchmark as something that might help you understand the performance difference that @Licenser saw between snmalloc and smalloc on Tremor. I never directly benchmarked Tremor with snmalloc, but I know a couple of years ago @Licenser and @darach found snmalloc performed very well. This flow of allocations through multiple processing nodes was what motivated the original design of snmalloc. We wanted to address issues that were in the Pony programming language runtime and how it performed allocation.

That benchmark was used to support the optimisation in the BatchIt paper:

https://www.microsoft.com/en-us/research/wp-content/uploads/2024/05/preprint_batchit.pdf

This involved adding an additional layer of batching to snmalloc and mimalloc.

Bad cases for snmalloc, the most common case is one where thread caching works really well. A collection of threads all allocating objects of size n, passing them to a different thread, deallocating them, and repeating. This works well for thread caching as each thread can reuse its deallocations for the allocation step. Where as allocators like snmalloc, mimalloc and tbbmalloc will pass them back to the original allocator to handle.

General bad cases for most allocators are where the distribution of objects sizes changes over time. Same for number of threads changing over time. This needs better benchmarking than mimalloc-bench provides as it needs RSS at specific times, rather than just peak.

Another area of specific weakness for snmalloc is if there are considerably more threads than cores. We do everything at the per thread level, so our memory usage would be much higher. The Windows heap is very good in this kind of scenario as it is very conservative in going to faster data structures and will share a lot, which leads to a very low working set. But this has throughput concerns in some scenarios.