Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I Got a Knuth Check for 0x$3.00

nickdrozd.github.io

Post reply on HN
Print view View original

81–90 of 149 posts

Re: I Got a Knuth Check for 0x$3.00

#81

Post by WrtCdEvrydy »

deathanatos wrote: post #62
edge17 wrote: post #38

Earlier quoted context omitted.

International Editions differ often in the problems at the ends of the chapters in order to protect US and other western markets. Differences in the problems means it discourages students from buying things that may lead to incorrect answers to assigned problem sets. As for things just being flat out wrong, I can only imagine this discourages US/western students from buying International Editions to save money.

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.

Re: I Got a Knuth Check for 0x$3.00

#84

Post by pantalaimon »

lisper wrote: post #72

> 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…

I had to try it myself but it looks like you are right!

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

Re: I Got a Knuth Check for 0x$3.00

#86

Post by cheerlessbog »

lisper wrote: post #72

> 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…

Also 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.

Re: I Got a Knuth Check for 0x$3.00

#87

Post by vram22 »

lisper wrote: post #72

> 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…

>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_scientis...

Re: I Got a Knuth Check for 0x$3.00

#89

Post by lisper »

pantalaimon wrote: post #84
lisper wrote: post #72

> 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…

I had to try it myself but it looks like you are right! 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 19…

Kudos to you for actually doing the experiment! With a control case even! I wish I could give you ten upvotes.

Re: I Got a Knuth Check for 0x$3.00

#90

Post by tedunangst »

cheerlessbog wrote: post #86
lisper wrote: post #72

> 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…

Also 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.

You would probably just swap the last element to temp storage, and swap back after.
Post reply on HN