gbadev.org forum archive

I have come across the problem of the compiler over optimizing my code in the following manner: I will have, for example, a function such as this:

Code:

inline F32 Model::LoadF32(byte*& ptr){
int tmpF32 = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);

ptr += sizeof(float);
return F32(*(float*)(&tmpF32));
}

Which I then may call multiple times in rapid succession such as this:

Code:

F32 location[] = { LoadF32(ptr), LoadF32(ptr), LoadF32(ptr) };

Which the compiler will then over optimize into something like this:

Code:

int tmpF32 = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);

F32 location[] = { F32(*(float*)(&tmpF32)), F32(*(float*)(&tmpF32)), F32(*(float*)(&tmpF32)) };
ptr += sizeof(float)*3;

Clearly, this is a problem and produces incorrect results. I was wondering if anyone could tell me some simple and hopefully less hacky method than I am currently using to get around this problem?
_________________
- relpats_eht

Last edited by relpats_eht on Thu Apr 12, 2007 11:16 pm; edited 1 time in total

The order of evaluation is not defined for function arguments or array initializers. Try this:

Code:

F32 location[3];

// Unroll if desired.
for(int i = 0; i < 3; ++i)
location[i] = LoadF32(ptr);

The problem persists.
_________________
- relpats_eht

I've never used references to pointers in that way, so maybe there's some rule I don't know about.

Try passing a regular pointer to the function, and modify the pointer outside the function.

If that doesn't work, I'd guess you have a bug elsewhere.

What about this?

Code:

F32 location[] = { (volatile F32)LoadF32(ptr), (volatile F32)LoadF32(ptr), (volatile F32)LoadF32(ptr) };

_________________
I'm a PSP hacker now, but I still <3 DS.

I think the code is flat out illegal. You aren't allowed to change any memory location more than once in the same expression. The result is random...you deserve what you got.

Now that's just not true... How about fred = ++fred? Or is that different?
But anyway, I have no idea regarding the actual problem! My C++ isn't too good, and I've never used references. Can't you remove the reference stuff and do it another way?
_________________
Big thanks to everyone who donated for Quake2

simonjhall wrote:

Now that's just not true... How about fred = ++fred? Or is that different?
But anyway, I have no idea regarding the actual problem! My C++ isn't too good, and I've never used references. Can't you remove the reference stuff and do it another way?

Actually, I'm pretty sure that's undefined too. You're modifying the same variable twice in the one statement (more technically, you're modifying a variable more than once between two consecutive sequence points).

Also, don't expect a function to evaluate its arguments in any particular order, as sajimori said.

The comp.lang.c FAQ has some good information about expressions, including a question that seems similar to yours.
_________________
http://chishm.drunkencoders.com
http://dldi.drunkencoders.com

Alright, thanks for the suggestion; I didn't know C++ left such things undefined.

Edit:
To clarify, the problem lies in lines such as this:

Code:

int tmpF32 = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);

and in calling the function as an argument of some sort, correct? There is no problem with passing the pointer as a reference?
_________________
- relpats_eht

relpats_eht wrote:

To clarify, the problem lies in lines such as this:

Code:

int tmpF32 = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);

and in calling the function as an argument of some sort, correct? There is no problem with passing the pointer as a reference?

That line is ok. You may be reading a variable more than once (ptr), but you're only writing to tmpF32 once. You can also call that function as an argument, as long as ptr is modified no more than once. The problem was that you were calling LoadF32 multiple times in the array initializer, without knowing which result would be put into which part of the array.

For example, if int f() returns 1 the first time it is called, 2 the second, 3 the third, etc., you don't know the results of this:

Code:

int a[3] = {f(), f(), f()};

It could be a = {1,2,3}, or a = {2, 3, 1}, or something else entirely.

Now imagine you have the function int g (int &x) {return x++;}, and the function void h (int a, int b);. The following would all cause problems:

Code:

