> The issue with this approach is that the more you can control, the less the compiler can assume.
That's absolutely true, but there's a workaround, albeit a complicated one. The compiler internals need the same kind of constraints or traits that abstract code such as language interfaces or template parameters can have. These can then be used to constrain the internals in a way that then would allow assumptions to be safely "plumbed through" the various layers. The (big!) challenge here is that these abstractions haven't been well-developed in the industry. Certainly nowhere near as well as the typical runtime "type theory" as seen in modern languages.
> some very basic ones like allocating heap memory.
Well... this is sort-of my point! For example, what's the fundamental difference between allocating memory in some heap[1] structure at runtime and a compiler allocating members in a struct/record/class for optimal packing?
It really opened my eyes to how one could very elegantly make a very complex and high-performance heap allocator from trivial parts composed at compile-time.
There's no reason that a nearly identical abstraction couldn't also be used to efficiently "bin pack" variables into a struct. E.g.: accounting for alignment, collecting like-sized items into contiguous sections, extra padding for "lock" objects to prevent cache issues, etc...
This is what my dream is: that a struct might just be treated as a sort-of comptime heap without deletions. Or even with deletions, allowing fun stuff like type algebra that supports division. I.e.: The SELECT or PROJECT-AWAY operators!
There was some experimental work done in the Jai language to support this kind of thing, allowing layouts such as structure-of-arrays or arrays-of-structures to be defined in code but natively implemented by the compiler as-if it was a built-in capability.
[1] Not really a traditional heap in most language runtimes these days. Typically a combination of various different allocators specialised for small, medium, and large allocations.
PS: The biggest issue I'm aware of with ideas like mine is that tab-complete and IDE assistance becomes very difficult to implement. On the other hand, keeping the full compiler running and directly implementing the LSP can help mitigate this... to a degree. Unsolved problems definitely remain!
> Well... this is sort-of my point! For example, what's the fundamental difference between allocating memory in some heap[1] structure at runtime and a compiler allocating members in a struct/record/class for optimal packing?
There are many fundamental differences! For example at compile time you can't know what the address of some data will be at runtime due to stuff like ASLR, nor can you know the actual `malloc` implementation that will be used since that might be dynamically loaded.
Of course this does not prevent you from trying to fake heap allocations at comptime, but this will have various issues or limitations depending on how you fake them.
(It helps if you've watched the linked allocator video.)
Conceptually, an abstract allocator in the style proposed by Andrei can be set up to just return an offset
This offset can then later be interpreted as "from the start of the struct" or "from the start of memory identified by the pointer to 0".
Fundamentally it's the same thing: take a contiguous (or not!) space of bytes and "carve it up" using some simple algorithm. Then, compose the simple algorithms to make complicated allocators. How you use this later is up to you.
I guarantee you that there's code just like this in the guts of any compiler that can reorder struct/record members, such as the Rust compiler. It might be spaghetti code [1], but it could instead look just like Andrei's beautiful component-based code!
I think it ought to be possible for developers to plug in something as complex as a CP-SAT solver if they want to. It might squeeze out 5% performance, which could be worth millions at the scale of a FAANG!
> This offset can then later be interpreted as "from the start of the struct" or "from the start of memory identified by the pointer to 0".
The issue is, how do you create such an offset, at comptime, such that you can interpet it as "from the start of memory identified by the pointer to 0" at runtime. Because at runtime you'll most often want to do the latter (and surely you don't want to branch on whether it's one or the other), but creating such offsets is the part that's very tricky if not impossible to do properly at comptime.
> I guarantee you that there's code just like this in the guts of any compiler that can reorder struct/record members
How is that relevant though? Ok, the code might look similar, but that's not the problematic part.
That's absolutely true, but there's a workaround, albeit a complicated one. The compiler internals need the same kind of constraints or traits that abstract code such as language interfaces or template parameters can have. These can then be used to constrain the internals in a way that then would allow assumptions to be safely "plumbed through" the various layers. The (big!) challenge here is that these abstractions haven't been well-developed in the industry. Certainly nowhere near as well as the typical runtime "type theory" as seen in modern languages.
> some very basic ones like allocating heap memory.
Well... this is sort-of my point! For example, what's the fundamental difference between allocating memory in some heap[1] structure at runtime and a compiler allocating members in a struct/record/class for optimal packing?
IMHO, not much.
E.g.: Watch this talk by Andrei Alexandrescu titled "std::allocator Is to Allocation what std::vector Is to Vexation": https://www.youtube.com/watch?v=LIb3L4vKZ7U
It really opened my eyes to how one could very elegantly make a very complex and high-performance heap allocator from trivial parts composed at compile-time.
There's no reason that a nearly identical abstraction couldn't also be used to efficiently "bin pack" variables into a struct. E.g.: accounting for alignment, collecting like-sized items into contiguous sections, extra padding for "lock" objects to prevent cache issues, etc...
This is what my dream is: that a struct might just be treated as a sort-of comptime heap without deletions. Or even with deletions, allowing fun stuff like type algebra that supports division. I.e.: The SELECT or PROJECT-AWAY operators!
There was some experimental work done in the Jai language to support this kind of thing, allowing layouts such as structure-of-arrays or arrays-of-structures to be defined in code but natively implemented by the compiler as-if it was a built-in capability.
[1] Not really a traditional heap in most language runtimes these days. Typically a combination of various different allocators specialised for small, medium, and large allocations.
PS: The biggest issue I'm aware of with ideas like mine is that tab-complete and IDE assistance becomes very difficult to implement. On the other hand, keeping the full compiler running and directly implementing the LSP can help mitigate this... to a degree. Unsolved problems definitely remain!