If you ever used GetAsyncKeyState() or GetKeyState() or any other windows function using virtual keys, this post might be useful to you.
There are certain situations where you might want to print out a string representation of the virtual key you're dealing with, and from what I've researched, I don't think there's an API function call that will do this for us, so I made my own.
The following function will take as input a Virtual Key Code (e.g. VK_RETURN) and then return the string representation of the key (e.g. "VK_RETURN"). Of course it works for 'A' to 'Z' and digits as well (there are no VK_* macros for such virtual keys because they're the same as the ascii char representation).
Here's the function, Its a big one so I've hidden it by default.
Show Code
I ended up needing this on my NES emulator in order to display mapped-keyboard settings. That's probably where other people will need it too.
In case you've never seen something like this and you're wondering how it works, it uses a powerful and very useful feature of the C/C++ preprocessor called 'stringification'.
Essentially you take convert arguments to a macro into string representations.
Here's more info:
http://gcc.gnu.org/onlinedocs/cpp/Stringification.html
I took the winapi macros for the virtual keys and wrapped them in a macro that converts them to strings. Mostly was just copy-paste and regex replace work.
Anyways have fun :)
Wednesday, November 24, 2010
Monday, October 11, 2010
Easy generic toString() function in C++
In c++ you can make a simple toString() template function that converts primitives to a string.
This will work for any type that defines the << operator for use with streams.
So with this simple one function we have an "int to string" function, a "float to string" function, a "double to string" function, etc...
Using it is of course simple:
#include <iostream>
using namespace std;
template<typename T>
string toString(T t) {
stringstream s;
s << t;
return s.str();
}
This will work for any type that defines the << operator for use with streams.
So with this simple one function we have an "int to string" function, a "float to string" function, a "double to string" function, etc...
Using it is of course simple:
int main() {
string s0 = toString(100);
string s1 = toString(100.1f);
string s2 = toString(100.12);
cout << s0 << " " << s1 << " " << s2 << endl;
return 0; // Prints out "100 100.1 100.12"
}
Monday, September 27, 2010
Fun Shader Bugs
Yesterday I ran into a funny bug when implementing an Eagle2x pixel shader.
I think the picture speaks for itself xD
(Click the picture to see the magnified version and spot the bug :D)
Funny thing is the bug wasn't actually caused by the shader itself, instead it was due to the way I applied the shader. On my emu I had 3 separate textures for Sprite Background, Sprite Foreground, and Tile Background. Then I would render all 3 of these textures to the output buffer. When I applied the shader it applied it to each individual layer (sprite/bg) instead of the picture as a whole. The sprite layers for instance were just a few sprites with a lot of transparency, and running the Eagle2x algorithm on this layer caused artifacts.
The solution then was to combine all 3 layers into 1 texture before applying the shader; using 1-complete texture fixed the cause of the artifacts. I ended up coming up with some pretty cool bitwise-based merge function which combined 3 bitmaps arrays according to priority and transparency without having to use any conditional statements.
Essentially the code creates masks by checking if the MSB is set (since the most significant byte is 0xff on non-transparent pixels, and 0x00 on transparent pixels, the most-significant bit is set when non-transparent; of-course this code won't work properly with partial-transparencies).
After it creates the masks, it uses some bitwise math to make sure the pixel with the highest priority is the one that is shown, and leaves the resulting pixel in the buffer[0] bitmap layer.
Note: The priority is (buffer[2] > buffer[1] > buffer[0]). So the pixel in buffer[2] is the top-most.
I initially had thought this bitwise version would be faster than a version using conditionals, but I was wrong. The compiled code for this is pretty bloated. Instead the conditional version compiles to much better optimized code:
So I guess the lesson learned here is that many times using conditionals are better than complex bitwise operations. Even though the bitwise versions may seem more clever and quicker on first impression.
Note: "elif" in the above code is a macro for "else if"
I like the elif macro because it keeps code more compact. Using "else if" almost always messes up text alignment and due to having too much letters.
I think the picture speaks for itself xD
Funny thing is the bug wasn't actually caused by the shader itself, instead it was due to the way I applied the shader. On my emu I had 3 separate textures for Sprite Background, Sprite Foreground, and Tile Background. Then I would render all 3 of these textures to the output buffer. When I applied the shader it applied it to each individual layer (sprite/bg) instead of the picture as a whole. The sprite layers for instance were just a few sprites with a lot of transparency, and running the Eagle2x algorithm on this layer caused artifacts.
The solution then was to combine all 3 layers into 1 texture before applying the shader; using 1-complete texture fixed the cause of the artifacts. I ended up coming up with some pretty cool bitwise-based merge function which combined 3 bitmaps arrays according to priority and transparency without having to use any conditional statements.
void combineLayers() {
for(int y = 0; y < bHeight; y++) {
for(int x = 0; x < bWidth; x++) {
s32 m0 = ((s32)(buffer[0][y][x])) >> 31;
s32 m1 = ((s32)(buffer[1][y][x])) >> 31;
s32 m2 = ((s32)(buffer[2][y][x])) >> 31;
m0 &= ~m1 & ~m2; m1 &= ~m2;
buffer[0][y][x] = buffer[0][y][x] & m0;
buffer[0][y][x] |= buffer[1][y][x] & m1;
buffer[0][y][x] |= buffer[2][y][x] & m2;
}}
}
Essentially the code creates masks by checking if the MSB is set (since the most significant byte is 0xff on non-transparent pixels, and 0x00 on transparent pixels, the most-significant bit is set when non-transparent; of-course this code won't work properly with partial-transparencies).
After it creates the masks, it uses some bitwise math to make sure the pixel with the highest priority is the one that is shown, and leaves the resulting pixel in the buffer[0] bitmap layer.
Note: The priority is (buffer[2] > buffer[1] > buffer[0]). So the pixel in buffer[2] is the top-most.
I initially had thought this bitwise version would be faster than a version using conditionals, but I was wrong. The compiled code for this is pretty bloated. Instead the conditional version compiles to much better optimized code:
void combineLayers() {
for(int y = 0; y < bHeight; y++) {
for(int x = 0; x < bWidth; x++) {
if (buffer[2][y][x] >> 31) buffer[0][y][x] = buffer[2][y][x];
elif(buffer[1][y][x] >> 31) buffer[0][y][x] = buffer[1][y][x];
elif(buffer[0][y][x] >> 31) buffer[0][y][x] = buffer[0][y][x];
else buffer[0][y][x] = 0;
}}
}
So I guess the lesson learned here is that many times using conditionals are better than complex bitwise operations. Even though the bitwise versions may seem more clever and quicker on first impression.
Note: "elif" in the above code is a macro for "else if"
#define elif else if
I like the elif macro because it keeps code more compact. Using "else if" almost always messes up text alignment and due to having too much letters.
Sunday, September 26, 2010
cottonNES - More Progress...
So I have been working diligently on cottonNES, and have made some progress over my last update.As far as the core goes, I've been able to pass some more cpu/ppu tests, but my emu still fails many of blargg's timing tests (those things are brutal!). I already switched my cpu core to a cycle-accurate design, this proves to be needed for a few games (Ms. Pacman, Bad Dudes, Baseball Stars 2, etc...). Whats cool is my emu now runs Battletoads and Battletoads & Double Dragons, these 2 games are very timing sensitive and many NES emulators still fail to run them properly (some even crash...). That said, the games still have graphical problems, but at least they go in-game.
Something else I implemented was joypad support. Currently its just hard-coded to match my ps3-controller, but in the future I'll do a fancy configuration screen. I ended up going with SDL for the joypad API because I just wanted something simple to use. Perhaps in the future I will rewrite the code with direct-input since i wasn't very satisfied with SDL.
The last big thing I did was support for pixel shaders! I'm a shader noob, but between yesterday and today I've learned enough of HLSL to make 2 shaders. One shader is a scanline shader, and the other is a Scale3x shader. The cool thing is this offloads the filtering onto the GPU so the CPU can do less work, overall the Scale3x filter was about 54% faster than my C++ based attempt (222fps vs 144fps in a scene). In the Super Mario Bros 2 pic above, I have the Scale3x shader on so you can see what it looks like.
Anyways, I still have a lot more work to do with my emulator before its ready for a release; particularly PPU and APU need more work since they're the cause of most problems I'm having now. I hope I continue to be motivated so that cottonNES can become one of the better NES emulators out there; I feel it has the potential, but it just depends on if I continue working on it.
Thursday, September 16, 2010
NES emu progress
For those that don't know, I had started a NES emu project from scratch a while back, but then I got bored and stopped working on it in favor of some other projects.This past week I have regained my interest in it and have made some progress.
After some hours of debugging, it now passes all normal opcode tests in Kevin Horton's nestest.nes rom.
Last week it failed most of those tests miserably (turns out I was just setting wrong flags in a few opcodes like BIT and PLP).
I currently have mappers 0(no-mapper),1,2,3,4,and 7 implemented. I think mapper #1 has a few bugs and mapper #4 needs to have its IRQ timer code redone later on to be more accurate (but its okay for now).
Mappers 2,3, and 7 are kind-of fun because they're so easy to implement. Each can be done in just a few lines of code.
For example, my Mapper #2 implementation is just:
class Mapper2: public Mapper {
public:
Mapper2() { Init(); }
virtual ~Mapper2() { Close(); }
void WritePROM(u16 addr, u8 value) {
clamp(value, ROM.romBanks, "Mapper2: PROM");
PROM_SLOT[0] = _PROM[value*2+0];
PROM_SLOT[1] = _PROM[value*2+1];
}
};
Something I've noticed when browsing through other NES emu's source-code, is that many of the emulators have horribly messy code. There is one popular emulator that uses OOP too much. When this happens it fucks up intellisense and makes browsing code a PITA. You right click on any method to go to the definition and intellisense finds ~50 possible matches and makes you chose manually which method is the one you're looking for. This always happens in projects that use too much OOP and is a very annoying problem.
Another popular emulator does the opposite; it doesn't use any OOP even though the code is now in c++ (I guess originally it was in C). Anyways the whole code is very C-like and abuses macros like crazy, this makes everything a mess. Its a common mistake to abuse macros; I did it when I started with c++, but any good coder knows that you should only use macros when there's no better way. Oh and the code uses 2-space tabbing which is ridiculous.
On the subject of macros, its more understandable to see macro usage in C code compared to C++ code. This is because C is very limited compared to C++, and there is a lot more stuff you can't do so you use macros to simulate these features. In C++ however you have templates and references which can help you remove the need for many macros. This is a big reason why C++ is better than C.
Many C-programmers move on to C++ and still code C-like because they don't know proper C++, that could be the case with the nes-emu I looked at. Anyways I suppose I'll save a C/C++ comparison rant for another blog post.
So back to talking about my emulator, cottonNES...
My emulator is no-where near ready for a release. Although it boots hundreds of games now that the big cpu bugs are fixed, it still has problems in many games (most-likely to do with PPU and timing issues...).
I would like to continue discussing nes emulation further here, but sadly I have an exam this week and need to study D:
I suppose this post will be boring without screen-shots :D
Saturday, September 4, 2010
Using the volatile keyword to prevent float precision problems
Consider the following code:
One should expect the above code to not print out anything, since the 2 operations are obviously equal.
Ironically, if you compile this code in msvc or gcc, you will most-likely get a bunch of numbers spammed to the console.
Why is this? Well it seems that the compilers take liberties with floating point calculations; even though you're dealing with single-precision 32bit floats, the compilers may use the full 80bit precision of the x87 FPU in calculations, or may even use double-floating point arithmetic for one of the operations, and use single-floating point for another one... mix and matching precisions, causing problems...
In the end, the different precision of the operations will cause the results of two seemingly equal operations to be unequal.
One solution is to use the volatile keyword.
The volatile keyword essentially makes the compiler always write-back values to memory once an operation is preformed, and it always reloads the value from memory when it will be used again.
This allows us to force the compiler to truncate the values to 32bit floats when it writes them to memory, and when it loads the value again it will be limited to the precision of a 32bit float.
So now we can do:
This will fix the problems we were having before, and not print out anything.
There are many papers and discussions about ways to compare floating point values, and I won't go into more detail here.
This site lists a few methods, and the problems they could have.
So I suggest reading that if you're interested.
int main() {
for(float i = 0; i < 100; i++) {
float f = i / 100.0f;
if (f != i / 100.0f) {
cout << i << ", ";
}
}
cout << endl;
return 0;
}
One should expect the above code to not print out anything, since the 2 operations are obviously equal.
Ironically, if you compile this code in msvc or gcc, you will most-likely get a bunch of numbers spammed to the console.
Why is this? Well it seems that the compilers take liberties with floating point calculations; even though you're dealing with single-precision 32bit floats, the compilers may use the full 80bit precision of the x87 FPU in calculations, or may even use double-floating point arithmetic for one of the operations, and use single-floating point for another one... mix and matching precisions, causing problems...
In the end, the different precision of the operations will cause the results of two seemingly equal operations to be unequal.
One solution is to use the volatile keyword.
The volatile keyword essentially makes the compiler always write-back values to memory once an operation is preformed, and it always reloads the value from memory when it will be used again.
This allows us to force the compiler to truncate the values to 32bit floats when it writes them to memory, and when it loads the value again it will be limited to the precision of a 32bit float.
So now we can do:
int main() {
for(float i = 0; i < 100; i++) {
volatile float f1 = i / 100.0f;
volatile float f2 = i / 100.0f;
if (f1 != f2) {
cout << i << ", ";
}
}
cout << endl;
return 0;
}
This will fix the problems we were having before, and not print out anything.
There are many papers and discussions about ways to compare floating point values, and I won't go into more detail here.
This site lists a few methods, and the problems they could have.
So I suggest reading that if you're interested.
Sunday, August 22, 2010
32bit Floats - Integer Accuracy and Interesting Consequences
There are big misconceptions I've seen regarding the accuracy of floats.
One professor of mine even went as far as to say, the computer might not store "2" as "2.0", but rather "2.000019" if using floats.
This is not true.
32-bit floats can actually represent quite a large amount of integer values 100% accurately.
The exact integer-range a 32bit float can represent accurately is -16777216 to 16777216.
This means that it is roughly equivalent to a 25-bit signed integer, which has the range -16777216 to 16777215.
If you only care about positive values, then the float is equivalent to a 24-bit unsigned integer, which has the range 0 to 16777215.
I commonly see these values messed up, with people saying a float can only represent a 24-bit signed integer (which would be -8388608 to 8388607, which is wrong).
Below I made a test case to prove the floating point range by exhaustive search.
Now its pretty interesting what happens once a 32-bit float reaches its limit of 16777216.
If you try to increase the float by 1 when it has this value, the float will actually stay the same. This means if you try to increment a float by 1 in a loop, you will never get past 16777216! It will just get stuck in an infinite loop.
Here is some proof of that:
The programs output is:
Admittingly, I didn't know this infinite looping behavior until I made the test-case. This is something you should definitely watch out for.
Oh and btw, you might be wondering why I was using "volatile float" in the above test-cases, instead of just "float". The "volatile" keyword is useful to use when we need to compare floats with their exact precision. I'll probably explain why in another article :)
One professor of mine even went as far as to say, the computer might not store "2" as "2.0", but rather "2.000019" if using floats.
This is not true.
32-bit floats can actually represent quite a large amount of integer values 100% accurately.
The exact integer-range a 32bit float can represent accurately is -16777216 to 16777216.
This means that it is roughly equivalent to a 25-bit signed integer, which has the range -16777216 to 16777215.
If you only care about positive values, then the float is equivalent to a 24-bit unsigned integer, which has the range 0 to 16777215.
I commonly see these values messed up, with people saying a float can only represent a 24-bit signed integer (which would be -8388608 to 8388607, which is wrong).
Below I made a test case to prove the floating point range by exhaustive search.
int testFloatRange(bool pos) {
volatile int i = 0;
volatile float f = 0.0f;
volatile double d = 0.0;
for (;;) {
volatile double t = (double)(float)i;
if ((double)f != d || (int)f != i || t != d) break;
if (pos) { f++; d++; i++; }
else { f--; d--; i--; }
}
printf("%f != %d\n", f, i);
return pos ? (i-1) : (i+1);
}
int _tmain(int argc, _TCHAR* argv[]) {
int p = testFloatRange(1);
int n = testFloatRange(0);
printf("Positive Range = 0 to %d\n", p);
printf("Negative Range = %d to 0\n", n);
printf("Full Range = %d to %d\n", n, p);
}
Now its pretty interesting what happens once a 32-bit float reaches its limit of 16777216.
If you try to increase the float by 1 when it has this value, the float will actually stay the same. This means if you try to increment a float by 1 in a loop, you will never get past 16777216! It will just get stuck in an infinite loop.
Here is some proof of that:
int _tmain(int argc, _TCHAR* argv[]) {
volatile float f = 0xffffff-100;
for( ; f < 0xffffff+100; f++) {
printf("Value = %f, Binary Representation (0x%x)\n", f, (int&)f);
}
}
The programs output is:
...
Value = 16777214.000000, Binary Representation (0x4b7ffffe)
Value = 16777215.000000, Binary Representation (0x4b7fffff)
Value = 16777216.000000, Binary Representation (0x4b800000)
Value = 16777216.000000, Binary Representation (0x4b800000)
... Keeps repeating the last line infinitely...
Admittingly, I didn't know this infinite looping behavior until I made the test-case. This is something you should definitely watch out for.
Oh and btw, you might be wondering why I was using "volatile float" in the above test-cases, instead of just "float". The "volatile" keyword is useful to use when we need to compare floats with their exact precision. I'll probably explain why in another article :)
Friday, August 20, 2010
Checking if a Float is a Power of 2
Last article I showed bitwise ways to check if integers are powers of 2, for completeness I'll show bitwise ways to check if floats are powers of 2.
For floating point numbers, remember that they're represented in the form |S*1|E*8|M*23|.
S = Sign Bit (1-bit)
E = Exponent (8-bits)
M = Mantissa (23-bits)
Check out the IEEE-754 standard for more info:
http://en.wikipedia.org/wiki/IEEE_754-1985
The exponent is actually used to compute powers of 2, which is then multiplied by the mantissa, which has an implicitly hidden '1.' in front of it.
So when we're checking if a float is a power of two, all we have to do is check if the mantissa is 0, and the exponent is non-zero (when the exponent is zero, the result is zero when the mantissa is also zero, or a denormal value when the mantissa is non-zero, so we don't want to consider these as powers of two).
The code ends up looking like this:
This however will end up counting negative-exponent powers of 2 (such as 2^-1 = 0.5), if this is not desirable, then we can modify the code to only count non-negative exponents (2^0 = 1, 2^1 = 2,...)
The modified code looks like this:
One last thing, both these versions will also consider negative powers of two (such as -4, -2, -1) to be powers of two.
If this is also undesirable, then we just need to check the Sign-bit of the float to determine if its negative, and if it is, then we will return false.
This last function returns true if the float is a positive power of two with a positive exponent (1, 2, 4, 8, 16...).
For floating point numbers, remember that they're represented in the form |S*1|E*8|M*23|.
S = Sign Bit (1-bit)
E = Exponent (8-bits)
M = Mantissa (23-bits)
Check out the IEEE-754 standard for more info:
http://en.wikipedia.org/wiki/IEEE_754-1985
The exponent is actually used to compute powers of 2, which is then multiplied by the mantissa, which has an implicitly hidden '1.' in front of it.
So when we're checking if a float is a power of two, all we have to do is check if the mantissa is 0, and the exponent is non-zero (when the exponent is zero, the result is zero when the mantissa is also zero, or a denormal value when the mantissa is non-zero, so we don't want to consider these as powers of two).
The code ends up looking like this:
typedef unsigned __int32 u32;
bool isPow2(float f) {
u32& i = (u32&)f;
u32 e = (i>>23) & 0xff;
u32 m = i & 0x7fffff;
return !m && e;
}
This however will end up counting negative-exponent powers of 2 (such as 2^-1 = 0.5), if this is not desirable, then we can modify the code to only count non-negative exponents (2^0 = 1, 2^1 = 2,...)
The modified code looks like this:
bool isPow2(float f) {
u32& i = (u32&)f;
u32 e = (i>>23) & 0xff;
u32 m = i & 0x7fffff;
return !m && e >= 127;
}
One last thing, both these versions will also consider negative powers of two (such as -4, -2, -1) to be powers of two.
If this is also undesirable, then we just need to check the Sign-bit of the float to determine if its negative, and if it is, then we will return false.
This last function returns true if the float is a positive power of two with a positive exponent (1, 2, 4, 8, 16...).
bool isPow2(float f) {
u32& i = (u32&)f;
u32 s = i>>31;
u32 e = (i>>23) & 0xff;
u32 m = i & 0x7fffff;
return !s && !m && e >= 127;
}
Checking if an Integer is a Power of 2
There are a few ways to check if an integer is a power of 2; some better than others.
One crucial thing to notice for power-of-two integers, is that in their binary representation, they only have 1 bit set.
So one approach we can do to check if an integer is a power of two, is to just loop through the bits, and check if only 1 bit is set.
Now the above approach is pretty obvious and simple; but its not that nice considering we have to loop for every bit (32 times for 4-byte integers).
There's a popular bitwise trick for determining if an integer is a power of 2, and it looks like this:
Now this is a lot nicer than our loop version. Instead of looping 32 times, we do just a few bitwise calculations.
I was playing around with bitwise operations earlier today, and I discovered another bitwise method for checking powers of 2.
I was really excited because I found this one out on my own, and I thought I had discovered it. However I did a google search on it, and I found out that this trick is already known :(
The nice thing about this second bitwise version, compared to the more popular version above it, is that its a lot simpler to remember IMO. Speed-wise, they're both around the same, I suppose it depends on your target architecture on which one is actually fastest, but in practical purposes it probably doesn't matter which one you use.
Note:
Its important to mention that both of the bitwise methods mentioned above, will incorrectly treat zero as a power of two.
To fix this behavior you can modify the functions like so:
and...
Sadly this adds an extra conditional to our fast bitwise methods, however it still ends up being a lot nicer (and faster) than our initial loop version.
One crucial thing to notice for power-of-two integers, is that in their binary representation, they only have 1 bit set.
0001 = 1
0010 = 2
0100 = 4
1000 = 8
... and so on...
So one approach we can do to check if an integer is a power of two, is to just loop through the bits, and check if only 1 bit is set.
bool isPow2(uint n) {
const uint len = sizeof(uint)*8; // 32 for 4-byte integers
uint count = 0;
for(uint i = 0; i < len; i++) {
count += n & 1;
n >>= 1;
}
return count == 1;
}
Now the above approach is pretty obvious and simple; but its not that nice considering we have to loop for every bit (32 times for 4-byte integers).
There's a popular bitwise trick for determining if an integer is a power of 2, and it looks like this:
bool isPow2(uint n) {
return (n & (n-1)) == 0;
}
Now this is a lot nicer than our loop version. Instead of looping 32 times, we do just a few bitwise calculations.
I was playing around with bitwise operations earlier today, and I discovered another bitwise method for checking powers of 2.
bool isPow2(uint n) {
return (n & -n) == n;
}
I was really excited because I found this one out on my own, and I thought I had discovered it. However I did a google search on it, and I found out that this trick is already known :(
The nice thing about this second bitwise version, compared to the more popular version above it, is that its a lot simpler to remember IMO. Speed-wise, they're both around the same, I suppose it depends on your target architecture on which one is actually fastest, but in practical purposes it probably doesn't matter which one you use.
Note:
Its important to mention that both of the bitwise methods mentioned above, will incorrectly treat zero as a power of two.
To fix this behavior you can modify the functions like so:
bool isPow2(uint n) {
return n && ((n & (n-1)) == 0);
}
and...
bool isPow2(uint n) {
return n && ((n & -n) == n);
}
Sadly this adds an extra conditional to our fast bitwise methods, however it still ends up being a lot nicer (and faster) than our initial loop version.
Saturday, July 31, 2010
Small Comparison Optimization = Big Gains
This is a small and pretty well known trick, but its worth mentioning since a lot of high-level coders don't seem to realize it, and it could result in some big speedups.
Lets take a look at some random code snippet:
What this code is doing is printing out all fractions that are less than 1/3, for all denominators less than 10,000.
Notice anything that we can optimize?
Well if you take a look at the if-statement, notice we are dividing j by i, and then doing a comparison. But as we should know by now, division is a slow operation.
On Core 2 Duos, double floating-point division has a 6~32 clock cycle latency (exact latency depends on the operand values), whereas multiplication is only 5 cycles, and add/sub are 3 cycles.
So it would be nice if we can omit that division from the comparison... oh wait we can!
Using simple mathematics we can do:
Now we got the same equation, but we were able to remove the division completely!
So in the worst-case that our division was taking ~32 clock cycles, this new optimization is ~6 times faster.
Now lets see this code in action.
Here is the same problem as above, except we've now increased 'len' to 100,000, and instead of printing out the results, we just count the fractions (this way we're not limited by console-write speed):
When I ran the above code using "if (j/i < fract)", it took ~19 seconds to finish on my PC.
When I ran the optimized version using "if (j < fract*i), it took ~2 seconds to finish executing! That's an even bigger speedup than predicted.
I hope this shows why optimization is important.
One last thing to note:
When using integers, you might not always want to do this trick.
j/i > x, is not necessarily the same as j > x*i when using integers, since the first one truncates the value (obviously, since integers don't hold the fractional part).
For example:
The above example only prints out "Second one" since we're using integers (if i and j were doubles, it would print out "First one" and "Second one").
This isn't really a negative, since when using integers you probably want to be using the second-method anyways, so you don't have to deal with converting to floats; in that case, you not only would save time by not doing a division, but you would also save time by not doing an int-to-float conversion.
Lets take a look at some random code snippet:
int main() {
const double len = 10000;
const double fract = 1.0/3.0;
for(double i = 1; i < len; i++) {
for(double j = 1; ; j++) {
if (j/i < fract) {
cout << j << " / " << i << endl;
}
else break;
}}
}
What this code is doing is printing out all fractions that are less than 1/3, for all denominators less than 10,000.
Notice anything that we can optimize?
Well if you take a look at the if-statement, notice we are dividing j by i, and then doing a comparison. But as we should know by now, division is a slow operation.
On Core 2 Duos, double floating-point division has a 6~32 clock cycle latency (exact latency depends on the operand values), whereas multiplication is only 5 cycles, and add/sub are 3 cycles.
So it would be nice if we can omit that division from the comparison... oh wait we can!
Using simple mathematics we can do:
j/i < fract =>
i * (j/i) < fract * i =>
j < fract * i
Now we got the same equation, but we were able to remove the division completely!
So in the worst-case that our division was taking ~32 clock cycles, this new optimization is ~6 times faster.
Now lets see this code in action.
Here is the same problem as above, except we've now increased 'len' to 100,000, and instead of printing out the results, we just count the fractions (this way we're not limited by console-write speed):
int main() {
const double len = 100000;
const double fract = 1.0/3.0;
int ret = 0;
for(double i = 1; i < len; i++) {
for(double j = 1; ; j++) {
if (j < fract * i) {
ret++;
}
else break;
}}
cout << ret << endl;
}
When I ran the above code using "if (j/i < fract)", it took ~19 seconds to finish on my PC.
When I ran the optimized version using "if (j < fract*i), it took ~2 seconds to finish executing! That's an even bigger speedup than predicted.
I hope this shows why optimization is important.
One last thing to note:
When using integers, you might not always want to do this trick.
j/i > x, is not necessarily the same as j > x*i when using integers, since the first one truncates the value (obviously, since integers don't hold the fractional part).
For example:
int main() {
int i = 21;
int j = 2;
if (i/j > 10) cout << "First one" << endl;
if (i > 10*j) cout << "Second one" << endl;
}
The above example only prints out "Second one" since we're using integers (if i and j were doubles, it would print out "First one" and "Second one").
This isn't really a negative, since when using integers you probably want to be using the second-method anyways, so you don't have to deal with converting to floats; in that case, you not only would save time by not doing a division, but you would also save time by not doing an int-to-float conversion.
Wednesday, July 21, 2010
Recursion is not always good!
In my university's computer science curriculum, they seem to put a big emphasis in using recursion to solve things, as opposed to alternative methods (such as loops).
It is indeed true that recursion can simplify the high-level code, and many times it can look beautiful. There is of-course a price to pay with recursion, and that is the extra overhead recursive calls have (therefor they're usually slower than alternative iterative/loop versions).
I will stress that learning to think recursively is indeed a good skill to have, and any good programmer should be able to do so. So in that sense, it is good that computer science curriculums seem to be stressing recursion; however, once you have learned to think recursively, it is again beneficial to start thinking non-recursively when algorithms are simple-enough to do so.
Let's consider one of the most common examples of recursion used, the factorial function! (I have used this function many times in my previous articles to demonstrate things, so shouldn't be a surprise :D)
This does end up looking pretty clean, as we can do the whole factorial function in one line.
Now lets take a look at the iterative/loop version:
Now this iterative version is not as 'beautiful' as the recursive version, because as you can see its 3 lines instead of 1.
However the generated code for this version ends up being nicer than the recursive version.
When you make recursive calls, the arguments that are passed to the recursive function need to be pushed on the stack, and then these arguments eventually need to be popped back out as well. Furthermore, not only do the arguments need to be pushed on the stack, but also the return address needs to be pushed. Sometimes the recursion can be nested so-deep, that you end up running out of stack, and get a stack-overflow crash. This extra overhead is the downside of recursion.
The iterative/loop version doesn't have such problems. No function calls are made so you don't have the function call overhead. Instead the loop versions usually end up compiling with a simple short-jump.
Another thing is that the loop version is inline-able, whereas the recursive version likely will not be inlined, and even if it does get inlined, it probably will only inline the first call to the function.
Potentially the compiler might be able to turn a recursive call into a iterative/loop-version, but don't count on this. At least, I haven't seen it happen...
Now, there are some cases where an algorithm will end up being naturally-recursive, and it ends up being difficult or unpractical to code an iterative version. In these cases recursion is the better way to go (in these cases, the algorithm can end up being faster using recursion instead of iteration as well). So in the end, it really depends on the situation whether to go with recursion or iteration/loops; the more experience you get, the more you figure out when to use recursion vs iteration.
Notes:
If you noticed, I was using template-functions for the factorial function. The reason I made it a template, is because the factorial function is something you may want to re-use with different data-types (int, unsigned int, long long int, float, double, some custom BigInteger class, etc...).
Using templates, we only have to code one function that can be reused by these different data-types.
It is indeed true that recursion can simplify the high-level code, and many times it can look beautiful. There is of-course a price to pay with recursion, and that is the extra overhead recursive calls have (therefor they're usually slower than alternative iterative/loop versions).
I will stress that learning to think recursively is indeed a good skill to have, and any good programmer should be able to do so. So in that sense, it is good that computer science curriculums seem to be stressing recursion; however, once you have learned to think recursively, it is again beneficial to start thinking non-recursively when algorithms are simple-enough to do so.
Let's consider one of the most common examples of recursion used, the factorial function! (I have used this function many times in my previous articles to demonstrate things, so shouldn't be a surprise :D)
template<typename T>
T factorial(T n) {
return n <= 1 ? 1 : n * factorial(n-1);
}
int main() {
int n = factorial(5);
cout << n << endl; // Prints "120"
return 0;
}
This does end up looking pretty clean, as we can do the whole factorial function in one line.
Now lets take a look at the iterative/loop version:
template<typename T>
T factorial(T n) {
T ret = n ? n :(n=1);
while(--n) ret*=n;
return ret;
}
int main() {
int n = factorial(5);
cout << n << endl; // Prints "120"
return 0;
}
Now this iterative version is not as 'beautiful' as the recursive version, because as you can see its 3 lines instead of 1.
However the generated code for this version ends up being nicer than the recursive version.
When you make recursive calls, the arguments that are passed to the recursive function need to be pushed on the stack, and then these arguments eventually need to be popped back out as well. Furthermore, not only do the arguments need to be pushed on the stack, but also the return address needs to be pushed. Sometimes the recursion can be nested so-deep, that you end up running out of stack, and get a stack-overflow crash. This extra overhead is the downside of recursion.
The iterative/loop version doesn't have such problems. No function calls are made so you don't have the function call overhead. Instead the loop versions usually end up compiling with a simple short-jump.
Another thing is that the loop version is inline-able, whereas the recursive version likely will not be inlined, and even if it does get inlined, it probably will only inline the first call to the function.
Potentially the compiler might be able to turn a recursive call into a iterative/loop-version, but don't count on this. At least, I haven't seen it happen...
Now, there are some cases where an algorithm will end up being naturally-recursive, and it ends up being difficult or unpractical to code an iterative version. In these cases recursion is the better way to go (in these cases, the algorithm can end up being faster using recursion instead of iteration as well). So in the end, it really depends on the situation whether to go with recursion or iteration/loops; the more experience you get, the more you figure out when to use recursion vs iteration.
Notes:
If you noticed, I was using template-functions for the factorial function. The reason I made it a template, is because the factorial function is something you may want to re-use with different data-types (int, unsigned int, long long int, float, double, some custom BigInteger class, etc...).
Using templates, we only have to code one function that can be reused by these different data-types.
Monday, July 19, 2010
Max/Min Values for Signed and Unsigned Ints
There are a variety of ways you can assign the max/min values to a signed/unsigned integer.
A very professional looking way is using the numeric_limits class like so:
But there are many other ways you can do this; and they all take a lot less typing than using numeric_limits, and you don't have to include any extra headers...
Lets first take a look at max/min integer values for different variables (in hexadecimal representation because its easier to memorize):
The table is pretty easy to memorize. Essentially, for unsigned ints, the max value is always a bunch of f's in hexadecimal, and the min-value is always 0.
For signed ints, the max value is always 0x7f, followed by a bunch of f's.
And lastly the min value for signed ints is always 0x80, followed by a bunch of 0's.
One thing to notice is the bitwise representation for "-1" always has all-bits set.
That means that for a 32bit integer, "-1" is "0xffffffff", which is the max value for an unsigned integer.
This means that for unsigned integers, we can declare int max/min like this:
In c++, you can put the suffix "u" at the end of an int literal to mean its unsigned. So what that code is doing, is treating the value "-1" as an unsigned int, which means its assigning 0xffffffff to the variable 'x'.
Here's the thing, I've noticed that some compilers end up generating warnings when you treat a negative number as unsigned in operations, so instead of writing '-1u', we can notice that negative one, is really the same as NOT 0, so we can instead write '~0u'. This will do the same thing, and is generally better to do since it won't generate the compiler errors.
So its nicer to do:
Now that we know this trick for unsigned ints, lets think of signed integers.
The max value for 32bit signed integers is 0x7fffffff.
If we notice though, 0x7fffffff is really (0xffffffff >> 1).
That is, signed int max, is equal to unsigned int max shifted right by one.
But since we already learned the trick on how to represent unsigned int max easily, we can use that to our advantage:
The last thing to notice for signed ints, is that the minimum value for 32bit signed ints in hex is 0x80000000, but it just so happens that that number is signed int max + 1, that is 0x7fffffff + 1.
So we can end up doing this:
That about does it for integers, for floats its not as simple so I didn't talk about them here. Maybe I'll end up making another blog post about the different floating point representations...
Notes:
When doing the '-1' or '~0' tricks where you shift the value; be sure to do the shift as an unsigned operation! That is either do: ~0u>>1 or (unsigned int)~0>>1, DO NOT do ~0>>1. This will do an arithmetic shift, instead of a logical shift, and make the result be -1, instead of 0x7fffffff.
And in-case you're wondering, these tricks are not 'slower' than typing in the numbers manually. C++ compilers do something called constant-propagation and constant-folding, which converts stuff like (-1u>>1)+1 to a constant at compile-time, and therefore there's no extra overhead compared to typing 0x80000000....
Also, this will not apply to most people, but another thing to note is that some very-old/weird hardware can use one's complement integers (instead of two's complement) or some other funky stuff; when dealing with weird hardware its best to use the numeric_limits class instead of bitwise tricks, because numeric_limits assigns its values based on the specific platform. That-said, I don't even know any hardware that uses one's complement for signed integers, so these tricks are almost always safe :p
A very professional looking way is using the numeric_limits class like so:
#include <limits>
int main() {
int x = numeric_limits<int>::max();
int y = numeric_limits<int>::min();
return 0;
}
But there are many other ways you can do this; and they all take a lot less typing than using numeric_limits, and you don't have to include any extra headers...
Lets first take a look at max/min integer values for different variables (in hexadecimal representation because its easier to memorize):
// u8, u16, u32... mean unsigned int of 8, 16, and 32 bits respectively
// s8, s16, s32... mean signed int of 8, 16, and 32 bits respectively
----------------------------------
| type | max | min |
----------------------------------
| u8 | 0xff | 0x0 |
| u16 | 0xffff | 0x0 |
| u32 | 0xffffffff | 0x0 |
----------------------------------
| s8 | 0x7f | 0x80 |
| s16 | 0x7fff | 0x8000 |
| s32 | 0x7fffffff | 0x80000000 |
----------------------------------
The table is pretty easy to memorize. Essentially, for unsigned ints, the max value is always a bunch of f's in hexadecimal, and the min-value is always 0.
For signed ints, the max value is always 0x7f, followed by a bunch of f's.
And lastly the min value for signed ints is always 0x80, followed by a bunch of 0's.
One thing to notice is the bitwise representation for "-1" always has all-bits set.
That means that for a 32bit integer, "-1" is "0xffffffff", which is the max value for an unsigned integer.
This means that for unsigned integers, we can declare int max/min like this:
int main() {
unsigned int x = -1u; // Unsigned int max
unsigned int y = 0; // Unsigned int min
return 0;
}
In c++, you can put the suffix "u" at the end of an int literal to mean its unsigned. So what that code is doing, is treating the value "-1" as an unsigned int, which means its assigning 0xffffffff to the variable 'x'.
Here's the thing, I've noticed that some compilers end up generating warnings when you treat a negative number as unsigned in operations, so instead of writing '-1u', we can notice that negative one, is really the same as NOT 0, so we can instead write '~0u'. This will do the same thing, and is generally better to do since it won't generate the compiler errors.
So its nicer to do:
int main() {
unsigned int x = ~0u; // Unsigned int max
unsigned int y = 0; // Unsigned int min
return 0;
}
Now that we know this trick for unsigned ints, lets think of signed integers.
The max value for 32bit signed integers is 0x7fffffff.
If we notice though, 0x7fffffff is really (0xffffffff >> 1).
That is, signed int max, is equal to unsigned int max shifted right by one.
But since we already learned the trick on how to represent unsigned int max easily, we can use that to our advantage:
int main() {
int x = ~0u>>1; // Signed int max
return 0;
}
The last thing to notice for signed ints, is that the minimum value for 32bit signed ints in hex is 0x80000000, but it just so happens that that number is signed int max + 1, that is 0x7fffffff + 1.
So we can end up doing this:
int main() {
int x = ~0u>>1; // Signed int max
int y =(~0u>>1)+1; // Signed int min
return 0;
}
That about does it for integers, for floats its not as simple so I didn't talk about them here. Maybe I'll end up making another blog post about the different floating point representations...
Notes:
When doing the '-1' or '~0' tricks where you shift the value; be sure to do the shift as an unsigned operation! That is either do: ~0u>>1 or (unsigned int)~0>>1, DO NOT do ~0>>1. This will do an arithmetic shift, instead of a logical shift, and make the result be -1, instead of 0x7fffffff.
And in-case you're wondering, these tricks are not 'slower' than typing in the numbers manually. C++ compilers do something called constant-propagation and constant-folding, which converts stuff like (-1u>>1)+1 to a constant at compile-time, and therefore there's no extra overhead compared to typing 0x80000000....
Also, this will not apply to most people, but another thing to note is that some very-old/weird hardware can use one's complement integers (instead of two's complement) or some other funky stuff; when dealing with weird hardware its best to use the numeric_limits class instead of bitwise tricks, because numeric_limits assigns its values based on the specific platform. That-said, I don't even know any hardware that uses one's complement for signed integers, so these tricks are almost always safe :p
Thursday, July 15, 2010
C++0x reusing same keywords and symbols for entirely different meanings
One thing especially bad about c++0x is that it seems to give different meanings to already known keywords and symbols.
For example, the array subscript operator "[]", already can be used to define arrays and index them, but now in c++0x they also denote lambda expressions.
But an even more ludicrous example is the keyword "auto".
"auto" in c++0x can be used to infer the type of an identifier, but it just so happens that "auto" already has a meaning in c++.
auto is used to denote "automatic storage", which essentially means stack-storage for variables that weren't declared globally..
So you can do:
The reason you don't ever see code explicitly using auto, is because 'auto' is on by default, so its rarely used.
This means however, that in a c++0x function you should be able to do this:
I tested this with GCC 4.5.0, and got a compiler error :/
In fact, GCC 4.5.0 with c++0x extensions enabled doesn't even compile "auto int i = 0;"...
I think this is a GCC bug, but still this shows the problems that reusing keywords and symbols can cause.
Also, needless to say, it makes things a lot more confusing for beginners to understand the different meanings of the words...
For example, the array subscript operator "[]", already can be used to define arrays and index them, but now in c++0x they also denote lambda expressions.
But an even more ludicrous example is the keyword "auto".
"auto" in c++0x can be used to infer the type of an identifier, but it just so happens that "auto" already has a meaning in c++.
auto is used to denote "automatic storage", which essentially means stack-storage for variables that weren't declared globally..
So you can do:
auto int i = 0;
The reason you don't ever see code explicitly using auto, is because 'auto' is on by default, so its rarely used.
This means however, that in a c++0x function you should be able to do this:
auto auto i = 0;
I tested this with GCC 4.5.0, and got a compiler error :/
In fact, GCC 4.5.0 with c++0x extensions enabled doesn't even compile "auto int i = 0;"...
I think this is a GCC bug, but still this shows the problems that reusing keywords and symbols can cause.
Also, needless to say, it makes things a lot more confusing for beginners to understand the different meanings of the words...
Wednesday, July 14, 2010
String Literal with Array Subscript Trick
This is a cool trick I just found out recently.
If you have a string literal such as "abcdef", you can interpret that as an array and use the '[]' operator to get the correct character from the string.
For example:
That will print out "jihgfedcba".
Now knowing this trick (as well as some other minor changes), we can omit a few lines from our hexToString() function in my previous article.
If you have a string literal such as "abcdef", you can interpret that as an array and use the '[]' operator to get the correct character from the string.
For example:
int main() {
for (int i = 9; i >= 0; i--) {
cout << "abcdefghij"[i];
}
cout << endl;
}
That will print out "jihgfedcba".
Now knowing this trick (as well as some other minor changes), we can omit a few lines from our hexToString() function in my previous article.
string toHexString(u32 value) {
char str9[9] = {'0'}; // '0' char followed by null bytes
for (int i = 7, pos = 0; i >= 0; i--) {
char dig = (value>>(i*4))&0xf;
if (!dig && !pos) continue;
str9[pos++] = "0123456789abcdef"[dig];
}
return string(str9);
}
Multi-Dimensional Array Optimization
When using multidimensional arrays in c++ (or most languages for that matter), it is better to use powers of 2 for all dimensions (except for the first one which doesn't matter).
For example, take the following multi-dimensional array:
int a[3][3][3];
It will be faster to reference the elements in the following array instead:
int a[3][4][4];
The reason is that the compiler can use shifts when calculating the address to read from, as opposed to using multiplication operations. On x86 processors, this shifting by powers of 2 could even be implicit as part of the memory addressing modes which allow a shift parameter in their encoding.
So if you need speed, it could be beneficial to use powers of 2 dimensions even when you don't actually reference the extra memory. Although this optimization may require benchmarking if you increase the size of the array with too much unused data; because it may slow down the code by having less efficient cache-usage due to the extra unused memory. (in the case where all the memory will be used, then its a win-win situation)
In some cases you don't even need to increase the array dimensions to benefit from this knowledge. If you have an array "int arr[4][7];" you know it will be more efficient to swap the dimensions and just access it the other way: "int arr[7][4]".
For example, take the following multi-dimensional array:
int a[3][3][3];
It will be faster to reference the elements in the following array instead:
int a[3][4][4];
The reason is that the compiler can use shifts when calculating the address to read from, as opposed to using multiplication operations. On x86 processors, this shifting by powers of 2 could even be implicit as part of the memory addressing modes which allow a shift parameter in their encoding.
So if you need speed, it could be beneficial to use powers of 2 dimensions even when you don't actually reference the extra memory. Although this optimization may require benchmarking if you increase the size of the array with too much unused data; because it may slow down the code by having less efficient cache-usage due to the extra unused memory. (in the case where all the memory will be used, then its a win-win situation)
In some cases you don't even need to increase the array dimensions to benefit from this knowledge. If you have an array "int arr[4][7];" you know it will be more efficient to swap the dimensions and just access it the other way: "int arr[7][4]".
Subscribe to:
Comments (Atom)