[tw061023]

These are microbenchmarks, thoroughly optimized to the point some of them are written almost completely in SSE intrinsics.

I would expect Rust to be 2x-3x slower in real production code, solely due to approach to memory allocation.

[kaba0]

That’s naive to think that someone will actually make proper use of custom allocators in Zig. Low-lever, performance-oriented programming is hard, especially when you are doing a more exploratory job without clear goals up front.

And when you do know what you want, explicitly optimizing those parts is equally possible in the two languages.

[aw1621107]

> solely due to approach to memory allocation

Would you mind elaborating on this? I don't think I've read anything (yet?) that touches on performance differences due to that particular aspect of the languages.

[kibwen]

The only thing I can think of is that Zig makes it easier to use different allocators on a per-collection basis, whereas for Rust the only way to alter the allocator used by the standard containers is to change the global allocator. But Rust programs aren't allocating that much in the first place, certainly not so much that swapping out an allocator on a per-collection basis is going to triple the performance of arbitrary programs; at best, fine-grained allocator control will give modest gains on certain extremely allocation-heavy workloads. And collections in Rust can certainly use custom allocators if they want to, e.g. https://crates.io/crates/bumpalo , so that's not something inherent to the language.

[tw061023]

I respectfully disagree.

> to use different allocators on a per-collection basis

It's far more than that. There are different memory management optimization patterns that are hard to implement in Rust, ie. splitting allocations to different arenas based on allocation lifetime.

> But Rust programs aren't allocating that much in the first place

Are Rust programs allocating mostly from the stack then?

> is going to triple the performance of arbitrary programs

The difference between malloc and any hand-rolled O(1) allocator is enormous, it's just people rarely benchmark this particular aspect.

There is a reason why Rust used to ship jemalloc and why #[global_allocator] is a thing. I would argue there's even more reason to avoid touching heap in the first place.

Edit: formatting.

[kibwen]

> Are Rust programs allocating mostly from the stack then?

Yes, overwhelmingly so.

The basic rule of manual optimization is that the upper bound for the improvement that can be gained by optimizing any one "thing" is equal to the proportion of the program's runtime that is devoted to that thing. E.g. if a flamegraph shows that 10% of a program's runtime is devoted to a specific function, then improving the performance of that function is going to improve the performance of that program by at most 10%. (We might call this "generalized Amdahl's law": https://en.wikipedia.org/wiki/Amdahl%27s_law )

Therefore, in order to improve the performance of a program by 2-3x by changing allocators, that requires that a program be spending at least 50% to 66% of its runtime on allocation. And it would be a highly anomalous Rust program that was allocator-bound in this way.

[dxhdr]

How do you measure cache line utilization with a flame graph? I'm not sure it's as simple as you're describing. Poor memory access patterns from heap allocations can kill performance via death from a thousand cuts. It's not about spending "X% of the time on allocation," it's about every computation spending unnecessary time reading and writing to the cache due to poor choice of allocation strategy. Custom allocators can ensure data layout fits the access pattern.

More specifically, arrays are about the fastest thing around, and handing out objects from within a preallocated array tends to give the best access performance by a large margin. From what I understand you basically have to sidestep the Rust borrow checker to achieve this. Which does raise some interesting questions.

I think the original poster was also saying that heap allocations are slow, which is true, but I agree it'd be easier to tell if your program is having trouble with that.

[kibwen]

I'm unclear how cache line utilization is relevant here. In both Zig and Rust, the choice of allocator has no effect on the layout of data in a given collection. In other words, this Zig code:

    var foo_list = ArrayList(u8).init(foo_allocator);
    try foo_list.append(1);
    try foo_list.append(2);
    try foo_list.append(3);

...and this Rust code:

    let mut foo_list = Vec::new();
    foo_list.push(1);
    foo_list.push(2);
    foo_list.push(3);

...are both going to produce an array of [1,2,3] stored in the heap. The choice of allocator only affects where that array itself ends up being stored. Fetching an element of foo_list is going to cache the other elements in the list regardless of its location in memory, so the choice of allocator doesn't matter for that purpose. The only thing that could make a difference is if you want multiple different collections to be fetched in the same cache line, but if your collections are so small that multiple collections fit in the same cache line then your data isn't big enough to be worrying about optimizing your cache utilization (and furthermore, even if you carefully lay out your collections in such a way, as soon as any of your growable arrays need to be reallocated that completely throws all of your careful organization out the window).

> More specifically, arrays are about the fastest thing around, and handing out objects from within a preallocated array tends to give the best access performance by a large margin. From what I understand you basically have to sidestep the Rust borrow checker to achieve this.

Where did you get this impression? Rust has stack allocated arrays, and you can hand out references to them just as well as you can to any other owned type. I can think of no distinction that the borrow checker makes between stack- and heap-allocated types.

[tw061023]

While I agree with you, my point was specifically the cost of a malloc. As someone who had actually profiled a pool vs malloc, this is kind of a salient point for me.

In some workloads short-lived allocations are common. Like memory is allocated for milliseconds and then deallocated - and X% of time will be spent just inside the allocator trying to find the best block to allocate. At this point you want to make sure that you don't spend more time in the allocator than allocations actually live.

[tw061023]

> Yes, overwhelmingly so.

I wonder how common business tasks can be coerced to this model.

Also I believe this is not a good excuse - the language should still provide a way to properly manage allocations even if it is not needed most of time.

> The basic rule of manual optimization is that the upper bound for the improvement that can be gained by optimizing any one "thing" is equal to the proportion of the program's runtime that is devoted to that thing.

Yep, and this is why you should always measure things before optimizing. But then again, you can save yourself a lot of time by not doing stupid things like allocating from heap in a hot loop and profiling just to discover such basic mistakes.

[hgs3]

All references in Rust must have an explicit owner. It's common to create additional structures whose entire purpose is to manage the lifetime of your actual data structures. This means more memory consumption and potentially extra indirection, e.g. slot map handles vs pointers.

[kibwen]

You don't need heap allocations in order to have an explicit owner. Data on the stack is owned, and references to stack-allocated data can be handed out just fine.

[hgs3]

Sure, but you can't always use the stack. It has a limited amount of memory and doesn't handle dynamic data structures well, e.g. for a growable undirected graph you need auxiliary data structures for managing its nodes.

[tw061023]

Long story short, heap allocation is painfully slow. Any sort of malloc will always be slower than a custom pool or a bump allocator, because it has a lot more context to deal with.

Rust makes it especially hard to use custom allocators, see bumpalo for example [0]. To be fair, progress is being made in this area [1].

Theoretically one can use a "handle table" as a replacement for pools, you can find relevant discussion at [2].

[0] https://github.com/fitzgen/bumpalo

[1] https://github.com/rust-lang/rust/issues/32838

[2] https://news.ycombinator.com/item?id=36353145

Edit: formatting.