h (g(x), g(x)); // (1) Modifies x twice, and unknown which order the arguments will be evaluated
h (g(x), x++); // (2) Same problems as above
h (x++, x++); // (3) Same problems as above
h (g(x), x); // (4) Is the value first argument going to be more than, less than or equal to the second argument?

Note, however, that if g was defined as int g (int x) {return x++;}, lines (1) and (4) would be okay. In the case of (1), the compiler would most likely call g only once, then use the result for both arguments. This is an optimization it can make, given the details of the standards. It's the same assumptions made for the optimization that are possibly causing your problems.
_________________
http://chishm.drunkencoders.com
http://dldi.drunkencoders.com

If I understand you correctly, then there is no problem with the function itself; however, why then would these two segments of code produce different results?

Code:

// This doesn't work, all three values are the same
F32 location[3];
location[0] = LoadF32(ptr);
location[1] = LoadF32(ptr);
location[2] = LoadF32(ptr);

Code:

// This works as expected
F32 location[3];
int tmpLocation[3];

tmpLocation[0] = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);
ptr+=sizeof(float);
location[0] = F32(*(float*)(&tmpLocation[0]));

tmpLocation[1] = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);
ptr+=sizeof(float);
location[1] = F32(*(float*)(&tmpLocation[1]));

tmpLocation[2] = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);
ptr+=sizeof(float);
location[2] = F32(*(float*)(&tmpLocation[2]));

_________________
- relpats_eht

I find when I get 'obscure' bugs like this, it's much better to simplify the code than blame the compiler. While we all (probably) understand what you are trying to accomplish, why not simplify it a bit and move it across a couple lines of code. It will be easier to read, easier to maintain, and easier to debug and decode for the compiler.

Or, if speed is essential, just code it in assembly and get rid of the compiler completely.

Don't worry, there is no importance in what I am doing. Compilers are programs, it takes no effort for it to translate the input into machine code. There is no need for me to clean up my debugging code. Also, as to maintenance and debugging, don't worry there, my code is commented well enough and generally much more readable in actuality, I merely condensed it for the sake of my posts not taking up too much space.

Nonetheless, knowing now the expressions C++ leaves undefined, my problem is solved well enough.
_________________
- relpats_eht

relpats_eht wrote:

If I understand you correctly, then there is no problem with the function itself; however, why then would these two segments of code produce different results?

Code:

// This doesn't work, all three values are the same
F32 location[3];
location[0] = LoadF32(ptr);
location[1] = LoadF32(ptr);
location[2] = LoadF32(ptr);

Code:

// This works as expected
F32 location[3];
int tmpLocation[3];

tmpLocation[0] = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);
ptr+=sizeof(float);
location[0] = F32(*(float*)(&tmpLocation[0]));

tmpLocation[1] = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);
ptr+=sizeof(float);
location[1] = F32(*(float*)(&tmpLocation[1]));

tmpLocation[2] = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr);
ptr+=sizeof(float);
location[2] = F32(*(float*)(&tmpLocation[2]));

That's harder to explain. What happens when you don't inline the function?
_________________
http://chishm.drunkencoders.com
http://dldi.drunkencoders.com

I'd rather not rewrite all my debugging code, but if memory serves me, as I did check that case, the same problem occurred.

In any event, only continue with this thread if you are curious, I have merely settled on the idea that the compiler optimizes the creation of an array followed by a rapid succession of array initializers as shows in my earlier code example as the array merely being truly initialized by those values in the manner which you explained was undefined. Although this is most likely untrue, it is of no real concern as now that I have moved away from that debugging code and have put the Load functions on more complex data structures -- dynamically allocated arrays of structures containing the arrays -- the problem is no longer present. Yes, I know that was extremely hard to follow.
_________________
- relpats_eht

I take it back. I just discovered that this over optimization is a thorn in my side textures. I have tried removing the inlining of the function, but to no avail.

Thus, I ask again, any suggestions?
_________________
- relpats_eht

If I were you, I'd take Mike's suggestion: simplify the code. The combination of casting and weird modifications of nonlocal variables via non-const references makes things very hard to follow.

