There Are Only Four Billion Floats – So Test Them All

http://randomascii.wordpress.com/2014/01/27/theres-only-four-billion-floatsso-test-them-all/

by thedufer • 12 years ago

235 118 12 years ago

randomascii.wordpress.com

jevinskie• 12 years ago

A trillion tests can complete in a reasonable amount of time, and it should catch most problems.

When your individual test is a handful of instructions, you can make such impressive claims. I only wish $work's test suite was so svelte!

jwmerrill2• 12 years ago

Who's using single precision floats these days?

plorkyeran• 12 years ago

They're the standard choice for 3d graphics in games.

lelandbatey2• 12 years ago

Yeah, I was going to say. The wisdom that I'm being taught in school is "Don't use single precision floats, at least not when you're on any kind of a modern system."

nkurz• 12 years ago

That's OK wisdom unless you are aiming for high performance. I'd put it at about the same level as "Don't use C if something higher level will work." If you are hoping to gain from vectorization, or if you have enough of them to care about memory usage, single precision is twice as good, unless the extra precision of a double actually gains you something.

ajuc5• 12 years ago

If you don't care about precision use single floats. That's most of the time in games. Some people even used ints as fixed precision fractions.

If you care about precision - doubles still aren't precise - for currency use bigdecimals, for some stuff ratios can give precise results, for irrational things your only options are doubles, but be aware that you aren't precise, even for simply looking operations. No way to compute 10% of something precisely with doubles.

dagw• 12 years ago

Like all good wisdom, there are plenty of exceptions. I use single precision all the time. The most obvious advantage to me is that I can load twice as large data sets into memory, which has some definitive performance advantages.

forrestthewoods• 12 years ago

Oh god. The future is doomed.

nabla9• 12 years ago

Anyone who wants to do fastest possible floating point arithmetic with graphics card. Also, if the memory, disk access, or IO-troughtput is the bottleneck with number crunching, single floats might give huge advantage.

wlievens2• 12 years ago

We do all our image processing using floats (as memory and disk storage - not as computation accumulators obviously). It helps a lot if you keep a dozen seventy-megapixel images in memory, because it means you can run twice as many jobs on your cluster.

LnxPrgr32• 12 years ago

Depends on the application. If I'm processing audio in a PBX, 64-bit floating point precision isn't going to do me much good when my source is a noisy 8-bit µ-law stream. All I'd gain is twice the demand for memory space and bandwidth—not a cost I'm willing to pay when I gain zero developer productivity from it.

Even CD-quality audio only has 16 bits per sample. My digital camera only records 12 bits per pixel, and that's before the image is converted to a more reasonable 8-bit-per-channel format.

Single precision is still overkill in a number of applications.

yread• 12 years ago

but these are all fixed point!

When doing arithmetics you can lose as much as 1 bit of precision per floating point operation. So, it pays off to do use more precision for calculations even when the storage format doesn't persist it.

Besides I remember reading somewhere that 32-bit floats instructions aren't actually any faster than 64-bit (except of course the cache...). They even might be slower because the FPU has to extend them to 64-bit before performing the operation

VLM2• 12 years ago

True about the memory and bus bandwidth, but don't forget the battery draw and/or device cost, especially when doing DSP / SDR / software modems / stuff like that. And latency issues.

So I could use a chip that costs more, results in shorter battery life, more thermal problems, and is slower so smaller BW processed and less audio filtering possible. But, at least I'm using doubles instead of floats, which doesn't even matter when it results in no measurable signal metric improvement while every other measurable performance and economic metric tanks downward.

You can do a lot of DSP and plain ole signal processing with fixed point of course, and sometimes doing weird things requires doubles.

Negitivefrags• 12 years ago

Your comment makes me feel sad. It just reflects a whole mindset that makes me feel like an oppressed minority somehow.

It sucks that most people don't really care about performance any more. It sucks when people causally dismiss people who do care about performance with arguments like "premature optimization" and so on.

It kind of sucks that the web is taking over because it gives an excuse to use slow languages. It almost makes me feel sick to think that Javascript stores all numbers as doubles.

So you know what? It makes me feel happy to use the most efficient type that will work. I like my single precision floats.

I can die happy knowing that I didn't waste everyone's collective network, disks and CPUs with needless processing. Can't it be good to save just for the sake of saving?

So you want a practical reason do you?

I shaved over 2 gigabytes off the size off the download size of our product simply by using more efficient data types. Using half size floats is good enough for some data (16 bits).

And let me tell you about a data type that we used to use called a char. 8 bits would you believe! Turns out those x86 CPUs that are sitting there a few VMs deep still support those things.

hvidgaard6• 12 years ago

