Cache coherence is king, also neat to use linear/pool allocators whenever possible. I am somewhat fond of realizing I can do that in modern C++ anyways, while avoiding most of the oop nonesense.
I know this is a toy example, but can't appending a node potentially cause all of the pointers to be invalidated if the dynamic array needs to allocate a bigger chunk of memory?
Yes, unless Odin does something truly wild(!) behind the scenes like mmap a terabyte of virtual memory for every [dynamic] array or something. Even worse if the video author themselves didn't realize -- my guess is the author is mostly familiar with garbage collected environments, isn't used to working with pointers, and just want to encourage memory pooling or arena allocation in general and picked an unfortunate way to show it. Instead of returning pointers, one way to solve it would be to just return opaque IDs or something like that (indices into the array, for example) that act like Node pointers -- if the language provides the option to overload "dereferencing" (like in C++/Nim/Rust/etc., I don't know if Odin can do this).
@@frankhestvik9859 I imagine the video maker is very familiar with manual memory environments, but mapped an example that used an arena or bump allocator onto a dynamic array for simplicity of explanation.
Yes, in that case, you can use ids rather than pointers, or make sure not to keep pointers across calls that may realloc, or use a larger preallocated pool, etc
isn't what you showed basically a pool allocator? and what's the point of using a linked list when using vectors in the background anyways? (I'm just curious)
You still keep the properties of why you want a linked list. It allows you to add and remove items faster, because you don't need to moving memory around. Arrays/Vector/dynamic arrays are just blocks of memory.
I am more of an array person myself, you often do not need to store pointers. But grouped lifetime thinking can also be applied to tree like structures (and if you are weird you can see a link list as a tree where every node only has at most one child). Linked lists have some advantages over array,s especially in the functional programming realm where they are a persistent data structure.
Yeah it is basically a pool allocator The linked list example is just as an example - because that's something we learn very early and it's usually the individually allocated elements way That said, you can still back a linked list with a pool (probably different to this one so you don't get reallocations) and get decent cache locality while maintaining characteristics you want from the list (->next, ->prev) Why you'd want that just depends on what you are working on
i have been playing with arena allocators in C for a month now, i even built some data structures on top of them like "vectors" but i am starting to feel like these types of allocators are mostly powerful for game development and not so much systems programming (which is what i mainly do) i say this because i only hear game developers talking about this, and from my little experience im not entirely sold on them right now, maybe i'm just using them badly but i feel like there is some mental overhead and rewriting with this paradigm
It's interesting that you say that because I feel the exact opposite way Once I started thinking in groups, it became much easier to program What do you usually do in systems programming?
@@DylanFalconer i'm a student taking a class on low level programming in C in which we are asked to frequently write console applications for linux/unix systems, i just came back to this video because today i received an assignment in which grouped lifetime thinking is probably the best way to solve my problem efficiently. so i guess i was totally wrong because i actually did exactly what you described in your video, we had to implement a kind of stack that rotates and in which you had to pop and push elements sometimes. i used a memory pool with a free list to keep track of which elements were popped so i can reuse their slots and it worked wonderfully!
This seems nonsensical or a misunderstanding. The "individual" in "individual lifetimes" that Rust focuses on is a completely different concept than the "individual malloc()/free() calls can cause fragmentation"; that's like conflating the size of a for loop in the source with the number of iterations during run-time. In practice it might actually be the opposite: Rust's type system is such a pedantic pain in the ass that people end up "giving up" on their (usually bad) linked list/heap-node strategies and instead just go back to using a vector/ECS/data-oriented approach, e.g. backed by vector storage or an arena/pool allocator, which tend to be much simpler to do in Rust -- and which is exactly what this video seemingly would argue for... I mean this is why I don't like Rust either, but to say it doesn't encourage data-oriented design seems wrong. The main problem you would have in Rust with this code tho is that it would (correctly) tell you that what you're doing is bullshit because you're returning pointers into a seemingly dynamically allocated array that may move around on the heap (unless Odin does something truly wild like map every dynamic array to its own terabyte of virtual memory).
Cache coherence is king, also neat to use linear/pool allocators whenever possible. I am somewhat fond of realizing I can do that in modern C++ anyways, while avoiding most of the oop nonesense.
Also neat to sometimes leverage globals, const or not, for static storage. And stack too.
Somehow I also became a huge fan of templates, something I once sought to destroy.
It is really good for performance and I find it to be much easier to reason about
I know this is a toy example, but can't appending a node potentially cause all of the pointers to be invalidated if the dynamic array needs to allocate a bigger chunk of memory?
Yes, unless Odin does something truly wild(!) behind the scenes like mmap a terabyte of virtual memory for every [dynamic] array or something. Even worse if the video author themselves didn't realize -- my guess is the author is mostly familiar with garbage collected environments, isn't used to working with pointers, and just want to encourage memory pooling or arena allocation in general and picked an unfortunate way to show it.
Instead of returning pointers, one way to solve it would be to just return opaque IDs or something like that (indices into the array, for example) that act like Node pointers -- if the language provides the option to overload "dereferencing" (like in C++/Nim/Rust/etc., I don't know if Odin can do this).
@@frankhestvik9859 I imagine the video maker is very familiar with manual memory environments, but mapped an example that used an arena or bump allocator onto a dynamic array for simplicity of explanation.
Yes, in that case, you can use ids rather than pointers, or make sure not to keep pointers across calls that may realloc, or use a larger preallocated pool, etc
isn't what you showed basically a pool allocator? and what's the point of using a linked list when using vectors in the background anyways? (I'm just curious)
Maybe educational purposes, Idk.
You still keep the properties of why you want a linked list. It allows you to add and remove items faster, because you don't need to moving memory around. Arrays/Vector/dynamic arrays are just blocks of memory.
I am more of an array person myself, you often do not need to store pointers. But grouped lifetime thinking can also be applied to tree like structures (and if you are weird you can see a link list as a tree where every node only has at most one child). Linked lists have some advantages over array,s especially in the functional programming realm where they are a persistent data structure.
Yeah it is basically a pool allocator
The linked list example is just as an example - because that's something we learn very early and it's usually the individually allocated elements way
That said, you can still back a linked list with a pool (probably different to this one so you don't get reallocations) and get decent cache locality while maintaining characteristics you want from the list (->next, ->prev)
Why you'd want that just depends on what you are working on
Same, in practice I usually use arrays for most things unless there's some good reason not to
you might be the only newsletter i subscribed to that i actually read. Amazing articles and video explanations
That means a lot! Thank you
i have been playing with arena allocators in C for a month now, i even built some data structures on top of them like "vectors" but i am starting to feel like these types of allocators are mostly powerful for game development and not so much systems programming (which is what i mainly do)
i say this because i only hear game developers talking about this, and from my little experience im not entirely sold on them right now, maybe i'm just using them badly but i feel like there is some mental overhead and rewriting with this paradigm
It's interesting that you say that because I feel the exact opposite way
Once I started thinking in groups, it became much easier to program
What do you usually do in systems programming?
@@DylanFalconer i'm a student taking a class on low level programming in C in which we are asked to frequently write console applications for linux/unix systems, i just came back to this video because today i received an assignment in which grouped lifetime thinking is probably the best way to solve my problem efficiently.
so i guess i was totally wrong because i actually did exactly what you described in your video, we had to implement a kind of stack that rotates and in which you had to pop and push elements sometimes. i used a memory pool with a free list to keep track of which elements were popped so i can reuse their slots and it worked wonderfully!
What is this language?
Odin
This also explains why Rust's philosophy is not so great since it is focused on managing individual lifetimes.
This seems nonsensical or a misunderstanding. The "individual" in "individual lifetimes" that Rust focuses on is a completely different concept than the "individual malloc()/free() calls can cause fragmentation"; that's like conflating the size of a for loop in the source with the number of iterations during run-time. In practice it might actually be the opposite: Rust's type system is such a pedantic pain in the ass that people end up "giving up" on their (usually bad) linked list/heap-node strategies and instead just go back to using a vector/ECS/data-oriented approach, e.g. backed by vector storage or an arena/pool allocator, which tend to be much simpler to do in Rust -- and which is exactly what this video seemingly would argue for... I mean this is why I don't like Rust either, but to say it doesn't encourage data-oriented design seems wrong.
The main problem you would have in Rust with this code tho is that it would (correctly) tell you that what you're doing is bullshit because you're returning pointers into a seemingly dynamically allocated array that may move around on the heap (unless Odin does something truly wild like map every dynamic array to its own terabyte of virtual memory).
i'm 4 minutes in and you still haven't got to the point