5 ms·

Is it reasonable to estimate that the performance of this code will be bounded by log2(n) memory round-trips per lookup? If so then could you double performanc

• jsnell 9y ago
  Have a look at https://arxiv.org/abs/1509.05053 https://arxiv.org/abs/1509.05053 from pkhuong. They discuss this issue and other variants that paper. So e.g. branchless binary search, the branchy binary search + speculative execution as a form of prefetching, branchless binary search with explicit prefetching.
  • lukego 9y ago
    Seriously awesome paper! The answer seems to be "yes" judging by their dramatic conclusion: > Our conclusion is contrary to our expectations and to previous findings and goes against conventional wisdom, which states that accesses to RAM are slow, and should be minimized. A more accurate statement, that accounts for our findings, is that accesses to RAM have high latency and this latency needs to be mitigated. In other words: to optimize memory access you should think like a network engineer - treat RAM as a "long fat pipe" and do the usual optimizations like pipelining that you would in TCP or HTTP or .... Related: "Computer architecture for network engineers." https://github.com/lukego/blog/issues/18 https://github.com/lukego/blog/issues/18.