Hacker News Reader

Comment by ajross | Hacker News Reader

> Mumble mumble kernel embedded something something intrusive.

And this is why kernel/embedded/something/something developers don't take Rust as seriously as you want them to.

You can't simultaneously declare your language the best choice for system software development and treat the long-evolved patterns of those paradigms as a joke.

There are very good reasons for intrusive data structures, not least of which being their ability to operate in contexts where no heap is available. If you don't understand them or don't want to talk about them or want to limit your discussion to situations with different requirements, then say so.

View on HN

The actual context of your quote:

> Just so we're totally 100% clear: I hate linked lists. With a passion. Linked lists are terrible data structures. Now of course there's several great use cases for a linked list: > > - You're writing a kernel/embedded thing and want to use an intrusive list.

So I’ve got no clue what you’re railing about. The project specifically acknowledges that there is a need in kerneldev for those data structures.

I’m a kernel dev using Rust for my kernel. I use both intrusive linked list and growable vectors in it. The thing is, the sentiment expressed in the article really resonates in me: in most cases, growable vectors are a better choice, performance-wise.

The quote that the GP is talking about is included below, which copy/pasted from the project page, and the Mumble mumble line is the heading for a paragraph:

‘’’Mumble mumble kernel embedded something something intrusive.

It's niche. You're talking about a situation where you're not even using your language's runtime. Is that not a red flag that you're doing something strange?

It's also wildly unsafe.’’’

Also, prior to this author claims the following, where the first line also a section heading:

‘’’ I can't afford amortization

You've already entered a pretty niche space’’’

These fiat rulings based on one an authors generalization of what is ‘niche’ are what I assume GP was commenting on. These are the kinds of dismissals that some developers take issue with, as GP states.

Kernel development is niche. Most of the time you don’t need linked lists.

When all you have is Rust everything starts to look like adjustable array.

Rust has singly linked, double linked ( in its minimal std library) and intrusive linked lists - all with APIs that guarantee a lack of memory errors and data races at compiler. I don’t know any good kernel developer that wouldn’t like those guarantees and I work in the Linux kernel professionally full time.

What’s an adjustable array? A vector?

A vector is a one-dimensional array. Adjustable arrays can have arbitrary number of dimensions, although am not sure if it's a thing in Rust.

I've spent years programming rust and I'm not sure what you mean. Do you mean arrays of tuples, or nested arrays?

I mean a multi-dimensional array.

Thanks! Why does everything look like a multi-dimensional array for you in rust?

An array (an ADT) can be arbitrary dimensional, with one-dimensional case often called vector (and two-dimensional called matrix). An array can also be adjustable, both in one and multi-dimension variants.

So a vector can be both adjustable and non adjustable, and some language do have both versions. Some language have adjustable one-dimensional array/vector as the only dynamic aggregate/ordered datatype.

And to answer the post I replied to originally, a vector in rust is a one-dimensional adjustable array. To answer your question above, no that's not what I meant, sorry for not being clear enough from the beginning.

Thanks for clarifying.

I think we're just using different definitions. The only real definition of an array I've encountered in work and school is that it's just a one dimensional collection of elements, usually of static size. A vector depending on context is usually the same thing as an array but you conveniently change the size dynamically. Lists can whatever you need it to be given the context, just needs to be sequential.

Of course you can represent higher dimension structures by linearizing indices (x + row_size * y, etc).

I think people are getting confused as most don't consider arrays to be arbitrarily dimensional without some scheme.

Completely off topic but you've reminded me of this great article: https://hypirion.com/musings/understanding-persistent-vector...

That just sounds like a graph.

How in the heaven an array can sound like a graph?

Sounds like one to me.

If you can't tell when to break or not break rules then maybe you are not a kernel developer? It's almost like a King only following his own laws instead of being the one making them. Why are you a King again?

(Had to edit in a quote to what I was replying to because you fixed the original):

> The actual context of your fake quote:

Good grief, that was a verbatim quote! Here's a link to the exact text I quoted:

https://rust-unofficial.github.io/too-many-lists/#mumble-mum...

I think it must be stressed that this is an unofficial guide and not "the voice of the project", etc...

