71–80 of 89 posts
Sedgewick's 1978 paper[0] on implementing quicksort has some interesting hand optimizations of the assembly code -- loop rotating, unrolling, etc. I wonder if modern compilers do the same? [0] http://penguin.ewu.edu/cscd300/Topic/AdvSorting/Sedgewick.pd...
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/…
Maybe like PGO? https://en.wikipedia.org/wiki/Profile-guided_optimization
Profiling information could be gathered during testing; we could kill two birds with one stone if we gathered profiling information during property checking, e.g. in the style of QuickCheck/(Lazy)SmallCheck/etc. Maybe with an option to add weights to the test cases, so we can assign a low weight to tests which throw crazy data at the system, like fuzzing, and higher weight to those with realistic data generators, golden tests, etc.
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/…
There's this [1], there are also some superoptimizers that will save the optimizations they find for later use, such as [2] [1] https://en.wikipedia.org/wiki/Superoptimization [2] https://github.com/google/souper
Souper is a cool project, and I definitely agree with the use of such techniques as a form of static/dynamic analysis to inform the user, rather than as a compilation step.
Whilst the time taken by superoptimisation is a big problem, another big problem with this kind of approach is its unpredictability. Rather than using the output of such optimisers directly, it seems preferable to use those optimisers to find hints which we can annotate our code with; that way, the performance will be more predictable, and more robust to code changes.
why the best-case was chosen instead of mean or median?
You should never do this. Best-case favors outliers and does not represent expected performance, which is what we care about. Just because the stars happen to align one time doesn't mean you report that run. Consider the following runs of two systems: system A: 10s, 10s, 10s, 10s, 10s, 10s, 10s, 5s system B: 6s, 6s, 6s, 6s, 6s, 6s, 6s, 6s Which one is faster? (Hint: don't say system A)
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
I think a more data-based approach would be preferable, for example we might think of "source text", "preprocessed", "lexed", etc. as being tables in a relational database, and the phases of the pipeline as views/projections which populate one table from another. Optimisation would just be a one:many relation, with a single source text corresponding to multiple possible expressions. This data could be stored, collated, mined, augmented, etc. by various other processes, which allows more approaches to be taken than just compiling.
Of course, this is just one idea; and the relational part would only need to be an interface to the data, it could be computed lazily, and wouldn't necessarily be implemented with an actual RDBMS storing all of the intermediate bits.
Earlier quoted context omitted.
> I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has. From the makefile: GCCFLAGS = -O3 --std=c++11 MSFLAGS = /nologo /Ox /Ob2 /Ot /Oi /GL
Would march=native and fstrict-aliasing do any difference? It would be interesting to compare the compiled asm with the hand rolled one. The code has some potential improvements also but maybe the compiler is smart enough to find them, such as reading pivot.key in the loop even though it doesn't change.
As a result, most high level programming has very poor performance - whatever the compiler quality. This is certainly why we keep waiting seconds for simple operations.
Questioning compiler output is a very good exercise to become a better developer, whether you can beat the compiler or not.
why the best-case was chosen instead of mean or median?
You should never do this. Best-case favors outliers and does not represent expected performance, which is what we care about. Just because the stars happen to align one time doesn't mean you report that run. Consider the following runs of two systems: system A: 10s, 10s, 10s, 10s, 10s, 10s, 10s, 5s system B: 6s, 6s, 6s, 6s, 6s, 6s, 6s, 6s Which one is faster? (Hint: don't say system A)
Is not a tail-recusrion version of the quicksort algorithm needed to really allow compiler to optimize performance?