It's not even about performance. It's about actively thinking about what data you'd be processing. Why use doubles when singles are okay? I'd sure not be using 64 bit ints just because "it's bigger" when a normal 32 bit would be just fine.

jwmerrill2• 12 years ago

Sorry for making you feel sad. Good points all around, here, and in the other comments about GPUs. Regarding CPU, though, my understanding is that on a 64 bit machine, 32 bit arithmetic is no faster than 64 bit arithmetic. Is that incorrect?

lmm4• 12 years ago

It sucks that most people don't really care about performance any more. It sucks when people causally dismiss people who do care about performance with arguments like "premature optimization" and so on.

Why? Really. To my mind it's good that we no longer have to care about these implementation details, and can concentrate on writing code that expresses what we mean. Like writing on paper rather than scratching letters into tree bark.

thedufer• 12 years ago

It almost makes me feel sick to think that Javascript stores all numbers as doubles.

That's not actually true. JS engines are highly optimized. For example, anything that fits in a 32-bit int (and is an integer, of course) is stored as such, at least in V8.

Gravityloss• 12 years ago

EEGLab, a Matlab plugin used by brain researchers, at least used to use explicitly single precision floats for data series.

zvrba2• 12 years ago

In engineering applications, it's perfectly sensible to use float for world modelling, which give you precision of about 1 in 10 million. Then you can use double for intermediate results and lose less precision in a long calculation, producing a more accurate result (rounded to float) in the end.

Also, if the dynamic range of your data allows it [and for physical application it usually does], you can first rescale it to [0,1] in order to further increase precision. [It's the interval where floats are most dense.]

Having worked for a few years now in computational geometry, i'm more and more convinced that "float by default" is the way to go. Doubles should be used for intermediate computations.

sampo4• 12 years ago

rescale it to [0,1] in order to further increase precision. [It's the interval where floats are most dense.]

Who not to scale to [0,0.5], where they are even more dense? ;-)

ygra• 12 years ago

Last place I had to use them was OpenGL stuff on Android. No doubles even supported, as far as I could tell.

nly2• 12 years ago

Anyone who doesn't need more than 6 digits of decimal precision but can't be arsed to scale everything in to a fixed point format.

epsylon• 12 years ago

The whole games industry uses 99.999% floats.

dj-wonk4• 12 years ago

Ironically, like a float, I suspect the precision of your `99.999%` estimate is dubious.

malkia• 12 years ago

Oh wow. Just about anyone in game development :) - lol... lol since I've had the exact opposite arguments with my own folks - but it wasn't for in game use, but rather game tools. But I think I was wrong at the end. Storing all model geometry vertices in floats would be too much of a loss, also stick to 16-bit vertex indices (instead of 32-bit).

wglb5• 12 years ago

In many applications, single is good enough. If you have a mass of values that needs to be stored somewhere, and the accuracy of single precision is fine, then single precision it should be.

If there is a long chain of calculations that use those numbers, you might do the intermediate calculations in double, or even long double.

zomgbbq• 12 years ago

If it takes 90s to test 2^32 floats then it should only take about 12,257 years to test 2^64 doubles.

Someone• 12 years ago

It's perfectly parallelizable. Go to AWS, fire up 2^20 four core instances for a day, and you are all set :-)

kordless2• 12 years ago

Assuming you could do it, would it be worth it to do it?

croddin• 12 years ago

That would only cost 7.5 million dollars using c3.xlarge instances! I am actually surprised that it is that close to being feasible.

kazagistar• 12 years ago

Isn't distributing hardware tests missing the point?

zvrba2• 12 years ago

Actually, 2^53 different mantissas, plus a few different exponents, depending on the function under test. Also, there's a huge number of NaNs, all of which are equivalent. For ceil/floor, it wouldn't make sense to test exponents larger than 54.

brucedawson2• 12 years ago

There are a huge number of double-precision NaNs in the absolute sense -- there are 2^54-2 of them. But they are a small portion of all of the doubles (roughly 1/2048) so omitting them from the tests does not help significantly with saving time.

And, skipping testing of large numbers and NaNs can lead to missing bugs. One of the fixed ceil functions handled everything except NaNs correctly. Implementations that failed on exponents beyond 63 or 64 are easy to imagine.

But, testing doubles requires compromises. Testing of special values plus random testing plus exhaustive testing of the smallest ten trillion or so numbers should be sufficient -- better than the current status quo at least.

qwerta• 12 years ago

You could test corner cases very quickly. Just define important bites, and run permutation on those.

wglb5• 12 years ago

Ah, but with floating point that can really be quite tricky.

VLM2• 12 years ago

An opposition to "test everything" is to play telecom signal to noise ratio type games. And error rates. So attempting a 1 part in 2 ^ 64 implies your memory access error rates and disk error rates are already far under 1 in 2 ^ 64 which is quite expensive. There are of course solutions to those problems, but they may be more expensive and complicated than you want.

