5 ms·

It’s because Big O is Computer Science. Cache effects are Software Engineering. Professors of CS do a fine job of teaching CS. They even briefly mention that th

It’s because Big O is Computer Science. Cache effects are Software Engineering. Professors of CS do a fine job of teaching CS. They even briefly mention that there is a implicit constant factor k in O(k n log(n)) and then they never mention it again. They certainly don’t mention that k can easily vary by 128x between algos. AKA: 7 levels of a binary tree. Or that most of the data they will be dealing with in practice not only won’t be infinite, but will actually be less than 128 bytes. Or, that even with huge data and an proven-ideal O() algo, there is often 10x speed-up to be had with a hybrid algo like a b-tree instead of a binary tree. And, another 2-10x with SIMD vs scalar. 100x isn’t infinite, but it’s still counts. So, grads listen to their CS professors and that’s what they know. It’s not until they get lectures from greybeard software engineers that they learn about the reality algos and not just the idealized algos.

dilyevsky 7y ago
Every good cs course has a section on cache aware algorithms. And i call bullshit that constant factor is not mentioned too
- dwheeler 7y ago
  Mentioned, yes, but often not learned. In many situations the only thing that matters is the constant factor. If the number of data items is relatively small, the difference between N log N and and N squared may be completely dominated by the constant factor. In addition, there is the challenge of maintaining the code later and making sure it's correct.
  - vvanders 7y ago
    Yup, so much truth here. Take a look at Real-time Collision Detection[1]. I takes a great look at both algorithmic complexity and cache awareness. That's how it should be done. [1] https://www.amazon.com/dp/1558607323 https://www.amazon.com/dp/1558607323
- corysama 7y ago
  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.
  - 7y ago
- willberman 7y ago
  When I took data structures and algorithms, I believe almost every single lesson was concluded with the caveat that constants are important.
- eyegor 7y ago
  I've looked before, but I've never seen a class dedicated to practical algorithm design. Being able to reason about cache layout, context switch costs, branch prediction behavior, simd refactoring, and basic compiler level optimizations will result in much more performant code. In the real world people often write complex algorithms which operate on structs/classes instead of primitives. This means there's a huge performance hit just from pointer traversal in a hot path, especially if someone naively does math across data inside heap objects. You can easily write a fancy dynamic algorithm approach which has theoretical O(k*n) performance which takes forever in the real world due to abstraction traversal. If you're doing more than one operation, it's often a massive performance boost to cache all your object pointer evaluations into primitive arrays, do simd operations on them, and then populate the objects at the end. Does anyone have a good textbook suggestion for cache/simd aware algorithm design? I've seen plenty of papers that cover single examples but never something the scope of a book.
lonelappde 7y ago
That's an arbitrarily restrictive view of computer science. It's like saying teaching physics ignoring friction perfectly fine.
- pretendscholar 7y ago
  Yes you should ignore the details of friction for the first few semesters.
  - lonelappde 7y ago
    For how many semesters? All the way through to graduation?
    - rriepe 7y ago
      No. You wouldn't want people slipping on stage.
      - alasdair_ 7y ago
        > No. You wouldn't want people slipping on stage. Since all the students will merely be spheres of equal density, that shouldn’t matter much.
        bialpio 7y ago
        I guess in that case you can also skip teaching them about angular momentum!
        saagarjha 7y ago
        They’d still have angular momentum; it just wouldn’t be immediately apparent.
    - eternauta3k 7y ago
      Funnily enough, you only solve problems with friction in your first semester (and maybe a little bit afterward when you study waves).
Jasper_ 7y ago
Models are easy when you turn every cow into a sphere. But physicists never believe their models respect the real world. Computer Science should be about the Science of Computers, not hypothetical models acting on hypothetical architectures.
- duck2 7y ago
  Computer Science existed long before there were computers. I think the Science of Computers you mention is known as Computer Architecture.
  - msla 7y ago
    > Computer Science existed long before there were computers. Not in its current form, and not if you define "computers" with a sufficiently broad net. (Or broad loom, tipping a hat to Jacquard... )
  - msla 7y ago
    > Computer Science existed long before there were computers. No, various bits and pieces of it did, but not the whole, coherent field, which is motivated by the existence of computers.
