Difference between revisions of "Efficient Hex"

Revision as of 06:36, 29 October 2007

Function: string hex(integer value);

Returns the hexadecimal nybbles of the integer value in order, from most to least significant, starting with the first nonzero nybble.

Parameters:

• integer

value

–

value to be expressed as hex

We derived this specification from the specification found at the hex article. We began with that conventional specification but then discarded any merely conventional requirement that prevented us from making the code more clever, small, or fast.

Our LSL wiki includes two articles to discuss the astonishingly non-trivial problem of converting to hex string from 31 signed or 32 unsigned bits of integer instead of just one article because our LSL wiki serves at least two distinct communities of LSL authors. Our new authors need to see brief & clear & conventional exemplars first, our experts find appropriate uses for the clever & small & fast exemplars.

We don't know how to write LSL that implements a hex function that is conventional and brief and clear and small and fast, all at once. We think that design goal is an impossibility in LSL, as in many other programming languages.

Different, Clever and Fast

You should choose this different, clever, and fast code when you can accept the cost of abandoning the conventional specification in order to make the code most clever and fast and small.

This code sees the most significant bit of the integer as just another data bit, rather than as the sign bit, so results with eight nybbles can begin with any of the nonzero unsigned nybbles 1 2 3 4 5 6 7 8 9 A B C D E F. This code also doesn't bother to calculate the "-0x" or "0x" part of the conventional answer.

This code returns "0" for 0, unsigned "80000000" for -0x80000000, unsigned "FFFFFFFF" for -0x1, etc. The code presented here does return easy-to-read upper case A B C D E F nybbles, but code exactly as small and fast can instead return easy-to-type lower case a b c d e f nybbles.

// http://wiki.secondlife.com/wiki/Efficient_Hex

string bits2nybbles(integer bits)
{
    integer lsn; // least significant nybble
    string nybbles = "";
    do
    {
        integer lsn = bits & 0xF; // least significant nybble
        nybbles = llGetSubString("0123456789ABCDEF", lsn = (bits & 0xF), lsn) + nybbles;
    } while (bits = (0xfffFFFF & (bits >> 4)));
    return nybbles;
}

161 bytes of code reported by llGetFreeMemory

Different and Small

You should choose this different and small code rather than the different, clever, and fast code when you think smaller means faster, or you have some other reason to care more about small than about clever and fast.

// http://wiki.secondlife.com/wiki/Efficient_Hex

string bits2nybbles(integer bits)
{
    string nybbles = "";
    do
    {
        integer lsn = bits & 0xF; // least significant nybble
        nybbles = llGetSubString("0123456789ABCDEF", lsn, lsn) + nybbles;
    } while (bits = (0xfffFFFF & (bits >> 4)));
    return nybbles;
}

139 bytes of code reported by llGetFreeMemory

Clever and Fast

You should choose this clever and fast code when you care most about clever and fast and small but you still have to implement the conventional specification.

We think this code produces the same results as the brief, clear, and conventional code of the hex article. After adequate education & review, you should agree.

This code cleverly packs all the source lines into one function, not two. This code cleverly assigns a variable and passes a copy of that variable within the parameter list of a function call, which works only when you & the compiler agree over which parameters to evaluate first. This code cleverly loops once per nonzero nybble, rather than unrolling the loop. This code cleverly zeroes the most significant nybble once per loop, rather than zeroing that nybble once and then looping separately to process the remaining nybbles if any. This code cleverly declares its variables outside the loop.

// http://wiki.secondlife.com/wiki/Efficient_Hex

string hex(integer value)
{
    string lead = "0x";
    if (value & 0x80000000) // means (integer < 0) but is smaller and faster
    {
        lead = "-0x";
        value = -value; // unnecessary when value == -0x80000000
    }

    integer lsn; // least significant nybble
    string nybbles = "";
    do
    {
        nybbles = llGetSubString("0123456789abcdef", lsn = (value & 0xF), lsn) + nybbles;
    }
    while ((value = (0xfffFFFF & (value >> 4))));
    
    return lead + nybbles;
}

202 bytes of code reported by llGetFreeMemory

Clever and Small

You should choose this clever and small code when you care most about clever and small and fast but you still have to implement the conventional specification.

We think this code produces the same results as the brief, clear, and conventional code of the hex article. After adequate education & review, you should agree.

// http://wiki.secondlife.com/wiki/Efficient_Hex

string hex(integer value)
{
    string lead = "0x";
    if (value & 0x80000000) // means (integer < 0) but is smaller and faster
    {
        lead = "-0x";
        value = -value; // unnecessary when value == -0x80000000
    }

    string nybbles = "";
    do
    {
        integer lsn = value & 0xF; // least significant nybble
        nybbles = llGetSubString("0123456789abcdef", lsn, lsn) + nybbles;
    } while ((value = (0xfffFFFF & (value >> 4))));

    return lead + nybbles;
}

197 bytes of code reported by llGetFreeMemory

Brief, Clear, and Conventional Code

You should choose this code when you care more about brief and clear than about clever and small and fast.

You should feel that the concise & conventional code is easy to review and modify. For example, you should immediately understand how to substitute the easy-to-read upper case A B C D E F nybbles of IBM style for the easy-to-type lower case a b c d e f nybbles of AT&T style. Also you should immediately see what results to expect that code to return for any input.

To see the code, visit the hex article.

// http://wiki.secondlife.com/wiki/hex

...

347 bytes of code reported by llGetFreeMemory

Instruments and Procedures

Science

By definition, our results are scientific only if we can teach you to reproduce them.

Instruments

Measuring clever, clear, and brief is hard. Eventually we present our consensus here, but consensus is hard to achieve among computer programmers, who by nature often passionately disagree, like other poets. Possibly the most useful opinions on clever, clear, brief, small, and fast come from the http://www.jargon.net/jargonfile/l/languagelawyer.html community.

Measuring small is easy. Compile two copies of the code into one script, call llGetFreeMemory, delete one copy, and report the difference. For more detailed instructions, especially if your results are off by exactly four bytes, see the Code Sizer article.

Measuring fast is hard, because a closed-source server runs a script and often crashes when we try to create enough results to average meaningfully, such as 7 x 10,000 x 5 runs of hex(0x7fffFFFF). The science of persuasively measuring fast in Second Life remains a work in progress, now ongoing in such places as the Efficiency Tester and Code Racer articles on how best to harness llGetTime and llGetTimestamp.

Measuring fast is painfully tedious too. 10,000 runs of 200ms burns thru more than 33 minutes of your time & attention. We welcome volunteers to advance this science.

Why Bother

The relative value of clever, clear, and brief is disputed. See http://en.wikipedia.org/wiki/Optimization_(computer_science)#When_to_optimize

The value of fast and small in Second Life LSL scripts is disputed, but not with enough passion for us to have found a cross-reference to share with you.

Illustrative Details

To see the raw data and arithmetic that stand behind the summary results briefly presented here, visit the discussion tab.

@@ Line 213: / Line 213: @@
 </div>
 </div>
+<div id="box">
 == See Also ==