With non-ECC memory and a simplistic brute force algo it doesn't make much sense to talk about doing 2^64 tests because any errors will swamp the memory errors that will be detected. Depending on who's numbers you select (1e-10? 1e-15?) to get the predetermined result you want (LOL)

At 1 in 2 ^ 32 range its commodity desktop hardware time. To pull off 1 in 2 ^ 64 hardware error rates is way harder.

vanderZwan• 12 years ago

However the ceil function gave the wrong answer for many numbers it was supposed to handle, including odd-ball numbers like ‘one’.

Given all the special and unique features of the number one, I sincerely cannot tell if he's being sarcastic or not.

ghayes2• 12 years ago

I believe he's (dramatically) saying that you'd expect someone to have checked that number manually, if not by other means.

sampo4• 12 years ago

Maybe they were like "of course it works for simple cases like 1, let's just test some more difficult numbers".

maho2• 12 years ago

Round to nearest even is the default IEEE rounding mode. This means that 5.5 rounds to 6, and 6.5 also rounds to 6.

Wat. I had never even heard about this, but the more I read and think about it, the more this rule makes sense to me.

How did I miss this - is this commonly taught in school and I just did not pay attention? It seriously worries me that I don't even know how to round properly - I always thought of myself as a math-and-sciency guy...

ghayes2• 12 years ago

I learned about this in HS chem class and it's always stuck, even if people don't use it in informal settings. Also called "unbiased rounding" or "bankers' rounding" [1]

[1] http://en.wikipedia.org/wiki/Rounding#Round_half_to_even

hvidgaard6• 12 years ago

it's rarely taught in school. Most people know that you round .5 up, but that is a slightly uneven distribution and rounding to the even number however produce a perfectly even distribution. It's also the way you round in the financial sector.

pkolaczk• 12 years ago

Financial sector of many (all?) countries in UE is required to round all .5 up. If you use banker's rounding, you might get into trouble with the tax office. So always check the local regulations for the rounding mode.

maho2• 12 years ago

I don't believe the round-to-next-even-method will give you a perfectly even distribution. Benford's law can be generalized to the second, third, ... digit, and although the distribution is not as skewed as for the first digit [1], you'd still be rounding down a bit more often than rounding up.

Benford's law applied to rounding floats is splitting hairs, really - but it goes to show how even "simple" things like rounding can be really difficult if you only worry about them for too long.

[1] http://en.wikipedia.org/wiki/Benford%27s_law#Generalization_...

Ciechanowski• 12 years ago

Percentages is the best example of why it's so useful. For value A at 41.5% and value B at 58.5% their sum is equal to 100%. Rounding up would make them 42% and 59% respectively, thus 101% in total. Round half to even ensures the final values of 42% and 58% sum to 100% as intended.

Pxtl• 12 years ago

I learned the "round .5s to the nearest even" in my first year of undergrad engineering. Don't remember seeing it in high-school.

cperciva• 12 years ago

