KD-Tree traversal without if-statements? back

(L) [2006/08/11] [Michael77] [KD-Tree traversal without if-statements?] Wayback!

Hi,


I am just wondering if it is possible to traverse a KD-Tree ( or BIH) without if-statements in the main loop just by using conditional assignments. Has anyone tried this? Is there any benefit from it. I just did a test run with VTune and is seems like most clockticks are spend on the jump-instructions. And considering the fact that my 1.7GHz Pentium M beats a 3.2GHz Xeon on the bunny benchmark, my guess is, I am giving the branch prediction some headache so removing some of the if instructions could possibly a great win.


Any ideas? I am currently trying this by using a stack approach but if someone already did something like that, I would love to hear it.


Michael

(L) [2006/08/11] [Phantom] [KD-Tree traversal without if-statements?] Wayback!

I believe Carsten Benthin's thesis (see links & papers) has kd-tree traversal pseudo code that doesn't use branches. He states that it isn't faster on average, though some cases benefit. Have a look at the thesis for details.
_________________
--------------------------------------------------------------

Whatever

(L) [2006/08/12] [tbp] [KD-Tree traversal without if-statements?] Wayback!

I've tried that way back when. Of course it didn't bear fruits as that was for a k8 that isn't branching-handicaped to begin with.

As it also raises the register pressure, i don't think it really makes sense but on x86-64.
_________________
May you live in interesting times.

[LINK https://gna.org/projects/radius/ radius] | [LINK http://ompf.org/ ompf] | [LINK http://ompf.org/wiki/ WompfKi]

(L) [2006/08/12] [Michael77] [KD-Tree traversal without if-statements?] Wayback!

Yes, you are right. I just implemented it (or sort of) and performance was a littlebit lower than when using if statements / conditionals. So I guess I will leave it as is and try to figure out other ways to improve performance (still thinking about using SAH on the BIH...).


Michael

(L) [2006/08/12] [Lerc] [KD-Tree traversal without if-statements?] Wayback!

I'd been mulling this one over too.  Tree traversal loops can be a killer on branch prediction.

My thought was that a non looping if statement might work.  Larger code but it lets branch prediction tag each branch with the last direction taken in the tree.


basicly going from