I actually use linked lists to reduce the number memory allocations and amount of memory required as opposed to, say, storing 160,000 dynamic arrays that grow for the grid which would have an explosive memory use (typically one pointer plus two integers at least per grid cell along with heap allocations per grid cell as opposed to just one integer and zero heap allocations per cell). Just wanted to chip in there since if you are using a data structure to store a boatload of elements, then 4-8 bytes may not always be so negligible. So 4-8 bytes actually isn't trivial in most of the contexts in which I use linked lists in the first place. 90% of the time I use linked lists, it's for cases like these, and so a tail pointer would actually be relatively quite expensive to store. Making it a doubly-linked list would double the list overhead of each particle. It also requires insertion to require a branch to check if the list is empty instead of being branchless. The linear-time removal from a cell isn't actually an overhead since we're processing the particle logic by iterating through the particles in a cell, so a doubly-linked list would just add overhead of a kind that isn't beneficial at all in my case just as a tail wouldn't benefit me at all either.Ī tail pointer would double the memory usage of the grid as well as increasing the number of cache misses. with the next index ("pointer") of a particle node serving as either an index to the next particle in the cell or the next free particle to reclaim if the particle has died (basically a free list allocator implementation using indices): ![]() Now as particles move around on the screen, all we have to do is update a few 32-bit integers to move a particle from one cell to the other, like so: In that case, a pretty efficient way to store that is to store 160,000 singly-linked lists, which translates to 160,000 32-bit integers in my case (~640 kilobytes) and one 32-bit integer overhead per particle. I also generally don't allocate list nodes one at a time and instead, again, just use a big array to store all the nodes and then use 32-bit indices to link the nodes together.Īs an example, imagine a video game using a 400x400 grid to partition a million particles which move around and bounce off of each other to accelerate collision detection. ![]() I use indices into an array instead since the indices can be 32-bit, e.g., taking half the space of a 64-bit pointer. I also generally don't use pointers for linked lists. Often my common case usage for a singly-linked list might store hundreds of thousands of linked lists which only contain a few list nodes each. It's because in my common use cases, the tail pointer is actually expensive, just as making the singly-linked list into a doubly-linked list is expensive. ![]() I rarely use a tail pointer for linked lists and tend to use singly-linked lists more often where a stack-like push/pop pattern of insertion and removal (or just linear-time removal from the middle) suffices.
0 Comments
Leave a Reply. |