I’ve reached the conclusion that hype is an important aspect of any project. I shall jump on that bandwagon then, for I am announcing that I am working on a new project!
More details to come in the following weeks…
Every now and then I remember playing the games I used to play as a child. One of those games was Super Mario World for the SNES. The reason why I bring this up is because of this very cool trick you could pull off in the Forest of Illusion level. With it, a semi-skilled player could go from 0 to 99,999,990 points in a few minutes.
Here’s the video displaying you how to do it, it’s pretty neat:
Now as you watch it, you can see Mario jumping from Wiggler to wiggler, and while he does that he gets points and extra lives. Here’s the screen shots of his points:
And as continues to bounce, the lives he gets:
However on the 7th wiggler jump he gets this symbol:
And then this one:
And so on and so on:
When I was 9 years old and saw those symbols for the first time, I had no idea what they were. The manual where I read this secret trick from said they were “secret super symbols that show how awesome you are!” But after reviewing this video a few times, I think I have a different opinion on what it might be: an offset pointer in video memory going haywire.
To understand what I mean by that, let’s have a quick discussion. In classic consoles programming, for an image (normally known as sprite) to be drawn into the screen, it’s done in the following sequence:
Given that condition, here’s one of the most basic animation algorithms for sprite based rendering. You’d load a sprite such as this:
Into memory and you’d use the sprite render pointer offset to interpolate between the frames. So you’d start with coordinates (0,0), then after a few fractions of a second you’d switch to (1,0), then (2,0) and so on. Via this method you’d get an animation such as:
Given that technical description and the above Super Mario World glitch, here’s my assumption of what went wrong:
So say the player jumped on a wiggler. The jump_counter would increase to 1 and render 1000 points. If the player jumped on another wiggler, the jump_counter would go to 2, and render 2000. As the player continued to “bounce” around, this process would continue.
So my assumption is that the algorithm was basically:
if( player_jumped_on_bouncy_object() )
{
Jump_counter++ ;
Points_variable += power_of_two( jump_counter ) * 1000;
player_lives += ( jump_counter > 4 ) ? jump_counter : 0 ;
ImageHandle Image_to_render = memory_offset_via_jump_counter(jump_counter);
Render_image( get_player_bounced_pos(), image_to_render ) ;
}
Now let’s explain the above pseudo-code:
Simple, isn’t it? However there’s a bug in the above pseudo-code. We can only retrieve valid image handles when the jump_counter’s range is from [1,7]. What if we make a request when jump counters is equal to 8 and above?
And that’s the catch! We get an invalid pointer offset to somewhere else in memory! Since that memory area is used for what’s to be displayed on the screen, we get bits and pieces from other sprites.
Obviously this is all an assumption of what went wrong. I could be incredibly incorrect in my analysis, but at least it’s worth a shot. What are your thoughts on this one?
A few weeks ago I saw this forum question where a user asked help on making an algorithm that:
“replaces all the vowels in a string with the character ‘*’”
The other users in the forum quickly replied and helped him with that question. For some reason though, that problem stuck to my head. Sure it’s a simple algorithm, but I thought what if I added a new constraint: It has to be done fast, really, really fast.
To me this created a whole new approach to the problem, and I was interested in seeing how far I could take it. So, for starters I took the best reply to the forum thread from user Dominuz (who himself stated that he focused more on clarity and ease of understanding rather than optimization )
Below is his sample code:
#include <stdio.h>
char vogais[] = {'a','e','i','o','u'};
void subst(char* nome)
{
for( unsigned int i = 0; nome[i] != '\0'; ++i )
{
for( unsigned int j = 0; j < 5; ++j )
{
if( nome[i] == vogais[j] )
{
nome[i] = '*';
break;
}
}
}
}
int main()
{
char criatura[] = "12 Criatura aeiou 123456";
printf( "%s \n", criatura );
subst( criatura );
printf( "%s \n", criatura );
return 0;
}
For starters, I knew a simple text string would not be enough to measure different algorithms performance. So I decided to take a larger text as input, in this case Michael Jackson’s Wikipedia page as a tribute to the late king of pop. The total file was 273kb.
I modified Dominuz code to open the file, perform the subst function a thousand times, while recording how long it took to do that. The result was stored in a text file. Here’s my initial modification of his code:
#include <iostream>
#include <fstream>
#include <Windows.h>
using namespace std;
char vogais[] = {'a','e','i','o','u'};
void trunc_double()
{
fstream file( "out.txt", ios::out | ios::trunc ) ;
file.close() ;
}
void save_float( double d )
{
char buffer[256] ;
fstream file("out.txt", ios::out | ios::app ) ;
sprintf_s(buffer,"%.15f\n", d ) ;
file.write( buffer, strlen(buffer) ) ;
file.close() ;
}
char* malloc_and_setup_buffer()
{
char *b = NULL ;
int b_size = 0 ;
fstream file ;
file.open( "mj.txt", ios::in | ios::binary ) ;
if( !file )
return NULL ;
file.seekg( 0, ios_base::end ) ;
b_size = (int) file.tellg() ;
file.seekg( 0, ios_base::beg ) ;
b = new char[b_size];
file.read( b, b_size ) ;
file.close() ;
b[b_size-1] = '\0' ;
return b ;
}
void dealloc_buffer( char* b )
{
if( !b )
return ;
delete[] b ;
}
void subst(char* nome)
{
if( !nome )
return ;
for( unsigned int i = 0; nome[i] != '\0'; ++i )
{
for( unsigned int j = 0; j < 5; ++j )
{
if( nome[i] == vogais[j] )
{
nome[i] = '*';
break;
}
}
}
}
int main()
{
LARGE_INTEGER lg0, lg1, frequency ;
QueryPerformanceFrequency(&frequency) ;
trunc_double() ;
for( int i=0; i<1000; i++ )
{
char* b = malloc_and_setup_buffer() ;
if( !b )
return 0;
QueryPerformanceCounter(&lg0) ;
subst( b );
QueryPerformanceCounter(&lg1) ;
float dt = (float)(lg1.QuadPart - lg0.QuadPart)/(float)frequency.QuadPart;
save_float(dt) ;
dealloc_buffer( b ) ;
}
return 0;
}
As you can see, I’m only worried on how long it takes to run the subst function. After putting this data into excel, I got that the average for sample one is 0.002205584 seconds. From that basic setup, I started the optimizations.
A quickly saw that you could force inline the subst function, making a call to it faster. However the biggest issue I had with it was accessing ‘vogais’ as a global variable, instead of a local function variable.
What’s the big deal about that? Well when you reference a global variable you are referencing an area of memory, contrary to when you access a local variable, which implies you are referencing the stack. And in terms of access speeds, stack beats memory.
So after re-implementing subst I got this:
__inline void subst(char* nome)
{
if( !nome )
return ;
char vogais[] = {'a','e','i','o','u'};
for( unsigned int i = 0; nome[i] != '\0'; ++i )
{
for( unsigned int j = 0; j < 5; ++j )
{
if( nome[i] == vogais[j] )
{
nome[i] = '*';
break;
}
}
}
}
After running it again and calculating the average I got 0.001782024 seconds. Not bad, I got a bit of an improvement over the previous algorithm. It still wasn’t enough to say I had a significant impact though.
If you look inside subst we have two loops, one iterates through each letter while the other iterates through each vowel. Well loops translate into assembly as jump instructions and those are expensive. So in order to get rid of jump instructions I performed a technique called ‘loop unrolling’. Below is the result:
__inline void subst(char* nome)
{
if( !nome )
return ;
for( unsigned int i = 0; nome[i] != '\0'; ++i )
{
if( nome[i] == 'a' || nome[i] == 'e' || nome[i] == 'i' || nome[i] == 'o' || nome[i] == 'u' )
nome[i] = '*';
}
}
Its average was 0.001161438 seconds. Not bad! Almost twice the performance when compared to the first one. But I wasn’t ready to finish yet.
You see my big issue with this model is that we are performing five vowel comparisons per letter. This translates to several compare and jump instructions in assembly and that’s just slow. I had to think of a way of getting rid of those comparisons.
After giving it some thought, I found a way out! I used a lookup table. Since bytes can only have 256 different values, I created a lookup table with 256 bytes in size. All bytes were set to 0, except indexes 97, 101, 105, 111 and 117, who were set to 1. What’s special with those values? Well they are exactly the indexes for the vowels a, e, i, o and u in the ascii chart.
I thus use the letter itself as the index in the lookup table, which indicates if it’s a vowel or not. Here’s the code:
__inline void subst(char* nome)
{
if( !nome )
return ;
char table[256] ;
memset( table, 0, sizeof table ) ;
table['a'] = 1 ;
table['e'] = 1 ;
table['i'] = 1 ;
table['o'] = 1 ;
table['u'] = 1 ;
for( unsigned int i = 0; nome[i] != '\0'; ++i )
if( table[ nome[i] ] )
nome[i] = '*';
}
The result? 0.000951169seconds. Not bad, managed to go in under 1 microsecond.
I kept thinking though that there was something else that I could add to this code… somehow I was missing something obvious. After a few minutes it hit me! I could do loop unrolling again and perform even less jump instructions!
After some testing, I decided to unroll the loop 4 times. For that I had to split the loop into two parts. The first part would have to iterate all the way up to the closest multiple of four, but not greater than the string’s size. The second loop I would need to take care of the last 3 potential characters left in the text
Now to reach the closest multiple of a number using integer arithmetic you do:
Number = ( number * multiple ) / multiple
Due to the nature of integer division, since it naturally rounds down the numbers, we reach our value. The problem though is that multiplication and division are expensive and should be avoided in fast algorithm construction. Is there a way to get rid of them?
Well yes! We just have to use bitwise operations. I didn’t just choose to unroll the loop four times for no reason. Since four is a power of two, it thus has the following property: adding it to a number, then performing the bitwise AND with its negative bitwise gives the closer or greater multiple of that number. We just subtract the number once from the result and alas, we have the closest or lower multiple of four from the original number.
So finally here’s the result:
__inline void subst( buffer_data bd )
{
char *b = bd.b ;
char table[256] ;
memset( table, 0, sizeof table ) ;
table['a'] = 1 ;
table['e'] = 1 ;
table['i'] = 1 ;
table['o'] = 1 ;
table['u'] = 1 ;
int i ;
const int upper_s = (bd.size_b + 3) & ~0x03 - 4 ;
for( i = 0; i < upper_s ; i+=4 )
{
if( table[ bd.b[i] ] )
bd.b[i] = '*';
if( table[ bd.b[i+1] ] )
bd.b[i+1] = '*';
if( table[ bd.b[i+2] ] )
bd.b[i+2] = '*';
if( table[ bd.b[i+3] ] )
bd.b[i+3] = '*';
}
for( ; i < bd.size_b ; i++ )
{
if( table[ bd.b[i] ] )
bd.b[i] = '*';
}
}
The result is then 0.000845947 seconds. I was almost ready to settle with it but I remembered one last detail: cache.
I’m using a 256 size lookup table. But I only care about the alphabet characters in the ascii chart. I could thus reduce the table to 32, which is the closest power of two multiple from 23. The bright side of having a smaller lookup table is that we manage to maintain it longer in the CPU’s cache. Less cache misses, faster algorithm. So here’s the code with that in mind:
__inline void subst( buffer_data bd )
{
char *b = bd.b ;
char table[32] ;
memset( table, 0, sizeof table ) ;
table['a'-97] = 1 ;
table['e'-97] = 1 ;
table['i'-97] = 1 ;
table['o'-97] = 1 ;
table['u'-97] = 1 ;
int i ;
const int upper_s = (bd.size_b + 3) & ~0x03 - 4 ;
for( i = 0; i < upper_s ; i+=4 )
{
if( bd.b[i] < 97 || bd.b[i] > 122 )
continue ;
if( table[ bd.b[i] - 97 ] )
bd.b[i] = '*';
if( table[ bd.b[i+1] - 97 ] )
bd.b[i+1] = '*';
if( table[ bd.b[i+2] - 97 ] )
bd.b[i+2] = '*';
if( table[ bd.b[i+3] - 97 ] )
bd.b[i+3] = '*';
}
for( ; i < bd.size_b ; i++ )
{
if( bd.b[i] < 97 || bd.b[i] > 122 )
continue ;
if( table[ bd.b[i] - 97 ] )
bd.b[i] = '*';
}
}
And the final result is 0.00084498. Not much faster from the previous algorithm but a lot faster when compared to the first one. In fact it’s over two and half times faster.
Now I’m sure that if I kept at it I’d find even better ways to optimize this algorithm, but I’m settling with what I got for now. With this exercise I just wanted to prove a few points:
1. Knowing computer architecture and how code translates into assembly can be quite useful.
2. Like Michael Abrash pointed out, there’s no such thing as the fastest code in the west.
3. Knowing bitwise and pointer arithmetic helps as well.
4. I should have a better social life.
Well I guess that’s it for now! Click here: Fast Vowel (87) to download the sample code and take a look at it yourself. Do keep in mind that I only tested this in one machine and in different environments the results may vary.
The comparisson table:
In Brazil I usually hear in social circles, or even in the news, the expression ‘jeitinho brasileiro’. It’s normally used to express a sort of “way of getting things done via the right person” attitude. It’s seen as a trait of Brazilians, that describes our social cordiality to one another, for it is our attempt to bend a system or process to aid someone in need. It’s usually regarded as a positive trait and encouraged for us Brazillians to have.
We shouldn’t.
The ‘jeitinho brasileiro’ displays a clear systematic failure in our capacity of getting things done. It displays our inability to create dynamic processes in a way that is fair, consistent and reliable to others. For if you need the cordiality of an individual at the right time, then clearly others will not have the same aid when they need it. There will be no basis to judge who really needs it or even if someone doesn’t deserves it all
The ‘jeitinho brasileiro’ thus creates a parallel system to the current processes being executed in which individuals can switch back and forth when possible to gain personal advantage over others. It thus induces people to follow the rules only as needed, as well as power play, and even to allow individuals the capacity to control such a system altogether. Let me give you an example;
A few months ago, I went to a bank to close an account, since I was leaving the country. The clerk told me that the only way to close it was if I made the request at the original agency where I opened it. The only problem was that this agency was 2 and a half hours away from where I was.
I left the bank and by luck found another one just a few blocks down the street. I entered the agency and used a very emotional ‘pwuese help mi mista’. They said I had to indeed go to the original agency to close the account, but after discussing a few minutes with one of his co-workers, he found a loop hole in the system. Basically he printed a check from the bank, put in my bank account information and with it I withdrew all the money I had in the account. When you empty an account, it prompts the clerk if he wants to close it and he used that trick to cancel my account.
Sure it was great he helped me with the ‘jeitinho’ but that’s exactly the problem. If a system inadvertently possesses a loop hole, why isn’t it being fixed? If a system possesses a way to aid users, why isn’t it being standardized?
That’s the problem with the ‘jeitinho’. With it, we can use it to keep and even maintain a clearly inefficient system. Since the system is ‘working’ why fix it? It hides weak links that need to be fixed….. and yes that implies firing people. It also implies in hiring people… trainning them… and all that comes with it.
Unless things keep being done in the ‘little way’ they’ll stay exactly like that: Little.
I think any close friend I’ve had through out the years knows that if there’s one thing I love is games and game development. It’s something I always knew I wanted to do professionally.
Now the idea in itself wasn’t the problem, reaching that goal however, was. As a Brazilian living in Brazil for most of my life, I often felt in a situation where I had to somehow find a way to break out and make it in the gaming industry. It was like I was in an uphill battle to at least get my foot in the door. How could one find a way to cross the ocean and prove himself?
For most of my childhood and early teens I had no idea how this could be done. I remember reading and re-reading countless interviews with game professionals, on how they got their start, trying to find a pattern so that I could follow the same approach. To my frustration, those interview didn’t help at all. Most of the developers said they landed on the industry ‘by luck or chance’. That was of no help to me.
You see if you want to become a doctor, you go to Med school. If you want to become a lawyer, you go to Law School. It’s a pretty A to B basis in terms of career paths. Due to the nature of the gaming industry, my frustration was the lack of a clear path on how to become a developer. Just because you went to college and got a Computer Science degree, that didn’t mean you’d eventually find a way towards a game development house.
However, like most stories, that all changed one day…
Years ago, circa 98-99, I was watching an episode of Cybernet, an old british program about games. In that episode, they were interviewing several famous developers and asking them on how one could find a way to join the gaming industry. Some of them gave vague answers, others told about books you could read, etc. None of it, to me at least, gave a clear and concise structure.
Then showed up a developer named Gabe Newell. I’m sure most of you have heard of him. His approach to it was quite simple, something alone the lines of:
“Develop something. Anything. Show it off to friends and to developers. Get the feedback they give you and insert it into your development process. Improve and expand what you’re doing. Keep doing it and eventually you should pick up the interest of someone willing to hire you.”
When I heard that, it was like I was shot with a diamond bullet. It was simple, brilliant and elegant. If you want to become a professional game developer, just develop games until they are good enough to spark interest.
I finally had what I needed: a plan.
And boy did I take that plan seriously. I took it for granted in every sense of the word. I bought dozens of books to develop my projects. I setup time during my college years to develop my projects. I gave up on academic scholarships with my professors so that I could focus on my projects.
Everything evolved around them. If I had free time, projects. Vacation time, projects. Weekends, projects. Time in between classes, projects. I became obsessed with it as some of my colleagues probably noticed, but to me it was a chance.
In some ways I felt it was my only chance.
Now these projects they were simple, crude, unfinished and lacking any real polish, but by god I worked on them. I re-wrote the Solis engine and editor so many times I grew used to it. I remember during my late night coding sessions taking the conscious decision on developing the entire Solis scripting language and interpreter. I said to myself “I guess during an interview process, this should impress someone”.
And it did, for I was asked to explain it during my on-sight interview at Microsoft, in Redmond. Two weeks later, I got the e-mail saying I go the job.
Thus here I am saying that the plan worked. Of course I owe to my family and friends for their support during those years, but in some ways, I wanted to say thanks to Gabe N. A long time ago, in a forgotten interview, you showed a young Brazilian a way to get things working.
And they did. Thanks.
Today I saw something that changed my life:
I saw my grandmother, who’s been learning to play the piano for a few months, play for the first time. I was the first person, besides her teacher, that heard her music.
And it was magical. It filled me with so much joy and pride that I don’t know how to put it in words… here is a lady, that’s been through hell and fire, playing this soft piano music…
And it hit me like a diamond bullet… It made me realize that things change. That people change. That things do get better eventually. When she finished I had no idea of what to say…
So we just hugged, laughed and cried.
Because you never need words after a nice song.
Today I finished reading this book: Writing Secure Code vol 2.
I picked it up when I went to the mall with my sister and a friend of hers. While they were chit chatting I was browsing the book store and started reading it. The first 50 pages felt rock solid with materials on how buffer overflows, off-by-one rounding errors and heap overflows could give users overwhelming potential risk over your system. So I bought it expecting to learn more on how to write good, solid and safe code.
After reading it I can definatly say that I did learn that, both the authors have extensive knoledge on this topic. What I really did enjoy though is that as the authors went further with the topics at hand they started giving personal experiences they had with software security and vulnerabilities.
They talked about the Microsoft Push Security Move, what they learned, common mistakes other developers told them, bets they made to see if anyone could crack their systems, etc. It’s filled with amazing little side stories on how certain issues rise from common misconceptions and how the authors dealt with them.
One of my favorites was when one of the authors found a critical security flaw on the software he and his team were developing. He discussed this issue with his managers, but they saw no threat in it and told him to ignore it. So he used that exact bug to invade the general manager’s computer, proving his point on how deadly this bug was. The issue was then promptly resolved.
I think one of the implicit ideas both developers taught in this book is that for a manager to know how to deal with the management of developing safe software, he needs to understand how safe software is developed. In other words, and extending the idea to a broader term:
Good software managers are good software developers.
And I couldn’t agree more.
I like playing games and listening to music at the same time. I think most people do too.
However, I have the habit of when finding a song or band I like just listening to it over and over and over again.
The funny thing is that it creates in my mind a sort of union between the band I was hearing and the game I played. Also, since I traveled a lot due to my father’s career, these games and songs also marked the place where I stayed.
So whenever I listen to that band or play the game or hear a conversation about a place I visited I remember the other two. It’s gives me a good nostalgia sensation that I love. Here’s a list that I managed to remember:
Middle school in Rio
Falls church in Washington D.C.
College years in São Carlos
Weeks before graduating from college, while I was handing out resumes and doing job interviews, my father, who has an engineering background, asked me the following question:
If I were a farm owner and wanted you to create a machine that sorted the bad potatos from the good ones, what would you do?
Seemed like a simple task so I thought about it for a few seconds. Initially I imagined a device that would take pictures of the potatoes and perform image processing queries on them. These queries could then figure out if there were any fungus or odd shapes in the potatoes.
When I told this to my father he laughed. He said: just throw the potatoes in water. The ones that don’t float are the bad ones.
Now this is a very simple example of an issue that I think rises with a lot of development and engineering teams. You see, had you had asked that question to an electrical engineer he might have thought if the current that passes in bad potatoes is different than in the good ones. A mechanical engineer might have thought about the weight difference between the potatoes, and so on.
People tend to face problems from their technical backgrounds, which is not particular a bad thing, but it is important to be able to extend to other areas of knowledge, even trivial ones. Had any of those engineers had asked a cook about the potato problem, they would have probably had the best answer.
And to me that’s the crucial point here. I think a lot of projects fail because people fail to assume some other realm of knowledge might have a better understanding of the problem they are facing. They assume they can ‘deal with it’ and in the end, all they get is a bunch of bad project decisions and thus, bad potatoes.
In my last year of high school I had your typical Brazilian literature teacher, where he used to praise Brazilian authors in contrast with foreigner ones. He used to denounce reading foreigner authors and that the Brazilian mass should enjoy more of its local authors.
I pretty much disagreed with most of the things he said, but he did say one thing that struck me as true and it’s pretty much the only thing I took with me from his classes. He said:
An artist writes how he feels and how he feels is a direct consequence of the environment he finds himself at.
In other words an artist’s background, culture and the society around him influence his artistic views. Makes pretty much sense doesn’t it? But people usually apply this to writers and the normal standard of an artist. The catch is that it affects all creative thinkers, this includes engineers and software developers as well. Here’s an example.
Every now and then I read some article comparing the PlayStation 3 architecture with that of the Xbox360. Makes sense since they were both platforms developed to handle massive amounts of data. Usually those comparisons involve a instruction/triangle/frame/shading per second/pass view or how the 6 synchronous SPU cores compare with 3 asynchronous cores.
It’s all quite interesting, since for on one hand you have an architecture that’s basically massive raw power, running at the highest possible clock speed, with tons of ram. Big and bulky American muscle. On the other side you have a series of smaller cores, that require a more ellaborate design, streched throughout each individual node. Less but more refined, efficiency through group effort. When I see these sorts of things I think of only one thing: Motorcycles.
You have the classic American choppers, big bulky American muscle. Lots of fuel, big engine cylinders, raw power per torque. Made to last.
And then you have the Kawasaki’s lines. Less fuel per cycle, more refined in it’s architecture. Made to run fast.
Each of those types of Motorcycles present its ups and downs. With one you can go from coast to coast and back again. The other you can only go from one to state to the other but at top speed. They’re the same type of vehicle but the catch is that they were designed by engineers of different nationalities.
I’m not trying to throw the cliche dilemma of East vs. West here because I see it more as a general social example. Both engineering teams were given the same task: built me a motorcycle, but their final product is obviously different in terms of style and scope. To me a big part of it is that both teams had different cultural backgrounds, were in different societies and had thus different views on how to solve the same problem.
I think the same happened with the Xbox 360 and ps3 teams. Both had the same task: build me a video game, and the final product is obviously different.
Both systems have it’s ups and downs but the point I’m trying to make is that I think an ideal developer/engineer would be able to go beyond his cultural heritage and be able to reach the same conclusions the other team had, and in the end make the best overall decisions.
Generally I think a good artist is not bound by the limitations he found himself at. He is able to roam freely from it and create an art that doesn’t speak to only those individuals in his current social realm, but to all individuals. To me a good artist is universal in his approach of seeing and making art. As James Joyce put it brilliantly:
When the soul of a man is born in this country there are nets flung at it to hold it back from flight. You talk to me of nationality, language, religion. I shall try to fly by those nets
I think it’s a beautiful quote and strikes at the core of that which I spend so much time thinking about. Joyce is a relly good read, though unfortunally I don’t think my Literature teacher would read him.
At least you understand now why I disagreed with him so much.
