4 ms·
Cache locality will never beat algorithmic complexity as a performance factor. Don't exaggerate its importance.
by saosebastiao 9y ago
Cache locality will never beat algorithmic complexity as a performance factor. Don't exaggerate its importance.
- falcolas 9y agoIt can, when the constant portion of the algorithm chosen is high and the number of items being pushed through the algorithm is low. e.g. bubblesort will beat quicksort for tiny lists or large lists which are already sorted. Or, put another way, 1000 operations against 1ns latency memory (L1) has the same performance as 10 operations against 100ns latency memory (RAM).