Hacker News Reader

Compilers spend a lot of time with hashtables, which exist on the heap. Rust isn't some magical language that makes the heap some unnecessary entity. One still has objects whose lifetime do not fit the stack model or whose size is dynamic

Their comment went on to claim that given their hypothesis, allocation optimization shouldn't be impactful. Yet this post demonstrates otherwise, perhaps showing that therefore their hypothesis is false (if a then b, b is false, therefore a is false)

One of the post's optimizations was to use Cow<str> over String tho, which is an example of reducing allocations with borrows

Additionally it's oft mentioned that a weak point in Rust's compile time is LLVM. This has to do with various things, some of which are Rust's fault (it could generate less IR), but it points out that there's a lot of time being spent in C++ code. LLVM's great, but it's guidelines essentially suggest 'if you want to make llvm play nice, generate IR like clang'

> Their comment went on to claim that given their hypothesis, allocation optimization shouldn't be impactful.

And what was the hypothesis? That the code for the compiler itself should use the features imagined to be used by the language, just like your example:

> One of the post's optimizations was to use Cow<str> over String

Then:

> allocation optimization shouldn't be impactful. Yet this post demonstrates otherwise

"not impactful": It looks to me like that: 36.526s vs 32.373s for the longest compile tested. It is measurable, but not something that I as the programmer will be able to notice. My definition of impactful for the compilation times is "at least a factor of 2" not 1.1.

And the claim is, once the language possibilities are actually used. If the code is written differently, of course not much is expected. The result of a moderate speedup exactly shows that the language possibilities weren't always used in a way to minimize allocations, but the difference is still not, for my perception, significant (10% is hard to recognize unless measured or the actual compilations last hours and not seconds). But I still claim that much bigger potential gains are the actual changes in the algorithms and the data structures. The data structures especially can hugely change the result if they are made to be really cache friendly, and together with the changes in algorithms such modifications have the potential to make an order of magnitude speedups, if they are actually possible.

Because the parent poster's thesis

>>Moreover, the compilers in general have an advantage to know that most of the objects are needed only during specific times, allowing optimized allocation and bundled deallocation

Is flawed.

Compiler can know this. Most the time they don't. In Turing complete languages you can't reason about how much space/time a program will need to run.

When you do know that and object, or objects will be determanstically allocated/de-allocated together. Then you need to know how large they'll grow too over their their lifetimes. Which again may hit a Turing Tarpit, and you lose this ability.

Here is an incredibly simple example

        fn read_file(path: &str) -> String;
        fn get_tokens<'a>(s: &'a str, r: &Regex) -> HashMap<&'a str, &'str>
        fn main() {
            let my_regex = //something
            let file_data = read_file(&arg[1]);
            let tokens = get_tokens( &file_data, &my_regex);
        }

On can see the String that will contain the file's data, and Hashmap can be allocated together. But one cannot reason about how large either will be head of time to pre-size these on the heap.

Lastly, address randomization is a good thing. Knowing ahead of time which allocations will determanstically be in relation to each other is a security vulnerability.

My claim about "the compilers in general have an advantage to know that most of the objects are needed only during specific times" is directed to the construction of the compiler, like the Rust compiler written in Rust, not that there's any magic. That means, the writer of the compiler can write the compiler knowing much more about the lifetime of the objects used in the compilation than most of the software.

When you write a server, you don't know who much which pieces of the database should be in the memory. When you write a compiler, you know that everything goes away after the compilation is done. It allows extremely speedy compilers (considering the number of their malloc calls), which seldom allocate memory blocks and seldom deallocate.

That means that even for the stuff that you allocate "on the heap" you don't have to allocate objects one-by-one, but allocate big chunks of memory and then just deliver the small pieces of it as the memory for "objects." The same way, for the deallocation, instead of deallocation many small objects, you can deallocate a lot at once.

I've personally made the compiler that made only a few malloc calls for the whole compilation process, even if it internally "created" tens of thousand of "objects." I've done it in C, and Rust is made to allow the speed of C with the higher safety, so the equivalent strategies should be possible. The mention of "arenas" suggests to me that the writers actually think in that direction.

>>I've created a similar system

Cool then submit a patch to the Rust project.

> That means that even for the stuff that you allocate "on the heap" you don't have to allocate objects one-by-one, but allocate big chunks of memory and then just deliver the small pieces of it as the memory for "objects." The same way, for the deallocation, instead of deallocation many small objects, you can deallocate a lot at once.

IIRC jemalloc does this anyway?

Regardless, the Rust compiler uses arenas a lot, but that doesn't make them a one-size-fits-all solution. Arenas are a great solution when allocations are used to be able to let data escape the stack frame (i.e. when you aren't able to just use a stack variable like your original comment said). But that's not the only reason allocation is used. For growable collections like vectors and maps a typed arena isn't necessarily the best solution. An untyped arena might help, but again, that's sort of one of the things jemalloc gets you.

Even with arenas, of course allocations will get you measurable overhead. With arenas individual allocations cause no overhead, but there's a tipping point (i.e. when a block of the arena fills up) when it starts to matter.

> ...if the features of the language are used...

The Rust compiler uses Rust's features terribly, just because Rust's features were a moving target for the majority of the compiler's lifetime.