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

Beating the Compiler

codersnotes.com

Post reply on HN
Print view View original

81–89 of 89 posts

Re: Beating the Compiler

#81

Post by kayamon »

titzer wrote: post #61
titzer wrote: post #50

Nice job. Here's 900,000 lines of C++ code for you to now translate to assembly. And after you're done with that, I'd like to change a few lines and have you do it over again, preferrably 100 times a day. /sigh /compiler person

It'd be nice if people replied instead of just downvoting. You're missing the point of a compiler. It does a huge amount of work to reliably get a very, very good solution to a huge problem in a reasonable amount of time. Depending on the optimization settings, of course it is not going to try its hardest to get the very best code out of every single function. Besides, you can always use the output of the compiler as…

I can't beat the compiler even 0.01% of the time? Really? Because that's the point of the article -- I just grabbed the first piece of C I found and managed to beat the compiler.

Re: Beating the Compiler

#82

Post by gfody »

DannyBee wrote: post #43
gfody wrote: post #30

Earlier quoted context omitted.

It's totally ridiculous - I spent several years coding almost exclusively in x86 assembly and the prospect that a compiler could best a human at optimizing a specific function is ignorant. The only exception I can think of so-called 'superoptimization' where the optimal sequence of instructions is determined by exhaustively testing every combination. And that's not an effective strategy for anything beyond a handful…

"optimizing a specific function is ignorant" Depends entirely on the domain. Sorry, but i have never seen a programmer come up with the kinds of parallelizing transforms, cache blocking and iteration reordering, etc, that most polyhedral optimizers do. Now, if you aren't doing these kinds of things, and are just trying to optimize the hot loop of some simple program, yeah, you can definitely win given enough time, be…

You speak as though all low-level optimization is alignment, unrolling, pairing, etc.. These are basically micro optimizations that yield negligible gains unless applied over a large code base. That Pluto output is just a wall of code because it has been unrolled several times, it's not any sort of impressive optimization achievement.

A human would probably convert this to fixed point, convert the entire inner-most loop into a couple of address operations and a single fused multiply add, process the array 64 bytes per iteration without unrolling anything. At that point it's probably 10-20x more efficient than that slab of polyhedral bullshit and finally he'd come back to carefully pad here and there to avoid misalignment penalties.

As for optimizing for 4 cores - you take your shiny hand-polished assembly routine and spin it up on 4 threads, most likely in high level code since you're talking to the OS to get threads, synchronize them, etc. It's not wise to chase parallelism at a low level because that goes counter to minimizing the overhead costs in setting it up.

> But you also are often starting with the output of a good compiler.

No, nobody does this. I mean maybe if you're just learning assembly. Starting with the compiler-generated garbage does not help you other than maybe by giving you a benchmark to beat.

Re: Beating the Compiler

#83

Post by Vendan »

bArray wrote: post #78
to3m wrote: post #60

Earlier quoted context omitted.

What's wrong with using the best result? If you're concerned the code could run faster than possible: don't be :)

What if the test data is random? Could just get lucky and get a happy day scenario.

Then both versions should get that "happy day"? If you are using distinct random data for each version, then you aren't really benchmarking properly.

Re: Beating the Compiler

#84

Post by chriswarbo »

refset wrote: post #70
chriswarbo wrote: post #58

Compilers are usually at a disadvantage compared to human programmers, as they're under pressure to produce code as quickly as possible; seconds if possible, minutes at worst. A human may spend many hours or days writing, profiling, testing, etc. This biases the kinds of algorithms that compilers use (especially JITs, since they have even stricter requirements). It would be nice to have a compiler/optimiser/analyser/…

Your description of the assistant reminds me of a Clojure talk I watched recently[1] where the speaker outlines how a central pool of knowledge about invariant compilation properties could embody the scientific method. [1] "Bare Metal Clojure with clojure.Spec" https://www.youtube.com/watch?v=yGko70hIEwk

Just watched the talk. The technique the author's discovered is called "supercompilation" (note: this is distinct from "superoptimisation", mentioned in sibling comments).

The idea is to use an evaluation strategy which works at compile time, reducing statically-known expressions whilst shuffling around unknown values symbolically to preserve the semantics. The result ends up folding constants, inlining, unrolling, etc. automatically, just like the examples in the talk.

Whilst supercompilation can be slow, the main criticism is that resulting code is quite large, due to the amount of inlining.

The main difference between supercompilers and the technique discussed in the talk is that supercompilation is provably correct: it doesn't rely on testing or placing exhaustiveness requirements on the user. I don't think it's necessary to sacrifice correctness; the speaker mentioned the use of guards in JITs, and how he avoids them for speed, but I think that since we're performing such extensive rewriting of the code anyway, many redundant guards can be supercompiled-away, and those remaining can be shunted to the start of the program, so that no branches appear in the hot path.

The allusions to the scientific method seem to be about properties/invariants, and potential counterexamples to them. I'm all for finding and sharing properties of programs, both conjectured and proven, although I don't like the idea of assuming the conjectures are true.

