I am looking for book recommendations when it comes to the optimization and overclocking of processes. Do you have any to recommend? I'm thinking of a book on optimizing compilers, but I have not read any yet.

taby said:
when it comes to the optimization and overclocking of processes.

Something has gone horribly wrong in that statement.

taby said:
Do you have any to recommend?

Optimization is about knowing your options. You measure the code and look at where performance is an issue. You study it, then you figure out what your options are. Would a different algorithm be faster? Would a different data structure be faster? Could something be re-arranged earlier or later or removed or compressed or decompressed or encoded or decoded or moved to a different area or otherwise done differently to achieve a better result? The only way to know those things is to study a LOT of structures and algorithms. You also need to study exactly how your target hardware works. Then when you've made your changes, you measure again and verify that it really did improve.

Optimization is also a moving target. Hardware is constantly changing, compilers are constantly changing. Something that was a major improvement five years ago may be detected and done automatically by a compiler these days, it's an unnecessary complication. Something that used to be a performance improvement decades ago may be an impairment today. Something that you feared may have been a problem might be measured only to discover it isn't an issue at all. And something that is an improvement on one computer, such as leveraging a large L2 and L3 cache, may cause massive slowdowns on another computer that has much smaller cache, you can sometimes see that on patterns that run fast on an Intel i7 but terribly slow on an i3, where the reason is just cache effects. Last year's CPU and this year's CPU each take advantage of different patterns, and benefit from different optimizations. This year's compilers will produce different results than last year's compilers.

You must learn how to use the measuring tools, how profilers work and how you get useful results from them. The tools also change rapidly and vary between systems. The PC and Xbox both currently rely on PIX, a free download, but other great profilers exist and it seems every version update changes key features, so websites and docs are the better source, and change constantly.

A few optimizations have even oscillated into use, don't use, use, don't use. The in-place swap with triple xor is one. In the 1980s it was a must-use method to save space and achieve high performance, then it became bad performance, then good again, then terrible with long pipelines, then autodetected and replaced by the CPU with an ideal fix, then that was replaced with a so-so fix, then both options became invalidated and it doesn't matter any more as they vanish in the OOO core and cache. Duff's Device was another, a high performance optimization, then became bad performance, then CPUs detected it and it became either amazing if the CPU detected it or terrible stalls if it didn't. You've got to know your current hardware before applying old optimization techniques and alternate algorithms.

Every good book on algorithms and data structures makes a great study of optimization. Robert Sedgwick's book Algorithms has been around since 1983 and is an amazing study. It's probably the best balance of explanatory teaching and comprehensive depth, and used by universities across the globe. He doesn't show you something like 20 different sorting algorithms across the book just so you can use quicksort, it is because each one has pros and cons and beneficial uses. He doesn't show 40-something different tree and table data structures just so you can use a C++ vector or unordered map, he does it because each one has pros and cons and beneficial uses. Each one offers an opportunity for optimization you might be able to apply in some specific problem.

If you can tolerate it, Advanced Data Structures by Peter Brass is another good, in depth study. TAOCP, The Art of Computer Programming by Knuth is archaic and complex and uses a custom assembly-style language made just for him, but a deep dive into a bunch of algorithmic options for people who love academic text. It is definitely not a good set of teaching books, but if you're looking for alternative ways to do something TAOCP has it covered in it's arcane incantations. Introduction to Algorithms by Cormen et al, and Algorithm Design Manual by Skiena are good books, too. The website the Dictionary of Algorithms and Data Structures (DADS) is great as a reference but assumes a base level of knowledge so it's less good as a teaching resource.

I am reading “Engineering a compiler” 2nd edition, by Keith D.Cooper and Linda Torczon, and it describes how optimizing inside a compiler works. It is aimed at compiler authors, CS university level.

Basically after generating assembly language, it breaks the code down to basic blocks (a basic block has an entry point, a sequence of non-jumping machine instructions, and a jump to next block(s) at the end). It makes a graph of the blocks, and runs algorithms on the blocks and the graph to detect live or dead variables (variables that are needed / unneeded downwards), detect duplicate computations, detect constant computations, etc.

All this is explained in the book at a fairly high level, algorithms are written as iterative math equations, there is no actual code in the book that implements any of the above (except for short pseudo code fragments with little context).

Thanks y'all!

Thanks frob. Yes, I know that it sounds strange, but if there’s time dilation, then there is likely time contraction — via the optimization and overclocking of physical processes. I mean, don’t tell me that a sparrow experiences time at the same rate as a human… the acrobatics that they’re capable of requires something faster in terms of experiencing reality. We are lumbering beasts by comparison.

I will buy that book Alberth. thanks for the recommendations.