Try writing this function as a starting point:

Code:

u32 read32(const u8*);

No matter how hard the code is to follow, it is still correct. Even though it is a mere helper function designed to make the actual code for loading the model much easier to read, it is still heavily commented in Real Life, comments which I merely did not copy over with the function.

Since you insist, however, I will show you a simplified version of the function with more explanations that does the exact same thing.

Code:

/* This inline function loads an F32 from the model file, where it is stored as a float. It takes a reference to the pointer that is the current position in the model file, loads the float as a series of bytes, for loading all four simultanesouly as a single float variable does not work, ORs these bytes together, then is set as a float and returned as an F32.*/
inline F32 Model::LoadF32(byte*& ptr){
u8 byte1 = (*(u8*)(ptr+3)); // The first byte of the float Because of little endianess, is the final byte in binary data
u8 byte2 = (*(u8*)(ptr+2)); // Second
u8 byte3 = (*(u8*)(ptr+1)); // Third
u8 byte4 = (*(u8*)ptr); // Fourth

int tmpF32 = (byte1<<24) | (byte2<<16) | (byte3<<8) | byte4; // OR the bytes together, shifting as necessary, to create the same binary representation of the original float, only stored in an integer. It is just easier to read this way, converting to a float later. This will break the strict aliasing rule and cause a warning on compile, but to no ill effects.

ptr += sizeof(float); // Move the pointer forward the size of a floating point variable (4 bytes), so the next number can be loaded simply from another call to this, or a similar, function from the model file. This is why I pass a reference to the pointer, and not just a pointer, and especially not a constant pointer.

return F32(*(float*)(&tmpF32)); // Cast a pointer to the integer as a pointer to a float and return the value at that pointer. This effectively makes the bytes loaded earlier, which were stored in an integer, come out to the same floating point value they originally contained, albeit breaks the aliasing rule and results in a warning. The F32 class handles the loading of floats.
}

But that is all beside the point. I am not looking for a problem -- I see the problem, the same code in an function sometimes does not in the same fashion as the exact same segment of code would outside of the function -- I am looking for a more efficient workaround than not using the function, either that, or some explanation as to some segment of the language which is causing the problem, as was the case earlier.

I deeply apologize if I sound rude, it is not my intention.
_________________
- relpats_eht

I don't know.

Maybe ptr is getting destroyed between calls.
Maybe it's a compiler bug.
Maybe F32 is a class and it's doing something weird in its constructor or destructor.
Maybe 'byte' is a complex type rather than just a u8, and it's doing something weird.
Maybe it's just a problem with the client code.
Maybe your test results are wrong.

Anyway, write the function I described earlier. It'll work.

I know the function you described will work, but my goal here isn't to make things work, I already have functions that work 99% of the time replaceable with their contents during the extra 1%. My model loader is working exactly as it should right now, all vertices are in the right place, the animation is smooth, etc. What I want is a compact, easy to read, consistent method. Constantly loading u32 and converting them over all the variables I load does no fit these qualifiers.

None the less, I will answer your maybes, as the answer may warrant some assistance.
There is no modification to the pointer anywhere but in these functions, I have thoroughly tested and minimized all allocations not directly related to the problem at hand, I doubt the pointer is being destroyed.
Maybe.
F32 is a class, but there is nothing weird in the constructor and nothing at all in the destructor.
Byte is a typedef for unsigned char
Maybe.
Unless my eyes deceive me, which they have been doing recently, no.

Further information: While writing the function out for each load where it is necessary, using the same variable as a temporary integer storage for the float has the same effect as using the function itself.
_________________
- relpats_eht

relpats_eht wrote:

There is no modification to the pointer anywhere but in these functions, I have thoroughly tested and minimized all allocations not directly related to the problem at hand, I doubt the pointer is being destroyed.

It could be destroyed by memory corruption elsewhere in the program, or being changed in an interrupt handler.
_________________
I'm a PSP hacker now, but I still <3 DS.

Does F32 hold anything by reference, or take anything by non-const reference?

