131–140 of 149 posts
Earlier quoted context omitted.
Do most array structures have a pointer to last element? Or similarly useful do they track length?
Not in C and similar languages, but you already need to know the length for the bounds check.
Earlier quoted context omitted.
I bought an international edition of a text in college because it was priced significantly cheaper. And indeed, it had all the same problems, but they had been re-arranged, so when the professor assigned problems "5-15", I needed to know the mapping from the US 5-15 to the international version's numbers. Which, by quickly thumbing through another student's copy, I could generate pretty rapidly, but boy was that anno…
We had a professor that kept mappings for 2-3 versions behind and basically allowed you to buy the used book on Amazon for about $12 compared to $200 for the new one. It's these little things that make your professors stand out.
The calculus text at my university was a “custom” edition that came unbound and shrink-wrapped and still cost as much as a regular new text. My calculus IV professor said many times over the first week: “Do not take your copy down to the document shop on Jackson avenue and run off copies of the relevant chapters for your friends, because that would be illegal. I say again, I cannot advise you take your copy down to the document shop on Jackson Avenue next to Pizza Hut and run off copies of the relevant chapters for your friends because that is IP theft and illegal.”
Fantastic professor—I really that semester because of him.
Earlier quoted context omitted.
Which contexts? I used to be a physicist so voodoo around constants so that we end up mass having energy units was common but I cannot think off my head of problems better where imperial units are easier. There are certainly, I am genuinely curious which.
Well, it's easy to remember that the speed of light is roughly 1.8 terafurlongs per fortnight...
Now I know what imperial units are useful for, thanks.
> 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 i…
naive search average: 779106.00 ns
knuth search average: 593421.56 ns
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
LBB2_8:
cmpl %ebx, (%r12,%rdx)
je LBB2_11
addq $4, %rdx
cmpq %rdx, %rax
jne LBB2_8
> 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 i…
Except 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…
> 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 i…
With 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 and the changes were mostly removing constants here and there to keep the super-sm…
Earlier quoted context omitted.
With 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 and the changes were mostly removing constants here and there to keep the super-sm…
What happens when you make the array size larger than your processor cache?
#define ARRAY_SIZE 1234567890
#define ITERATIONS 10
naive search average: 790441856.00 ns
knuth search average: 627306112.00 ns
By the way, the results varied a bit between runs, but always had about the same ratio.
> 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 i…
Optimizations 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…
> 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.
Earlier quoted context omitted.
What happens when you make the array size larger than your processor cache?
Making 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…
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.
Earlier quoted context omitted.
Making 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…
Wow, 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.
However, when I modify it to not include they key in the search array (`myarray[i] = random() & 0x7fffffff;`, `key = 0xffffffff;`) I see the same behavior:
-O0, i5-2500K
naive search
average: 1773653.88 ns
knuth search
average: 1865263.62 ns
naive search
average: 590244.25 ns
knuth search
average: 345119.06 ns