Sign in to follow this  
Slaru

Epsilon and float comparison

Recommended Posts

I read this article on why not to use epsilon to compare floats. I had always used epsilon for float comparison, but am now wondering if the methods in that article are truly better. Is epsilon good enough for general game programming problems? Or is the method in that article better? Slaru

Share this post


Link to post
Share on other sites
The method in the article is probably better, however it looks like it might be possible for that function to divide by zero, I'm not sure.

The problem is that floating point numbers aren't linear. The number of representable numbers between 0.4 and 0.5 is a lot more than the number of representable numbers between 100.4 and 100.5. As such, epsilon, the smallest representable number, isn't constant constant. If you use too small a value, large numbers won't appear equal when they should be. Too large a value, and small numbers will appear equal when they shouldn't be. Their method attempts to fix this.

Another problem with both methods is that you can get a situation when A equals B, B equals C, but C doesn't equal A.

Share this post


Link to post
Share on other sites
Is there any benefit to using this method over the epsilon method? Or should I stick to the common epsilon method? Or is this one of those "it's up to you" questions?

Slaru

Share this post


Link to post
Share on other sites
Quote:
Original post by Magmai Kai Holmlor
I'm concerned about the amount of time it will take to move the float from the SSE unit or FPU to the ALU registers. I don't think you can do a register to register move (meaning it will hit main memory, and be very slow).


If one were to use this method, then they would profile afterwards to see if this was a real bottleneck or an imaginary one. So while it is nice to note possible performance concerns, I wouldn't make it a primary factor in determining it's usage till after profiling.

Share this post


Link to post
Share on other sites
I've come to a decision. I have a function that tests to floats for equality taking into account the innaccuracies of floats called Equals. Later, when I have more of my game done (wish me luck, I'm rewriting my game from scratch), I will profile then with both implementations (epsilon and the article's) to see if there are any performance problems. If not, I will decide then.

Thanks for the input.

Slaru

Share this post


Link to post
Share on other sites
Quote:
Original post by Washu
If one were to use this method, then they would profile afterwards to see if this was a real bottleneck or an imaginary one. So while it is nice to note possible performance concerns, I wouldn't make it a primary factor in determining it's usage till after profiling.

Completely disagree. Performance checking for such an elementary operation as a compare is absolutely vital beforehand. Such operations will 100% inline, and can therefore create a kind of omnipresent performance killing "fog" within a profiler. Means, it becomes almost impossible to spot them as being the bottleneck, since every single compare operations adds a little, but none enough to stick out alone.

And even if you finally indentify them as being the bottleneck, good luck replacing an approximate floating point comparison operation with an optimized function afterwards - a function that will most certainly behave completely differently from a mathematical point of view, especially in special case situations. Welcome to a total and complete nightmare (we had a similar situation once, and ended up rewriting around 50k lines of code).

Conclusion: such elementary operations should be timed before committing to their use in production level code. They're almost always a one way street - once you start using them, there's no way back.

Edit, just to clarify: I fully agree with Washu that some types of "premature optimization" (God, I hate this term ;) can indeed be harmful. But this is definitely not such a case.

Share this post


Link to post
Share on other sites
Quote:
Original post by Yann L
* various things that I can agree with

Conclusion: such elementary operations should be timed before committing to their use in production level code. They're almost always a one way street - once you start using them, there's no way back.

Yes, the problem is, the majority of people don't KNOW how to properly profile an operation (how many times have you seen a for loop that runs a million times and just calls a function without doing anything with the result?). More importantly, he must make the determination if he wants accuracy or if a less accurate method will do. Performance isn't everything. Especially with what compilers can do these days.

But, more importantly, while my statement did imply that he should use it in his code and then profile. It could be taken to mean that he should profile it in a test case first before deciding that it is a bottleneck, which was the spirit of my message. One that I see you agree with.
Quote:
Edit, just to clarify: I fully agree with Washu that some types of "premature optimization" (God, I hate this term ;) can indeed be harmful. But this is definitely not such a case.


This is such a case, it's just that the profiling takes place in a test case, not in the application.

Share this post


Link to post
Share on other sites
Quote:
Original post by Washu
Yes, the problem is, the majority of people don't KNOW how to properly profile an operation (how many times have you seen a for loop that runs a million times and just calls a function without doing anything with the result?).

Well, Magmai mentioned SSE to FPU register transfer times, so I guess he knows how to time such an operation ;) Generally, I agree with you though.

Quote:
Original post by Washu
More importantly, he must make the determination if he wants accuracy or if a less accurate method will do. Performance isn't everything. Especially with what compilers can do these days.

