5 ms·
> People also say that TAOCP is irrelevant or outdated or otherwise inapplicable to “real programming”. This also wrong. For instance, the first section after t
by lisper 8y ago
> People also say that TAOCP is irrelevant or outdated or otherwise inapplicable to “real programming”. This also wrong. For instance, the first section after the chapter intro deals with the basic problem of searching for an item in an unsorted array. The simplest algorithm should be familiar to all programmers. Start your pointer at the head of the array, then do the following in a loop:
Check if the current item is the desired one. If it is, return success; otherwise
Check if the pointer is past the array bound. If it is, return failure; otherwise
Increment the pointer and continue.
> Now consider: how many bound checks does this algorithm require on average? In the worst case, when the array doesn’t contain the item, one bound check will be required for each item in the list, and on average it will be something like N/2. A more clever search algorithm can do it with just one bound check in all cases. Tack the desired item on to the end of the array, then start your pointer at the head of the array and do the following in a loop:
Check if the current item is the desired one.
If it is, return success if the pointer is within the array bound and return failure if it isn’t; otherwise
Increment the pointer and continue.
> With this algorithm, things are arranged such that the item is guaranteed to be found one way or another, and the bound check only needs to be executed once when the item is found. This is a deep idea, but it’s also simple enough even for a beginning programmer to understand.
All this is true, but it overlooks one very important thing: on a modern processor architecture, this "optimization" will almost certainly be completely useless [1]. Almost certainly, the bounds check will be pipelined in such a way that it is essentially free on every iteration. Almost certainly, for a problem of any size where efficiency actually matters, the run time will be dominated by memory access latency.
So this is not a very good example to refute the argument that TAOCP is irrelevant and outdated.
[1] In fact, it will almost certainly be worse than useless because the extra setup and teardown steps required at the beginning and end will make the algorithm run more slowly than it otherwise would have.
- Arnavion 8y agoIt's already questionable for a search algorithm to require the ability to write to the array it's searching in, but it's even worse if it wants to be able to extend and shrink the array to do so. Edit: I haven't read the book. Presumably it gives some context for the algorithm that you only bring it out in the specific situation where it makes sense to use it.
- renox 8y agoExtending the array is not needed: you can store the last element in a variable, then overwrite the last element with the searched value, do the search then restore the last element. I remember a talk from Alexei Andrulescu(sp?) where he talk about this optimisation but I don't remember if there was benchmarks.
- mkl 8y agoThat's clever, but it still requires writing to the array, which is dodgy in many circumstances; other threads may be using it, so the search function is likely to be given only read-only access.
- blitmap 8y agoI wish I could find a good text that talks about how removed from 'directly executing on hardware' you are. Modern [x86] processors are (as described) executing very much out of order or calculating things in parallel. I wish I could find something that spoke to the whole field of tricks at play. I'm sure there's a great depth of indirection I'll never understand.
- matt_d 8y agoThe following (can be read in chronological order) give a pretty good idea: - J.E. Smith and G.S. Sohi, "The Microarchitecture of Superscalar Processors," Proc. IEEE, vol. 83 (1995) - ftp://ftp.cs.wisc.edu/sohi/papers/1995/ieee-proc.superscalar.pdf, http://www.eng.ucy.ac.cy/theocharides/Courses/ECE656/superscalar.pdf http://www.eng.ucy.ac.cy/theocharides/Courses/ECE656/supersc... - Tejas S. Karkhanis and James E. Smith. "A First-Order Superscalar Processor Model." (ISCA 2004) - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.6017&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.... - Stijn Eyerman, Lieven Eeckhout, Tejas Karkhanis, and James E. Smith. "A mechanistic performance model for superscalar out-of-order processors." ACM Trans. Comput. Syst. 27, 2 (2009) - http://www.elis.ugent.be/~leeckhou/papers/tocs09.pdf http://www.elis.ugent.be/~leeckhou/papers/tocs09.pdf - Maximilien B. Breughe, Stijn Eyerman, and Lieven Eeckhout. "Mechanistic analytical modeling of superscalar in-order processor performance." ACM Trans. Architec. Code Optim. 11, 4, Article 50 (2014) - https://users.elis.ugent.be/~leeckhou/papers/taco2015-breughe.pdf https://users.elis.ugent.be/~leeckhou/papers/taco2015-breugh... - "Modeling Superscalar Processor Memory-Level Parallelism", Sam Van den Steen and Lieven Eeckhout, IEEE Computer Architecture Letters (CAL), Vol 17, No 1 (2018) - https://users.elis.ugent.be/~leeckhou/papers/cal2018-MLP.pdf https://users.elis.ugent.be/~leeckhou/papers/cal2018-MLP.pdf - A whirlwind introduction to dataflow graphs - https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/ https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introdu...
- blitmap 8y agoVery much appreciated, sir :-)
- pantalaimon 8y agoI had to try it myself but it looks like you are right! http://codepad.org/tw6EJMr4 http://codepad.org/tw6EJMr4 i5-2500K: naive search found: 0, took 1856721 ns found: 0, took 1799554 ns found: 0, took 1908483 ns found: 0, took 1921622 ns found: 0, took 1856173 ns found: 0, took 1812736 ns found: 0, took 1819938 ns found: 0, took 1846232 ns found: 0, took 1821858 ns found: 0, took 1898503 ns average: 1854182.00 ns knuth search found: 0, took 1969758 ns found: 0, took 2125165 ns found: 0, took 2081280 ns found: 0, took 2033002 ns found: 0, took 1948852 ns found: 0, took 2049150 ns found: 0, took 2046759 ns found: 0, took 2101704 ns found: 0, took 2083800 ns found: 0, took 2120793 ns average: 2056026.38 ns edit: I was wondering how it would look on a simpler CPU, presumably without branch prediction and my router came to mind. Indeed there the picture looks different: Qualcomm Atheros QCA9558 (MIPS 74Kc V5.0) naive search found: 0, took 20582795 ns found: 0, took 21233303 ns found: 0, took 20505486 ns found: 0, took 20633735 ns found: 0, took 21079799 ns found: 0, took 20619782 ns found: 0, took 21099067 ns found: 0, took 20558769 ns found: 0, took 20398468 ns found: 0, took 20888357 ns average: 20759956.00 ns knuth search found: 0, took 16323322 ns found: 0, took 16530714 ns found: 0, took 16255532 ns found: 0, took 16416161 ns found: 0, took 16577751 ns found: 0, took 16488995 ns found: 0, took 16417074 ns found: 0, took 16466930 ns found: 0, took 16295522 ns found: 0, took 16277085 ns average: 16404909.00 ns
- lisper 8y agoKudos to you for actually doing the experiment! With a control case even! I wish I could give you ten upvotes.
- pantalaimon 8y agoWell kudos to you for having the right theory! I would have never assumed this behavior on modern CPUs. That trick might still be useful in the embedded space - I had to try it on my samr21-xpro too (with only an 8kiB array and slightly modified code - http://codepad.org/aPOZraI2 http://codepad.org/aPOZraI2) samr21 (Cortex M0+) naive search found: 0, took 1714 ticks found: 0, took 1713 ticks found: 0, took 1714 ticks found: 0, took 1714 ticks found: 0, took 1714 ticks found: 0, took 1713 ticks found: 0, took 1714 ticks found: 0, took 1713 ticks found: 0, took 1714 ticks found: 0, took 1714 ticks average: 1713 ticks knuth search found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks found: 0, took 1372 ticks average: 1372 ticks
- cheerlessbog 8y agoAlso doesn't "tack on the end of the array" imply allocating new memory and copying the whole array? It might make sense for a linked list, or a self expanding list whose backing storage wasn't full. Even then there is the cost of pulling the end of the array into cache up front.
- tedunangst 8y agoYou would probably just swap the last element to temp storage, and swap back after.
- vram22 8y ago>All this is true, but it overlooks one very important thing: on a modern processor architecture, this "optimization" will almost certainly be completely useless [1]. Almost certainly, the bounds check will be pipelined in such a way that it is essentially free on every iteration. Interesting, that. I've been reading here on HN a few times, that assembly language is harder to write / analyze nowadays because of such features of modern processors. Regarding the optimization being useless: That technique is called using a sentinel, and was common in algorithms earlier, maybe before modern processors' pipelining and suchlike features existed. E.g., it (using a sentinel to avoid one comparison per iteration - the check for passing the array end - in a search) is mentioned in the classic book "Writing Efficient Programs" by Jon Bentley. (great book, BTW. I owned and read most of it.) See Bibliography section here: https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientist) https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientis...
- nickdrozd 8y agoCertainly I'm not saying that this is the algorithm to use in all cases. It's not even obvious how you would implement the sentinel algorithm in a language like Python, not in idiomatic code anyway. The point is that the book is written from the perspective of an actual programmer writing actual code and thinking about how it will run. Granted, he's writing in a pixie assembly language for an imaginary machine, but still, the thought process is similar to writing real code. He doesn't just figure out the big-O and call it a day, he works out the low-level details. The lesson in this case is that a lot of extra work can be done in a loop, even for the simplest of algorithms. Now you might think, that's a truism, duh, any programmer knows that loops need to be fast. But what can I say? I read that section and spent a few hours thinking about it (even writing out some old-timey flowcharts), and I came out the other side writing better, faster code.
- lisper 8y ago> The point is that the book is written from the perspective of an actual programmer writing actual code and thinking about how it will run. Sure, I don't dispute that in the least. All I'm saying is that if you want to argue that TAOCP is not dated you could have chosen a better example.
- atq2119 8y agoPerhaps even more importantly, requiring the array to be mutable hurts composability in the age of multithreading, as it prevents the algorithm from being used concurrently on the same array by multiple threads.
- z3t4 8y agoOptimizations can be fun, but all bets are off when next generation of hardware comes out, and a thousand man-hours spent on compiler/optimizer. And most performance increases the last decade have come from multi-process/threading, while single core execution have actually become slower. I think in the future it will be increasingly more important for algorithms to work in parallel, so the performance can scale with the number of CPU/cores or Moore's law.
- tempguy9999 8y agoI don't agree. > but all bets are off when next generation of hardware comes out the sentinel trick reduces the number of checks, so should be independent of hardware. > and a thousand man-hours spent on compiler/optimizer I can't see a conventional compiler ever automatically doing the sentinel trick as it relies on knowing at least 1. whether multithreading will be happening 2. the size of the array, as the trick's likely increasingly pointless as it outgrows the cache, and possibly other stuff I can't think of. I might also disagree on making things parallel - cache aware code can bring significant speedups on single threads so that first, then parallise. disclaimer: I'm not Knuth/Terje Mathisen/Hennesy or Patterson.
- turogallus 8y agoExcept that the optimization seem to be quite spectacular. Compiling pantalaimon's code, there doesn't seem to be any significative difference between the two algorithms with the default compilation parameters of gcc. However compiling with gcc -O3, Knuth's algorithm is almost twice as fast on an Intel i7-7700HQ, old tricks still work well: naive search found: 0, took 597719 ns found: 0, took 601291 ns found: 0, took 593332 ns found: 0, took 592513 ns found: 0, took 592799 ns found: 0, took 592409 ns found: 0, took 592563 ns found: 0, took 592289 ns found: 0, took 631602 ns found: 0, took 592928 ns average: 597944.50 ns knuth search found: 0, took 300860 ns found: 0, took 318691 ns found: 0, took 317502 ns found: 0, took 317348 ns found: 0, took 351612 ns found: 0, took 317625 ns found: 0, took 318217 ns found: 0, took 312106 ns found: 0, took 397532 ns found: 0, took 318284 ns average: 326977.69 ns Just for fun, here is the dump of assembler code for function search_knuth: 0x0000000000001220 <+0>: add %rsi,%rdx 0x0000000000001223 <+3>: mov %edi,%eax 0x0000000000001225 <+5>: mov %dil,(%rdx) 0x0000000000001228 <+8>: cmp (%rsi),%dil 0x000000000000122b <+11>: je 0x1238 <search_knuth+24> 0x000000000000122d <+13>: nopl (%rax) 0x0000000000001230 <+16>: add $0x1,%rsi 0x0000000000001234 <+20>: cmp %al,(%rsi) 0x0000000000001236 <+22>: jne 0x1230 <search_knuth+16> 0x0000000000001238 <+24>: cmp %rsi,%rdx 0x000000000000123b <+27>: setne %al 0x000000000000123e <+30>: retq And here is the dump of assembler code for function search_naive: 0x00000000000011e0 <+0>: add %rsi,%rdx 0x00000000000011e3 <+3>: mov %edi,%eax 0x00000000000011e5 <+5>: cmp %rdx,%rsi 0x00000000000011e8 <+8>: je 0x1205 <search_naive+37> 0x00000000000011ea <+10>: cmp (%rsi),%dil 0x00000000000011ed <+13>: jne 0x11fc <search_naive+28> 0x00000000000011ef <+15>: jmp 0x1210 <search_naive+48> 0x00000000000011f1 <+17>: nopl 0x0(%rax) 0x00000000000011f8 <+24>: cmp %al,(%rsi) 0x00000000000011fa <+26>: je 0x1210 <search_naive+48> 0x00000000000011fc <+28>: add $0x1,%rsi 0x0000000000001200 <+32>: cmp %rsi,%rdx 0x0000000000001203 <+35>: jne 0x11f8 <search_naive+24> 0x0000000000001205 <+37>: xor %eax,%eax 0x0000000000001207 <+39>: retq 0x0000000000001208 <+40>: nopl 0x0(%rax,%rax,1) 0x0000000000001210 <+48>: mov $0x1,%eax 0x0000000000001215 <+53>: retq
- lisper 8y agoWhat happens when you make the array size larger than your processor cache?
- drfuchs 8y agoWith some improvements to pantalaimon's test, and compiling with -O3, Knuth's scheme is 25% faster than the naive search on my 2012 MacBook Pro with latest developer tools (Apple LLVM version 10.0.1 (clang-1001.0.46.4)): naive search average: 779106.00 ns knuth search average: 593421.56 ns The sources are in http://codepad.org/G2SBmTnC http://codepad.org/G2SBmTnC and the changes were mostly removing constants here and there to keep the super-smart compiler from unrolling the loop in the naive case (which in the real world, it wouldn't, as the size of the array would not be known at compile-time). Also, searching for a 32-bit integer is way more realistic than searching for a byte! The inner-loops are pretty much as you'd expect (although why it uses two registers for addressing the array is beyond me). Knuth: LBB1_1: cmpl %edi, (%rdx,%rcx) leaq 4(%rcx), %rcx jne LBB1_1 Naive: LBB2_8: cmpl %ebx, (%r12,%rdx) je LBB2_11 addq $4, %rdx cmpq %rdx, %rax jne LBB2_8 Of course, all the comments about not being thread-safe are correct, and you probably only want to do this trick in primitive environments where you can allocate an extra slot at the end of the array when it's first created. But it's a nice trick when circumstances call for it.
- lisper 8y agoWhat happens when you make the array size larger than your processor cache?
- drfuchs 8y agoMaking the array a thousand times bigger (~5Gigabytes): #define ARRAY_SIZE 1234567890 #define ITERATIONS 10 still results in a 20% speed advantage for Knuth: naive search average: 790441856.00 ns knuth search average: 627306112.00 ns It would be great to see if these results hold up on the most recent CPUs (compiled with -O3, of course). By the way, the results varied a bit between runs, but always had about the same ratio.
- lisper 8y agoWow, that is so weird. I would have expected this to be entirely dominated by memory latency. I'm also scratching my head trying to figure out why this only shows up with -O3. I would have expected the exact opposite, i.e. a bigger difference on lower optimization settings.