Packhx

Packhx is a bit packed array abstract implementation for Haxe. It is considered alpha level, use at your own risk!

Bit packing is useful in situations where you need an array of integers, but do not need to use the entire maximum integer value range ( around 4 billion).

By specifying a new max size, Packhx can use a given Int32 array cell for more than one value. In the example below, we are storing the 9 bit packed values i{0-9} in the 32 bit array cell values b{0-2}. Note that values can overlap, and that the first cell is used to contain Packhx-specific metadata.

b0

b1

b2

b3

...

(metadata)

i0

i1

i2

i3

i4

i5

i6

i7

i8

...

Packhx stores positive or negative integers. The sign bit is always the highest bit of the integer, just as it is for 32 and 64 bit integers. However, Packhx also uses the lowest bit to store the null status of the value. For instance, the table below shows how Packhx stores the value -2 with a bit size of 5. (S = signed bit position, B = normal bit position, N = null bit position).

S	B	B	B	N
1	1	1	0	1

To create packed IntArray, you must specify the maximum bit size you want. Keep in mind that you must include the bits for the sign and null status.

var parr = new packhx.IntArray(5);

You can iterate over it normally :

for (p in parr){ trace(p); }

You can set and access the packed values using normal array accessors :

parr[3] = 4;
trace(parr[3]);

If you're curious, you can access the raw underlying array value :

trace(parr.dump());
//[44,65536]

The packed array value is often much smaller than the equivalent native array:

   var k = new IntArray(12); // 12 bit maximum number
   var l = new Array<Int>();
   for (i in 0...1000){ l[i] = Std.int(Math.random() * 500); k[i] = l[i]; }
   trace(l.length); // size is 1000
   trace(k.dump().length); // size is 377... ***>60% reduction!***

The total array size savings will be roughly equivalent to the ratio of your bit size argument to 32 bits, minus a small amount of space used for packhx internals.

You can use a packed int array whenever you need a normal int array. The Haxe abstract will convert it for you (note that this will make a copy an incur some overhead. Consider using the IntArray iterator method instead.)

   var f = function(iarr : Array<Int>){
      trace(Std.is(iarr, Array));
   }
   f(parr); // call an array argument function with an IntArray

Caveats

Packhx supports Haxe 3.1.3 and up.

Acknowledgements

• I used some markdown table and examples from Gregory Pakosz's PackedArray library.
• I learned about some basic performance characteristics from Daniel Lemire's recent blog post on the subject.