Spider Mastermind
Register | User Profile | Member List | F.A.Q | Privacy Policy | New Blog | Search Forums | Forums Home
Doomworld Forums : Powered by vBulletin version 2.2.5 Doomworld Forums > Classic Doom > Source Ports > Strictly defined means to interpolate angle_t
 
Author
All times are GMT. The time now is 15:14. Post New Thread    Post A Reply
Quasar
Moderator


Posts: 6045
Registered: 08-00


Nobody is using one, according to the C++ standard.
code:
return oldangle + FixedMul(lerp, newangle - oldangle);

Given fixed_t defined as signed int (or int32_t) and angle_t defined as unsigned int (or uint32_t), the above expression invokes implementation-defined behavior for any difference value which lies outside of the range from INT_MIN to INT_MAX.

I have tried a thousand different ways of getting around this and none of them work so far. I am about to call it quits unless somebody has a better solution. I will NOT deliberately invoke the above sort of lazy pray-it-works behavior when I know better.

Old Post 01-05-14 05:16 #
Quasar is offline Profile || Blog || PM || Email || Homepage || Search || Add Buddy IP || Edit/Delete || Quote
andrewj
Senior Member


Posts: 1638
Registered: 04-02


Angles cannot be interpolated as simply as that code. For example, going from 1 degree to 359 degrees should go the short way (interpolate over 2 degrees) and not the long way.

Also the C standard (section A4.2) guarantees that unsigned integers will wrap around when an addition overflows.

Old Post 01-05-14 05:31 #
andrewj is offline Profile || Blog || PM || Search || Add Buddy IP || Edit/Delete || Quote
MP2E
Junior Member


Posts: 157
Registered: 09-07


Quasar found two versions that work and are more correct, however, they are slower. From benchmarks run on an x86_64 Linux system running on an i7 3770K @ 4.2ghz, the times are as follows:
No optimization from compiler:
code:
103 seconds elapsed for double routine. 93 seconds elapsed for int routine.

O3 optimization:
code:
40 seconds elapsed for double. 20 seconds elapsed for int(!)


This benchmark was built using clang 3.4, but any fairly recent C++ compiler with support for C++11 should work. Please test and report back on different platforms/architectures so as to give Quasar a better "feel" for which will perform better on a majority of systems.

The benchmark in question just calls each interpolation routine with random data as the arguments 300 million times per routine, while timing how long it takes.

Here is the source code of benchmark program:
http://pastebin.com/Y9wx41d4

EDIT:
GCC 4.7.3 is even faster.
No optimizations:
code:
79 seconds elapsed for double. 61 seconds elapsed for int.

O3 optimizations:
code:
21 seconds elapsed for double. 15 seconds elapsed for int.

Last edited by MP2E on 01-05-14 at 11:27

Old Post 01-05-14 08:34 #
MP2E is offline Profile || Blog || PM || Email || Search || Add Buddy IP || Edit/Delete || Quote
Archi
Member


Posts: 299
Registered: 07-09



MP2E said:
Please test and report back on different platforms/architectures so as to give Quasar a better "feel" for which will perform better on a majority of systems.

Here is my results:
I'm running the test on Windows 7 x64 running on AMD Phenom II x6 1035t @ 2.6ghz, compiler is the latest MinGW pack, so it doesn't support c++11 features, so I slightly edited your source file.
Here it is: http://pastebin.com/2mXmsM4R
Please correct me if there's something wrong.

No optimizations:
code:
21 seconds elapsed on getting 3*300 million random numbers. 37 seconds elapsed for double. 38 seconds elapsed for float. 27 seconds elapsed for int.


O3:
code:
22 seconds elapsed on getting 3*300 million random numbers. 30 seconds elapsed for double. 30 seconds elapsed for float. 25 seconds elapsed for int.

Old Post 01-05-14 13:15 #
Archi is offline Profile || Blog || PM || Search || Add Buddy IP || Edit/Delete || Quote
Graf Zahl
Why don't I have a custom title by now?!


Posts: 7736
Registered: 01-03


Visual C++ 2013, Core i7, 3.2 GHz:

Unoptimized:

15 seconds elasped for getting random.
30 seconds elasped for double.
44 seconds elasped for float.
35 seconds elasped for int.

Optimized with SSE math:

10 seconds elasped for getting random.
13 seconds elasped for double.
14 seconds elasped for float.
15 seconds elasped for int.

Optimized with x87 math:

10 seconds elasped for getting random.
11 seconds elasped for double.
13 seconds elasped for float.
15 seconds elasped for int.

I find it interesting that x87 math is consistently faster than SSE2, quite contrary to common wisdom - but I experienced the same in GZDoom as well.

Old Post 01-05-14 14:34 #
Graf Zahl is offline Profile || Blog || PM || Email || Search || Add Buddy IP || Edit/Delete || Quote
wesleyjohnson
Senior Member


Posts: 1011
Registered: 04-09


I would have to know what horrible thing the C++ standard has implied now that is causing the problem.
Is it the lack of a specified behavior for integer overflow ??
I assume it is not some problem with truncating instead of rounding, or some loss of precision. Or is there some concern that some compilations may get more precision than others if the compiler uses longer registers than the specified 32 bits ?
The C++ standard may have left itself open to alternatives to handling overflow, such as limiting math (an Overflow value for integer, like FP has), or an exception on overflow, but the available processors we are using do not implement integer math that does not allow overflow wrap.
It is also desirable to have overflow math available, with reliable wrapping, so one question is what did the C++ standard provide to do such calculations.

My stock answer when pressed with such a problem:
1. Imbed the 32 bit value as an unsigned value in a signed 64 bit register. The upper bits can be all 0. This is the same as adding your angle to some 64 bit constant. If you don't want the result to go negative, add an additional constant before subtracting.
2. Do the difference calculation. There cannot be overflow.
The conversion constants added previously will have canceled each other.
3. Use the lower 32 bits as an unsigned result. The mask step emulates the wrap. There is no sign to cause problems.
4. To convert to a signed result involves another wrap.
Easiest is to assign the 32 bit unsigned to a signed type and let the format change do it. There is no overflow to trigger an exception.
5. This will be much faster than any code that tests to prevent overflow.

Last edited by wesleyjohnson on 01-08-14 at 19:04

Old Post 01-08-14 18:40 #
wesleyjohnson is offline Profile || Blog || PM || Search || Add Buddy IP || Edit/Delete || Quote
All times are GMT. The time now is 15:14. Post New Thread    Post A Reply
 
Doomworld Forums : Powered by vBulletin version 2.2.5 Doomworld Forums > Classic Doom > Source Ports > Strictly defined means to interpolate angle_t

Show Printable Version | Email this Page | Subscribe to this Thread

 

Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is OFF
vB code is ON
Smilies are OFF
[IMG] code is ON
 

< Contact Us - Doomworld >

Powered by: vBulletin Version 2.2.5
Copyright ©2000, 2001, Jelsoft Enterprises Limited.