(here’s part 1 and part 2 if you missed them)
(full sample code through part 3 is here)
Finally! We’ve covered enough foundation to introduce something “new”. Though not really new at all, perhaps just less obvious.
Let’s remember back to our “boring” CS102 Data Structures class, and bring back the linked-list. A singly-linked list would do for these purposes, but I’ll make it doubly-linked anyway, as it’ll prove to be greatly advantageous in the future. (assuming I actually get around to writing a “part 4” of this series to cover insert/remove, maybe a “part 5” to cover entity pool maintenance, etc)
At this point we don’t need anything “fancy”, and in fact we can just install our linked list “over the top” in-place within the existing entity list:
|
1 2 3 4 5 6 7 8 9 |
do local prev = nil for i = 1, #entityList do local entity = entityList[i] entity.prev = prev entity.next = (i==#entityList and nil) or entityList[i+1] end end local head = entityList[1] |
If linked-lists are new to you, all that code is doing is giving each entity a “pointer” to it’s “neighbors”. We also save the first of those links in the variable “head”.
The real surprise, though, is iteration. The lowly while loop, which is entirely generic and not optimized for any particular use over another, really shines:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
-- benchmark "linked list" iteration -- do local function fn() local entity = head while (entity) do entity = entity.next end end local elapsed = bench(fn,NREPS) print("linked list", elapsed-baseline) end |
Again, as before, I won’t post my own test results. Instead I suggest you run it for yourself. No guarantees, but I’d be surprised if you didn’t find the linked list iteration to be easily another 10% or so faster than “for i” (which was our previous performance winner from part 2)
(full sample code through part 3 is here)
That’s all for now, but if you’re at all familiar with linked lists then it ought to be obvious where this series is heading. Things like insert/remove in the context of an entity pool system become absolutely trivial with doubly-linked lists. Until then…