4 ms·

It wasn’t taught to me. And, in my previous job I interviewed many dozen fresh grads. One of my questions was “How much slower is it to sum integers in a trivia

It wasn’t taught to me. And, in my previous job I interviewed many dozen fresh grads. One of my questions was “How much slower is it to sum integers in a trivial linked list vs. a trivial array?” 90% answered “Umm... I don’t know. 2x?” When asked why, they all said “1 op to sum the int +1 op to traverse the pointer.” It was amazingly consistent.

willberman 7y ago
I can see how this wouldn’t be covered in an undergrad cs education. I took only a single computer architecture class which was extremely limited in scope. The only reason I knew about vectorization during undergrad is because a friend mentioned it to me once.
- temac 7y ago
  The basic speed up will not even be because of vectorisation. It will be because of caches.
  - willberman 7y ago
    Are you saying that the majority of the speed up is from caches and then there's a secondary, much smaller, speed up from the vectorization? Or are you saying all the speed up is from caches and I'm off base here with vectorization.
cjfd 7y ago
O dear.... Am I happy that I never studied computer 'science'..... On the other hand, there must be smart computer science students and/or smart places of education where actual learning about processor caches and the like takes place.....
- lghh 7y ago
  I don't think anyone answering in this way would be "not smart" like you seem to imply.
onekorg 7y ago
The answer could be 2x. Let's say you're in a 64 bit platform. Your linked list nodes consist of a next pointer and a 64 bit integer. If your linked list nodes are all allocated sequentially in memory then it'd only be 2x as slow as an array of 64 bit integers. But maybe it's not fair to call sequentially allocated linked list a "trivial linked list".
- deleted 7y ago
  [deleted]
- deleted 7y ago
  [deleted]
- koala_man 7y ago
  This kind of CS-based rationalization is arguably another aspect of what the article comments on. I wrote a benchmark and found the difference in this case to be 3x-3.5x.
joshlemer 7y ago
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,

willberman 7y ago

I can see how this wouldn’t be covered in an undergrad cs education. I took only a single computer architecture class which was extremely limited in scope. The only reason I knew about vectorization during undergrad is because a friend mentioned it to me once.

temac 7y ago
The basic speed up will not even be because of vectorisation. It will be because of caches.
- willberman 7y ago
  Are you saying that the majority of the speed up is from caches and then there's a secondary, much smaller, speed up from the vectorization? Or are you saying all the speed up is from caches and I'm off base here with vectorization.

cjfd 7y ago

O dear.... Am I happy that I never studied computer 'science'..... On the other hand, there must be smart computer science students and/or smart places of education where actual learning about processor caches and the like takes place.....

lghh 7y ago
I don't think anyone answering in this way would be "not smart" like you seem to imply.

onekorg 7y ago

The answer could be 2x. Let's say you're in a 64 bit platform. Your linked list nodes consist of a next pointer and a 64 bit integer. If your linked list nodes are all allocated sequentially in memory then it'd only be 2x as slow as an array of 64 bit integers. But maybe it's not fair to call sequentially allocated linked list a "trivial linked list".

deleted 7y ago
[deleted]
deleted 7y ago
[deleted]
koala_man 7y ago
This kind of CS-based rationalization is arguably another aspect of what the article comments on. I wrote a benchmark and found the difference in this case to be 3x-3.5x.

joshlemer 7y ago

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,