pcordes · HackerTrans

9 yıl öncediscuss

Actual high-performance-computing clusters are typically used efficiently, running well-tuned code. BLAS libraries (matrix multiplication) are usually very heavily optimized.

Of course, a lot of code just uses these optimized building blocks and ends up doing multiple passes over the data instead of doing more with each pass while it's still hot in cache. It's disappointing that we still don't have optimizing compilers that know how to produce code for an efficient matrix multiply or something, and be able to mix in some other work right into that.

Your point definitely applies to server farms, though, running a huge stack of interpreted languages and big clunky "building blocks" instead of something written efficiently.

pcordes

9 yıl öncediscuss

You're basically asking why Intel doesn't expose their internal uops as an ISA that you can program in. See my answer on a SO question asking exactly that. https://stackoverflow.com/a/32866797/224132

The other answers on that question make some good points, too.

Most instructions decode to a single internal uop already, so x86 machine code is just a compact way of programming in uops.

Things like variable-count shifts are multi-uop because of x86's legacy CISC flag-handling, but BMI2 fixes that by giving you no-flags shifts that do decode to a single uop.

You're usually not missing out on much.

Also, there's plenty of voodoo besides just translation to uops. Programming in uops directly wouldn't help you figure out why there seems to be some kind of limit on register reads per clock (http://agner.org/optimize/blog/read.php?i=415#852) for example, since the uops you'd program with would still have register renaming done to them as they're issued into the out-of-order core.

pcordes

9 yıl öncediscuss

Nice. It seems gcc/clang don't know that trick. They still divide and then check that x/3 * 3 == x. https://godbolt.org/g/V4kfuu. (So do ICC17 and MSVC CL19).

pcordes

9 yıl öncediscuss

Presumably the usual technical meaning: https://en.wikipedia.org/wiki/Critical_section

i.e. the part protected by a lock() / unlock() in multi-threaded code.

pcordes

9 yıl öncediscuss

This is almost exactly the same as dmitryg's answer, using a state-machine the same way. It would compile to nearly the same code, but with an extra instruction to sign-extend the first char into a register before adding.

You did remove a level of indirection for the format-strings, though. You could have done that with

    struct state {
        int next;
        char fmt[6];
    };

Anyway, this has probably a 5 cycle loop-carried dependency chain on Skylake, from x += *x; compiling into a 4-cycle latency movsx rax, byte [rdi], then a 1-cycle add rdi, rax. (Or whatever registers the compiler picks).

If you'd stored pointers, you could have got it down to 4 cycles on Skylake for the load-use latency of a simple addressing mode ([reg + disp] where displacement is 0..2047).

pcordes

9 yıl öncediscuss

It's pretty ridiculous to pretend that printf is free. The crux of the matter is to concat string constants and string-representations of integers into a buffer. "buzz\n" is only 5 bytes, so you can store it in a uint64_t.

Also, no, a typical x86 CPU would take about 4 or 5 cycles per iteration even if printf (and the cost of moving its arguments into the right register) was free.

state = nfo[state].next is a pointer-chasing loop-carried dependency chain, so you will bottleneck on L1D load-use latency. (For Skylake, 5 cycles for a complex addressing mode: http://www.7-cpu.com/cpu/Skylake.html).

If out-of-order execution could overlap many of these loops then the throughput could be close to 1 iter per clock.

pcordes

9 yıl öncediscuss

One common trick is to handle the %3 and %5 with down-counters that you reset to 3 or 5 when they reach zero. Or better, unroll the loop by 3 so you only need one down-counter.

(Also, no, `%5` isn't "horrifically" slow when it's a compile-time-constant modulus: you or the compiler can do it with a multiply and shift for the integer division, and then x%5 = x - (x/5 * 5). https://godbolt.org/g/3HwBrF. It still sucks though.)

I wrote an x86 assembly FizzBuzz for fun a while ago, intended to be an example of how to optimize (https://stackoverflow.com/a/37494090/224132). Some parts of it kind of suck, though. I made some parts efficient (like appending "buzz\n" to a buffer with a mov [rdx], r13 / add rdx, 5), but left in too many conditional branches and a function call instead of inlining everything when unrolling.

I'm glad so many people like my post that the OP linked. It was fun to write. :)

pcordes

10 yıl öncediscuss

I added a link to this post in an update to my answer (where I added a section about causing AVX<->SSE transition stalls, which is actually highly plausible).

pcordes

10 yıl öncediscuss

I finally got around to re-ordering my answer to put the "cheating" ideas like gimping the compiler with atomic<uint64_t> on `-m32`, or atomic<long double>, at the end. I totally agree it was crap, but my answer just kind of grew that way, and left the good stuff buried.

I'm now pretty happy with my answer's presentation of some actually relevant ideas that are specific to slowing down an out-of-order pipelined CPU like Haswell. The assignment itself doesn't seem to have much scope for solving it the way it seems to be intended. There's not a lot you can do with those dependency chains that out-of-order execution isn't going to eat for breakfast.

Since the answer has gotten widely publicized, I've tried to include links for further reading on anything people might want to know more about. It's up to 28227 chars in length now, though :P

pcordes

10 yıl öncediscuss

That's correct; I'm sure icc has vectorized versions of those functions to inline. Each monte-carlo iteration is independent, so the code vectorizes very easily if you have a vectorized RNG and vectorized exp() and log(). (vector sqrt() is available in hardware, so even gcc and clang will vectorize that, but not exp / log even with -ffast-math)

pcordes

10 yıl öncediscuss

I'd love it if the OP would clarify what kinds of things are and aren't allowed. I voted to reopen even without that, since I thought it was an interesting question.

Every rule has exceptions, and judging from the voting clearly a lot of people are ok with allowing this specific exception to the rules.

I just wish the 100 votes were spread out over more days. I answered because I personally thought it was interesting, and I'm not really a rep whore, but still. :P

pcordes

10 yıl öncediscuss

That's what I found when writing my answer on SO. The only justification I could come up with for using memory was to generate all the random numbers first, then use them later.

I did include several potential microarchitectural slowdowns, like causing a store-forwarding stall by modifying just the high byte of `double` with an XOR to flip the sign bit. That isn't much of a stretch, but will hurt a lot

Multi-threading with a shared atomic loop counter is also really good, and maybe worse than you'd naively expect (i.e. easy to justify re: diabolically incompetent).

comments