11 ms·

Zig's new LinkedList API (it's time to learn fieldParentPtr)

227 points by todsacerdoti 2y ago

roetlich 2y ago
This looks somewhat horrifying. How do I safely write a function that takes a linked list as a parameter?
- the_mitsuhiko 2y ago
  > How do I safely write a function that takes a linked list as a parameter? Zig does not have a lot of generic code. You would pass the user directly and then walk the list or you use comptime. The real answer is that "you don't write code like that in Zig".
- reissbaker 2y ago
  Assuming you mean "how would I safely write a function that takes a generic linked list and does something with the data," I'm pretty sure you would use comptime: your function would take the concrete type (say, User) as a comptime parameter, and then you would do your list stuff via accessing .node and use the fieldParentPtr to access the underlying data. Syntactically I don't think it's that weird, TBH. And it's typesafe: if you write invalid code the compiler will give you an error.
  - fpoling 2y ago
    But how does the generic code know the name by which the field is known in the struct that contains the field? Is it supposed to be passed as an extra parameter to the generic function?
    - reissbaker 2y ago
      Yup, you could pass it in at comptime as well! And access via @field.
    - spiffyk 2y ago
      I think the more important question here is: What operations would you possibly want to do with a linked list that are generic and at the same time do something with the concrete data in it? To me these complaints sound like hypotheticals with no sound grounding in the real world. If there indeed is data that is common to the various types you would want to operate upon in such linked lists, you would nest. E.g. you would have some common Entity struct containing the common data and the LinkedList.Node; this Entity would then be inside your more concrete structs. The generic function would then take a pointer to Entity.
      - reissbaker 2y ago
        I think a pretty good example would be: how do you write a map function? Or filter, find, etc. (You would do it with more comptime, but the question is legitimate!)
        spiffyk 2y ago
        > how do you write a map function? Or filter, find, etc. You just don't. Zig does not have lambdas anyway, there's no readability incentive to having such functions there. You do these things with plain old loops built into the language.
        reissbaker 2y ago
        Zig has first-class functions (you can pass functions as parameters); it just doesn't have closures. Map pretty rarely uses closures anyway IME; e.g. converting a list to JSON doesn't need to close over outside variables. And anyway, anything that's: 1. Generic over lists, and 2. Takes a function as a parameter Will want to know what the node field name is. Luckily, comptime provides a solution there. TBH I think "you just don't" is a pretty unsatisfying answer to "how do I use these features that are built into Zig" — especially when you can use them, very easily.
        spiffyk 2y ago
        I mean yes, you can pass functions as parameters in Zig, you can even define them inline if you wrap them in anonymous structs, but my point is that — in a language where this is supported somewhat properly — you would do this to improve readability with some sort of a fluent API. If you attempt to do it in status-quo Zig, readability will only suffer and you are still much better off doing it with for and/or while loops (depending on the data structure), especially when Zig has nice syntax sugar with payloads in both to support these. edit: formatting
  - roetlich 2y ago
    Okay, thanks for explaining more. > And it's typesafe: if you write invalid code the compiler will give you an error. One more question, if @fieldParentPtr("node", n) is typesafe and can get you a User, the compiler needs to know that the struct has the fields of a User, and that this pointer is indeed pointing at a node field, right? Then why do you need to specify "node" at all? I think I don't understand Zig at all :)
    - messe 2y ago
      What if the User is in multiple linked lists? const User = struct { username: []const u8, id: u128, age: u7, sorted_by_age: std.SinglyLinkedList.Node, sorted_by_id: std.SinglyLinkedList.Node, };
  - boomlinde 2y ago
    @fieldParentPtr is not type safe. It assumes that the given pointer is to a field of the given name in the inferred type. Zig can detect at compile time whether the inferred type has a field of that name of the same type as the pointer child. So far, so good: type safe. The lack of safety stems from the fact it doesn't know that the assumption that the pointer has that parent is true. Here's a very simple illustration. It'll compile. const T = struct { field: i32 = 0, }; pub fn main() void { var nonfield: i32 = 0; _ = @as(*T, @fieldParentPtr("field", &nonfield)); } `nonfield` doesn't have a parent T. The use of @fieldParentPtr here causes what the official reference calls "unchecked illegal behavior"; it isn't checked even in the safe build modes.
    - grayhatter 2y ago
      > The use of @fieldParentPtr here [...] the *hypothetical* use here... This simple example as written is actually correct, and not actually unchecked illegal behavior. But this is just a bit of pedantry, because it would be unchecked illegal if you use this in a more complicated example. I mention it because it's important to note, it can be done correctly, as you obviously just did it correctly, by accident. That said, I still agree, there're no guardrails on this pattern.
      - boomlinde 2y ago
        > the hypothetical use here... No, it's not hypothetical. I just did it, which demonstrates that it's not type safe and that the compiler won't give you an error if you write invalid code, which is what the post I responded to claimed. > This simple example as written is actually correct No. The official reference is clear about this: "If field_ptr does not point to the field_name field of an instance of the result type, and the result type has ill-defined layout, invokes unchecked Illegal Behavior." Because there is no well-defined layout for plain structs in Zig, they satisfy the "ill-defined layout" requirement. Merely invoking the @fieldParentPtr on a pointer that doesn't satisfy the other requirement in that case invokes unchecked illegal behavior according to the language reference. > I mention it because it's important to note, it can be done correctly, Ignoring that you can't seem to get the facts straight, the claim I am responding to is that it's "type safe" and that "if you write invalid code the compiler will give you an error". This is not the case, regardless of whether my example invokes unchecked illegal behavior (which it does) or not. I'm very clearly not saying that it can't be done correctly and I don't think you can argue for that in good faith.
- GolDDranks 2y ago
  If you write a function that takes a _generic_ linked list as a parameter, you'd have a function that refers to just the linked list subrecord, and does only linked list operations to that and the linked nodes. If you want to write a function that takes a linked list of a specific type as a parameter, you just take in a value of that type. The linked list is baked in, so you can get to the other nodes, and because the type is known, you can get back to the parent type from the linked nodes with fieldParentPtr. How to do that _safely_? I don't think that Zig embraces any Rust-like safe/unsafe dichotomy, so you don't.
