A 100x speedup makes sense because a cache miss costs around 100 nanoseconds, compared to arithmetic operations themselves costing under one nanosecond. If you

A 100x speedup makes sense because a cache miss costs around 100 nanoseconds, compared to arithmetic operations themselves costing under one nanosecond. If you traverse a data structure in which everything's a pointer, every access may well be a cache miss, especially if the rest of the code is also pointer-heavy and thrashes the cache.