It explicitly says that there are good use cases, just that they’re very rare.

It does not. Maybe somewhere else it does. That section, verbatim, says:

It's niche. You're talking about a situation where you're not even using your language's runtime. Is that not a red flag that you're doing something strange?

It's also wildly unsafe.

But sure. Build your awesome zero-allocation lists on the stack.

And this is (1) wildly mistating the requirements and (2) deeply offensive to those of us who work in those regimes.

Obviously, yes, there's room for a reasoned argument about this stuff and whether alternative paradigms can be deployed in heapless contexts. This isn't it.

> (2) deeply offensive to those of us who work in those regimes

You know how sometimes someone who is A Little Too Online gets offended because they think you said a Bad Thing, but it was actually just a typo or a straight misreading, and you try to explain that they’re reacting to something you didn’t even say let alone believe, but because they have already decided you are the Bad Person they interpret that as you “doubling down“ on the bad opinion that they attributed to you, so they get even angrier and even more convinced that you sincerely believe the Bad Thing?

I mean no judgment. We all have such sensitivities. But maybe now you see how easily you can wind up on the wrong side of a public debate by searching for offense where there is in fact none.

> And this is (1) wildly mistating the requirements and (2) deeply offensive to those of us who work in those regimes.

Care to expand how? While not a kernel dev, I've had my share of use cases where I've done exactly this kind of thing in gamedev, and I simply cannot bring myself to disagree with what's been said, or see what's offensive.

It's strange, debugging when the pointers get corrupted by other code exhibiting UB is painful, it's a potential multithreading hazard, and flat contiguous arrays are frequently more appropriate - but it's sometimes useful. It's not arguing that an alternative paradigm can - or even should - be deployed in a heapless context. It's explicitly admitting that intrusive linked lists are an appropriate paradigm.

> It's a fine data structure with several great use cases, but those use cases are exceptional, not common.

https://github.com/Amanieu/intrusive-rs implements what you're looking for with no heap. There's no need to flame or misrepresent what the book says (no one said embedded was a joke). The Rust embedded community is strong.

You're like the sixth person to argue I'm somehow "misrepresenting" what is being said in this book? I'm quoting it directly. The "flame" is in the original, and I'm responding to it.

Take it out. It's bad.

Assuming that you're not trolling, I'll explain how you misinterpreted what you read: the section that you quoted is a sub-heading under:

> An Obligatory Public Service Announcement

which is an argument that:

> Linked lists are as niche and vague of a data structure as a trie.

The author then goes on to state that many people have contacted him to argue that linked lists are not niche and he puts each of those arguments under a heading:

> Mumble mumble kernel embedded something something intrusive.

is one such heading. Inside of it, he continues the argument that linked lists for embedded no-heap scenarios are niche and—to continue his argument—we therefore shouldn't be teaching undergrads linked lists just like we don't teach them tries.

I think what ajross is arguing is that it is the author of the tutorial who is trolling here. It is all true what you and everyone else say against ajross‘ argument on the purely factual layer, it is just that the tone of the PSA is needlessly aggressive and condescending.

To explain what I think this comment means. When working on embedded systems, you can interact with hardware devices by writing directly to specially mapped memory areas.

E.g., if you want to write text to a small screen, the kernel driver gives you a memory region that you write bytes to, and they're shown on the screen immediately, without requiring the CPU.

> To explain what I think this comment means. When working on embedded systems, you can interact with hardware devices by writing directly to specially mapped memory areas.

And why can't you do this in rust?

You can. Rust allows full memory addressing.

There's nothing to prevent you from doing this, although you may have to wrap it in an unsafe block.

They're saying more that intrusive data structures are really nice in situations that restrict heap allocation. The memory overhead outside of the structures linked together is O(1), because all of the per object metadata is stored in the objects themselves. That means consumers generally don't have to be hardcoded for certain number of objects like you would for an array/vector that doesn't have access to a heap.

My feelings, too. I do both embedded programming (in C/C++ and CUDA) and Erlang programming for a living. Erlang, too, doesn't let you (easily) write your own linked list structures, etc.