- flohofwoe 2y ago
  Since you don't need to care about the 'outer type' in that case you just pass a pointer to the linked list header or a linked list node and that's it. If you need to access the outer type, just pass a pointer to that type (since your functions need to know the outer type anyway I don't think there's a need to reach for generics).
  - skywal_l 2y ago
    You have to pass the field name too ("node").
    - flohofwoe 2y ago
      Not really. If you only want to manipulate the list, you only need a direct pointer to the nested node but don't need to know the 'outer type'. Only if the function takes a pointer to the outer type it needs to know how to get the pointer to the embedded node struct from the item pointer. ...I guess it makes a lot more sense if you ever wrote code for AmigaOS ;)
- kllrnohj 2y ago
  You don't & generally shouldn't be in the first place, in any language. Linked lists are a very niche data structure, so generic code should ~never be using them. So it's a moot question. It's kinda like the complaints about how hard a doubly linked list is in Rust - it's just not important because it's not something you should be using 99.999% of the time anyway.
  - roetlich 2y ago
    Well I personally almost never use linked lists, don't like them. But Zig seems to think otherwise, they have two implementations in the standard library. I don't know much Zig, I just wanted to ask how to use the type that the article talks about? Let's use the very simple example from the article. Let's say I want to extract this code into a function: while (node) |n| { const user: *User = @fieldParentPtr("node", n); std.debug.print("{any}\n", .{user}); node = n.next; } 1. How does that look, what's the type signature of this function? 2. What happens if I put in a list doesn't contain users? Do I get a simple to understand compile time error, or can I segfault because I'm accessing bad memory? And I don't think that would need any generics, since the list type isn't generic, right?
    - boomlinde 2y ago
      1. If you mean @fieldParentPtr, the first argument is a compile time-known name of a field, the second argument is a pointer to a field of that name in the parent type, which is inferred from the left hand side of the assignment 2. Then you're screwed. In Zig, using @fieldParentPtr on a field that doesn't have the given parent is unchecked illegal behavior, meaning that there are no checks that can catch it at compile time. This change basically guarantees that there will be a pretty serious foot gun every time you iterate over the items of a standard library list.
      - roetlich 2y ago
        Thank you, that answers all my questions.
      - 2y ago
- AndyKelley 2y ago
  Two points here: Linked lists are useful in unsafe code. Most recent use case I had for them was in an event loop with coroutines. It's not possible to implement such thing in memory safe languages. For example if you use Rust, you have to use unsafe [1]. @fieldParentPtr does not yet have safety but it is a planned upcoming change to the language, with a fairly straightforward implementation [2]. [1]: https://github.com/search?q=repo%3Atokio-rs%2Ftokio%20unsafe&type=code https://github.com/search?q=repo%3Atokio-rs%2Ftokio%20unsafe... [2]: https://github.com/ziglang/zig/issues/2414 https://github.com/ziglang/zig/issues/2414
  - roetlich 2y ago
    Oh, that makes more sense. Thank you! Is this linked list type then mostly meant to be used as an internal implementation detail, and not be exposed in a public API? Because if I see a function that takes a non-generic list I won't really know how to call it. :)
    - AndyKelley 2y ago
      Linked lists are sometimes the right tool for the job. They are available in the standard library for such cases. If you are struggling to understand how you would use this API then it probably means you have not yet been exposed to such a use case, and you are being quite intentionally steered away from using them.
      - roetlich 2y ago
        Fair, thanks.
spiffyk 2y ago
For better or worse, the Zig community has long been embracing the `@fieldParentPtr` builtin as the primary way to do things like OOP-ish inheritance, so this change feels pretty in-character for the language to me.
- Zambyte 2y ago
  Really? I did a quick grep in ghostty (160k lines of Zig) and found four total references to @fieldParentPtr. I'm still a Zig baby, but I have not seen very many references to @fieldParentPtr at all.
  - spiffyk 2y ago
    I would expect the inheritance pattern to be quite rare in performance-aware software design overall, since such constructs tend to be rather cache-unfriendly. So I would attribute the low number of references to inheritance being rare, rather than @fieldParentPtr not being used for inheritance.
steventhedev 2y ago
This feels like a net negative result. It removes some of the complexity of using generics, but it couples between the data type and the collections it can be indexed by. What are the benefits of this approach? Is it limited to data alignment, or is it out of a greater desire to remove generics?
- reissbaker 2y ago
  Zig has no desire to remove comptime AFAIK (comptime being the larger Zig feature by which people implement generics in the language) — comptime is pretty much the reason to use Zig. The benefits of intrusive linked lists are higher performance; you can use comptime to still have decoupled code.
  - kevin_thibedeau 2y ago
    C++20 has consteval to do the same thing.
  - surajrmal 2y ago
    The generic approach should be the same performance. This approach just lets you place your data in multiple lists without needing multiple allocations.
    - reissbaker 2y ago
      No, the generic approach requires your data to be spaced out further in memory (or to be heap allocated), which causes CPU cache misses and is slower. The entire reason for intrusive linked lists is performance. Standard linked lists are notoriously slow compared to almost any other similar data structure, which is why they are hardly ever used in real code (ArrayLists and vectors are much more common).
      - foldr 2y ago
        Maybe it requires this in Zig (I don’t know), but in general there’s no reason why you couldn’t allocate the nodes of an extrusive linked list from a pool residing on the heap or on the stack. For example, you could do this with the STL (for all that STL allocators are a pain to use in practice). Or you could have a slightly different API where you add nodes to the list by passing an entire Node<T> to the relevant function rather than just T, at which point you can trivially allocate the nodes as you please.
