> The last time I used [a doubly linked list] was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
This and sibling comments about the supposed uselessness or outdatedness of linked lists taught me something about the disconnect between many systems engineers resistant to Rust and many members of the (evangelical) Rust community.
To address the technical topic first: a doubly linked list is what you reach for when you’re looking for an intrusive data structure with fast append and fast delete. You need to iterate over it, but don’t need random access. Queues where you may need to remove elements. Think a list of completions that can be cancelled.
Why an intrusive data structure? Because you don’t want to, or can’t allocate. Because you want only a non-owning reference to the object, and you don’t want to have to manage any other lifetimes or dynamic (potentially unbounded, or arbitrarily bounded) allocations. Intrusive data structures are a great tool to minimize allocations, and to keep allocations (and ownership) logically separated across modules.
And now onto the cultural topic. That a member of the Rust community might not know this (which is of course totally fine) is what taught me something, which was maybe obvious to many: Rust brings safety to a C++ style language and audience. For the same reasons many dislike C++, many dislike Rust. For the same reasons many would opt for C over C++ when they have the choice (either across all their projects or for certain projects), many continue to opt for C over Rust.
Rust will not be taking over systems programming for the same reasons C++ did not. Well, by the numbers, it probably did (and Rust probably will too), so maybe better to say that it will not stamp out C for systems programming for the same reasons C++ did not. And it’s not just because of the stubbornness of C programmers.
Systems programming has 2 cultures and practice groups: the C camp, and the C++ camp. The C++ camp is a big tent. I’d argue it includes Rust and Swift (and maybe D). Zig belongs to the C camp.
Safety is important, and maybe Rust has the right model for it, but it is not a solution for the C camp. It likely did not intend to be, and again, by the numbers, replacing C++ is probably the more important task.
Animats 14 hours ago [-]
This is the back-link problem in Rust. You can do back links with weak pointers, but it's rather verbose and involves extra run-time checks.
I've been trying to figure out a compile-time approach to that problem.
Here's an early version of a tech note on that.[1]
It looks possible, but there are many issues. But it's important to look at now. The C++ people are trying to figure out safe backlinks.
My gut says the following, so take with a grain of salt:
If your goal is to not do refcounting,
You can tie compile time guaranteed access on a 'parent getter' (but only ever as a non-mut reference) by saying:
- parent element MUST be present at time of construction
- When doing a 'parent get' call, you MUST still prove you're in the parent's lifetime.
This can be done at compile time at 0 runtime cost.
The problem is, that these constraints drastically reduce the usability of those back-links.
There is no compiler solution in Rust. Rust lifetimes form a DAG of (overlapping) ranges. (in terms that some leaf nodes are inductive proofs)
To relax those 2 constraints require a bi-directional graph, and I'm not sure if that can ever be computed in a reasonable time.
discardable_dan 54 minutes ago [-]
It's pretty easy to do at runtime without weak pointers, people who write rust are just allergic to reference counting. Which is absurd, because most programmer use RC values thousands of times every day without even thinking about it. It's really this easy: https://pastebin.com/SAeKG7Sw
mwkaufma 13 hours ago [-]
> Handles are deterministic. If a bug made your program crash on the last run, it will crash the same way on this run.
> Given that the arena will still be subject to array bounds checking, handle bugs won't allow an attacker to overwrite arbitrary memory the way pointer bugs do.
Just because you're in-bounds of the arena, doesn't mean you're not stomping on in-bounds neighboring data -- which can introduce "nondeterminism" as the author defines it. These are hand-waving arguments.
thinkharderdev 48 minutes ago [-]
> doesn't mean you're not stomping on in-bounds neighboring data
I don't see how you would do that in safe rust though. The point of the arena would just be to solve the lifetime issue. It just moves the ownership problem one level higher. Instead of having circular ownership in a linked list, all linked list nodes are owned by the arena and hence have the same lifetime as the arena.
mwkaufma 13 hours ago [-]
Anticipating pushback: yes, you can disallow "pointer arithmetic" on handles, and store fingerprints in the "slots" to ensure they still contain the handle's identity to detect user-after-free, but congrats, you've implemented sparse sets, which there are dozen's of C++ implementations of with the same safety guarantees, so it's unclear what rust is bringing in that case (e.g. https://github.com/skypjack/entt/blob/master/src/entt/entity...)
at_compile_time 10 hours ago [-]
That C++ already has many implementations of sparse sets seems to be a point in favor of sparse sets rather than a point against Rust, especially given that C++ doesn't need them the same way Rust does.
mwkaufma 10 hours ago [-]
Well, there's several implementations because it's a bit of a leaky abstraction, and implementation details matter/vary across use-cases, which is consistent w/ my experience of rust having heavy fragmentation in applying the array-index pattern for "weak pointers."
airstrike 10 hours ago [-]
If only devs had any other reason to use Rust.....
mwkaufma 9 hours ago [-]
The topic is "Arenas in Rust" not "Arenas in Rust or anything other tradeoff."
eviks 8 hours ago [-]
Indeed, the topic is "in Rust", so you'd do arenas in Rust due to those memory safety benefits outside of arenas. And since arenas aren't as bad due determinism etc, it's still a net benefit: safer outside, safer inside
kobebrookskC3 1 hours ago [-]
stomping on in-bounds data might result in "nondeterminism", but bounded and not ub, which is unbounded.
Someone 5 hours ago [-]
Given Rust’s memory safety goal, IMO the proper way to solve the circular reference problem in the context of Rust would be in the language. It should have a way to express what cycles may exist, maybe also how the code will break them when needed.
The hardest problems I think is that this requires a fundamental change to the language that something might be already borrowed just by existing. It also likely needs to introduce a notion of "stable" places that will not move when you move a prefix of them, e.g. to allow moving a `Box` holding self-referential data. In other words, there's a lot of bikeshedding to do.
asplake 5 hours ago [-]
> The last time I used [a doubly linked list] was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
Curious to know in the Linux context whether moves away from doubly linked lists have ever been tested?
gavinsyancey 2 hours ago [-]
Linux uses them because it has a lot of lists of objects that very rarely or never need to be iterated over, but where it needs to be fast to
- Insert a new item
- Delete a specific item (that you have a pointer to
- Move a specific item from list A to list B
- Get the next item to work on
And where pointers to an item need to be stable. Doubly-linked lists are very fast for all of that; their main downside is they are slow to iterate over due to cache incoherency but that doesn't matter if you very rarely or never iterate through the entire list. And since you need to have stable pointers to items in the list that don't change when you insert/remove items, most other data structures would need an extra level of indirection so you lose the cache coherency benefit anyways.
sfpotter 13 hours ago [-]
Here's an implementation of a doubly-linked list which is perfectly fine on modern hardware: an array of structs where each struct contains a pointer to its next and previous elements in addition to whatever other data is being stored.
Here's a situation where a traditional pointer-based double-linked list is fine: when the payload is very large (e.g., an entire document in some app).
cindyllm 12 hours ago [-]
[dead]
procaryote 5 hours ago [-]
I kinda think rust is a dead-end. The learning curve is really challenging for most people, and you gain all these new constraints.
It competes against languages that give you memory safety by having garbage collection, or I guess even by using arenas in a few cases. GC comes with a performance hit, but a bit of a performance hit is usually much easier to deal with than having a smaller pool of effective developers
Worse is better
simonask 6 minutes ago [-]
Rust competes with both GC languages (offering way superior performance) and with C++ (offering safety and modern language features).
It’s a pretty strong value proposition, but it doesn’t mean there aren’t good reasons to pick a GC language if you can afford the performance hit.
The list of reasons to pick C++ over Rust is very short, mostly momentum, recruitment, and legacy. For greenfield projects, the list is even shorter.
The general experience is that developing software in Rust is slightly more expensive compared with, say, C#, and way, way cheaper than C++.
SomeoneOnTheWeb 51 minutes ago [-]
I strongly disagree.
* The performance difference can be pretty massive depending on scenarios. Sure, most programs don't need it, but still
* Rust has not only memory safety but full safety around it. For instance, in Java if you iterate over a list while mutating it you'll get a runtime error. In Rust, it won't compile, preventing you from a possible bug later on
* The time you spend learning Rust is so much time saved afterwards because the language is specifically designed to reduce the risk of programming errors. Many things like the absence of a `null` value like we have in Java is an immense time saver when your program gets bigger
pimeys 3 hours ago [-]
Nah. It's like learning vim, you get over the first shock and then you have a lifetime friend.
And another thing is with current coding agents, like the gpt-5-codex, Rust really shines here. The agent can easily guide you through the first borrow checker issues, and the compiler helps the agent to write good code.
Source: been writing Rust for a decade now. It is easily the best language I've ever used, still.
t43562 2 hours ago [-]
I'm experiencing that shock now. Can't create a global instance of my self-made heap datastructure. I'm longing for C memory management at the moment - it seems a tiny price to pay.
Now I learn that linked lists aren't possible and one has to use some, frankly, bullshit scheme to pretend to have them. IMO the documentation isn't really preparing people for the new reality of what can be done and how to do things.
simonask 12 minutes ago [-]
Linked lists aren’t just possible in Rust, they are in the standard library.
They are just an example of the borrow checker’s limitations, which mean that you can only form a DAG of mutable references. But that’s why we have `unsafe`.
binarymax 2 hours ago [-]
The way I think about rust is this: you can experience the pain up front while you’re getting your program to compile, or you can experience pain later during runtime in random unpredictable ways. Rust is the former. It takes time to learn how to reduce the up front pain, but I’m so much more confident in the end result.
I say this having years of coding background in languages like C, C#, Java, JavaScript, Python, etc.
tonyedgecombe 1 hours ago [-]
> It competes against languages that give you memory safety by having garbage collection
I wouldn’t use it where I could get away with garbage collection (nor C/C++) but that still leaves enough space for Rust to exist in.
crq-yml 12 hours ago [-]
I'm a bit agnostic about the specific solution these days. In general, early binding(so, static memory and types, formalized arenas and handles, in-line linear logic with few or no loops or branches) debugs more readily than late(dynamic memory allocs and types, raw pointers, virtual functions, runtime configuration). The appeal of late binding is in deferring the final computation to later so that your options stay open, while the converse is true with early binding - if you can write a program that always returns a precomputed answer, that's easier to grasp and verify.
When we compare one method of early binding with another, it's probably going to be a comparison of the granularity. Arenas are "stupid simple" - they partition out memory into chunks that limit the blast radius of error, but you still make the error. Ownership logic is a "picky generalization" - it lets you be more intricate and gain some assurances if you put up with the procedures necessary, but it starts to inhibit certain uses because its view into usage is too narrow with too many corner cases.
If we take Go's philosophy as an example of "what do you do if you want idioms for a really scalable codebase" - though you can certainly argue that it didn't work - it's that you usually want to lean on the stupid simple stuff and customize what you need for the rest. You don't opt into a picky Swiss Army Knife unless there's a specific problem to solve with it. Larger codebases have proportionately smaller sections that demand intricacy because more and more of the code is going to itself be a method of defining late binding, of configuring and deferring parts of processing.
That said, Rust lets you fall back to "stupid simple", it just doesn't pave the way to make that the default.
wasmperson 13 hours ago [-]
> There are several ways to solve this problem. One way is to avoid using direct references to the particular class of objects at all. Instead, allocate a big array of objects, and refer to them with integer indexes into that array. There are several names that have been used for such arrays and indexes; let's call them arenas and handles.
I thought the term "Arena" referred to linear allocators, but maybe it's not so narrowly defined.
> At one level, this question is not very fair, because an answer to it as stated would be that one simply does not use doubly linked lists. They have been popular in introductory computer science lectures because they are a neat way to explain pointers in a data structure that's easy to draw on a whiteboard, but they are not a good match to modern hardware. The last time I used one was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
The arena data structure you described is inefficient unless it uses a linked list to track empty slots. All general-purpose heap allocators use linked lists in their implementations. Linked lists show up wherever you want pointer stability, low fragmentation, or a way to decouple the storage of objects from their participation in data structures. I struggle to imagine how it would be possible to implement something like Linux without at least one linked list in it.
> Essentially you are bypassing the notion of pointers provided directly by the hardware
Pointers aren't a hardware concept, they're a language concept. Array indices and pointers both rely on indirect addressing, which is the underlying hardware concept. The "handles" strategy in Rust feels like a kludgy approach not because it bypasses the hardware but because Rust's borrow checker isn't actually involved in ensuring safety in that case, just its bounds checking and mandatory initialization (and if all you need is those two things then...).
jmull 11 hours ago [-]
> Doesn't that mean you are throwing out all the memory safety properties you were hoping to achieve by using Rust in the first place? ...That argument sounds logical, but it's not actually correct.
Actually, it is correct. The more generally you use "arenas" the more they are subject to the same kinds of issues as other manual memory management systems. "arenas" can only avoid/reduce the "nondeterminism" and "security" issues of general manual memory management on top of a buffer of bytes by not becoming general manual memory management on top of a buffer of bytes.
simonask 3 minutes ago [-]
It all comes down to whether pointers into the arena do something different than normal pointers when they are dangling.
Normal pointers cause UB. That’s astronomically bad. If your arena pointers crash your program in a well-defined way, that’s already a much better situation.
tyre 5 hours ago [-]
How could using arenas lead to remote code execution?
jmull 2 hours ago [-]
You just need to put something executable, in whatever sense, in the arena... values that represent functions to call or dynamic libraries to load, or privileges to do those things, etc.
pizlonator 14 hours ago [-]
Arenas let you use OOBAs to do data attacks, and those can give you the moral equivalent of remote code execution.
Like if your arena contains both a buffer that OOB's and a buffer passed to a syscall, then having memory safety around the arena doesn't help you
achierius 11 hours ago [-]
And as a bonus, they also conveniently opt you out of any other hardening features your system malloc might have implemented (like MTE).
I certainly appreciate the performance benefits of custom allocators but it's disheartening to see people naively adopting them just as the world's allocators are starting to get their acts together with regards to security.
Animats 14 hours ago [-]
Yes. This is a big headache in graphics, where there are big tables indexed by texture index down at the GPU level. Managing those as the content changes, with the GPU using the data while the CPU alters it, leads to huge complexity in Vulkan graphics.
The two times I've had to deal with a really tough debugging problem in Rust, it's been related to some crate which did that.
lenkite 6 hours ago [-]
I wish Rust would finalize its custom memory allocators api (allocator_api) and put it in the stdlib as soon as possible. That feature has been unstable for a decade now.
whytevuhuni 3 hours ago [-]
I'd really like them not to hurry (or at least not "ASAP"). Among features that Rust should get right, this is definitely one of them.
And from its tracking issue [1], it seems there's alternatives with really important trade-offs (especially the very interesting storage API alternative), and it'd be really sad if we got stuck with something that ends up being unusable in many cases people actually want to use them on.
I'd like to see something powerful for safety and speed in Crates.io and Cargo:
The ability for crates to specify whether they use certain features of Rust:
- unsafe
- arena allocation or other future "useful" stuff
- proc_macros, eg. serde (a huge compile speed hit)
- deep transitive dependency (total #, or depth)
- some proxy for the "number of compiler steps" (compiler workload complexity)
We should be able to set a crate-wide or workspace-wide policy that can ban other crates that violate these rules.
We could make this hand-written early on, but eventually enforced by the compiler. You could then easily guarantee that no downstream dependency uses unsafe code, has a crazy number of dependencies, or has crazy compile times.
You could opt-in or opt-out to these things without having to think too much about them or constantly (manually) be on the lookout.
This would be hugely beneficial to the Rust ecosystem, safety, code quality, and developer productivity / happiness.
burnt-resistor 5 hours ago [-]
Many of these currently exist as lints that can live in a Cargo.toml:
Perhaps what would be useful is crates.io determining through analysis which in the set of all lint(s) a crate is compatible with and exposing that as automatic metadata?
5 hours ago [-]
IshKebab 14 hours ago [-]
Insightful article. As they say doubly linked lists are approximately useless and never used. But trees were nodes can refer to their parents are extremely common.
And I agree, a custom arena is usually the best option here. Even though it seems like "giving up" and going back to C, it's still way better.
Some of them have keys that can't be reused too, so you can avoid "use after free" style bugs (at runtime) which is way better than C pointer wrangling.
It's not perfect though. I kind of wish Rust did have some kind of support for this stuff natively. Pretty low on my list of Rust desires though - way behind better compile time and fewer async footguns.
sgarland 11 hours ago [-]
> doubly-linked lists are approximately useless
Leaf pages in InnoDB’s B+tree implementation is the big one I can think of. Turns out being able to quickly walk pages for a range scan is helpful.
I agree that there isn’t wide variety of applications where they jump out as being the best choice. So, yeah, “approximately useless” sounds about right.
Rendered at 11:40:44 GMT+0000 (Coordinated Universal Time) with Vercel.
This and sibling comments about the supposed uselessness or outdatedness of linked lists taught me something about the disconnect between many systems engineers resistant to Rust and many members of the (evangelical) Rust community.
To address the technical topic first: a doubly linked list is what you reach for when you’re looking for an intrusive data structure with fast append and fast delete. You need to iterate over it, but don’t need random access. Queues where you may need to remove elements. Think a list of completions that can be cancelled.
Why an intrusive data structure? Because you don’t want to, or can’t allocate. Because you want only a non-owning reference to the object, and you don’t want to have to manage any other lifetimes or dynamic (potentially unbounded, or arbitrarily bounded) allocations. Intrusive data structures are a great tool to minimize allocations, and to keep allocations (and ownership) logically separated across modules.
And now onto the cultural topic. That a member of the Rust community might not know this (which is of course totally fine) is what taught me something, which was maybe obvious to many: Rust brings safety to a C++ style language and audience. For the same reasons many dislike C++, many dislike Rust. For the same reasons many would opt for C over C++ when they have the choice (either across all their projects or for certain projects), many continue to opt for C over Rust.
Rust will not be taking over systems programming for the same reasons C++ did not. Well, by the numbers, it probably did (and Rust probably will too), so maybe better to say that it will not stamp out C for systems programming for the same reasons C++ did not. And it’s not just because of the stubbornness of C programmers.
Systems programming has 2 cultures and practice groups: the C camp, and the C++ camp. The C++ camp is a big tent. I’d argue it includes Rust and Swift (and maybe D). Zig belongs to the C camp.
Safety is important, and maybe Rust has the right model for it, but it is not a solution for the C camp. It likely did not intend to be, and again, by the numbers, replacing C++ is probably the more important task.
I've been trying to figure out a compile-time approach to that problem. Here's an early version of a tech note on that.[1] It looks possible, but there are many issues. But it's important to look at now. The C++ people are trying to figure out safe backlinks.
[1] https://github.com/John-Nagle/technotes/blob/main/docs/rust/...
If your goal is to not do refcounting, You can tie compile time guaranteed access on a 'parent getter' (but only ever as a non-mut reference) by saying:
- parent element MUST be present at time of construction
- When doing a 'parent get' call, you MUST still prove you're in the parent's lifetime.
This can be done at compile time at 0 runtime cost. The problem is, that these constraints drastically reduce the usability of those back-links.
There is no compiler solution in Rust. Rust lifetimes form a DAG of (overlapping) ranges. (in terms that some leaf nodes are inductive proofs)
To relax those 2 constraints require a bi-directional graph, and I'm not sure if that can ever be computed in a reasonable time.
> Given that the arena will still be subject to array bounds checking, handle bugs won't allow an attacker to overwrite arbitrary memory the way pointer bugs do.
Just because you're in-bounds of the arena, doesn't mean you're not stomping on in-bounds neighboring data -- which can introduce "nondeterminism" as the author defines it. These are hand-waving arguments.
I don't see how you would do that in safe rust though. The point of the arena would just be to solve the lifetime issue. It just moves the ownership problem one level higher. Instead of having circular ownership in a linked list, all linked list nodes are owned by the arena and hence have the same lifetime as the arena.
Have people been thinking about that?
The hardest problems I think is that this requires a fundamental change to the language that something might be already borrowed just by existing. It also likely needs to introduce a notion of "stable" places that will not move when you move a prefix of them, e.g. to allow moving a `Box` holding self-referential data. In other words, there's a lot of bikeshedding to do.
Curious to know in the Linux context whether moves away from doubly linked lists have ever been tested?
- Insert a new item
- Delete a specific item (that you have a pointer to
- Move a specific item from list A to list B
- Get the next item to work on
And where pointers to an item need to be stable. Doubly-linked lists are very fast for all of that; their main downside is they are slow to iterate over due to cache incoherency but that doesn't matter if you very rarely or never iterate through the entire list. And since you need to have stable pointers to items in the list that don't change when you insert/remove items, most other data structures would need an extra level of indirection so you lose the cache coherency benefit anyways.
Here's a situation where a traditional pointer-based double-linked list is fine: when the payload is very large (e.g., an entire document in some app).
It competes against languages that give you memory safety by having garbage collection, or I guess even by using arenas in a few cases. GC comes with a performance hit, but a bit of a performance hit is usually much easier to deal with than having a smaller pool of effective developers
Worse is better
It’s a pretty strong value proposition, but it doesn’t mean there aren’t good reasons to pick a GC language if you can afford the performance hit.
The list of reasons to pick C++ over Rust is very short, mostly momentum, recruitment, and legacy. For greenfield projects, the list is even shorter.
The general experience is that developing software in Rust is slightly more expensive compared with, say, C#, and way, way cheaper than C++.
* The performance difference can be pretty massive depending on scenarios. Sure, most programs don't need it, but still * Rust has not only memory safety but full safety around it. For instance, in Java if you iterate over a list while mutating it you'll get a runtime error. In Rust, it won't compile, preventing you from a possible bug later on * The time you spend learning Rust is so much time saved afterwards because the language is specifically designed to reduce the risk of programming errors. Many things like the absence of a `null` value like we have in Java is an immense time saver when your program gets bigger
And another thing is with current coding agents, like the gpt-5-codex, Rust really shines here. The agent can easily guide you through the first borrow checker issues, and the compiler helps the agent to write good code.
Source: been writing Rust for a decade now. It is easily the best language I've ever used, still.
Now I learn that linked lists aren't possible and one has to use some, frankly, bullshit scheme to pretend to have them. IMO the documentation isn't really preparing people for the new reality of what can be done and how to do things.
They are just an example of the borrow checker’s limitations, which mean that you can only form a DAG of mutable references. But that’s why we have `unsafe`.
I say this having years of coding background in languages like C, C#, Java, JavaScript, Python, etc.
I wouldn’t use it where I could get away with garbage collection (nor C/C++) but that still leaves enough space for Rust to exist in.
When we compare one method of early binding with another, it's probably going to be a comparison of the granularity. Arenas are "stupid simple" - they partition out memory into chunks that limit the blast radius of error, but you still make the error. Ownership logic is a "picky generalization" - it lets you be more intricate and gain some assurances if you put up with the procedures necessary, but it starts to inhibit certain uses because its view into usage is too narrow with too many corner cases.
If we take Go's philosophy as an example of "what do you do if you want idioms for a really scalable codebase" - though you can certainly argue that it didn't work - it's that you usually want to lean on the stupid simple stuff and customize what you need for the rest. You don't opt into a picky Swiss Army Knife unless there's a specific problem to solve with it. Larger codebases have proportionately smaller sections that demand intricacy because more and more of the code is going to itself be a method of defining late binding, of configuring and deferring parts of processing.
That said, Rust lets you fall back to "stupid simple", it just doesn't pave the way to make that the default.
I thought the term "Arena" referred to linear allocators, but maybe it's not so narrowly defined.
> At one level, this question is not very fair, because an answer to it as stated would be that one simply does not use doubly linked lists. They have been popular in introductory computer science lectures because they are a neat way to explain pointers in a data structure that's easy to draw on a whiteboard, but they are not a good match to modern hardware. The last time I used one was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
The arena data structure you described is inefficient unless it uses a linked list to track empty slots. All general-purpose heap allocators use linked lists in their implementations. Linked lists show up wherever you want pointer stability, low fragmentation, or a way to decouple the storage of objects from their participation in data structures. I struggle to imagine how it would be possible to implement something like Linux without at least one linked list in it.
> Essentially you are bypassing the notion of pointers provided directly by the hardware
Pointers aren't a hardware concept, they're a language concept. Array indices and pointers both rely on indirect addressing, which is the underlying hardware concept. The "handles" strategy in Rust feels like a kludgy approach not because it bypasses the hardware but because Rust's borrow checker isn't actually involved in ensuring safety in that case, just its bounds checking and mandatory initialization (and if all you need is those two things then...).
Actually, it is correct. The more generally you use "arenas" the more they are subject to the same kinds of issues as other manual memory management systems. "arenas" can only avoid/reduce the "nondeterminism" and "security" issues of general manual memory management on top of a buffer of bytes by not becoming general manual memory management on top of a buffer of bytes.
Normal pointers cause UB. That’s astronomically bad. If your arena pointers crash your program in a well-defined way, that’s already a much better situation.
Like if your arena contains both a buffer that OOB's and a buffer passed to a syscall, then having memory safety around the arena doesn't help you
I certainly appreciate the performance benefits of custom allocators but it's disheartening to see people naively adopting them just as the world's allocators are starting to get their acts together with regards to security.
The two times I've had to deal with a really tough debugging problem in Rust, it's been related to some crate which did that.
And from its tracking issue [1], it seems there's alternatives with really important trade-offs (especially the very interesting storage API alternative), and it'd be really sad if we got stuck with something that ends up being unusable in many cases people actually want to use them on.
[1] https://github.com/rust-lang/rust/issues/32838
The ability for crates to specify whether they use certain features of Rust:
- unsafe
- arena allocation or other future "useful" stuff
- proc_macros, eg. serde (a huge compile speed hit)
- deep transitive dependency (total #, or depth)
- some proxy for the "number of compiler steps" (compiler workload complexity)
We should be able to set a crate-wide or workspace-wide policy that can ban other crates that violate these rules.
We could make this hand-written early on, but eventually enforced by the compiler. You could then easily guarantee that no downstream dependency uses unsafe code, has a crazy number of dependencies, or has crazy compile times.
You could opt-in or opt-out to these things without having to think too much about them or constantly (manually) be on the lookout.
This would be hugely beneficial to the Rust ecosystem, safety, code quality, and developer productivity / happiness.
Perhaps what would be useful is crates.io determining through analysis which in the set of all lint(s) a crate is compatible with and exposing that as automatic metadata?
And I agree, a custom arena is usually the best option here. Even though it seems like "giving up" and going back to C, it's still way better.
There's this great comparison of Arenas in Rust: https://donsz.nl/blog/arenas/
Some of them have keys that can't be reused too, so you can avoid "use after free" style bugs (at runtime) which is way better than C pointer wrangling.
It's not perfect though. I kind of wish Rust did have some kind of support for this stuff natively. Pretty low on my list of Rust desires though - way behind better compile time and fewer async footguns.
Leaf pages in InnoDB’s B+tree implementation is the big one I can think of. Turns out being able to quickly walk pages for a range scan is helpful.
I agree that there isn’t wide variety of applications where they jump out as being the best choice. So, yeah, “approximately useless” sounds about right.