3 ms·
Unfortunate that the testing only covers the performance impact of the recursive calls used by the main implementation - a tuned binary search function would pr
by kevingadd 13y ago
Unfortunate that the testing only covers the performance impact of the recursive calls used by the main implementation - a tuned binary search function would probably not recurse and simply maintain a tiny stack of indices. The increased number of comparisons would probably matter a lot more in that case.
- munificent 13y ago> a tuned binary search function would probably not recurse and simply maintain a tiny stack of indices. You don't even need a stack. Binary search is an iterative process: int binarysearch(int a[], int k, int lo, int hi) { while (lo < hi) { int p = lo + (hi - lo) / 2; if (k < a[p]) { hi = p; } else if (k == a[p]) { return p; } else if (k > a[p]) { lo = p + 1; } } return -1; }
- penrod 13y agoQuite. I am puzzled by the article. As even the author points out, binary search is tail-recursive, and therefore trivially transformed to an iterative form. So why on earth profile a recursive implementation?
- munificent 13y agoThat was the big WTF for me too. Before you start microbenchmarking and talking about the machine instructions for a function call, get rid of the damn function call.
- CWuestefeld 13y agoAnd if we're talking about the cost in cycles of the operations for jump versus compare, shouldn't we also then consider the cost of the calculation of the pivot points? I haven't done assembly language in a couple of decades, but it seems to me that the cost of calculating the traditional pivot point will be rather cheaper than that for the dual pivots. At least back in the day, a division by two was a trivial operation (arithmetic shift right by 1), whereas the division by three would require an actual calculation: not a big deal, but more expensive than the ASR.
- deletes 13y agoIf your range is not too big( < 32768 ) and the divisor is constant you can do it with a single multiplication and a shift. More complicated method: http://www.hackersdelight.org/divcMore.pdf http://www.hackersdelight.org/divcMore.pdf But the compiler will( should, look at generated code ) optimize the constant division anyway. --- Behold, division by three using only addition and shifting( works up to 32767 ): unsigned int div3upto32767( unsigned int n ) { return ( ( n << 13 )+( n << 11 )+( n << 9 )+( n << 7 )+( n << 5 )+( n << 3 )+( n << 1 )+n ) >> 15 ; } --- This one works up to 32767, and then produces a wrong result every ~32767 numbers or so. The result is of by one. When you get over a million, every number is of by a couple of digits. uint64_t div3almost( uint64_t n ) { n -= ( n >> 15 ) ; return ( ( n << 13 )+( n << 11 )+( n << 9 )+( n << 7 )+( n << 5 )+( n << 3 )+( n << 1 )+n ) >> 15 ; } I don't think the additions are worth it.