7 ms·
Improving math performance in glibc
- Marat_Dukhan 12y agoWhy not just merge the CRLibM implementations?
- GFK_of_xmaspast 12y agoAre they actual improvements? The project looks like it's been dead almost five years. (Second guess: ideology)
- Marat_Dukhan 12y agoImplementations in CRLibM are correctly rounded (i.e. as accurate as possible) and are, in my benchmarks, faster than GNU LibM. Thus, they are a Pareto improvement over GNU LibM.
- siddhesh 12y agoThe crlibm code is terrible to read and hence maintain. I had considered including crlibm too during my work but decided against it because it would be a lot more work. Also, crlibm functions are provably correctly rounded only for univariate transcendentals (thanks to the worst case paper I cited in the blog). There is no such proof available for bivariate functions, which is why computing at an arbitrary very large precision (the way glibc does) is the only way to increase the likelihood of correctly rounded results. IIRC crlibm does not even try for bivariates. I believe some documentation on the crlibm website cites benchmark numbers where IIRC glibc performs better (although not by much) in the fast paths of most functions they mention but gets hit really badly in the slow path. Slow path inputs are usually quite rare, but if your application/benchmark hits them regularly enough (especially sice the slow path is a factor of 1000 times worse) then you'll obviously conclude that the performance sucks and that crlibm is better.
- derf_ 12y agoIn many contexts, the problem is not the absolute performance, but the variation in performance. For example, we want the Opus codec to be relatively insensitive to timing analysis, since Opus audio is often encrypted and transmitted over a network. Large variations represent an information leak that could be exploited by an external observer. When we started looking at actual timings, we found that it was mostly pretty consistent, except for huge slowdowns in some frames. The cause? glibc's exp() slow path.
- siddhesh 12y agoWe have had this in our todo list for a while. The leading idea currently is to provide compiler selectable function variants that don't fall into the multiple precision abyss. The biggest challenge here is to come up with data about accuracy of results without the mp path.
- Marat_Dukhan 12y agoSorry, I don't buy the argument that "code is terrible to read and hence maintain" from a GLibC developer. CRLibM does have a bunch or tricky macros to work-around bugs in decade-old compilers for architectures no one cares about, but GNU LibC is not any better in this aspect. CRLibM does not have a provably correctly-rounded pow, but univariate functions can be merged. The paper you cited is about decimal floating-point implementation, it is not relevant to the LibM functions discussed in the article. I have a utility for benchmarking LibM libraries here: https://bitbucket.org/MDukhan/hysteria https://bitbucket.org/MDukhan/hysteria Some benchmarks including CRLibM and GNU LibM are here: http://www.yeppp.info/benchmarks.html http://www.yeppp.info/benchmarks.html
- csense 12y agoAren't these implemented in hardware on most CPU's? Or is this floating point emulation for CPU's that don't have built-in floating point?
- CurtHagenlocher 12y agoI believe on x86/x64 CPUs there's an advantage to doing these operations via SSE rather than using the old x87 opcodes. For instance, you don't need to move data into the x87 registers.
- Narishma 12y agoRight, you have to move it instead into the SSE registers.
- FeepingCreature 12y agoWhere it should be living anyways.
- gsg 12y agoThe hardware implementations often have problems: http://randomascii.wordpress.com/2014/10/09/intel-underestimates-error-bounds-by-1-3-quintillion/ http://randomascii.wordpress.com/2014/10/09/intel-underestim...
- derf_ 12y agoThere's an x87 asm implementation for x86-32 in sysdeps/i386/fpu/e_exp.S [1]. For x86-64, it falls back to the generic C code for exp(), in sysdeps/ieee754/dbl-64/e_exp.c. The sad part is that there is x86-64 asm for a few variants (exp10l, exp2l, expf, expl), but since these are not C90, people tend to avoid them for more portable versions. So, ironically, it can be orders of magnitude faster to compute a long-double expl() than a double-precision exp(). [1] Even the asm contains a lot of extra code to handle edge cases that Intel screwed up, like returning NaN for exp(+/- Inf).
- 12y ago
- fdej 12y agoRelated: I recently published a preprint describing some techniques to speed up evaluation of transcendental functions in the range of a few hundred bits to a few thousand bits: http://arxiv.org/abs/1410.7176 http://arxiv.org/abs/1410.7176
- revelation 12y agoNo wonder people don't like doing floating-point calculations if theres a chance with certain input to have your pow-call fallthrough into a 1000x slower code path. I mean, that should probably be an option. It's realloc all over, plain unusable because of the rare chance the function goes mad and copies data instead of failing.
- GFK_of_xmaspast 12y agoWhy are you blaming this on ~~~floating point~~~ instead of glibc?
- pascal_cuoq 12y agoDo you have a reference for the claim that realloc() is unusable for the reason you say? Many users of floating-point are not using floating-point in hard real-time contexts. Even soft real-time contexts can be fine with Ziv-style successive approximations. Correctly rounded library functions have intangible benefits beyond precision (portability, for instance), but if you don't value these benefits, you can always use inaccurate and always fast functions. You don't even need to invent your own: just rip off the first stage of a multi-stage Ziv implementation. I don't think any of this is the reason why “people don't like doing floating-point calculations”.
- MichaelCrawford 12y agoI am tinkering around with making some library code faster. I don't have definite results yet but I expect to soon. Consider the comment in glibc's qsort that says something like "this works well on a Sun 4/260". That machine is about 25 years old. When I have something to report of course HN will be the first to know. My main focus is the reduction of energy consumption. Often but not always that can be done by making the code faster.
- simonbyrne 12y agoThe easiest way to make elementary functions faster is to use a different libm: the glibc preoccupation with being correctly rounded (ie accurate to within 0.5 ulps) imposes significant performance penalties. For example the glibc log function, which is often the dominant cost in a lot of sampling algorithms, is about 2.5x slower than a straightforward implementation (ie no fancy SIMD tricks) of Tang's 25 year old table lookup algorithm, which is accurate to 0.57 ulps. Recent OS X libms are faster still, and appear to be accurate to about 0.51 ulps, though unfortunately are closed source.
- gaius 12y agoBack in the good old days, Motorola provided a drop-in highly optimized replacement maths library for Power Macs http://uk.mathworks.com/matlabcentral/newsreader/view_thread/1220 http://uk.mathworks.com/matlabcentral/newsreader/view_thread... I remember being amazed in the final year of college, the PowerMac 7600 I'd spent my student loan on, was running my FORTRAN as quick as the DEC Alphas in the lab.
- grandinj 12y agoMaybe this is a place where GLIBC could provide additional variants with improved performance and reduced rounding accuracy.
- cschwan 12y agoDid anyone find the authors commits in glibc's repository? Would be nice to know what he really changed and when.
- siddhesh 12y agoThese are all the changes I made in math during 2.18. They're almost all mp stuff with some code cleanup thrown in. git log --author=siddhesh release/2.18/master -- sysdeps/ieee754/dbl-64