# Costs of lookups versus calculations

I am interested in setting up calculations to check if a distance criterion is satisfied: that is, the distance between a vector ${\bf x}_i$ and anther vector ${\bf x}_j$ should be less than some value $r_{\rm max}$. My data is partitioned according to an orthogonal grid of coordinates. Since my cutoff is smaller than the distance between the endpoints of nearest-neighbor coordinates, I'd like to add an "octant" variable to check if things are set up correctly:

if octant[j] in allowed_list continue


as a "short-circuit" to

if dist(x[i], x[j]) < r_max


My question is: how efficient computationally are boolean lookups and comparisons relative to floating-point operations? Is this worth doing on modern architectures?

• Would you be willing to branch your code and test it? I feel like the standard answer to most of these "Is better to code it (one way) or (some other way)?" types of questions is "Try it and benchmark it." – Geoff Oxberry Jun 8 '12 at 11:41
• Just my 2 cents. As Geoff wrote, this kind of advice is what I always got when I asked similar questions on stackoverflow, regarding the C++ code: code everything first, organize the code so that i remains modular and re-usable, and only then start refactoring. There is an 80-20 rule: software spends 80 % of time on 20 % of the code. Wait until the structure is up, and then change, test, change, test.. – tmaric Jun 8 '12 at 12:40
• @GeoffOxberry: My question is not so specific: I just want to know if there's a hardware or compiler advantage given to doing a boolean check compared to doing a floating-point operation. – aeismail Jun 8 '12 at 12:49
• But your question is too general. Nobody can tell without seeing some concrete code. There's a rule of thumb that says that even the best programmers can't tell where the bottlenecks of their code is without profiling. I've spent my past 25 years programming and I know it's true for me. – Wolfgang Bangerth Jun 8 '12 at 21:49

My rule of thumb is that if you can compute some quantity efficiently (good utilization of the FPU) in less than 50 flops per double precision value, it's better to recompute than to store. The trend, which has been steady for decades, is for floating point capability to improve faster than memory performance, and is not likely to relent due to physical constraints and energy requirements of fast memory. The value of 50 is of the right magnitude for all popular computing platforms (Intel/AMD, Blue Gene, and GPUs).

### Approximate cost estimates per core

[guidelines for 2011/2012 Intel- and AMD-based machines]

• $0.05$ ns: time to do one double precision floating point operation as part of a vectorized code without data dependencies and interleaved multiply/add
• $0.2$ ns: time to do one non-vectorized floating point operation without vectorization or data dependencies
• $0.4$ ns: time to do one non-vectorized floating point operation without vectorization or data dependencies, but without interleaved multiply/add (1 clock cycle)
• $0.4$ to $0.8$ ns: latency to reference L1 cache
• $2$ ns: latency of a floating point operation (vectorized or not)
• $3$ to $5$ ns: time to load one double precision value from memory as part of perfectly prefetched and fully utilized stream
• $3$ to $5$ ns: indirect function call (virtual method or function pointer, without register pressure)
• $5$ ns: conditional branch mis-predict
• $4$ to $8$ ns: time for one division (vectorized or not, cannot run concurrently with other other instructions)
• $12$ ns: L1 cache miss satisfied from local L2
• $12$ ns: best case compare-and-swap or fetch-and-add atomic instruction
• $30$-$50$ ns: L1 write cache miss or atomic instruction in which the cache line is available locally, but the current core has to obtain exclusive access
• $100$ ns: cache miss or atomic instruction satisfied from off-socket or memory
• $10^3$ ns ($1$ $\mu$s): hardware network latency for a fancy network
• $10^4$ ns ($10$ $\mu$s): low-data neighbor exchange when well-mapped to the network
• $10^6$ ns (1 ms): time (per process) to create a file on a parallel file system
• $2\cdot 10^6$ ns (2 ms): small data MPI_Allreduce (e.g. a norm or dot product) on a large machine
• $10^7$ ns (10 ms): local disk seek
• $5\cdot 10^8$ ns (500 ms): time to rewrite all available memory
• $1.8\cdot 10^{12}$ ns (0.5 hour): time to checkpoint entire machine state to disk