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_a...
[1] https://en.wikipedia.org/wiki/Strassen_algorithm
[2] https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
Although apparently that threshold can be lowered (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.
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.
That's naive. E.g. SIMD is here since a good time and going to stay. So are GPGPU, with now quite similar architectures for tons of chips.
And Computer Science can actually be about science for real computers, and computers are not 8086 nor PDP11 anymore, and have never been a turing machine. So there actually is some existing generic CS and ongoing research that cares about cache effects and so over. Maybe it is applied CS if you want, and some kind of pure CS should not care about that, but I really don't see what should be the criteria to decide which is what anyway, so IMO there should not be any (but I do not mean that all research should care about e.g. cache effects, just that it is not really useful to attempt to distinguish between those which do and those which don't).
We don't teach advanced math by only showing what was done at e.g. the beginning of algebra. Neither should we stick to only basic subjects in computer science.
I wasn't very clear on that point, but didn't mean to suggest it be the same textbook. These other topics deserve courses and books of their own. The algorithms lecturer should be careful to emphasise the limitations of complexity theory though.
> that knowledge (at least once you attach numbers to it) has a shelf life, and not a very long one
Plenty of long-lived principles to be learned there, even if the particulars change over time. Caches are still going to be around in 10 years time.
They are in many places I'm aware of. At least, as an EE (at Stanford, but I've heard MIT and several others do the same), I had to take a digital system design class, but the majority of the class was spent on performance engineering. In fact, the very first (actual) project of the class was to take a 10-line piece of C code, which applies a simple filter in real time to a video, and make it performant. The initial code runs at around .5 FPS.
Our resulting performant code was, of course, many times larger (I think it might have been ~150 lines), but it ran incredibly quickly (110 FPS, iirc), by doing crazy compiler tricks and often calling ASM from within the C code, even though the asymptotic (big O) performance was exactly the same.
For context, this is not just a digital systems thing (my work is in mathematical optimization theory and my undergrad was in photonics and physics), but I do know that this class is not a requirement for CS since it's potentially too hardware oriented. The classes exist, but I'm not sure people are taking them.
Yes, sure. I hadn't meant to imply otherwise. The pure-algorithms lecturer needn't cover these other topics in detail in their course, but should be careful to emphasise the uses and limitations of complexity theory.
> this class is not a requirement for CS since it's potentially too hardware oriented
I don't see the sense in this. Computer scientists publish work on applying GPU acceleration, as they should - that's not electronic engineering work they're doing. We could quibble about whether it's computer science of software engineering.
I agree, I'm not sure why this is the case either, just my idea as to why it may not be a requirement. (Some part of the class does involve writing a good chunk of a 5-stage RISC processor based on MIPS, but this was still relatively straightforward with just a basic understanding of digital logic.)
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".
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.
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.
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.
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.
I'm guessing it's not CRUD apps.
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-scal...
[2] https://stackoverflow.com/questions/10930595/sse-instruction...
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.
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.
Since all the students will merely be spheres of equal density, that shouldn’t matter much.
No, various bits and pieces of it did, but not the whole, coherent field, which is motivated by the existence of 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... )
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.