MaxBarraclough 7y ago
> briefly mention that there is a implicit constant factor k in O(k n log(n)) and then they never mention it again A fine concrete example of this is the Coppersmith–Winograd algorithm (and its derivatives), a matrix multiplication algorithm with impressive complexity properties, but which in practice always loses to the Strassen algorithm, despite Strassen's inferior complexity. [0][1][2] (Aside: the Strassen algorithm is pretty mind-bending, but also easily shown. If you've got 22 minutes spare, there's a good explanation of it on YouTube. Perhaps there's a more dense source elsewhere. [3]) > It’s not until they get lectures from greybeard software engineers that they learn about the reality algos and not just the idealized algos. To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc. [0] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a... [1] https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm [2] https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra https://en.wikipedia.org/wiki/Computational_complexity_of_ma... [3] https://www.youtube.com/watch?v=ORrM-aSNZUs https://www.youtube.com/watch?v=ORrM-aSNZUs
- dwohnitmok 7y ago
  Even Strassen can be overly expensive for reasonably sized matrices. Almost all matrix multiplication algorithms have a threshold only beyond which do they use Strassen. Although apparently that threshold can be lowered (http://jianyuhuang.com/papers/sc16.pdf http://jianyuhuang.com/papers/sc16.pdf), but even then it's a matrix that's several hundred columns by several hundred rows large. Some CS classes explicitly use Strassen to teach the realities of asymptotic vs wall-clock time complexity, challenging students to come up with a hybrid matrix multiplication algorithm that performs the fastest and switches at the best thresholds of matrix size.
- msla 7y ago
  > To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc. Which would have the positive knock-on effect of the textbook being sufficiently obsolete every year or so that the students could no longer trade it in for credit, saving the bookstores money! More seriously, that knowledge (at least once you attach numbers to it) has a shelf life, and not a very long one. Teaching big-O analysis means the knowledge is timeless, which any good theoretical knowledge is, and moving more towards practice would force the professors to keep on top of the state of the art, and the state of the mainstream, of hardware design in addition to everything else they're doing.
fchu 7y ago
As a side note: O(k n log(n)) and O (n log (n)) have exactly the same meaning for k non-null constant by the definition of big O notation. The more you know!
jrs95 7y ago
And then we seriously overvalue these "core CS skills" for a lot of positions, many of which will not involve actually using any of it at all. I can't tell you how many people I've worked with that could tell you a bunch of Big O crap off the top of their heads but all they were working on was web apps and they couldnt seem to remember that running an ORM query in a loop is a bad idea. The way the U.S. uses college education as a prerequisite to employment but also seems to not be very good at teaching stuff that's actually relevant to the work you allegedly need the degree for is very disturbing to me.

dilyevsky 7y ago

Every good cs course has a section on cache aware algorithms. And i call bullshit that constant factor is not mentioned too

dwheeler 7y ago
Mentioned, yes, but often not learned. In many situations the only thing that matters is the constant factor. If the number of data items is relatively small, the difference between N log N and and N squared may be completely dominated by the constant factor. In addition, there is the challenge of maintaining the code later and making sure it's correct.
- vvanders 7y ago
  Yup, so much truth here. Take a look at Real-time Collision Detection[1]. I takes a great look at both algorithmic complexity and cache awareness. That's how it should be done. [1] https://www.amazon.com/dp/1558607323 https://www.amazon.com/dp/1558607323
corysama 7y ago
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.
- 7y ago
willberman 7y ago
When I took data structures and algorithms, I believe almost every single lesson was concluded with the caveat that constants are important.
eyegor 7y ago
I've looked before, but I've never seen a class dedicated to practical algorithm design. Being able to reason about cache layout, context switch costs, branch prediction behavior, simd refactoring, and basic compiler level optimizations will result in much more performant code. In the real world people often write complex algorithms which operate on structs/classes instead of primitives. This means there's a huge performance hit just from pointer traversal in a hot path, especially if someone naively does math across data inside heap objects. You can easily write a fancy dynamic algorithm approach which has theoretical O(k*n) performance which takes forever in the real world due to abstraction traversal. If you're doing more than one operation, it's often a massive performance boost to cache all your object pointer evaluations into primitive arrays, do simd operations on them, and then populate the objects at the end. Does anyone have a good textbook suggestion for cache/simd aware algorithm design? I've seen plenty of papers that cover single examples but never something the scope of a book.

lonelappde 7y ago

That's an arbitrarily restrictive view of computer science. It's like saying teaching physics ignoring friction perfectly fine.

pretendscholar 7y ago
Yes you should ignore the details of friction for the first few semesters.
- lonelappde 7y ago
  For how many semesters? All the way through to graduation?
  - rriepe 7y ago
    No. You wouldn't want people slipping on stage.
    - alasdair_ 7y ago
      > No. You wouldn't want people slipping on stage. Since all the students will merely be spheres of equal density, that shouldn’t matter much.
      - bialpio 7y ago
        I guess in that case you can also skip teaching them about angular momentum!
        saagarjha 7y ago
        They’d still have angular momentum; it just wouldn’t be immediately apparent.
  - eternauta3k 7y ago
    Funnily enough, you only solve problems with friction in your first semester (and maybe a little bit afterward when you study waves).

Jasper_ 7y ago

Models are easy when you turn every cow into a sphere. But physicists never believe their models respect the real world. Computer Science should be about the Science of Computers, not hypothetical models acting on hypothetical architectures.

duck2 7y ago
Computer Science existed long before there were computers. I think the Science of Computers you mention is known as Computer Architecture.
- msla 7y ago
  > Computer Science existed long before there were computers. Not in its current form, and not if you define "computers" with a sufficiently broad net. (Or broad loom, tipping a hat to Jacquard... )
- msla 7y ago
  > Computer Science existed long before there were computers. No, various bits and pieces of it did, but not the whole, coherent field, which is motivated by the existence of computers.

MaxBarraclough 7y ago

> briefly mention that there is a implicit constant factor k in O(k n log(n)) and then they never mention it again A fine concrete example of this is the Coppersmith–Winograd algorithm (and its derivatives), a matrix multiplication algorithm with impressive complexity properties, but which in practice always loses to the Strassen algorithm, despite Strassen's inferior complexity. [0][1][2] (Aside: the Strassen algorithm is pretty mind-bending, but also easily shown. If you've got 22 minutes spare, there's a good explanation of it on YouTube. Perhaps there's a more dense source elsewhere. [3]) > It’s not until they get lectures from greybeard software engineers that they learn about the reality algos and not just the idealized algos. To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc. [0] https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a... [1] https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm [2] https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra https://en.wikipedia.org/wiki/Computational_complexity_of_ma... [3] https://www.youtube.com/watch?v=ORrM-aSNZUs https://www.youtube.com/watch?v=ORrM-aSNZUs