I did something quite similar when I was finding worst-case inputs for complex multiplication rounding errors. Here I had to search over tuples of four floating-point values; but I could ignore factors of two (since they don't affect relative rounding errors) and I had some simple bounds on the inputs such that I had only a hundred billion tuples left to consider -- a small enough number that it took a few hours for my laptop to perform the search.

Replicating this for double-precision inputs would have been impossible, of course; but fortunately knowing that the worst-case single precision rounding error occurred in computing

  (3/4 + 12582909 / 16777216 i) * (5592409 / 8388608 + 5592407 / 8388608 i)

made it easy to anticipate what the worst cases would be in general -- and as usual, knowing the answer made constructing a proof dramatically easier.

kordless2• 12 years ago

It seems like a perfect fit for a genetic algorithm. Even for the speed stuff.

dj-wonk4• 12 years ago

A perfect fit? Care to expand on your idea? I'd like to see what you had in mind.

zamalek2• 12 years ago

The problem with this is that there are a select few cases where a machine can (or should) determine the expected value for a test assertion.

- My function does something complicated: chances are you will be replicating your function in your test code. Hand-code assertions.

- My function can be tested using a function that is provided by the runtime/framework: great! Remove your function and use the one in the framework/runtime instead.

- My function can be tested using a function that is provided by the runtime/framework, but is written for another platform or has some performance trick: test as described in the article.

- My function should never return NaNs or infinities: test as described in the article.

And, you can test every float bit-pattern (all four billion!) in about ninety seconds. [...] A trillion tests can complete in a reasonable amount of time, and it should catch most problems.

Your developers will never run said tests. Unit tests are supposed to be fast. However, these exhaustive tests could be run on the CI server.

chriswarbo2• 12 years ago

The code in the article is about optimisation, in which case there should always be a slow reference implementation. Never try to write highly optimised code on the first go: make it work, make it correct, then make it fast.

Also, these aren't unit tests; they're property tests.

zamalek2• 12 years ago

The code in the article is about optimization [...]

Very true but that really should have been stated up-front by the author. Next thing you know "some guy at Valve said all unit tests with floats should test all 4 billion cases." You would be surprised at how much people take away from a skim over something - e.g. a poor understanding of Apps Hungarian created the monster that is Systems Hungarian.

in which case there should always be a slow reference implementation.

Good point - however, keep in mind that bug fixes would need to be made in two places. Not only does it mean the maintainer needs to grok two pieces of code, but they may have to determine if the original code is providing bad truths. Hopefully there wouldn't be many places where this type of testing would be required as the low hanging fruit is often enough: however keep in mind certain industries do optimize to ridiculous degrees - and in some of those industries optimization can happen first depending on the developers [well-seasoned] intuition, and can be a frequent habit. The author's industry is a brilliant example of where the typical order of optimization (make it work, make it correct, make it fast) takes a back seat - life is incredibly different at 60/120Hz.

mistercow5• 12 years ago

That said, there are times when making it correct just doesn't matter. Sacrificing accuracy for speed can be an extremely powerful technique, as long as perfect accuracy isn't required (e.g. some graphics applications).

dj-wonk4• 12 years ago

Put another way, these are invariants; e.g. make sure that a faster implementation gives the same result as a reference implementation.

scott_s• 12 years ago

The author never called his tests "unit tests".

ajuc5• 12 years ago

- I have old function that I know worked but was hairy and I want my new function to work the same for all values.

nraynaud2• 12 years ago

I like his notion that IEEE errors result from sloppiness. So here are 2 "non-sloppy" version of the computation of the sign of a determinant: https://github.com/bjornharrtell/jsts/blob/master/src/jsts/a... http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predi...

Remember, the determinant value is not the rounded value of the exact computation with those things unless it is is zero, it's still "sloppy" if it's far from zero. You get only 1 bit of guaranteed accuracy in a 64bits FP number if the result is not zero.

I think there is a little bit to "sloppiness" in the fact that we carry very inexact results in FP. Even "good enough" FP computation is PhD level.

ElliotH• 12 years ago

I did some work for my third year dissertation on performing exhaustive testing on floats. Worked well enough, but I was never convinced that it was an especially effective way of testing.

If your test oracle is code itself, then it's not unlikely you'll make the same bug twice. I can't find the paper I'm after, but NASA did some work here.

If your test oracle isn't code, you have the problem of working out the correct outputs for the entire function space (at which point maybe you'd be better off with some kind of look-up table anyway)

The next problem is your input combinations grow much faster than you are able to test. Most functions don't just work on one float (which is very feasible) but they might work on three or four streams of input, and keep internal state.

The moment you have these combinations you run into massive problems of test execution time, even if you can parallelise really well.

Butler and Finelli did some work http://www.cs.stonybrook.edu/~tashbook/fall2009/cse308/butle... also at NASA investigating if doing a sample of the input space was worthwhile, but their conclusion was that it isn't helpful, and that any statistical verification is infeasible.

In my report I ended up concluding that it isn't a particularly useful approach. It seems that following good engineering practice has better returns on your investment.

wglb5• 12 years ago

This should be one of the required units of study in Floating Point School.

Quick--why would you sort an array of floating point numbers before adding them up? And in which order?

alanh• 12 years ago

Ooh, nice question.

Floats are a quantity and a magnitude. Adding two floats requires (at least) the larger of the two magnitudes because larger values are more important than smaller ones. So the smaller float essentially gets converted to a small quantity and a large magnitude. In an extreme case, this small quantity becomes zero. So when adding a very large number and a very small number, the result will be the same as adding zero to the very large number.

If you add numbers largest to smallest, then thanks to this, at a certain point you are simply doing $SUM = $SUM + 0 over and over.

But if you start with the smallest numbers, they have a chance to add up to a value with a magnitude high enough to survive being added to the largest numbers.

wglb5• 12 years ago

Exactly.

donpdonp• 12 years ago

This post feels particularly applicable since I just came across a huge bug in ruby's BigDecimal package.

If you use ruby 2.1, be sure to upgrade to BigDecimal 1.2.4.

https://www.ruby-forum.com/topic/4419577#1133001

The bug is basically: if the divisor is less than 1, the result will be 0.0.

https://gist.github.com/donpdonp/c36b33b861cea49c0a86

There Are Only Four Billion Floats – So Test Them All

Related Stories