DeathArrow 2y ago
I wonder why should a language implement in its libraries a SingleLinkedList and a DoubleLinkedList. I do get why you need an array-like list, a dictionary/hashmap, a stack and a queue. I got the impression that linked lists aren't used very often. Or maybe it's a different case with Zig?
- messe 2y ago
  Maybe because it's used elsewhere in the standard library? SinglyLinkedList is used in the standard library in std.Thread.Pool, and std.heap.ArenaAllocator. DoublyLinkedList is used in the http client's connection pool, as well as the ObjectCache for the package manager's git client.
- boomlinde 2y ago
  > I got the impression that linked lists aren't used very often. I did some cursory research on the software I've been using today and presented the results here: https://news.ycombinator.com/item?id=43684121 https://news.ycombinator.com/item?id=43684121 I think there is a misconception around linked lists mostly stemming from the fact that they're not great for cache locality. Someone presents the idea that linked lists under common circumstances are unintuitively slow and therefore should be considered carefully for performance sensitive applications. A game of Chinese whispers immediately forms around that idea and what comes out the other end is a new idea: that linked lists are bad, shouldn't be used and aren't used. Meanwhile, they continue to be used extensively in system software.
  - bsder 2y ago
    Linked lists get a bad reputation because they wound up being a default data structure--and that's almost always a mistake on modern computers. Back in days of yore, small memory and CPU meant that linked lists and arrays were really the only effective data structures. Allocating and computation were super expensive, so following a link or having an index is really the only thing that works. On today's computers, CPU is so much faster than memory that it is almost always better to recompute a value than try to look it up. Locality is so important that linear actions trump asymptotic complexity until you get quite a lot more elements than you might expect. Memory is so cheap that it is worth exponentially overallocating in order to amortize complexity. etc. At the end of the day with modern programming, you should almost always be reaching for something simpler than a linked list (array/vector) or you should be reaching for an abstraction that is more complex than a linked list (hash/dict, queue/deque, etc.). With modern CPUs, if you are using a linked list for anything other than building a more complex data structure, you're probably making an incorrect choice on almost all fronts.
ralferoo 2y ago
I don't use Zig, but one advantage of having a genericised intrusive linked list where the next pointer doesn't have to be the first thing in the structure is when you want to use larger types, such as 128-bit fields. Sticking a pointer at the beginning would mean the compiler would have to insert alignment padding after the pointer or break the default alignment.
- jwmerrill 2y ago
  The next pointer doesn’t have to go first in the structure here. It can go anywhere, and you can use @fieldParentPtr to go back from a reference to the embedded node to a reference to the structure.
  - n42 2y ago
    I think that's the point the parent was making. I read it as them describing a benefit of Zig's approach.
    - ralferoo 2y ago
      Yeah, that's what I was trying to say, but obviously not clearly enough.
      - jwmerrill 2y ago
        My mistake! It seems clear in hindsight…
mastax 2y ago
> The new version isn't generic. Rather, you embed the linked list node with your data. This is known as an intrusive linked list and tends to perform better and require fewer allocations. I don’t get this. In the generic version the data is embedded with the linked list node, so there’s only one allocation per node. ‘T’ isn’t a pointer (or doesn’t have to be) there’s no indirection between data and node.
- CBLT 2y ago
  > only one allocation per node I believe the implication is there's fewer than one allocation per node with the new API. You allocate contiguous memory once, and use it to store n elements.
  - flowerthoughts 2y ago
    No, that's not stated. > The new version isn't generic. Rather, you embed the linked list node with your data. This is known as an intrusive linked list and tends to perform better and require fewer allocations. Except in trivial examples, the data that we store in a linked list is typically stored on the heap. Because an intrusive linked list has the linked list node embedded in the data, it doesn't need its own allocation. Is simply a misunderstanding. The storage layout will be the same for the generic and the intrusive one. The benefit of intrusive linked lists is that each node can be a member of several linked lists with a single allocation per node. This is used heavily e.g. in the Linux kernel. The cost is that you need to keep track of the offset from object address to which linked list pointer you're currently dealing with. That's often a compile time constant, but makes the API more awkward. In this case it seems to be the string "node", which seems nice enough. C libraries often use the preprocessor to do something similar.
  - mastax 2y ago
    new Node<TStruct>[16]; new TStructContainingNode[16]; What’s the difference?
    - ulbu 2y ago
      there’s 16 contiguously stored pointers to 16 non-contiguously stored tstructs (they may be contiguously stored, but you can’t make this assumption from this type). there’s 16 contiguously stored tstructcontainingnode’s.
