3 ms·

The question had 2 goals: 1) Do you think about cache at all or is it just something you heard mentioned as important that one time? 2) It's a good lead-in to

The question had 2 goals: 1) Do you think about cache at all or is it just something you heard mentioned as important that one time? 2) It's a good lead-in to discussing the effects of cache in algorithms. How that conversation goes helps me to understand how that person thinks and discusses complex problems. A good answer would be "I'm not sure, but probably way, way slower because linked list can point all over memory but arrays cache really well." An excellent, A+ answer would be "In the best case it might not be too much slower if you have an intrusive linked list is arranged sequentially in memory like an array like onekorg explained. But, in practice most will be 20-200x slower because they are usually implemented as pointers to nodes containing pointers to data and each piece is allocated piecemeal in a already fragmented heap. Uncached memory reads can take 100+ cycles and summing an int is not enough work to hide that even if the CPU speculatively prefetches." I mainly expect a surprised reaction that they could be so slow and looked forward to the follow-up discussion.

TheOtherHobbes 7y ago
I sometimes wonder if CS should be renamed Computer Pseudo-Science. I blame Knuth and (mostly) Dijkstra for propagating the falsehood that you can estimate the performance of real code on real hardware with a some elegant academic blackboard math which gives you the wrong answer for many practical applications. It's not that Big O isn't useful - it's that it's taught as a set of "proofs" which somehow make it appear objective and "correct", when in reality performance is at least as dependent on cache architecture, median size-of-n, memory bandwidth, and other implementation details. Anyone who graduates CS without having been taught this very forcefully - preferably during a practical project - should be refunded at least some of their course fees.
- herbstein 7y ago
  But Big O was a lot more directly correlated when the CPU wasn't doing "magic" optimizations on its own. It was still estimations with an invisible constant factor, of course,
  - koreth1 7y ago
    This is a key point. The gargantuan performance difference between main memory and the CPU cache (or indeed, the existence of significant CPU caches at all) happened well after big-O was firmly established in the CS curriculum.
Cpoll 7y ago
> But, in practice most will be 20-200x slower My A+ answer is "My guess is [x] but instead of speculating we can create a test to discover the performance. [Describes test]." Koala_man above says: > I wrote a benchmark and found the difference in this case to be 3x-3.5x. The actual number depends on a lot of things, of course (language, architecture, test methodology...), but it is possible that your 20-200x A+ answer is incorrect.
- temac 7y ago
  There is no answers if you don't specify tons of parameters, like the number of element, prior memory fragmentation, etc. 200x can be a reasonable outcome. So can be 3x in other conditions. As a rule of thumb I now consider that a completely random memory access is on the order of accessing 1000 sequential bytes.
james_s_tayler 7y ago
Question... What kind of software do you mainly work on? I'm guessing it's not CRUD apps.
- corysama 7y ago
  High end 3D mobile games. We regularly measured direct correlations between performance and revenue. Higher performance meant a larger install base of devices could run the app with better responsiveness and lower battery burn. Thus, higher retention and engagement. Thus higher monies.

TheOtherHobbes 7y ago

I sometimes wonder if CS should be renamed Computer Pseudo-Science. I blame Knuth and (mostly) Dijkstra for propagating the falsehood that you can estimate the performance of real code on real hardware with a some elegant academic blackboard math which gives you the wrong answer for many practical applications. It's not that Big O isn't useful - it's that it's taught as a set of "proofs" which somehow make it appear objective and "correct", when in reality performance is at least as dependent on cache architecture, median size-of-n, memory bandwidth, and other implementation details. Anyone who graduates CS without having been taught this very forcefully - preferably during a practical project - should be refunded at least some of their course fees.

herbstein 7y ago
But Big O was a lot more directly correlated when the CPU wasn't doing "magic" optimizations on its own. It was still estimations with an invisible constant factor, of course,
- koreth1 7y ago
  This is a key point. The gargantuan performance difference between main memory and the CPU cache (or indeed, the existence of significant CPU caches at all) happened well after big-O was firmly established in the CS curriculum.

Cpoll 7y ago

> But, in practice most will be 20-200x slower My A+ answer is "My guess is [x] but instead of speculating we can create a test to discover the performance. [Describes test]." Koala_man above says: > I wrote a benchmark and found the difference in this case to be 3x-3.5x. The actual number depends on a lot of things, of course (language, architecture, test methodology...), but it is possible that your 20-200x A+ answer is incorrect.

temac 7y ago
There is no answers if you don't specify tons of parameters, like the number of element, prior memory fragmentation, etc. 200x can be a reasonable outcome. So can be 3x in other conditions. As a rule of thumb I now consider that a completely random memory access is on the order of accessing 1000 sequential bytes.

james_s_tayler 7y ago

Question... What kind of software do you mainly work on? I'm guessing it's not CRUD apps.

corysama 7y ago
High end 3D mobile games. We regularly measured direct correlations between performance and revenue. Higher performance meant a larger install base of devices could run the app with better responsiveness and lower battery burn. Thus, higher retention and engagement. Thus higher monies.