dwohnitmok 7y ago
Even Strassen can be overly expensive for reasonably sized matrices. Almost all matrix multiplication algorithms have a threshold only beyond which do they use Strassen. Although apparently that threshold can be lowered (http://jianyuhuang.com/papers/sc16.pdf http://jianyuhuang.com/papers/sc16.pdf), but even then it's a matrix that's several hundred columns by several hundred rows large. Some CS classes explicitly use Strassen to teach the realities of asymptotic vs wall-clock time complexity, challenging students to come up with a hybrid matrix multiplication algorithm that performs the fastest and switches at the best thresholds of matrix size.
msla 7y ago
> To mirror what some others are saying here, students should also be taught the realities of cache behaviour, SIMD-friendliness, branch prediction, multi-threaded programming, real-time constraints, hardware acceleration, etc. Which would have the positive knock-on effect of the textbook being sufficiently obsolete every year or so that the students could no longer trade it in for credit, saving the bookstores money! More seriously, that knowledge (at least once you attach numbers to it) has a shelf life, and not a very long one. Teaching big-O analysis means the knowledge is timeless, which any good theoretical knowledge is, and moving more towards practice would force the professors to keep on top of the state of the art, and the state of the mainstream, of hardware design in addition to everything else they're doing.

fchu 7y ago

As a side note: O(k n log(n)) and O (n log (n)) have exactly the same meaning for k non-null constant by the definition of big O notation. The more you know!

jrs95 7y ago

And then we seriously overvalue these "core CS skills" for a lot of positions, many of which will not involve actually using any of it at all. I can't tell you how many people I've worked with that could tell you a bunch of Big O crap off the top of their heads but all they were working on was web apps and they couldnt seem to remember that running an ORM query in a loop is a bad idea. The way the U.S. uses college education as a prerequisite to employment but also seems to not be very good at teaching stuff that's actually relevant to the work you allegedly need the degree for is very disturbing to me.