I've looked into this in Haskell, and found some great work, including:

- QuickSpec (v1 https://hackage.haskell.org/package/quickspec and v2 https://github.com/nick8325/quickspec ) which conjectures equations about functions by testing them on random inputs.

- HipSpec ( https://github.com/danr/hipspec ) which does the same as QuickSpec, but automatically proves the equations so they're guaranteed to hold.

- The GHC compiler's rewrite rule system ( https://wiki.haskell.org/GHC/Using_rules ) which allows programs to be optimised by replacing regular definitions with optimised versions in particular cases. This is how "fusion" and "deforestation" optimisations are implemented, e.g. https://donsbot.wordpress.com/2010/02/26/fusion-makes-functi...

I think there's definitely some low-hanging fruit there, for finding equivalent expressions, comparing their performance, and generating a list of rewrite rules which the programmer may want to consider adding to their code.

A slightly more ambitious project would use equations/properties about the program to generate a specialised supercompiler (maybe using something like a variant of knuth-bendix completion, ordered such that the normal forms are the higher-performing variants).

Re: Beating the Compiler

#85

Post by bjourne »

qb45 wrote: post #66
bjourne wrote: post #54

Earlier quoted context omitted.

That's very likely. Mine is an AMD Phenom(tm) II X6 1090T. Though I changed your code a little so that the intro looks like this: sortRoutine: ; rdi = items ; esi = count push rbp ; The "cmp esi, 2; jb done; dec esi" corresponds to your "sub rdx, 1; jbe done". That improves it on my machine to 63 ms/loop. If you are interested I can put it online somewhere.

push rbp ; This shouldn't be needed. 8 byte alignment is fine for the CPU itself. The purpose of 16 byte alignment is to facilitate making 16 byte aligned stack allocations.

RSP needs to be aligned to 16 bytes at CALL sites. See f.e https://blogs.msdn.microsoft.com/oldnewthing/20040114-00/?p=...

Re: Beating the Compiler

#86

Post by Joky »

pg314 wrote: post #47
Joky wrote: post #5

This seems quite ridiculous to me, I have seldom seen "modern compilers are always faster than you" but rather "they are good enough that it is not worth it". It provides a very over-confident "conclusion" based on a single dubious test. The main advantage of compilers is that the optimizations scale across a large codebase through inlining for example. Also, just moving from Sandy-Bridge to Haswell for example can h…

I agree with the gist of your post, but the pre-optimised libraries are often optimised for the general case. It can be quite worthwhile to dive deeper in some cases. Replacing e.g. the library malloc with your own pool based allocator or a general hash table with a hand-rolled one where you exploit certain knowledge about the data can be huge wins.

You're right, but what you're describing seems to be on the order of "algorithmic changes" or "data structure changes" to be more suited to your use-case.

It seems to me that it is a higher level than what I was addressing: "I'll write my code in assembly to get it to run faster". Unless you're writing your pool based allocator in assembly ;)

Re: Beating the Compiler

#87

Post by qb45 »

bjourne wrote: post #85
qb45 wrote: post #66

Earlier quoted context omitted.

push rbp ; This shouldn't be needed. 8 byte alignment is fine for the CPU itself. The purpose of 16 byte alignment is to facilitate making 16 byte aligned stack allocations.

RSP needs to be aligned to 16 bytes at CALL sites. See f.e https://blogs.msdn.microsoft.com/oldnewthing/20040114-00/?p=...

See the first answer here

http://stackoverflow.com/questions/612443/why-does-the-mac-a...

I also checked similar manual for AMD and it doesn't seem to mention RSP alignment at all, except that "some calling conventions may require ...".

The CPU doesn't care. It only matters when you call functions which allocate 16B objects on the stack.* This function calls only itself and pushes only 8B words on the stack so it's fine with 8B alignment.

* Some functions generated by C compilers do and they segfault if you call them with wrong alignment. Ask me how I know.

edit:

OK, so I downloaded this code. Results:

  as-is:     78111us
  push rbp:  73093us
  sub rsp,8: 72332us
  sub rax,8: 72222us
Seems to be a matter of instruction alignment, nothing to do with the stack.

Re: Beating the Compiler

#88

Post by bArray »

Vendan wrote: post #83
bArray wrote: post #78

Earlier quoted context omitted.

What if the test data is random? Could just get lucky and get a happy day scenario.

Then both versions should get that "happy day"? If you are using distinct random data for each version, then you aren't really benchmarking properly.

It doesn't say that they both use the same data sets.

Re: Beating the Compiler

#89

Post by Vendan »

bArray wrote: post #88
Vendan wrote: post #83

Earlier quoted context omitted.

Then both versions should get that "happy day"? If you are using distinct random data for each version, then you aren't really benchmarking properly.

It doesn't say that they both use the same data sets.

If they are using different data sets, then I'd say it's an invalid benchmark.
Post reply on HN