If you're more interested in knowing the cause than fixing the problem, then I'd suggest putting together a stand-alone demo that illustrates the issue, so readers can compile it. If you're using the usual homebrew devkit, there are people who will want to know about potential compiler bugs.

sajiimori, now I really have to apologize for you for stating that I did not have a problem. I did, I even wrote exactly what it was in the code I posted.

I, being too tired to code, set out to thinking. The thought occurred to me: if my code previously was attempting undefined operations, who is to say it still isn't? I grabbed some caffeine and started from the most obvious location, the warning about breaking the strict-aliasing rule. Well, I did a bit of research on that, and it turns out the first search result I clicked last time wasn't the best source in the world, and that, in fact, breaking that rule lead to undefined results. Thus, I replaced what I was doing previously -- int tmpF32 = ((*(u8*)(ptr+3))<<24) | ((*(u8*)(ptr+2))<<16) | ((*(u8*)(ptr+1))<<8) | (*(u8*)ptr); -- with this: byte tmpF32[] = {*(ptr), *(ptr+1), *(ptr+2), *(ptr+3)}; using information this much better source which stated that types of char* are not aliased and a bit of guessing as to how the memory would be stored.

Now everything works as it should, my code does nothing (I hope) undefined, and I know a bit more about C/C++. Yes, it is knowledge I never hoped I would have to know, but it is good nonetheless.

Thank you all for your assistance, even those who provided none, for continuous posting in this topic gave me some motivation to actually fix the problem, rather than continue writing workarounds.
_________________
- relpats_eht

Turn on as many of gcc's warnings as you can. If gcc is warning you about something then change the code to remove the warning. If you are sure that the warning can be ignored then make sure you understand why gcc is producing it and that your code is not going to break.

gcc is your friend.

relpats_eht wrote:

Code:

return F32(*(float*)(&tmpF32));

as you're noting yourself, this breaks the strict aliasing rules in C99 (strict aliasing dependent optimizations are enabled by default by gcc when the optimization level is high enough). Try this instead:

Code:

union {
int i;
F32 f;
} u;
u.i = tmp;
return u.f;

masscat: Yes, I do always check my warning and have them all on, it just so happens that, as I stated, the first link I clicked giving information gave false information, since I was tired, I researched no more.

kusma: Considering that I am moving this data from a large array of bytes to individual variables, some of which are type F32, which is the fixed point representation of a float, a union would not work, it would make the value of the F32 the literal byte interpretation of a float (which is no where near a sane number) divided by 4096. The method I have set up now may not be the most obvious and may obfuscate the code a bit, but it is fully commented and it works.
_________________
- relpats_eht

relpats_eht wrote:

kusma: Considering that I am moving this data from a large array of bytes to individual variables, some of which are type F32, which is the fixed point representation of a float, a union would not work, it would make the value of the F32 the literal byte interpretation of a float (which is no where near a sane number) divided by 4096. The method I have set up now may not be the most obvious and may obfuscate the code a bit, but it is fully commented and it works.

If float and F32 are different types, just do a cast / call the constructor in the end.

Code:

union {
int i;
float f;
} u;
u.i = tmp;
return F32(u.f);

The point here is that reinterpreting the data pointed to by a pointer with a simple cast is not allowed with strict aliasing. You should get rid of that invalid code.

By the way, I'm also a bit pizzeled by comments like "for loading all four simultanesouly as a single float variable does not work"... Why does it not work? Due to alignment issues? If so, is there a reason why you're not just fixing the alignment?

My code is legal now. I didn't post both changes, just the one.

Your point, however, is still invalid. A union explicitly casts data it reads in by the respective type you are using, it does not use the same byte interpretation for all types. Print a floating point number as binary data into a file and open that in a hex editor, or read it in again as an integer to see what the result would be of using a union. A floating point number is stored in a radically different manner than an integer, reading it in as an integer from a pointer, where the value is not changed from a floating point number to an integer, returns the integer value that is the bytes of the floating point number, which is in no way sane; however, if this was is a union with a float, if I then used the float accesser, I would get a floating point number that is the same completely inane value. I can't really explain it any better, just stick with it won't work.

