Slashdot Mirror
Red Hat Engineer Improves Math Performance of Glibc
jones_supa writes: Siddhesh Poyarekar from Red Hat has taken a professional look into mathematical functions found in Glibc (the GNU C library). He has been able to provide an 8-times performance improvement to slowest path of pow() function. Other transcendentals got similar improvements since the fixes were mostly in the generic multiple precision code. These improvements already went into glibc-2.18 upstream. Siddhesh believes that a lot of the low hanging fruit has now been picked, but that this is definitely not the end of the road for improvements in the multiple precision performance. There are other more complicated improvements, like the limitation of worst case precision for exp() and log() functions, based on the results of the paper Worst Cases for Correct Rounding of the Elementary Functions in Double Precision (PDF). One needs to prove that those results apply to the Glibc multiple precision bits.
Who needs glibc anymore ? we have systemd now.
99.9% of the time, no.
The purpose of the compiler is to identify and optimize the code structures in higher level languages. There are many, many tools, and generations of compilers that have been dedicated to just that. For the vast majority of cases, the compiler will do a better job and leave you with the much easier task of maintaining a high level language codebase.
That said, there are specific operations, most frequently mathematical in nature, that are so explicitly well defined and unchanging, that writing them in ASM may actually allow the author to take procedural liberties that the compiler is unknowledgeable of or exist in such a way that the compiler is unaware of.
The end result of such code is typically virtually unreadable. The syntax masks the math, and the math obfuscates the syntax. But the outcome is a thing of pure beauty.
-Rick
"Most people in the U.S. wouldn't know they live in a tyrannical state if it walked up and grabbed their junk." - MyFirs
It looks like the slowest paths of the transcendental functions were improved by a lot. But how often do these paths get used? The article doesn't say so the performance benefits may be insignificant.
From TFA, it sounds like the functions in question (pow() and exp()) work by first looking at a look-up table/polynomial approximation technique to see if the function can use that to get an accurate-enough value, then running through a series of multiplications to calculate the result if the table/approximation method wouldn't be accurate enough. Since this work improved the actual calculation part, my guess is that it will improve quite a few cases. TFA does say the lookup table method works in the "majority of cases", though it doesn't say exactly how big a majority, so it's hard to say exactly.
"None can love freedom heartily, but good men; the rest love not freedom, but license." --John Milton
Keep in mind: this is [w]hat the compiler tried to do; when you start down this path you are saying "that fancy compiler doesn't know what its doing, I'll do it all myself".
Trying to outsmart a compiler defeats much of the purpose of using one.
-- Kernighan and Plauger, The Elements of Programming Style
If it weren't for deadlines, nothing would be late.
I think that saying "This piece of code is going to be called a lot, so I'll implement it in assembler" is inadvisable. The more reasoned approach is "after profiling, my program spends a lot of time in this routine, so I'll go over the assembler the compiler generated to make sure it optimized correctly". The upshot being, it is useful to be able to read and write assembler when optimizing, but it would be rare that you would produce new code in assembly from whole cloth.
"Because Science" is one step from "Because old book". Try "Because of my experiment testing my falsifiable assertion".
What is perhaps a bit of irony of history, even for humans a lookup table is faster and more precise than manually calculating it via formula. That is why they published books of logarithms. Using interpolation you can even stretch out the precision to several more digits. With a table of values in memory you can also narrow down the inputs to Newton's method and calculate any differentiable function very quickly to an arbitrary precision. With some functions the linear approximation is so close that you can reduce it in just a few cycles.
Even in most trigonometric functions there is a simple table upon which the angle addition formulas are used to get the other values[an old example].
Given the size of most operating systems, where 8k of ram is hardly noticed (most gifs are larger than this), I am actually quite surprised that the lookup table method is not more used. It would seem one of the first things to put in cache on your ALU.
This is generally true, but when you've measured and proven the compiler is generating sub optimal code, it may be time to hand-optimize in assembly. Compilers don't always generate better code than a human. In general, if you have performance critical code, I find it better to write it in C/C++ first, then examine the compiler optimized assembly. IIF it is shown to be sub optimal, then you optimize by hand. Compilers are also finicky. One algorithm it may optimize it well, but make a slight change in a high level language and sometimes the compiler optimizer gets confused and generates horridly different and rather un-optimized code. Different compilers may also optimize differently, so it may be ideal to do the assembly by hand to get uniform performance across compilers. In general, if performance is *that* critical to you, you need to examine by hand those critical sections to verify the compiler is doing what you expect it to do. This isn't even to mention that compilers target the lowest common denominator of the architecture you specify. i.e. if you target x86, most compilers will not utilize any SSE or SIMD instructions unless separately and explicitly enabled.
Indeed it is, however it's still rare that you have to go to ASM in those cases. In simple cases the compiler already generates SIMD code on code which can benefit from it, and for almost all other cases, there are C intrinsics.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Not just every architecture. In general, you may need to write it for every major revision of every architecture. As CPU pipelines and instruction sets change, the hand-crafted assembler may no longer be optimal.
(Exercise: Write an optimal memcpy/memmove.)
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Not just every architecture. In general, you may need to write it for every major revision of every architecture. As CPU pipelines and instruction sets change, the hand-crafted assembler may no longer be optimal.
(Exercise: Write an optimal memcpy/memmove.)
I have some math code that I optimized in assembly for Pentium Pro (686) back in the day. The performance improvements vs C are getting smaller and smaller but they are still positive. At least through Core Duo, which was the last time I had access to that code. Whenever we upgraded compilers, or we upgraded our development systems, I would test my old assembly code against the reference C code.
Regarding a case like your memcpy example. An assembly version may still be warranted. A piece of software may need to optimize for the low end computers out there. So if the assembly is a win for the low end and neutral or a slight loss for the high end then it may still be the way to go. The low end is where the attention is needed to expand the pool of computers included in the minimum system requirement, think video games. You have to optimize for the three year old computer, its the one having performance problems, not the new computer. And if it does matter on the high end its simple enough to have earlier generations of an architecture use the assembly and later generations use the reference C code. Fear of future systems is no reason to leave current systems hobbled.
I once found an Bresenham line drawing algorithm written in Assembly (68k) on a Mac SE (black and white graphics).
That code was extremely complicated and the main mistake was that the author loaded each byte, manipulated it and rewrote it to memory each cycle.
Just to load in many cases the exact same byte again in the next cycle.
I immediately came to the idea to not load and store the bytes every cycle, and from that the jump to figure if you could also use words and long words depending on how steep the line was, was easy.
So I first wrote code in C that used chars, ints and longs depending on steepness and changed consecutive bits until it needed to access another "word". Each "word" was only loaded once into a register and was only written after all necessary bits where changed.
My C code rewrite was so fast (more than 100 times than the original assembly) that I never rewrote that in assembly itself.
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
No, you can do quicksort in one recursive call. Even in the two recursive call scenario, an optimizing compiler will turn it into one recursive call and a loop - it's such a basic operation it's called tail recursion.
Basically if you have a recursive function call at the end of the function, instead of making it a recursive call, you can reuse the current stack frame by readjusting the input parameters (on the stack) and jumping to the beginning of the function, saving yourself the headache of setting up and tearing down a stack frame because you're reusing the current stack frame. (or in other words, you're doing a loop).
In fact, this can be generalized into tall call optimization where if you call another function at the end of a function, the optimizing compiler will reuse the stack frame of the current function for the call instead.
Syntactically the code looks the same, but the output is vastly different because you get operations that rewrite the stack frame (a particularly smart compiler might actually put the parameters of the call right where they need to be by moving the arguments around so the final two instructions is a stack adjustment to compensate for different stack sizes and a direct jump, so when the tail function returns, it doesn't stop back at the calling function, but goes back to the original function.
So yes, you're right in that there's supposed to be two recursive calls in quicksort, but in practice, there's only one because the last one is always tail-recursive so compilers merely reuse the existing stack frame.
File a bug report for the compiler with 'missed optimization opportunity' in the title and a reduced test case.
We like to see real-world examples of where we're generating bad code - if we don't see them, we can't fix them.
I am TheRaven on Soylent News