Timeline for Is there any study or theory behind combining binary search and interpolation search?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 17, 2016 at 5:40 | comment | added | Neil Slater | @liori: Definitely I/O per midpoint was the main factor when indexing a log file, as it was being read on demand in order to find records. There was probably more than two orders of magnitude between calculating offset in file and reading a block - therefore number of midpoints calculated would be the deciding factor. I think if I replicate now without a log file to index - something I will try and post here - that there might not be a measurable speed difference, but there might be a measurable "number of midpoints needed" difference. | |
| Jun 17, 2016 at 0:56 | comment | added | Peter Cordes |
However, memory latency is much worse than memory bandwidth, since even multiple scattered accesses go faster if they're in flight at once. It's a win to prefetch (with prefetcht0 instructions) both possibilities for the NEXT iteration before loading the current midpoint, for an in-memory bsearch on modern x86 hardware. You can't do that if you can't predict the next fetch addresses ahead of time. So practical implementation details can be significant, aside from theoretical considerations.
|
|
| Jun 17, 2016 at 0:54 | comment | added | Peter Cordes | Also, even for an in-memory search, a cache miss (over 200 cycles latency) has a couple times the latency of even a 64bit integer division (32-96cycles), on Intel Haswell for example. 32bit integer division is significantly faster (22-29cycles). Main memory bandwidth is a shared resource for all cores, but integer division only uses resources duplicated on each core. | |
| Jun 17, 2016 at 0:47 | comment | added | Peter Cordes | @liori: The early few iterations of repeated binary searches on the same data might be more cache-friendly, because the same few elements are used. So the quarters and maybe eighths can be expected to stay hot in cache. Starting with binary and switching to interpolated after three iterations might make sense, if the ranges are big enough. (Or if you can do async I/O and use whichever result arrives first). | |
| Jun 17, 2016 at 0:26 | comment | added | liori | You wrote: "a binary search iteration is hundreds of times faster than an interpolation search one". Please note that in OP's case, the difference between computing the midpoint in those two methods is dwarfed by the I/O time necessary to retrieve the midpoint's value. | |
| Jun 16, 2016 at 21:11 | history | answered | Tom van der Zanden | CC BY-SA 3.0 |