As for loading for bytes simultaneously, if I recall correctly, the DS cannot access more than sixteen bits across a pointer (or something like that) due to hardware limitation. Therefore, I have to break up the 32 bit value into smaller representations, where bytes make the most sense due to endianess. I may be wrong in my reasoning, but in practice, loading four bytes at once from a block of memory via pointer does not work and the values are nonsensical.
_________________
- relpats_eht

The DS has no trouble reading 32 bit values from memory, as long as it's from an aligned address.

relpats_eht wrote:

My code is legal now. I didn't post both changes, just the one.

relpats_eht wrote:

Your point, however, is still invalid. A union explicitly casts data it reads in by the respective type you are using, it does not use the same byte interpretation for all types. [...]

A union stores all members at the same memory address, and you can access the same memory as all types.

Code:

union {
float f;
unsigned int i;
} u;
printf("address of u.f: %p\n", &u.f);
printf("address if u.i: %p\n", &u.i);

When assigning to one of the members, you can access the underlying memory as one of the other types.

Code:

u.i = 0x3f800000;
printf("%x %f\n", u.i, u.f);

u.f = 2.0f;
printf("%x %f\n", u.i, u.f);

If you're still not convinced, try this code that performs your conversion and my conversion on random input and tests the result for equality:

Code:

#include <assert.h>
#include <stdlib.h>

float convert_relpats(const unsigned int val)
{
return *(float*)(&val);
}

float convert_kusma(const unsigned int val)
{
union {
   float f;
   unsigned int i;
} u;
u.i = val;
return u.f;
}

int main(int argc, char* argv[])
{
for (int i = 0; i < 10000000; ++i)
{
   unsigned int v = rand() * rand();
   float f1 = convert_relpats(v);
   float f2 = convert_kusma(v);
   if (f1 != f2)
   {
      printf("*** ERROR: %d -> %f %f\n", v, f1, f2);
   }
}

return 0;
}

relpats_eht wrote:

I can't really explain it any better, just stick with it won't work.

You can't because it makes no sense. You are simply confused on this one :)

Also note that I'm only talking about the reinterpret-casting here, not the entire routine (or even line of code). As for the 16bit stuff, you're confused there as well. There's no problems reading 32bit values from memory as long as they are aligned.

And I thought I had aligned my structures, I will admit defeat in that regard, it does make sense, but you are still misinterpreting me kusma.

Perhaps code will explain...

Code:

float convert_kusma(const char* val) // val is a collection of bytes, the one we are currently loading being a float of value, say 2.
{
union {
float f;
unsigned int i;
} u;
u.i = *(int*)val; // This will set the integer to some obscure amount, most certainly not 2, because it is reading in a float as if it is an integer
return u.f; // u.f will not equal two, it will equal the same obscure value as u.i because it casted the value from an integer to a float by calling the float variable of the union. It does not matter that they use the same bytes.
}

But this is all really besides the point. I'll look into what more is necessary for alignment.
_________________
- relpats_eht

relpats_eht wrote:

And I thought I had aligned my structures, I will admit defeat in that regard, it does make sense, but you are still misinterpreting me kusma.

Actually, you're the one misunderstanding here. I'm telling you NOT to do that pointer cast. not to do it into a union.

Here's the full function that performs my technique, not just the cast isolated like last time.

Code:

float convert_kusma(const char* val)
{
union {
float f;
unsigned int i;
} u;

u.i = (val[3] << 24) | (val[2] << 16) | (val[1] << 8) | val[0];
return u.f;
}

int main(int argc, char* argv[])
{
char temp[4] = { 0x00, 0x00, 0x00, 0x40 }; /* 2.0 in binary */
printf("%f\n", convert_kusma(temp));
return 0;
}

edit: actually, the int-cast you did also works, but it has the same aliasing issue as the previous technique. And it should also only work when the input array is aligned.