But for embedded programming with tight memory or performance constraints these data structures are essential so we use C++ or even C. They're well understood and the implementations have simple, elegant solutions.

For "safety" when we don't need absolute control, we'll choose a GC language like C# or F#. No need for the complication of Rust.

Rust gives you just as much control as C when you need it.

I may be mistaken, but if using unsafe does not allow for the ‘borrow-checker’ to be turned off and allow for code which doesn’t abide by the checker’s requirements, then it clearly does not give “as much control as C”. Again, I might have missed some of the subtleties of circumventing Rust’s static checking, but I don’t think I can purposely create some non-deterministic racy-appearing abstractions, which would be trivial to do using global variables in C.

You can't turn off the borrow checker for references, but Rust also provides raw pointers which are not subject to borrow checking (these are exactly like pointers in C, and can be cast to and from references (this is a no-op at runtime since they share the same memory representation)).

https://doc.rust-lang.org/1.30.0/book/first-edition/raw-poin...

You can create and manipulate raw pointers in safe code, but dereferencing them requires an `unsafe` block.

AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced, and C inherits these requirements. This means that it might be desirable to restrict creation and manipulation of raw pointers to unsafe code in Rust as well, if this can be done without introducing undue incompatibilities.

(Rust editions would naturally allow for this: Rust 2021 would warn on creating/manipulating raw pointers in Safe Rust, and stop warning for "unnecessary" use of unsafe deriving from these operations; Rust 2024 would make these a hard error ouside `unsafe`.)

> AIUI, there are some hardware architectures where even creating a wild pointer might be undefined behavior, regardless of whether that pointer is subsequently dereferenced

Would you be able to point me to some references for such hardware? Im not sure how that would work (at least based on my admittedly limited amount of experience). Wouldn’t a pointer look like any other integer right up until it’s used as a memory operand? Or would said architecture have some way to distinguish pointers and a “regular” integer in registers?

Allegedly, some platforms have pointer trap representations, where a certain pointer can be created, but may not be used in any operations of that type. No modern systems have such trap representations for pointer types, but the C standard inherits their legacy, and, more importantly, C compilers use it as justification for certain types of optimizations. Since it's not a hardware limitation, Rust can perfectly well take the opposite path and say that the compiler may not use it for those optimizations.

https://stackoverflow.com/questions/6725809/trap-representat...

> No modern systems have such trap representations for pointer types

This may be incidentally true, but "address sanitizer"-like features are becoming more common on modern hardware, and while these do not currently trap on creation/manipulation of a 'wild' pointer (since, strictly speaking, a trap only happens on dereferencing), there's no solid reason to expect this to remain the case in the future.

I don't see how you could trap creation or manipulation, since those pointers are stored in registers and/or memory, and both are fundamentally untyped. How would the hardware even know that something is a pointer, on any architecture that is popular today?

Because you use typed instructions to access them. For example, on ARM with pointer authentication you’ll sign pointers and unsign them right before using them. If you forge a pointer it’ll cause a crash when it’s used because its signature will be incorrect.

But that would still happen at the point of dereference, no? Or does it allow to tag even operations like moves and adds?

> C compilers use it as justification for certain types of optimizations

I believe that the Rust compiler is free to make it's own choices about what is considered valid, and which optimisations it wants to enable. It doesn't need to follow C's lead here.

isn't that what I said

Maybe. Or maybe you'd just change it so 'wild pointers' created in safe code are stored as ints on that architecture.

> if using unsafe does not allow for the ‘borrow-checker’ to be turned off and allow for code which doesn’t abide by the checker’s requirements

It allows the latter. 'Code that doesn't abide by the checker's requirements' uses separate facilities that are only allowed in unsafe code. This means that `unsafe` doesn't have to turn off anything, and further pinpoints the parts of the code where caution is needed in order to maintain the invariants that Safe Rust is based on.

Unsafe doesn’t turn off the borrow checker, but it does give you access to pointers that aren’t checked.

> if using unsafe does not allow for the ‘borrow-checker’ to be turned off and allow for code which doesn’t abide by the checker’s requirements

It does, that’s why it’s there.

Reply on news.ycombinator.com