cycles needed for floating point asm?

[DarkBeam]

Hello guys,
I am evaluating about making a "faster" but very accurate polynomial version of trig functions.
Too bad I can't find anywhere basic infos.
How many cycles does it take to eval FRNDINT versus FSIN?
And how many for FPATAN? And FSQRT?
Thankies

[claude]

http://www.agner.org/optimize/ "4. Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs"

The trouble is it isn't just cycles per instruction that you can add up - pipelining has a big effect so you can do something else useful while a many-cycle instruction is running... measuring real code is probably the best way...

Some quick numbers from the PDF for Intel Haswell (latency column):
FRNDINT 11
FSIN 47-106
FPATAN 96-156
FSQRT 10-23

Which does correspond to my own experience (trig is slow, replacing it if possible is usually good).

[cKleinhuis]

hehe, just use a 256 entry sine lookup table, and round PI to 3

[DarkBeam]

Hehe Chris, lut are very hard to treat for me!
Only 11 cycles for frndint, hrm! Sure? Either my processor has a fast sin or a slow roundint.
Or maybe I added too many instructions afterwards

Ok, my idea was this, it gives a very accurate result (1e-8 error worst case)
1. x = x * twopiinv; x = x - roundint (x); x = 4. * x; // not sure about those passages ...
2. Fold (x, 1); // maybe a source of slowness due to abs() inside fold.
3. ox =x; x = abs(x); x2 = x^2 ... etc
4. x = ox* (pihalf + a x + b x2 + c x3 + d x4) / (1 + e x + f x2 + g x3) // divisions are slow

A...G coeffs are found using Maxima using a simple linear system, to force the function to be exact in some points. I use a fractional function to reduce fp errors without losing flexibility while the traditional approach was to use high x powers.

There are premade very good approx around but not that precise. will see!
Thanks for the kind reply!

[DarkBeam]

Ok, of course now I find all

A great solution is Chebychev up to x^7.
Chebyshev: max error around 6e-7, f(x) = 0.99999660x-0.16664824x3+0.00830629x5-0.00018363x7
Range = -pi/2 to +pi/2, degree 7 (4 terms)
Out of range use reflections (and frndint)

Found in - http://stackoverflow.com/questions/345085/how-do-trigonometric-functions-work/394512#394512

Now I hope it's really fast!

[hobold]

Chebychev polynomials are a good starting point. If you are looking for perfection, you could construct one of the so-called "minimax polynomials". These are the most numerically precise polynomial approximation of a given smooth function. However, there are no explicit formulas to determine the coefficients.

In practice, one uses some numerical optimization algorithm to find the coefficients which minimize the maximal error. A Chebychev polynomial is probably a good starting point for that kind of search.

Edit: you might find Estrin's scheme interesting, an evaluation method for polynomials that allows modern processors to better utilize their parallel execution units: https://en.wikipedia.org/wiki/Estrin%27s_scheme

[DarkBeam]

Another thing I did not found. Do you know if there's a place with premade Cheby polynomes for ArcTan (even for x inside [-1,+1]? I found many interesting formulas, but it's dispersive because error is rarely specified.

[claude]

http://www.coranac.com/2009/07/sines/ nice article about fixed point sin() approximation on ARM, probably much will also apply to floating point on x86 or amd64

[DarkBeam]

  Ahyeeah!

The Chebychev polynome works perfectly, using folds and I save one multiplication, using modified multipliers like that.

Code:

1. x = x * 0.15915494309189533576888376337251; x = x - roundint (x);
2. Fold (x, 0.25); // abs(x+Fold) - abs(x-Fold) - x
3. ox =x; x = sqr(x); x2 = x^2 ... etc
4. x = ox* (6.283163944 - 41.3371315 x + 81.34042392 x2 -70.99090501 x3 )

You have a sin() but 20% faster (circa) I am happy!

[DarkBeam]

Ah! found.

Minimax polynomes for any trig function here: http://www.geometrictools.com/Source/Functions.html

[quaz0r]

