Log in

(no subject)

Well, I never let ignorance stop me before, so here is my speculation on some answers to your interesting questions. That said, you might wish to contact the author. I believe that his email address is publicly available.

I would create a big array for all the objects, with the big boys at the end and an index to the last non-big-boy element. Each element has all the pointers needed to maintain the octtree (though the internal nodes could be allocated in a separate array if desired). The key point is that objects might be omitted from the octtree, but they remain in the underlying array. Alternatively, if the number of objects is not known up front, use a separate set of links to track the full set of objects (and follow these links instead of indexing through the array in the steps below).

So when it comes time to restructure the octtree, just start from the beginning, doing the non-big-boy elements in parallel, the doing the big-boy elements sequentially. This essentially discards the old octtree.

If it was desireable to incrementally update the octtree, first remove the big-boy elements sequentially, do the incremental update in parallel, then re-insert the big-boy elements, again, sequentially.

I have no idea what the best-case and worst-case distributions would look like. Why not try a few and see?

The author addressed the question about distributions by agreeing, and noting that his goal was to demonstrate one case where his lossy technique was useful. Determining the technique's area of applicability is future work, and he seemed to welcome help with this work.

Oddly enough, when used this way, xchg() still has CAS's branch overhead. The thing is that although the xchg()'s insertion is guaranteed to succeed, it might cause some other insertion to fail, hence returning a non-NULL pointer. To the xchg() has to retry not for its own failure, but for the failures that it induces.

Comment Form

No HTML allowed in subject


Notice! This user has turned on the option that logs your IP address when posting. 

(will be screened)