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

141–149 of 149 posts

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

#141

Post by drfuchs »

pantalaimon wrote: post #140
lisper wrote: post #139

Earlier quoted context omitted.

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.

First I thought this was because in drfuchs' version both the array and the key are completely random, so it's not likely the key is found before the end of the array is reached. This is of course the more realistic scenario, whereas my test was only testing the worst case where they key is not part of the array. However, when I modify it to not include they key in the search array (`myarray[i] = random() & 0x7ffffff…

Yeah, I was careless on not preserving the nice feature of your code that kept there from ever being a match, figuring that the chances were low of a hit; but of course that assumption went out the window when the array got way bigger. After posting, I noticed the issue, so I made a similar change to yours, and the results didn't change. I do suggest that you change the line that sets 'key' to not make it known at compile-time, to avoid unrealistic optimizations, thus:

  const int key = random() | 0x80000000; // ensure no match

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

#142

Post by pantalaimon »

drfuchs wrote: post #137
lisper wrote: post #136

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…

> It would be great to see if these results hold up on the most recent CPUs (compiled with -O3, of course).

On a Xeon Gold 6146:

-O0

    naive search
    average: 1289837.88 ns
    knuth search
    average: 1304139.38 ns
-O3

    naive search
    average: 272361.28 ns
    knuth search
    average: 270700.78 ns

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

#143

Post by nraynaud »

sjf wrote: post #116
nraynaud wrote: post #114

Earlier quoted context omitted.

I bought a mechanical engineering book, and I found the rent seeking quite clever: the international version(this one was targeted for the Indian market) did not have American units, only SI.

The rest of the world uses SI units, why would you expect anything else in the international edition?

it's the link with money that I found interesting, $100 for the american units (I mean American book have problems in both system of units, aerospace, military and engineering for science tend to work in metric) and $30 for the SI unit only.

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

#144

Post by bjourne »

drfuchs wrote: post #134
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…

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…

This is fun!

    $ clang -mtune=native -march=native -fomit-frame-pointer -O3 -o knuth_search2 knuth_search2.c 
    $ ./knuth_search2
naive search average: 65025704.00 ns knuth search average: 76994680.00 ns

and

    $ gcc -mtune=native -march=native -fomit-frame-pointer -O3 -o knuth_search2 knuth_search2.c
    $ ./knuth_search2
naive search average: 65636020.00 ns knuth search average: 64689948.00 ns

knuth_search2 is your modified code but with 100mb arrays.

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

#145

Post by 9HZZRfNlpR »

tialaramex wrote: post #103
Sharlin wrote: post #75

Earlier quoted context omitted.

Unless that German guy actually lives in the US, I'm surprised he was actually able to a) cash an American cheque somewhere and b) not have to pay an exorbitant service fee for cashing it. Cheques are approximately as common as unicorns in Europe.

My bank informs me that they would charge between £6 and £10 to accept such a cheque as payment into my account - depending on exactly the amount, how it was issued and so on. I guess if you literally wanted it turned into cash on the spot you'd pay a much larger fee corresponding to the risk they'd be taking on that deal.

When I was young I got a check from Google's AdSense. My bank (huge in Scandinavia) told me they don't know what to do with it and will call me back. Eventually they offered 20 euros + 9% to cash it. Felt like robbery but no one really even knows what a check is here, it's extremely rare.

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

#146

Post by blitmap »

matt_d wrote: post #126
blitmap wrote: post #74

Earlier quoted context omitted.

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

The 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/supersc... - Tejas S. Karkhanis and James E. Smith. "A First-Order Superscalar Processor Model." (ISCA 2004) - http:/…

Very much appreciated, sir :-)

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

#148

Post by WrtCdEvrydy »

andrepd wrote: post #94
WrtCdEvrydy wrote: post #81

Earlier quoted context omitted.

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.

>$200 for a textbook with borderline extorsion sale tactics That's the moment I fire up libgen

b-ok.cc?
Post reply on HN