i know i sound like kind of a party pooper but the thing about this stuff is that you are never going to be the first person who has asked "how can i make some basic math functions fast and efficient?"  everyone has already asked that question before, everyone has already worked on solving that question a million times over already, and the best approaches have already been implemented and refined a million times over in standard libraries and such since the dawn of computing.  and hand tailored assembly for every architecture has also been written already to maximize performance of these things with architecture specific code (the intel MKL and amd's ACML for example).  so the question isnt so much "what new and groundbreaking way can i invent to calculate the cosine" so much as "what methods have already been implemented a million times by tons of other people for every possible language and architecture?"   

on a similar note ive noticed in general that pretty much all the programs ive seen that are written by people on fractalforums do not make use of libraries, not even the standard library for the language a program was written in.  it kinda reminds me of how more people tended to approach programming 30 years ago.  maybe people arent super experienced coders, but there also appears to be a mindset that people want to do something that is way more amazing than what anyone else has ever done.  while that sounds like a fun endeavor, in practice that is just hardly ever going to be the case, especially if you are not an expert coder.  need to save a jpeg?  the culmination of all the brightest minds dedicated to that task and the pinnacle of human achievement in the history of saving jpegs is already available in a library somewhere.  need some arbitrary precision?  the culmination of all the brightest minds in the history of humanity dedicated to coming together and solving that task has already produced a library for that.  need to calculate a cosine?  same deal.

kate gregory gave an excellent little presentation about this at the last CppCon, specifically at 29m30s:    <a href="http://www.youtube.com/v/BiYliKliFvs&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/BiYliKliFvs&rel=1&fs=1&hd=1</a>

[hobold]

while that sounds like a fun endeavor

Added highlighting to answer your question.

Longer answer: when I am paid to write software, then time is short, perfection is frowned upon (because "good enough" is what sells), libraries are good (because someone else is responsible for testing and bug fixing code in there), and nobody cares what I learn in the process.

When I am programming on my own, I have all the time in the world to polish whatever irrelevant detail I always wanted to understand better. I use libraries that I want to familiarize with. I write stuff myself that I want to learn the basics of. I skip things that would be an absolute requirement for product quality code, but that I don't want to bother with for a single run of a prototype algorithm.

In short: my goals can differ a lot. In one situation I want to get something done. In the other situation I want to gain insight.


A note on existing numerical libraries. Earlier in my life, I earned the friendship of folks who wrote such highly tuned code for a living. (That happened due to a few cases of undue perfectionism on which I had wasted my spare time, and which caught their attention.)

These libraries are usually created in "get something done" mode. The experts who do that work are on somebody's payroll. And that somebody, being a successful business(wo)man, usually tends to impatience.

Existing high performance libraries are typically very good. But they are never perfect. When the next processor revision is released, the timing of the execution pipelines is rebalanced. But the library is still tuned for the previous hardware. There is usually no money budgeted to rewrite the library's existing functions. Instead, new features keep getting added to the library; tuned for whatever machine is interesting at the time.

In other words, the hardware target keeps shifting under the code tuners' feet. But their boss would rather release that software product now, instead of spending another three months re-tuning it.


The point of my ramblings is this:

1. It would be a herculean task not to use libraries at all and do everything over and over again. Libraries are good. Trying to write a big application from scratch without using any existing libraries would be pretty insane.

2. A single programmer with sufficient time and dedication, when focusing on a single detail of implementation, can occasionally outdo a team of experts. Trying to do that is not nearly as insane.

[quaz0r]

obligatory devil's advocacy

of course.  no person is perfect, no software is perfect, no code is perfect, no library is perfect, no team of all the world's biggest geniuses is perfect, no library that team of geniuses created is perfect.  pretty much no human and no thing ever created by a human or group of humans is ever as perfect as it could ever possibly be.  then again, you probably arent perfect either.  and whatever you naively came up with because you never heard of libraries before probably isnt the pinnacle of human achievement either.  but yes, it is of course always possible for one dedicated person or team of persons to reinvent a particular wheel a little better than somebody else might have done.  my point (of course) was more about this general mindset of "maybe this doesnt already exist," or "maybe nobodys ever thought of this before," or "maybe nobodys ever tried to make it fast before," or "maybe ill just reinvent that wheel regardless and hope for groundbreaking perfection and eternal glory" being in the main a rather naive and ill conceived approach to programming.

the point of my ramblings was a general observation regarding a general pattern ive noticed coming from multiple parties responsible for multiple pieces of software being more likely an indicator of inexperience than... the opposite.

[youhn]

Well, here it's not so much about perfection, efficiency or other Key Progress Indicator like goals. People here do whatever the irrational-fluff they want, just because it's fun. Some like the idea of using libs, some experience it as a constraint. Go preach at some other group of coders.

[DarkBeam]

Hey friends don't go crazy
(New emoticon ! )
In my case I am not even programming, that stuff is going into a new set of Mb3d formulas, and of course I didn't claim I found a fancy great polynome invented by me as I pretty much copied everything from other (wise and thoughtful) sources with a minimum effort.
(After I found those of course)
Because many mb3d formulas using sin() are not totally precision-critical so speedups would be very welcomed.
In any case - the 20% speedup can be pushed further using a cheat over rounding integer, so good news back to code!