Benchmarking the allocator of immix and hybrid allocators

[miguelraz]

Hello! This is a fantastic code!

I have a few questions:

From reading the paper, I noticed Supermalloc was mentioned, but not benchmarked against in the improved immix implementation. Is there any way to facilitate that?

If one wanted to help optimize the generated code for garbage collectors, how could one help?

Looking forward to hearing from this amazing project!

[cronburg]

In order to benchmark the immix-in-rust implementation against a manual allocator like Supermalloc we would need a way to run the same (compiled) programs with the two. The immix implementation included here was almost entirely based off an existing code-base (discussed a bit here: https://www.reddit.com/r/rust/comments/552lsf/rust_as_a_language_for_high_performance_gc/), and that project provided a way to run both C programs as well as Rust programs by conservatively scanning the program's stack for alleged pointers into the Immix heap; any integer with a value in the correct range, as found on the heap, is assumed to be a pointer into the heap.

But I don't see an obvious way to compare a malloc/free interface (supermalloc) with an alloc/sweep interface. Perhaps one could write Rust benchmarks which specify the Drop trait on boxed types to call supermalloc's free in one build configuration, and then to do nothing in the Immix implementation? This would require setting up the appropriate interfaces with Rust's FFI to C (to call supermalloc). But be careful with interpreting the results, because most of the difference in program runtime I'd guess will be a consequence of the different memory management paradigms (manual vs automatic) as opposed to the efficiency of either of the two.

As for your second question, most of the opportunity for "optimization of generated code" would involve finding existing GC operations that are performed in other garbage collectors, and fitting them into the typed-programming paradigm. The most obvious optimization I can think of is for a bitmap lookup table residing at the beginning of a block of memory. Namely the immix implementation included here uses addition operations, when bit-shifting operations alone would be faster and require less bookkeeping information. To implement that, the hardest part will be writing the static analysis which determines when to generate the faster bitmap operations, requiring particular size and alignment constraints to be specified in the Floorplan specification.