3 ms·
You do additional comparisons at each recursion depth, but you have a shallower recursion depth though. I think you break-even already at 4-way search.
by gpderetta 3y ago
You do additional comparisons at each recursion depth, but you have a shallower recursion depth though. I think you break-even already at 4-way search.
- pclmulqdq 3y agoI think that only helps if you assume exactly 1.5 comparisons per level with a branch predictor, and I think that will be hard to hit: you basically need the comparison function to be very short to have that (shorter than the mispredict penalty). Then, you are doing 3 comparisons per two levels vs 3 comparisons for 2 levels. If you were to extend this logic to do 3 levels at a time, you would be doing 7 comparisons to do the same amount of work that the branch predictor does in expected <4.5 comparisons.
- gpderetta 3y agoOk, I have been nerd sniped. I need to get near a compiler and a profiler ASAP.