Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Performant way to tag a number on JavaScript, using its less significant bit?

Often, for programming languages implementations, it is desirable to tag numbers using bitwise operators. In C, you could tag a double by using an union:

typedef union Tag_ { double d; long long i; } Tag;
double tag(double x){ Tag tmp; tmp.d = x; tmp.i |= 1; return tmp.d; };
double isTagged(double x){ Tag tmp; tmp.d = x; return tmp&1; };

What is a way to mimic this behavior on JavaScript? Using bitwise operators is ruled out, since it converts the doubles to Uint32s. I need a mathematical solution.

like image 526
MaiaVictor Avatar asked Nov 10 '22 00:11

MaiaVictor


1 Answers

This has not received an answer, perhaps you found one? If not:

Let me start off with the question in your comments, as it sounds like solving that question in the end solves the original question.

How can I create separated views of the same array?

This is essentially Bergi's proposal from the comments, slightly modified. It answers the How.

When you create an ArrayBuffer you can access the underlying array of bytes from multiple typed Arrays by passing that array buffer as an initial parameter. I've found JavaScripture -- ArrayBuffer to be quite helpful in the past with TypedArrays. So the following reserves 8 bytes in memory and accesses it as both a 64-bit float and 8 byte ints.

var myBuff = new ArrayBuffer(8);
var myU8Arr = new Uint8Array(myBuff);
var myFloat64Arr = new Float64Array(myBuff);

so if you say set the first byte in the buffer to 1, and then access that value from the float you will get a narly float:

myFloat64Arr[0] = 10000;
console.log(myFloat64Arr[0])//prints 0;
myU8Arr[7] |= 128;//sets sign bit of IEEE 754 Double-precision float.
//setting the sign because it's more straightforward than if another
//bit was to be set. 
console.log(myFloat64Arr[0]);//prints -10000 ... all dependent on system endianess

So, now that the question from the comments has been answered:

How can I use the least significant bit to tag my numbers?

Directly addressing the question; I don't see a problem with using the Typed Arrays. We can bitwise on the underlying bytes in the underlying Array Buffer without worrying that the byte will be turned into a 64-bit float and mess things over.

Sticking with your "stack" of floats will get you the added performance. Simple create the ArrayBuffer and then both the Uint8Array and Float64Array instead of an array of numbers (or an array of Tags). Otherwise you could make a Tag function with an ArrayBuffer, Uint8Array and Float64Array attributes in it's scope and then create new instances of it for each number... but this doesn't save you much of anything in the javascript realm. Might as well polyfill in a tag attribute/function on variables and the Number prototype if you're going to go that route of creating Tag-like structures. It won't give you the storage performance, but would at least keep the tag coupled with each number.

Because of endianess and there being no 64-bit integer array you'll need to handle the index of the LSB slightly differently. Check the endianess and set a global variable, or whatever other way you see most fit. on a little endian system:

var globalMyBuff = new ArrayBuffer(n);//n is your number of floats * 8 (8 bytes per float)
var globalMyU8Arr = new Uint8Array(globalMyBuff);
var globalMyFloat64Arr = new Float64Array(globalMyBuff);

//Load your floats into globalMyFloat64Arr

//tag a float at index when desired
function tag(index){
    //"index << 3 " is essentially the same as "index * 8", but faster
    //since it will get compiled into a shift op
    myU8Arr[index << 3] |= 1;//sets the LSB
}
//check tag at index when desired
function isTagged(index){
    //"index << 3 " is essentially the same as "index * 8", but faster
    //since it will get compiled into a shift op
    return (myU8Arr[index << 3] & 1) == 1;//checks LSB
}
like image 130
Arthur Weborg Avatar answered Nov 14 '22 21:11

Arthur Weborg