4 ms·

> use as much of cache line as possible. > For example in the next code when else clause is happening, we are throwing complete cache line which was fetched by

by gioele 12y ago

> use as much of cache line as possible. > For example in the next code when else clause is happening, we are throwing complete cache line which was fetched by accessing the is_alive member struct Obj { bool is_alive; … }; std::vector<Object> objs; for (auto o: objs) { if (o.is_alive) do_stuff(o); else { // just thrown a cache line } } So, how do you fix that? My first idea would be to remove the is_alive member from the objects and creating a is_alive array of boolean, one for each object. But this opens a whole new set of problems (how to map from objects to is_alive indexes, static vs dynamic set of object that can be alive, etc.).

Arelius 12y ago
Or even better, how about we just have an array of only alive objects.
ANTSANTS 12y ago
If you really want to optimize data cache usage, use a bitvector and (either through compiler intrinsics or inline assembly) your CPU's bit-scanning instructions. This can reduce the storage requirement to 1 bit per object and skip up to 32 or 64 not-alive objects in a single instruction. https://news.ycombinator.com/item?id=6176091 https://news.ycombinator.com/item?id=6176091
- devbug 12y ago
  As Arelius mentioned, it is more performant to just keep an array of alive objects as you're only touching memory that needs to be touched. That said, however, bitvictors/bitsets are incredibly useful if you have no easy or clean way of separating variations of objects. An example would be "scene-graphs" in my game engine. Ostensibly they are stored as components (but my game engine doesn't have components) which are accessed by an unique identifier via an indirection table. Something like Bitsquid.[0] Like Bitsquid, my "scene-graphs" can be linked to other "scene-graphs." This allows me to "glue" weapons to character's hands or armour to their torsos. This means I have "scene-graphs" that can be updated (nodes repositioned) in parallel (as they have no data dependencies) and others that cannot (linked "scene-graphs"). For performance reasons, I identify which "scene-graphs" can be updated in parallel, so I can kick them off to appropriate tasks which satisfy their data-dependencies. Thus enters the bitvector/bitset because copying my "scene-graphs" around and then adjusting other "scene-graphs" pointers (that point to the moved "scene-graph") when linking or unlinking results in a complete iteration (once if you batch) over all the "scene-graphs," or some form of indirection (some with memory fragmentation too!). Not to mention such approach complicates the code for handling "scene-graphs" a lot. Beyond that, I have to sort my "scene-graphs" (pointer list) by link depth when updating, so I don't update children before their parents, and the like. It's messy, but bitvectors/bitsets are a great solution. I am experimenting with other methods to manage linked "scene-graphs" which fall under a split (linked/unlinked) array method, but I don't have anything yet, especially when I consider that I get a free iteration over all scene-graphs anyways (which hides a lot of the cost of the current method). [0]: http://bitsquid.blogspot.ca/2011/09/managing-decoupling-part-4-id-lookup.html http://bitsquid.blogspot.ca/2011/09/managing-decoupling-part... Edit: And I completely forgot to mention the performance concerns of having multiple cores touch the same memory: irregular stalls!

by gioele 12y ago

Arelius 12y ago

Or even better, how about we just have an array of only alive objects.

ANTSANTS 12y ago

If you really want to optimize data cache usage, use a bitvector and (either through compiler intrinsics or inline assembly) your CPU's bit-scanning instructions. This can reduce the storage requirement to 1 bit per object and skip up to 32 or 64 not-alive objects in a single instruction. https://news.ycombinator.com/item?id=6176091 https://news.ycombinator.com/item?id=6176091

devbug 12y ago
As Arelius mentioned, it is more performant to just keep an array of alive objects as you're only touching memory that needs to be touched. That said, however, bitvictors/bitsets are incredibly useful if you have no easy or clean way of separating variations of objects. An example would be "scene-graphs" in my game engine. Ostensibly they are stored as components (but my game engine doesn't have components) which are accessed by an unique identifier via an indirection table. Something like Bitsquid.[0] Like Bitsquid, my "scene-graphs" can be linked to other "scene-graphs." This allows me to "glue" weapons to character's hands or armour to their torsos. This means I have "scene-graphs" that can be updated (nodes repositioned) in parallel (as they have no data dependencies) and others that cannot (linked "scene-graphs"). For performance reasons, I identify which "scene-graphs" can be updated in parallel, so I can kick them off to appropriate tasks which satisfy their data-dependencies. Thus enters the bitvector/bitset because copying my "scene-graphs" around and then adjusting other "scene-graphs" pointers (that point to the moved "scene-graph") when linking or unlinking results in a complete iteration (once if you batch) over all the "scene-graphs," or some form of indirection (some with memory fragmentation too!). Not to mention such approach complicates the code for handling "scene-graphs" a lot. Beyond that, I have to sort my "scene-graphs" (pointer list) by link depth when updating, so I don't update children before their parents, and the like. It's messy, but bitvectors/bitsets are a great solution. I am experimenting with other methods to manage linked "scene-graphs" which fall under a split (linked/unlinked) array method, but I don't have anything yet, especially when I consider that I get a free iteration over all scene-graphs anyways (which hides a lot of the cost of the current method). [0]: http://bitsquid.blogspot.ca/2011/09/managing-decoupling-part-4-id-lookup.html http://bitsquid.blogspot.ca/2011/09/managing-decoupling-part... Edit: And I completely forgot to mention the performance concerns of having multiple cores touch the same memory: irregular stalls!