It's not accuracy vs. less accuracy in this specific case. It's about two different methods, that will most of the time deliver very similar results, but will behave completely different in special case scenarios (handling of denormalized numbers, for example). If one uses the accurate but slow version, yet realizes afterwards that it turns out to be a bottleneck, then replacing it with a faster version can break an entire application. So one should make sure that the speed is appropriate beforehand, before reyling on it in development. That's what I meant by saying it's a one way street.

Quote:

This is such a case, it's just that the profiling takes place in a test case, not in the application.

Well, the term "bottleneck" usually implies in-application testing, unless you know beforehand what you're going to use the operation for. But this is almost impossible to say with elementary multipurpose operations such as a compare. Who knows how it will be used at a later point in time ?

Anyway, my point was simply that such operations should be treated as time critical from the beginning on. And that possible optimizations should be done before starting to use the operation for actual developement. If this is what you meant in your post, then accept my appologies :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Yann L
Quote:
Original post by Washu
Yes, the problem is, the majority of people don't KNOW how to properly profile an operation (how many times have you seen a for loop that runs a million times and just calls a function without doing anything with the result?).

Well, Magmai mentioned SSE to FPU register transfer times, so I guess he knows how to time such an operation ;) Generally, I agree with you though.

Indeed, I assume he does, but does the OP?
Quote:

It's not accuracy vs. less accuracy in this specific case. It's about two different methods, that will most of the time deliver very similar results, but will behave completely different in special case scenarios (handling of denormalized numbers, for example). If one uses the accurate but slow version, yet realizes afterwards that it turns out to be a bottleneck, then replacing it with a faster version can break an entire application. So one should make sure that the speed is appropriate beforehand, before reyling on it in development. That's what I meant by saying it's a one way street.

My bad, I didn't give a close enough look to the other operation presented in the article.
Quote:

Well, the term "bottleneck" usually implies in-application testing, unless you know beforehand what you're going to use the operation for. But this is almost impossible to say with elementary multipurpose operations such as a compare. Who knows how it will be used at a later point in time ?

Welcome to the wonderful world of programming eh?
Quote:

Anyway, my point was simply that such operations should be treated as time critical from the beginning on. And that possible optimizations should be done before starting to use the operation for actual developement. If this is what you meant in your post, then accept my appologies :)


Oh, I agree that the operation must be treated as performance critical, but does he KNOW that it's a bottleneck? I mean, Magmai mentioned register transfers. But most likely the numbers will be in the cache, and thus main memory won't be hit at all. More importantly, one should look at the assembly output as well, which is another form of profiling. Also, there are instructions like FEMMS which can enable a fast switch between MMX and FP.

As far as what I meant about the test case: Yes, that is what I meant. The test case is a platform for testing and optimizing the operation. There are only so many different ways one can use a comparison operation and have a meaningful result. The places it may be used vary, but the usage does not. So, a test case can be an easy way to profile and optimize an operation that will be commonly abused.

Share this post


Link to post
Share on other sites
I don't think that my comparitively small game will have any performance problems. So, it probably won't matter if one method is slightly slower.

I would like to see which method is faster though.
Quote:
Original post by Washu
Indeed, I assume he does, but does the OP?

I have heard of these so called FPU and normal registers and something goes on there. If I understand correctly, to transfer the value in the FPU's register, it may have to go to system memory and then to the normal register, which is slow right?

Also, I have the DevPartner profiler (the free edition, if you've heard of it before). How can I profile the two methods using a profiler. Is this specific to my profiler, or is there a general method (ie. just look at the average time it took to execute the function).

[EDIT] Oh yes, and I am not using any SIMD type code, if that matters.

Slaru

Share this post


Link to post
Share on other sites
I think epsilon compare is hardly ever needed. There have been discussions about this before and it nearly always turned out there was a better solution (real interval compare, integer compare, etc). So you should really try to see if there isn't a way you can avoid floating point compares. They are unreliable in most every situation.

Yann L, I agree that we should optimize inlined functions early, but in my experience it's actually even better to avoid the whole problem by not inlining prematurely. Personally I use three build configurations in Visual Studio: Debug, Release, and Profile. The Profile configuration includes all useful debugging information but also many optimizations, excluding inline expansion. This ensures that if I see a hotspot caused by a badly optimized small function which is called millions of times per second in one (maybe two) locations, I can focus on those hotspots. It helps to inline, but that happens automatically in the Release build anyway. So what I do is manually expand that function and ensure it's totally optimized for that particular location.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this