lightingthedark 2y ago
Can someone explain how the claim of higher performance works here? In C, which lacks generics, an intrusive list is preferred because otherwise you end up with each node having a void pointer to the data it holds. The previous Zig version was a generic, so the data type could easily be a value type. Given that the compiler is allowed to rearrange the layout of both structs unless data is packed or extern (in which case it almost certainly won't want to have a linked list node in the middle anyway) isn't the resulting type exactly the same in memory unless you intentionally made T a pointer type?
- deleted 2y ago
  [deleted]
- ashdnazg 2y ago
  I don't understand the higher performance either. What I know as the significant advantage is that you can have one object in multiple lists.
  - lightingthedark 2y ago
    Technically that should be possible the other way by using a Node<T> so the type of the second list ends up being a Node<Node<T>> but I can see why an intrusive list would be preferred to that, and also the linked list API might prevent that pattern. Usually if I have multiple lists holding something I have one that's the 'owner' and then the secondary data structures would have a non-owning pointer to it. Is that the case where the performance would be better with an intrusive list? My intuition would be that having multiple Node members would pollute the cache and not actually be a performance win but maybe it is still better off because it's all colocated? Seems like the kind of thing I'd have to benchmark to know since it would depend on the number of lists and the size of the actual data.
    - lightingthedark 2y ago
      Okay so in the multiple list case performance would actually be worse because you'd have a double pointer dereference. I was thinking you'd have the list nodes contiguous in memory so the first dereference would always hit cache but that's a bad assumption for a linked list. Since you shouldn't reach for a linked list as a default data structure modern hardware anyway, I actually do see how this change makes sense for Zig. Neat!
hoseja 2y ago
Linked lists should be obscure niche data structures for when you absolutely need their unique characteristics, not some front-and-center default.
- netbsdusers 2y ago
  They're not obscure or niche, they are everywhere in operating systems. The linked list is probably the single most essential and the most used data structure in any kernel.
  - simonask 2y ago
    Implementing an operating system is incredibly niche and obscure. The practices that apply to kernel development do not generally apply to very much else.
  - fcantournet 2y ago
    Ah yes, operating system kernels, famously super mainstream programs that almost everyone works on.
    - deleted 2y ago
      [deleted]
- grayhatter 2y ago
  This is true for the kind of programmin most people do. Linked Lists make no sense in JS, Python, Rust, etc. But they are without a doubt still an incredibly useful pattern with unmatched performance characteristics. Especially if you're trying to be memory efficient. It's a systems programming pattern, rarely useful if you're just a web developer. But then again... I never thought I'd need to know music waveform theory while I was watching the magic school bus as a kid... Turns out that was incredibly useful when I needed to implement a music note generator for a VoIP client... You never know when something might actually be really useful.
  - simonask 2y ago
esjeon 2y ago
Hmph, is there any rationale against a generic wrapper over it? Exposing the internal details can be irky in higher level application development. It would not hurt to have some inline functions.
MawKKe 2y ago
Isn't the new one also horribly type-unsafe? Since you can put (parent) objects of any kind into the list without any mechanism to detect which is which?
mgaunard 2y ago
There are several advantages to intrusive node-based data structures that I haven't seen stated in the article or the comments: - the same object can move between containers with no allocation and no need for a dedicated complex API - the same object can be part of multiple containers at once; particularly useful for intrusive binary trees, for indexing data with different criteria. - the container can be fully polymorphic, no need for all elements to be the same dynamic type. - no need for complex allocators, you can just store the objects as you see fit.
- rowanG077 2y ago
  All of these sound like grievous sources of bugs to me. Sure it's nice that it's possible but please don't do those things unless there isn't a safer way to do it.
  - Diggsey 2y ago
    They are definitely more error-prone usage patterns, and coming from Rust the amount of hidden unsafety is quite unsettling (in addition to the obvious potential for user errors, depending on the aliasing model of your language/compiler, which I suspect Zig hasn't figured out yet, this parent pointer trick could even lead to miscompilations...) Having said that, intrusive linked lists are quite an important data structure in code which is required to be allocation-free. Kernel code, signal handlers and code which requires consistent performance (eg. audio processing) need to be able to move objects between containers or have objects in multiple containers without allocating.
    - bananabiscuit 2y ago
      Do you mean you will likely make an error when implementing a standard textbook linked list? Or that a standard textbook linked list has non-obvious errors in its design? If so, would be curious to learn more.
      - im3w1l 2y ago
        Implementing anything is more error prone than using something battle-tested.
deleted 2y ago
[deleted]
deleted 2y ago
[deleted]
kajika91 2y ago
Couldn't we have a function to return the data like this? pub const SinglyLinkedList(comptime T: type) type { return struct { first: ?*Node = null, pub const Node = struct { next: ?*Node = null, }; const Self = @This(); pub fn data(self: Self) *T { return @fieldParentPtr("node", self); } };
- deleted 2y ago
  [deleted]
- nh1996 2y ago
  This would require the SinglyLinkedList to be generic and would require that the data struct use "node" as the field name. Also, as some comments have pointed out, this type of linked list can be useful when a data struct needs to be in multiple lists, in which case there is no single "node" field. const some_data = struct { // Some data fields // ... bar_node: SinglyLinkedList.Node, baz_node: SinglyLinkedList.Node, };
  - throwawaymaths 2y ago
    sure, just make T == void fall back to the existing implementation.
budmichstelk 2y ago
[dead]
RcouF1uZ4gsC 2y ago
Awesome! In my opinion, an intrusive linked-list is almost always what you really want when you reach for a linked list. An external linked list is often worse than a vector.
alexvitkov 2y ago
Please just use a pointer. Use metaprogramming when it makes sense, not to obfuscate something that was figured out 60 years ago.
bmandale 2y ago
A few notes I would make as an outsider: - conventionally we put the `node' struct at the start of the `user' struct. The advantage is that we can convert from node* to user* with a simple cast instead of messing around with offsets. Knowing the offset stuff is still potentially useful in case you want multiple `node's in a single struct, but that is seldom the case so you can almost always get by with just a cast. - this strategy is, especially with the node at the start of the user, equivalent to inheritance. I take it from the fine article that zig doesn't have inheritance? If they are planning on adding more interfaces like this linked list one, then inheritance would be a good idea. We often treat inheritance using analogies to the animal kingdom or to geometric shapes, but data structures like linked lists are (to my understanding) the problem that inheritance is actually designed to solve, and it is really the best approach to solving problems like in the OP. - just lol on zig speed running being a crappier C++.
RKFADU_UOFCCLEL 2y ago
This is in fact a com.on technique in the Linux kernel: https://en.wikipedia.org/wiki/Offsetof#Usage https://en.wikipedia.org/wiki/Offsetof#Usage
zoogeny 2y ago
> We give @fieldParentPtr the name of the field, a pointer to that field as well as a return type (which is inferred above by the assignment to a *User variable), and it gives us back the instance that contains that field. That seems like a refactoring nightmare. If I say: const user: *NotAUser = @fieldParentPtr("node", n); Will it calculate this incorrectly? I mean, if `NotAUser` has a "node" field and `n` is actually from the `User` type (and it has a different offset in each type)?
tpayet 2y ago
I read Zig's new LinkedIn API, and I was intrigued
codr7 2y ago
Not super uncommon in C land, I learned the technique from the Linux kernel. https://github.com/codr7/hacktical-c/tree/main/list https://github.com/codr7/hacktical-c/tree/main/list Haven't come across another language (besides Zig maybe) low level enough for it to make sense. I've tried in C++ and Go, but it gets so ugly that it loses its appeal.
xmorse 2y ago
It would be cool if Zig added a .. syntax, the same way . gets a child field, .. gets the parent field Then the code would become ``` const user: *User = n.. ``` Now it's easier to understand that .. is simply getting the parent struct.

227 points by todsacerdoti 2y ago

roetlich 2y ago

This looks somewhat horrifying. How do I safely write a function that takes a linked list as a parameter?

the_mitsuhiko 2y ago
> How do I safely write a function that takes a linked list as a parameter? Zig does not have a lot of generic code. You would pass the user directly and then walk the list or you use comptime. The real answer is that "you don't write code like that in Zig".
reissbaker 2y ago
Assuming you mean "how would I safely write a function that takes a generic linked list and does something with the data," I'm pretty sure you would use comptime: your function would take the concrete type (say, User) as a comptime parameter, and then you would do your list stuff via accessing .node and use the fieldParentPtr to access the underlying data. Syntactically I don't think it's that weird, TBH. And it's typesafe: if you write invalid code the compiler will give you an error.
- fpoling 2y ago
  But how does the generic code know the name by which the field is known in the struct that contains the field? Is it supposed to be passed as an extra parameter to the generic function?
  - reissbaker 2y ago
    Yup, you could pass it in at comptime as well! And access via @field.
  - spiffyk 2y ago
    I think the more important question here is: What operations would you possibly want to do with a linked list that are generic and at the same time do something with the concrete data in it? To me these complaints sound like hypotheticals with no sound grounding in the real world. If there indeed is data that is common to the various types you would want to operate upon in such linked lists, you would nest. E.g. you would have some common Entity struct containing the common data and the LinkedList.Node; this Entity would then be inside your more concrete structs. The generic function would then take a pointer to Entity.
    - reissbaker 2y ago
      I think a pretty good example would be: how do you write a map function? Or filter, find, etc. (You would do it with more comptime, but the question is legitimate!)
      - spiffyk 2y ago
        > how do you write a map function? Or filter, find, etc. You just don't. Zig does not have lambdas anyway, there's no readability incentive to having such functions there. You do these things with plain old loops built into the language.
        reissbaker 2y ago
        Zig has first-class functions (you can pass functions as parameters); it just doesn't have closures. Map pretty rarely uses closures anyway IME; e.g. converting a list to JSON doesn't need to close over outside variables. And anyway, anything that's: 1. Generic over lists, and 2. Takes a function as a parameter Will want to know what the node field name is. Luckily, comptime provides a solution there. TBH I think "you just don't" is a pretty unsatisfying answer to "how do I use these features that are built into Zig" — especially when you can use them, very easily.
        spiffyk 2y ago
        I mean yes, you can pass functions as parameters in Zig, you can even define them inline if you wrap them in anonymous structs, but my point is that — in a language where this is supported somewhat properly — you would do this to improve readability with some sort of a fluent API. If you attempt to do it in status-quo Zig, readability will only suffer and you are still much better off doing it with for and/or while loops (depending on the data structure), especially when Zig has nice syntax sugar with payloads in both to support these. edit: formatting
- roetlich 2y ago
  Okay, thanks for explaining more. > And it's typesafe: if you write invalid code the compiler will give you an error. One more question, if @fieldParentPtr("node", n) is typesafe and can get you a User, the compiler needs to know that the struct has the fields of a User, and that this pointer is indeed pointing at a node field, right? Then why do you need to specify "node" at all? I think I don't understand Zig at all :)
  - messe 2y ago
    What if the User is in multiple linked lists? const User = struct { username: []const u8, id: u128, age: u7, sorted_by_age: std.SinglyLinkedList.Node, sorted_by_id: std.SinglyLinkedList.Node, };
- boomlinde 2y ago
  @fieldParentPtr is not type safe. It assumes that the given pointer is to a field of the given name in the inferred type. Zig can detect at compile time whether the inferred type has a field of that name of the same type as the pointer child. So far, so good: type safe. The lack of safety stems from the fact it doesn't know that the assumption that the pointer has that parent is true. Here's a very simple illustration. It'll compile. const T = struct { field: i32 = 0, }; pub fn main() void { var nonfield: i32 = 0; _ = @as(*T, @fieldParentPtr("field", &nonfield)); } `nonfield` doesn't have a parent T. The use of @fieldParentPtr here causes what the official reference calls "unchecked illegal behavior"; it isn't checked even in the safe build modes.
  - grayhatter 2y ago
    > The use of @fieldParentPtr here [...] the *hypothetical* use here... This simple example as written is actually correct, and not actually unchecked illegal behavior. But this is just a bit of pedantry, because it would be unchecked illegal if you use this in a more complicated example. I mention it because it's important to note, it can be done correctly, as you obviously just did it correctly, by accident. That said, I still agree, there're no guardrails on this pattern.
    - boomlinde 2y ago
      > the hypothetical use here... No, it's not hypothetical. I just did it, which demonstrates that it's not type safe and that the compiler won't give you an error if you write invalid code, which is what the post I responded to claimed. > This simple example as written is actually correct No. The official reference is clear about this: "If field_ptr does not point to the field_name field of an instance of the result type, and the result type has ill-defined layout, invokes unchecked Illegal Behavior." Because there is no well-defined layout for plain structs in Zig, they satisfy the "ill-defined layout" requirement. Merely invoking the @fieldParentPtr on a pointer that doesn't satisfy the other requirement in that case invokes unchecked illegal behavior according to the language reference. > I mention it because it's important to note, it can be done correctly, Ignoring that you can't seem to get the facts straight, the claim I am responding to is that it's "type safe" and that "if you write invalid code the compiler will give you an error". This is not the case, regardless of whether my example invokes unchecked illegal behavior (which it does) or not. I'm very clearly not saying that it can't be done correctly and I don't think you can argue for that in good faith.
GolDDranks 2y ago
If you write a function that takes a _generic_ linked list as a parameter, you'd have a function that refers to just the linked list subrecord, and does only linked list operations to that and the linked nodes. If you want to write a function that takes a linked list of a specific type as a parameter, you just take in a value of that type. The linked list is baked in, so you can get to the other nodes, and because the type is known, you can get back to the parent type from the linked nodes with fieldParentPtr. How to do that _safely_? I don't think that Zig embraces any Rust-like safe/unsafe dichotomy, so you don't.
flohofwoe 2y ago
Since you don't need to care about the 'outer type' in that case you just pass a pointer to the linked list header or a linked list node and that's it. If you need to access the outer type, just pass a pointer to that type (since your functions need to know the outer type anyway I don't think there's a need to reach for generics).
- skywal_l 2y ago
  You have to pass the field name too ("node").
  - flohofwoe 2y ago
    Not really. If you only want to manipulate the list, you only need a direct pointer to the nested node but don't need to know the 'outer type'. Only if the function takes a pointer to the outer type it needs to know how to get the pointer to the embedded node struct from the item pointer. ...I guess it makes a lot more sense if you ever wrote code for AmigaOS ;)
kllrnohj 2y ago
You don't & generally shouldn't be in the first place, in any language. Linked lists are a very niche data structure, so generic code should ~never be using them. So it's a moot question. It's kinda like the complaints about how hard a doubly linked list is in Rust - it's just not important because it's not something you should be using 99.999% of the time anyway.
- roetlich 2y ago
  Well I personally almost never use linked lists, don't like them. But Zig seems to think otherwise, they have two implementations in the standard library. I don't know much Zig, I just wanted to ask how to use the type that the article talks about? Let's use the very simple example from the article. Let's say I want to extract this code into a function: while (node) |n| { const user: *User = @fieldParentPtr("node", n); std.debug.print("{any}\n", .{user}); node = n.next; } 1. How does that look, what's the type signature of this function? 2. What happens if I put in a list doesn't contain users? Do I get a simple to understand compile time error, or can I segfault because I'm accessing bad memory? And I don't think that would need any generics, since the list type isn't generic, right?
  - boomlinde 2y ago
    1. If you mean @fieldParentPtr, the first argument is a compile time-known name of a field, the second argument is a pointer to a field of that name in the parent type, which is inferred from the left hand side of the assignment 2. Then you're screwed. In Zig, using @fieldParentPtr on a field that doesn't have the given parent is unchecked illegal behavior, meaning that there are no checks that can catch it at compile time. This change basically guarantees that there will be a pretty serious foot gun every time you iterate over the items of a standard library list.
    - roetlich 2y ago
      Thank you, that answers all my questions.
    - 2y ago
AndyKelley 2y ago
Two points here: Linked lists are useful in unsafe code. Most recent use case I had for them was in an event loop with coroutines. It's not possible to implement such thing in memory safe languages. For example if you use Rust, you have to use unsafe [1]. @fieldParentPtr does not yet have safety but it is a planned upcoming change to the language, with a fairly straightforward implementation [2]. [1]: https://github.com/search?q=repo%3Atokio-rs%2Ftokio%20unsafe&type=code https://github.com/search?q=repo%3Atokio-rs%2Ftokio%20unsafe... [2]: https://github.com/ziglang/zig/issues/2414 https://github.com/ziglang/zig/issues/2414
- roetlich 2y ago
  Oh, that makes more sense. Thank you! Is this linked list type then mostly meant to be used as an internal implementation detail, and not be exposed in a public API? Because if I see a function that takes a non-generic list I won't really know how to call it. :)
  - AndyKelley 2y ago
    Linked lists are sometimes the right tool for the job. They are available in the standard library for such cases. If you are struggling to understand how you would use this API then it probably means you have not yet been exposed to such a use case, and you are being quite intentionally steered away from using them.
    - roetlich 2y ago
      Fair, thanks.

spiffyk 2y ago

For better or worse, the Zig community has long been embracing the `@fieldParentPtr` builtin as the primary way to do things like OOP-ish inheritance, so this change feels pretty in-character for the language to me.

Zambyte 2y ago
Really? I did a quick grep in ghostty (160k lines of Zig) and found four total references to @fieldParentPtr. I'm still a Zig baby, but I have not seen very many references to @fieldParentPtr at all.
- spiffyk 2y ago
  I would expect the inheritance pattern to be quite rare in performance-aware software design overall, since such constructs tend to be rather cache-unfriendly. So I would attribute the low number of references to inheritance being rare, rather than @fieldParentPtr not being used for inheritance.

steventhedev 2y ago

This feels like a net negative result. It removes some of the complexity of using generics, but it couples between the data type and the collections it can be indexed by. What are the benefits of this approach? Is it limited to data alignment, or is it out of a greater desire to remove generics?

reissbaker 2y ago
Zig has no desire to remove comptime AFAIK (comptime being the larger Zig feature by which people implement generics in the language) — comptime is pretty much the reason to use Zig. The benefits of intrusive linked lists are higher performance; you can use comptime to still have decoupled code.
- kevin_thibedeau 2y ago
  C++20 has consteval to do the same thing.
- surajrmal 2y ago
  The generic approach should be the same performance. This approach just lets you place your data in multiple lists without needing multiple allocations.
  - reissbaker 2y ago
    No, the generic approach requires your data to be spaced out further in memory (or to be heap allocated), which causes CPU cache misses and is slower. The entire reason for intrusive linked lists is performance. Standard linked lists are notoriously slow compared to almost any other similar data structure, which is why they are hardly ever used in real code (ArrayLists and vectors are much more common).
    - foldr 2y ago
      Maybe it requires this in Zig (I don’t know), but in general there’s no reason why you couldn’t allocate the nodes of an extrusive linked list from a pool residing on the heap or on the stack. For example, you could do this with the STL (for all that STL allocators are a pain to use in practice). Or you could have a slightly different API where you add nodes to the list by passing an entire Node<T> to the relevant function rather than just T, at which point you can trivially allocate the nodes as you please.

DeathArrow 2y ago

I wonder why should a language implement in its libraries a SingleLinkedList and a DoubleLinkedList. I do get why you need an array-like list, a dictionary/hashmap, a stack and a queue. I got the impression that linked lists aren't used very often. Or maybe it's a different case with Zig?

messe 2y ago
Maybe because it's used elsewhere in the standard library? SinglyLinkedList is used in the standard library in std.Thread.Pool, and std.heap.ArenaAllocator. DoublyLinkedList is used in the http client's connection pool, as well as the ObjectCache for the package manager's git client.
boomlinde 2y ago
> I got the impression that linked lists aren't used very often. I did some cursory research on the software I've been using today and presented the results here: https://news.ycombinator.com/item?id=43684121 https://news.ycombinator.com/item?id=43684121 I think there is a misconception around linked lists mostly stemming from the fact that they're not great for cache locality. Someone presents the idea that linked lists under common circumstances are unintuitively slow and therefore should be considered carefully for performance sensitive applications. A game of Chinese whispers immediately forms around that idea and what comes out the other end is a new idea: that linked lists are bad, shouldn't be used and aren't used. Meanwhile, they continue to be used extensively in system software.
- bsder 2y ago
  Linked lists get a bad reputation because they wound up being a default data structure--and that's almost always a mistake on modern computers. Back in days of yore, small memory and CPU meant that linked lists and arrays were really the only effective data structures. Allocating and computation were super expensive, so following a link or having an index is really the only thing that works. On today's computers, CPU is so much faster than memory that it is almost always better to recompute a value than try to look it up. Locality is so important that linear actions trump asymptotic complexity until you get quite a lot more elements than you might expect. Memory is so cheap that it is worth exponentially overallocating in order to amortize complexity. etc. At the end of the day with modern programming, you should almost always be reaching for something simpler than a linked list (array/vector) or you should be reaching for an abstraction that is more complex than a linked list (hash/dict, queue/deque, etc.). With modern CPUs, if you are using a linked list for anything other than building a more complex data structure, you're probably making an incorrect choice on almost all fronts.

ralferoo 2y ago

I don't use Zig, but one advantage of having a genericised intrusive linked list where the next pointer doesn't have to be the first thing in the structure is when you want to use larger types, such as 128-bit fields. Sticking a pointer at the beginning would mean the compiler would have to insert alignment padding after the pointer or break the default alignment.

jwmerrill 2y ago
The next pointer doesn’t have to go first in the structure here. It can go anywhere, and you can use @fieldParentPtr to go back from a reference to the embedded node to a reference to the structure.
- n42 2y ago
  I think that's the point the parent was making. I read it as them describing a benefit of Zig's approach.
  - ralferoo 2y ago
    Yeah, that's what I was trying to say, but obviously not clearly enough.
    - jwmerrill 2y ago
      My mistake! It seems clear in hindsight…

mastax 2y ago

> The new version isn't generic. Rather, you embed the linked list node with your data. This is known as an intrusive linked list and tends to perform better and require fewer allocations. I don’t get this. In the generic version the data is embedded with the linked list node, so there’s only one allocation per node. ‘T’ isn’t a pointer (or doesn’t have to be) there’s no indirection between data and node.

CBLT 2y ago
> only one allocation per node I believe the implication is there's fewer than one allocation per node with the new API. You allocate contiguous memory once, and use it to store n elements.
- flowerthoughts 2y ago
  No, that's not stated. > The new version isn't generic. Rather, you embed the linked list node with your data. This is known as an intrusive linked list and tends to perform better and require fewer allocations. Except in trivial examples, the data that we store in a linked list is typically stored on the heap. Because an intrusive linked list has the linked list node embedded in the data, it doesn't need its own allocation. Is simply a misunderstanding. The storage layout will be the same for the generic and the intrusive one. The benefit of intrusive linked lists is that each node can be a member of several linked lists with a single allocation per node. This is used heavily e.g. in the Linux kernel. The cost is that you need to keep track of the offset from object address to which linked list pointer you're currently dealing with. That's often a compile time constant, but makes the API more awkward. In this case it seems to be the string "node", which seems nice enough. C libraries often use the preprocessor to do something similar.
- mastax 2y ago
  new Node<TStruct>[16]; new TStructContainingNode[16]; What’s the difference?
  - ulbu 2y ago
    there’s 16 contiguously stored pointers to 16 non-contiguously stored tstructs (they may be contiguously stored, but you can’t make this assumption from this type). there’s 16 contiguously stored tstructcontainingnode’s.

lightingthedark 2y ago

Can someone explain how the claim of higher performance works here? In C, which lacks generics, an intrusive list is preferred because otherwise you end up with each node having a void pointer to the data it holds. The previous Zig version was a generic, so the data type could easily be a value type. Given that the compiler is allowed to rearrange the layout of both structs unless data is packed or extern (in which case it almost certainly won't want to have a linked list node in the middle anyway) isn't the resulting type exactly the same in memory unless you intentionally made T a pointer type?

deleted 2y ago
[deleted]
ashdnazg 2y ago
I don't understand the higher performance either. What I know as the significant advantage is that you can have one object in multiple lists.
- lightingthedark 2y ago
  Technically that should be possible the other way by using a Node<T> so the type of the second list ends up being a Node<Node<T>> but I can see why an intrusive list would be preferred to that, and also the linked list API might prevent that pattern. Usually if I have multiple lists holding something I have one that's the 'owner' and then the secondary data structures would have a non-owning pointer to it. Is that the case where the performance would be better with an intrusive list? My intuition would be that having multiple Node members would pollute the cache and not actually be a performance win but maybe it is still better off because it's all colocated? Seems like the kind of thing I'd have to benchmark to know since it would depend on the number of lists and the size of the actual data.
  - lightingthedark 2y ago
    Okay so in the multiple list case performance would actually be worse because you'd have a double pointer dereference. I was thinking you'd have the list nodes contiguous in memory so the first dereference would always hit cache but that's a bad assumption for a linked list. Since you shouldn't reach for a linked list as a default data structure modern hardware anyway, I actually do see how this change makes sense for Zig. Neat!

hoseja 2y ago

Linked lists should be obscure niche data structures for when you absolutely need their unique characteristics, not some front-and-center default.

netbsdusers 2y ago
They're not obscure or niche, they are everywhere in operating systems. The linked list is probably the single most essential and the most used data structure in any kernel.
- simonask 2y ago
  Implementing an operating system is incredibly niche and obscure. The practices that apply to kernel development do not generally apply to very much else.
- fcantournet 2y ago
  Ah yes, operating system kernels, famously super mainstream programs that almost everyone works on.
  - deleted 2y ago
    [deleted]
grayhatter 2y ago
This is true for the kind of programmin most people do. Linked Lists make no sense in JS, Python, Rust, etc. But they are without a doubt still an incredibly useful pattern with unmatched performance characteristics. Especially if you're trying to be memory efficient. It's a systems programming pattern, rarely useful if you're just a web developer. But then again... I never thought I'd need to know music waveform theory while I was watching the magic school bus as a kid... Turns out that was incredibly useful when I needed to implement a music note generator for a VoIP client... You never know when something might actually be really useful.
- simonask 2y ago

esjeon 2y ago

Hmph, is there any rationale against a generic wrapper over it? Exposing the internal details can be irky in higher level application development. It would not hurt to have some inline functions.

MawKKe 2y ago

Isn't the new one also horribly type-unsafe? Since you can put (parent) objects of any kind into the list without any mechanism to detect which is which?

mgaunard 2y ago

There are several advantages to intrusive node-based data structures that I haven't seen stated in the article or the comments: - the same object can move between containers with no allocation and no need for a dedicated complex API - the same object can be part of multiple containers at once; particularly useful for intrusive binary trees, for indexing data with different criteria. - the container can be fully polymorphic, no need for all elements to be the same dynamic type. - no need for complex allocators, you can just store the objects as you see fit.

rowanG077 2y ago
All of these sound like grievous sources of bugs to me. Sure it's nice that it's possible but please don't do those things unless there isn't a safer way to do it.
- Diggsey 2y ago
  They are definitely more error-prone usage patterns, and coming from Rust the amount of hidden unsafety is quite unsettling (in addition to the obvious potential for user errors, depending on the aliasing model of your language/compiler, which I suspect Zig hasn't figured out yet, this parent pointer trick could even lead to miscompilations...) Having said that, intrusive linked lists are quite an important data structure in code which is required to be allocation-free. Kernel code, signal handlers and code which requires consistent performance (eg. audio processing) need to be able to move objects between containers or have objects in multiple containers without allocating.
  - bananabiscuit 2y ago
    Do you mean you will likely make an error when implementing a standard textbook linked list? Or that a standard textbook linked list has non-obvious errors in its design? If so, would be curious to learn more.
    - im3w1l 2y ago
      Implementing anything is more error prone than using something battle-tested.

deleted 2y ago

[deleted]

deleted 2y ago

[deleted]

kajika91 2y ago

Couldn't we have a function to return the data like this? pub const SinglyLinkedList(comptime T: type) type { return struct { first: ?*Node = null, pub const Node = struct { next: ?*Node = null, }; const Self = @This(); pub fn data(self: Self) *T { return @fieldParentPtr("node", self); } };

deleted 2y ago
[deleted]
nh1996 2y ago
This would require the SinglyLinkedList to be generic and would require that the data struct use "node" as the field name. Also, as some comments have pointed out, this type of linked list can be useful when a data struct needs to be in multiple lists, in which case there is no single "node" field. const some_data = struct { // Some data fields // ... bar_node: SinglyLinkedList.Node, baz_node: SinglyLinkedList.Node, };
- throwawaymaths 2y ago
  sure, just make T == void fall back to the existing implementation.

budmichstelk 2y ago

[dead]

RcouF1uZ4gsC 2y ago

Awesome! In my opinion, an intrusive linked-list is almost always what you really want when you reach for a linked list. An external linked list is often worse than a vector.

alexvitkov 2y ago

Please just use a pointer. Use metaprogramming when it makes sense, not to obfuscate something that was figured out 60 years ago.

bmandale 2y ago

A few notes I would make as an outsider: - conventionally we put the `node' struct at the start of the `user' struct. The advantage is that we can convert from node* to user* with a simple cast instead of messing around with offsets. Knowing the offset stuff is still potentially useful in case you want multiple `node's in a single struct, but that is seldom the case so you can almost always get by with just a cast. - this strategy is, especially with the node at the start of the user, equivalent to inheritance. I take it from the fine article that zig doesn't have inheritance? If they are planning on adding more interfaces like this linked list one, then inheritance would be a good idea. We often treat inheritance using analogies to the animal kingdom or to geometric shapes, but data structures like linked lists are (to my understanding) the problem that inheritance is actually designed to solve, and it is really the best approach to solving problems like in the OP. - just lol on zig speed running being a crappier C++.

RKFADU_UOFCCLEL 2y ago

This is in fact a com.on technique in the Linux kernel: https://en.wikipedia.org/wiki/Offsetof#Usage https://en.wikipedia.org/wiki/Offsetof#Usage

zoogeny 2y ago

> We give @fieldParentPtr the name of the field, a pointer to that field as well as a return type (which is inferred above by the assignment to a *User variable), and it gives us back the instance that contains that field. That seems like a refactoring nightmare. If I say: const user: *NotAUser = @fieldParentPtr("node", n); Will it calculate this incorrectly? I mean, if `NotAUser` has a "node" field and `n` is actually from the `User` type (and it has a different offset in each type)?

tpayet 2y ago

I read Zig's new LinkedIn API, and I was intrigued

codr7 2y ago

Not super uncommon in C land, I learned the technique from the Linux kernel. https://github.com/codr7/hacktical-c/tree/main/list https://github.com/codr7/hacktical-c/tree/main/list Haven't come across another language (besides Zig maybe) low level enough for it to make sense. I've tried in C++ and Go, but it gets so ugly that it loses its appeal.

xmorse 2y ago

It would be cool if Zig added a .. syntax, the same way . gets a child field, .. gets the parent field Then the code would become ``` const user: *User = n.. ``` Now it's easier to understand that .. is simply getting the parent struct.