So you wanna make a laser go faster?



  • Just thought I'd share this little gem I cam across a couple of years ago when I was still a young and innocent games programmer, fresh out of university. We were working on a stealth game (you know, sneaking about in the dark, stealing stuff and dodging guards etc) when I was given command over the code that ran some of the "Security Devices" that were scattered about the levels for the players to try and circumvent. One of these devices was everybody's tried and tested favourite, the Laser Grid. You know the one, the thief is just about to run across the room to grab the ancient Inca treasure, when they spray an aerasol into the air and the room fills with beams of light causing the thief (usually some sort of black-leather clad lady of the night) to have to do all sorts of physical contortions and acrobatics to dodge past them.
     
     Now, we were developing for the PS2 which, for those of you not in the industry, only has 32mb of memory and a processor which isn't particularly fast or powerful. Imagine my surprise when I discovered the fact that, despite there being up to 30 or 40 lasers in a single room and upwards of a few hundred on a whole level (all of which needed to be held in memory at once), each laser beam was given its own in-game entity. This meant that each laser had a logical class in charge of handling it's game logic (i.e. "Has the player touched me?") and a graphical class in charge of rendering it to the screen.    There was no attempt made to group the lasers together for some optimisations or even just to save some memory, each laser was its own man, its own proud individual piece of OO craftmanship, cheerfully doing the same calculations as all the other lasers on screen to make sure it flickered in perfect synchronization with them.
     
     While pondering this fantastic expression of the rights of lasers over such morally insignificant issues as memory use, processor use and redundant repeated calculations, I discovered the secret technique used by the original coder to ensure that their code ran as swiftly and efficiently as a gazelle across the African plains:
     
     < C++ >
     bool inverse=false;
     if (*((int*)&laserAngle)&0x80000000)
           inverse=true;
     </ C++ >
     
     Of course, at first I had no idea of the true logic behind this code or, in fact, of anything that might be behind this code apart from the kind of mind that kicks Igor awake in the middle of a stormy night and demands that he go and procure some fresh brains as quickly as possible. Turns out that it's checking the sign bit of the float to see if it's negative; Presumably in the bad old days before people wrote optimising compilers, the above monstrosity was at least 3 cycles faster than:
     
     if (laserAngle<0)
     
     Later that day the laser code suffered a mysterious accident that caused it to be completely purged from the code base (I got in trouble for pouring holy water into the source control server), forcing me to rewrite it from scratch with something that used such new fangled techniques as:
     
     "Only do collision detection with a laser if the player is in the same room as it is"
     
     The trauma lives on though, and I still get a little twinge of guilt every time I think to use that pesky and inefficient < operator...



  • Yer lines are botched, sonny.



  • Two WTFs.

    One, your post doesn't line-wrap for some reason.

     
    Two, someone didn't use OOP for your game.



  • *Goes to check forum in Firefox*

     Oops... Maybe I should place a warning on the post, "Only view in Internet Explorer 7" >_<

    I'll fix it as soon as it let's me edit the post again...

     

    PS It was written in OO code, just not very well :)



  • [quote user="danielpitts"]

    One, your post doesn't line-wrap for some reason.

    [/quote]

    These are not lines - these are laser rays! Laser rays don't wrap.



  • Wraps fine for me. In Firefox 1.5 on Ubuntu



  • Its fixed now.



  • FF 2.0 on XP here, wraps fine



  • On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;



  • [quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

     Excellent, both harder to read and slower too, since as far as I can tell it does one extra operation than your version :)
     



  • [quote user="Devi"][quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

     Excellent, both harder to read and slower too, since as far as I can tell it does one extra operation than your version :)
     

    [/quote]

    <sarcasm> Heh, here I was, thinking that it was about job security through obfuscation... </sarcasm>



  • [quote user="Devi"][quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

     Excellent, both harder to read and slower too, since as far as I can tell it does one extra operation than your version :)
     

    [/quote]

    It's equivalent assuming val is signed.  If val is unsigned the expression is just a slow decrement.

    Depending on the CPU architecture the first version with the shifting might be faster.  There is a branch in the second version which will stop your instruction execution pipeline dead if branch prediction fails.  A branch prediction miss will cost a lot more than three instructions (shift, or, and subtract).  If the data is random and about half of it is below zero, branch prediction will be no better than random guessing and the execution speed could be cut in half.

     Finally, if your compiler isn't very smart it might code "val--" and "val++" less efficiently than "--val" and "++val".  OK, it would have to be dumb as a post to miss that obvious optimization as far as modern compilers go...
     



  • [quote user="Devi"][quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote] Excellent, both harder to read and slower too, since as far as I can tell it does one extra operation than your version :)

    [/quote]Counting operations doesn't give you the relative speed, though. You need to know how long each instruction takes, too.

    In this case, one uses an if() statement, thus causing a branch, whereas the other doesn't. Depending on your processor, a branch ranges from no problem at all all the way to a full pipeline stall.

    (Not defending the original, though - it's horrible, far from obvious, and only to be used when the code is a known speed bottleneck.)



  • [quote user="Bellinghman"](Not defending the original, though - it's horrible, far from obvious, and only to be used when the code is a known speed bottleneck.)[/quote]

    Not to mention it assumes that val is of a 32-bit type - and even if it's specifically defined as int32_t or the like, it's a magic number and brittle against changes.  The 31 should be (sizeof(val) * CHAR_BIT - 1).



  • [quote user="iwpg"]

    [quote user="Bellinghman"](Not defending the original, though - it's horrible, far from obvious, and only to be used when the code is a known speed bottleneck.)[/quote]

    Not to mention it assumes that val is of a 32-bit type - and even if it's specifically defined as int32_t or the like, it's a magic number and brittle against changes.  The 31 should be (sizeof(val) * CHAR_BIT - 1).

    [/quote]Very true. But at that point, if you're changing platforms, you should be retesting to see if the sane code is still a bottleneck anyway. I'd almost rather that your change wasn't made, because the program crashing and burning would call attention - but in the end, I'd probably put an assert(sizeof(val) * CHAR_BIT == 32) with a comment to that effect.

    Hmm, why does this silly editor suddenly decie to glabally replace ' ' with &nbsp;?



  • Imagine my surprise when I discovered the fact that, despite there being up to 30 or 40 lasers in a single room and upwards of a few hundred on a whole level (all of which needed to be held in memory at once), each laser beam was given its own in-game entity. This meant that each laser had a logical class in charge of handling it's game logic (i.e. "Has the player touched me?") and a graphical class in charge of rendering it to the screen.

    So seperate handling functions for each laser??



  • [quote user="nbit"]

    Imagine my surprise when I discovered the fact that, despite there being up to 30 or 40 lasers in a single room and upwards of a few hundred on a whole level (all of which needed to be held in memory at once), each laser beam was given its own in-game entity. This meant that each laser had a logical class in charge of handling it's game logic (i.e. "Has the player touched me?") and a graphical class in charge of rendering it to the screen.

    So seperate handling functions for each laser??

    [/quote]

     

    Oh yes, each laser was on the same level in the system as, say, a security camera. Each laser had it's own function call to render it, to update it, to query it etc. Also each laser had it's own ID registered with the central class factory, it's own housekeeping data and just about everything else needed for a full game entity. Considering that a laser is just a line segment, which could be stored in two 4-float vectors (i.e. 32 bytes min per laser) this meant that about 80%+ of the memory taken up by each laser was almost utterly redundant :)



  • [quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

     I don't see how they can be equivalent, how can the first version ever increment val? I think it's more like:

     if (val < 0) --val;
     



  • If I remember correctly, right shifts on a signed data type extend the sign bit.  So, if val is negative, then val>>31 will be -1 (all bits set), the |1 is effectively a nop, and val -= -1, thus val += 1.



  • Ah yes my bad, I was reading the | as a &.

    However, if I remember correctly, it is implementation defined whether shift right sign extends or not.


  • [quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

    Mandatory reply follows

    Use trigraphs for better representation of equivalence:

    val > 0 ? --val : ++val;

    End mandatory reply



  • [quote user="Mikademus"][quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

    Mandatory reply follows

    Use trigraphs for better representation of equivalence:

    val > 0 ? --val : ++val;

    End mandatory reply

    [/quote]

    Yeah,

        val -= (val>>31)|1;

    seems quite "elegant" until someone needs to change the variable to a different bitsize.

    I would use.  

        val += (val>0) ? 1 : -1;

    Using the bitshift just seems unportable, unreadable, unmaintainable, and just plain stupid. 



  • [quote user="Mikademus"][quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

    Mandatory reply follows

    Use trigraphs for better representation of equivalence:

    val > 0 ? --val : ++val;

    End mandatory reply

    [/quote]

    Ummm what has that got to do with trigraphs?
     



  • [quote user="Devi"][quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

     Excellent, both harder to read and slower too, since as far as I can tell it does one extra operation than your version :)
     

    [/quote]

    Not only slower, it doesn't do the same thing. regardless of what data type val is, try substituting 0 for val: -1; 1

    When I first saw this, I thought maybe I'd had too much Poopers Stoat on the weekend and had obliterated an important part of my brain, so I wrote a quick test for signed 32 bit ints from -5 to 5 for the two versions. I made sure I used copy and paste so my defective brain couldn't screw up the results and I found they produce markedly different results.

    Given that posts after the one I quoted use different implementations of the logic from the second version, there are a lot of WTFs right here in the posts to this thread, but at least I can rest assured that my brain still functions, albiet painfully.



  • [quote user="Devi"]

     "Only do collision detection with a laser if the player is in the same room as it is"

    [/quote]

     But what about quantum effects?
     



  • [quote user="woodle"][quote user="Devi"]

     "Only do collision detection with a laser if the player is in the same room as it is"

    [/quote]

     But what about quantum effects?
     

    [/quote]

    It's uncertain whether or not they occur. 



  • [quote user="ammoQ"][quote user="woodle"][quote user="Devi"]

     "Only do collision detection with a laser if the player is in the same room as it is"

    [/quote]

     But what about quantum effects?
     

    [/quote]

    It's uncertain whether or not they occur. 

    [/quote]

    So if >> does bit shifting, what does qubit shifting?



  • [quote user="CodeRage"][quote user="Mikademus"][quote user="dicey"]On a related note, not too long ago on a developer's mailing list for a large open-source project that I read, the following C fragment was called "quite elegant" 


    val -= (val>>31)|1;

    Wouldn't you agree? (it replaced the following code if you haven't figured it out by now (and who couldn't tell that the two are equivalent at a glance?))

    if (val > 0)
        val--;
    else
        val++;

    [/quote]

    Mandatory reply follows

    Use trigraphs for better representation of equivalence:

    val > 0 ? --val : ++val;

    End mandatory reply

    [/quote]

    Yeah,

        val -= (val>>31)|1;

    seems quite "elegant" until someone needs to change the variable to a different bitsize.

    I would use.  

        val += (val>0) ? 1 : -1;

    Using the bitshift just seems unportable, unreadable, unmaintainable, and just plain stupid. 

    [/quote]

    Well, I assumed the previous post had the correct equivalent form.  So, now that I remove this assumption, I would use...

        val += (val<0) ? 1 : -1;

    Which is more readable, and works better in case someone changes the int to a long, etc.  Why oh why don't I ever test my posts here better ;)


Log in to reply