Sentinels in JavaScript

Can you find the substring?

Can you find the substring?

In older procedural languages, the return values that came back from a function were restricted. If you said you were going to return a number, you returned a number. If you wanted to sometimes return a number, but other times return an indication of failure, you resorted to what is known as a “sentinel value” to return the failure.

A sentinel value is a number that doesn’t represent the answer to the problem that the function was asked to solve, but instead flags the caller to the fact that something rather out-of-the-ordinary has happened. For example, a value of -1 can indicate the end of a file being read in.

The problem with a sentinel is that it means nothing special to the language. The programmer has to keep in mind that the sentinel exists and that it has to be handled on every call that could possibly generate the sentinel value. Programmers are notorious for paying attention to and handling sentinels only when they crash a program.

Also, the programmer has to be careful in choosing the value. Is it 0? -1? 99? 255? 999? -999? MAXINT? The choice can bite you if you’ve misunderstood the possible values that can be generated in your function. I regret to inform you that I once wrote a BASIC program that had three different sentinel values returned from three different subroutines!

Sentinel values sound old and busted, don’t they? Their usage fell a bit once we could pass around pointers to data structures. With a little more elbow room, we could put a “success” boolean right up front in the data structure and do away with a lot of sentinels.

They Live!

But sentinels are still around. In JavaScript, the string method “indexOf” returns a -1 if the needle (substring) can’t be found in the haystack (the string to be searched).

Let’s look at a few different ways we can deal with that awkward -1.

function wrappedIndexOf(needle,haystack) {
    var res=haystack.indexOf(needle);
    if (res===-1) {
        res=false;
    }
    return res;
}

And you call it like this:

res=wrappedIndexOf(needle,haystack);
if (res!==false) {
    location=res;
}

We haven’t done much here but replace the need to check explicitly for -1 with a need to check explicitly for false. Too weird to sometimes return a number and sometimes return a boolean? Yeah, probably. I like it a bit better than the numeric sentinel because the calling code makes the exception check a bit more obvious. Because JavaScript functions can return just about anything (including wild things like anonymous functions), you always need to think about what can come out of a function, so what’s important is a consistent convention.

Similarly, you could return null or undefined.

But let’s move on to another solution–returning an object.

function wrappedIndexOf(needle,haystack) {
    var res=haystack.indexOf(needle);
    if (res===-1) {
        res={"success":false,"value":-1};
    } else {
        res={"success":true,"value":res};
    }
    return res;
}

And you call it like this:

obj=wrappedIndexOf(needle,haystack);
if (obj.success) {
    location=obj.value;
}

Note that I’ve left the -1 in obj.value, so you can still use that as a sentinel if you like.

What makes JavaScript really good for this task? Its object literals. You don’t need to have a structure or class around to hold the extra info. You just build the object on the fly and return it.

Bitwise, Byte Foolish?

 

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

In the post-apocalyptic world of Logan’s Run, humans live out cramped lives in a bunker. Because of the crowded conditions, all citizens must submit to Carnival on their 30th birthdays. What do you do on your Carnival day? You and all the other 30 year olds spiral up into the air and get zapped to death.

Sound like a bad deal? It gets worse. The radiation outside has long since subsided, and the rules being enforced are no longer necessary.

I’ve been immersed in JavaScript for the last few years. Every time I’ve read about JavaScript’s bit operations (and it has a very nice set of ops), I’ve been warned that they are “a hack,” and “slow.” This has always bummed me out. I love bits.

But I got to thinking the other day, all these warnings sound like a sort of a Logan’s Run passed-down message from days gone by. With all the cool things that have been going on with JavaScript lately (thanks to Google’s V8 and the various JIT subsystems going into browsers), maybe, just maybe, bitwise operations have sped up enough to be worthwhile. Since some of the JIT compilers are doing type inference, a series of bit operations could, in theory, be done at full speed, without costly implicit type conversions.

Who Needs Bits?

When I started programming (on 8-bit processors), I mostly worked with integers. When floating point numbers became available, I avoided them for years because they were slow. We did as much math as we could with integers and bit operations. Shift left once, and that’s a multiplication by 2. If you wanted to multiply by 10, you’d do a shift left by one (times two) and a shift left by 3 (times eight) and add those results together.

You wouldn’t do math like that any more, but bits are still good as flags. A single JavaScript number (when treated bitwise) can hold 32 boolean flags!

Here’s what I found out. Just about everything I tried was faster with bitwise operations than with other solutions (even in Internet Explorer). No, you can’t usefully replace one multiplication with a series of adds and shifts, but by no means are bitwise operators too slow to be useful.

        k=~~i; //this is much faster
        k=Math.floor(i); //than this

You can lop off the decimal part of a number not just with ~~, but with ^0 and <<0, too. And they are ALL significantly faster, in all modern major browsers, than calling Math.floor().

//break a number in the range 0-65535 into
// low and high bytes

// this is significantly faster
    lo = i & 255;
    hi = i >> 8;

//than this
    lo = i % 256;
    hi = (i-lo)/256;

Don’t discriminate against JavaScript’s bitwise operators. But keep these things in mind…

  1. You have 32 bits to work with when you treat a JavaScript variable as bits. And that top bit is a sign bit (meaning any number with that top bit set is a negative number).
  2. Don’t mistake bitwise for logical operators.
  3. Learn the difference between “-” and “~”.
  4. Remember that >> shifts the sign bit down while >>> shifts a zero into the top bit.

My favorite place to learn about JavaScript bitwise facilities is here: Bitwise Operators.

When should you be using bitwise operators? Obviously, when you want to pack a bunch of flags into one variable. That should be much faster than having an array of flags.

Dealing with the red, blue, and green parts of a color call out for bitwise operators.

And think about using a shift when you want to multiply or divide by a power of 2, while at the same time converting a floating point number into an integer. Two operations for the price of one!