News for hackers. Stuff that matters.
Re:CPU Cache Essentials by gioele on Thursday June 26, 2014 @02:10AM (#7948325)
> 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.).

Re:CPU Cache Essentials by ANTSANTS on Thursday June 26, 2014 @08:14PM (#7952189)
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

Re:CPU Cache Essentials by devbug on Friday June 27, 2014 @05:05PM (#7956301)
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...

Edit: And I completely forgot to mention the performance concerns of having multiple cores touch the same memory: irregular stalls!

Re:CPU Cache Essentials by Arelius on Thursday June 26, 2014 @02:59AM (#7948428)
Or even better, how about we just have an array of only alive objects.