I actually checked this time and you are correct, that union does work, but I still don't see how. My knowledge of unions must be off, I was under the assumption the output of that code would be 1073741824.
_________________
- relpats_eht

It would only be 1073741824 if the return was u.i since that is the number represented by 0x40000000 as a 32 bit integer.

Since a union is being used to access the memory as if it were actually a float then we obtain the float whose binary representation is 0x40000000. This is pretty much equivalent to

Code:

int i = 0x40000000;

float f = *(float*)&i;

This code however is what is known as type punning, recent versions of gcc consider this to be incredibly bad form and you will get bitten if you write code like this.

The union approach will work but I think you'd be much better off ensuring your structures are aligned properly in the data you're giving the DS.
_________________
devkitPro - professional toolchains at amateur prices
devkitPro IRC support
Personal Blog

So would this be considered bad too?

Code:

int i = 0x40000000;
float f = (float)i;

_________________
I'm a PSP hacker now, but I still <3 DS.

HyperHacker:
No, because that cast performs a conversion on the data itself, and doesn't merely reinterpret the data as a different type.
_________________
http://chishm.drunkencoders.com
http://dldi.drunkencoders.com

gbadev.org forum archive

DS development > Over Optimization Troubles [Solved]

#124439 - relpats_eht - Fri Apr 06, 2007 12:22 am

#124440 - sajiimori - Fri Apr 06, 2007 12:37 am

#124441 - relpats_eht - Fri Apr 06, 2007 12:58 am

#124451 - sajiimori - Fri Apr 06, 2007 2:07 am

#124478 - HyperHacker - Fri Apr 06, 2007 6:08 am

#124481 - 3D_geek - Fri Apr 06, 2007 6:23 am

#124498 - simonjhall - Fri Apr 06, 2007 10:29 am

#124504 - chishm - Fri Apr 06, 2007 12:29 pm

#124519 - relpats_eht - Fri Apr 06, 2007 3:00 pm

#124526 - chishm - Fri Apr 06, 2007 4:26 pm

#124529 - relpats_eht - Fri Apr 06, 2007 5:09 pm

#124532 - Miked0801 - Fri Apr 06, 2007 5:18 pm

#124567 - relpats_eht - Fri Apr 06, 2007 11:14 pm

#124593 - chishm - Sat Apr 07, 2007 3:00 am

#124597 - relpats_eht - Sat Apr 07, 2007 3:17 am

#125189 - relpats_eht - Thu Apr 12, 2007 12:21 am

#125191 - sajiimori - Thu Apr 12, 2007 1:05 am

#125199 - relpats_eht - Thu Apr 12, 2007 1:48 am

#125208 - sajiimori - Thu Apr 12, 2007 2:46 am

#125215 - relpats_eht - Thu Apr 12, 2007 3:48 am

#125231 - HyperHacker - Thu Apr 12, 2007 8:05 am

#125338 - sajiimori - Thu Apr 12, 2007 6:39 pm

#125381 - relpats_eht - Thu Apr 12, 2007 11:14 pm

#125383 - masscat - Fri Apr 13, 2007 12:46 am

#125384 - kusma - Fri Apr 13, 2007 12:58 am

#125389 - relpats_eht - Fri Apr 13, 2007 1:38 am

#125396 - kusma - Fri Apr 13, 2007 2:08 am

#125415 - relpats_eht - Fri Apr 13, 2007 4:13 am

#125426 - sajiimori - Fri Apr 13, 2007 6:06 am

#125443 - kusma - Fri Apr 13, 2007 12:08 pm

#125484 - relpats_eht - Fri Apr 13, 2007 8:51 pm

#125494 - kusma - Fri Apr 13, 2007 10:53 pm

#125503 - relpats_eht - Sat Apr 14, 2007 1:38 am

#125511 - wintermute - Sat Apr 14, 2007 2:54 am

#125523 - HyperHacker - Sat Apr 14, 2007 5:32 am

#125524 - chishm - Sat Apr 14, 2007 5:40 am