5 ms·

What would be the kind answer you're looking for?

corysama 7y ago
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.
jodrellblank 7y ago
At a guess, some understanding of this article[1] - if a CPU instruction scaled up to human time takes 1 second then a Level 1 cache lookup takes 2 seconds and a main memory lookup takes 4 minutes. Imagine for the array it's 1 CPU instruction to load a value, 1 to load the next value, 1 to add them, and one to store the result, that would be 4 instructions per sum; ideally the array would stream into the CPU after a single main memory lookup delay up-front, and then be 4 instructions per pair, summed as fast as the CPU can loop. The linked list at worst needs an imaginary 1 CPU instruction to load a value, 1 to load the pointer value, 1 to reference the pointer, a delay of 2 seconds to get that value from L1 cache - missed, it's not in cache - 240 seconds stalled waiting for main memory, 1 to add, 1 to store the result. Worst case, >240x slower. The linked list is not guaranteed to be in contiguous memory, but it might be, so the cache might have the right data in it. The linked list is 50% data, 50% metadata, so the cache is half wasted / can hold half as much data, and if the linked list is coming in from a big memory read quickly, half the bandwidth is carrying pointer addresses not data, so the throughput is halved for that, too, and the processor cycles were already able to happen much faster than the main memory bus max speed. If it's not contiguous memory, you don't know in advance where it is to request all the right memory areas at once - not until you read sequentially to the last item pointer and find there are no more. Maybe if they are both small, both in contiguous memory and go into Level 1 cache after a single main memory delay, it could be only ~2x time, but the more data there is overall, the more chance the linked list will bust the cache or be discontinuous in memory. And on the plain array side, it might be possible to speed up with SIMD/SSE instructions to spend fewer cycles adding and storing per element, which the linked list approach might not be amenable to at all[2], then best case might be ~4x slower, worst case ~500x slower. [1] https://www.prowesscorp.com/computer-latency-at-a-human-scale/ https://www.prowesscorp.com/computer-latency-at-a-human-scal... [2] https://stackoverflow.com/questions/10930595/sse-instructions-to-add-all-elements-of-an-array https://stackoverflow.com/questions/10930595/sse-instruction...

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.

jodrellblank 7y ago

At a guess, some understanding of this article[1] - if a CPU instruction scaled up to human time takes 1 second then a Level 1 cache lookup takes 2 seconds and a main memory lookup takes 4 minutes. Imagine for the array it's 1 CPU instruction to load a value, 1 to load the next value, 1 to add them, and one to store the result, that would be 4 instructions per sum; ideally the array would stream into the CPU after a single main memory lookup delay up-front, and then be 4 instructions per pair, summed as fast as the CPU can loop. The linked list at worst needs an imaginary 1 CPU instruction to load a value, 1 to load the pointer value, 1 to reference the pointer, a delay of 2 seconds to get that value from L1 cache - missed, it's not in cache - 240 seconds stalled waiting for main memory, 1 to add, 1 to store the result. Worst case, >240x slower. The linked list is not guaranteed to be in contiguous memory, but it might be, so the cache might have the right data in it. The linked list is 50% data, 50% metadata, so the cache is half wasted / can hold half as much data, and if the linked list is coming in from a big memory read quickly, half the bandwidth is carrying pointer addresses not data, so the throughput is halved for that, too, and the processor cycles were already able to happen much faster than the main memory bus max speed. If it's not contiguous memory, you don't know in advance where it is to request all the right memory areas at once - not until you read sequentially to the last item pointer and find there are no more. Maybe if they are both small, both in contiguous memory and go into Level 1 cache after a single main memory delay, it could be only ~2x time, but the more data there is overall, the more chance the linked list will bust the cache or be discontinuous in memory. And on the plain array side, it might be possible to speed up with SIMD/SSE instructions to spend fewer cycles adding and storing per element, which the linked list approach might not be amenable to at all[2], then best case might be ~4x slower, worst case ~500x slower. [1] https://www.prowesscorp.com/computer-latency-at-a-human-scale/ https://www.prowesscorp.com/computer-latency-at-a-human-scal... [2] https://stackoverflow.com/questions/10930595/sse-instructions-to-add-all-elements-of-an-array https://stackoverflow.com/questions/10930595/sse-instruction...