Costs of lookups versus calculations

Question

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?

Answer 1

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

Further reading

• Agner Fog's instruction tables
• Latency Numbers Every Programmer Should Know
• Paul McKenney slides on threading