1

The OP here mentions in the final post (4th or so para from bottom):

"Now one thing that always bothered me about this is all the child pointer checking. There are usually a lot of null pointers, and waiting on memory access to fill the cache with zeros just seems stupid. Over time I added a byte that contains a 1 or 0 to tell if each of the pointers is NULL. At first this just reduced the cache waste. However, I've managed cram 9 distance comparisons, 8 pointer bits, and 3 direction bits all through some tables and logic to generate a single switch variable that allows the cases to skip the pointer checks and only call the relevant children directly. It is in fact faster than the above, but a lot harder to explain if you haven't seen this version."

He is referring to octrees as the data structure for real-time volume rendering. These would be allocated on the heap, due to their size. What I am trying to figure out is:

(a) Are his assumptions in terms of waiting on memory access, valid? My understanding is that he's referring to waiting on a full run out to main memory to fetch data, since he's assuming it won't be found in the cache due to generally not-too-good locality of reference when using dynamically-allocated octrees (common for this data structure in this sort of application).

(b) Should (a) prove to be true, I am trying to figure out how this workaround

Over time I added a byte that contains a 1 or 0 to tell if each of the pointers is NULL.

would be implemented without still using the heap, and thus still incurring the same overhead, since I assume it would need to be stored in the octree node.

1
  • Is... this question really that difficult to answer? I would have thought that at least (b) would be simple for one of the gurus around here to shed light on.
    – Engineer
    Nov 13, 2011 at 22:08

1 Answer 1

0

(a) Yes, his concerns about memory wait time are valid. In this case, he seems to be worried about the size of the node itself in memory; just the children take up 8 pointers, which is 64 bytes on a 64-bit architecture, or one cache line just for the children.

(b) That bitfield is stored in the node itself, but now takes up only 1 byte (1 bit for 8 pointers). It's not clear to me that this is an advantage though, as the line(s) containing the children will get loaded anyway when they are searched. However, he's apparently doing some bit tricks that allow him to determine which children to search with very few branches, which may increase performance. I wish he had some benchmarks that would show the benefit.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.