TIL Rotations and strings are effective ways of storing integers in script memory

[Frionil Fang]

In my pursuit of effective ways of storing and randomly accessing 8-bit binary data, I realized that even if packing 4 bytes per integer is quick, simple and pretty speedy, it has absolutely awful overhead -- a single integer in a list costs 16 bytes, 12 bytes of overhead+4 bytes of payload, giving you a ratio of 4/16 = 25% -- and the speed starts to crumble rather non-linearly as the lists get longer, necessitating making several smaller lists, which in turn increases the overhead. After checking packing integers into roughly every datatype without using any super fancy tricks, i.e. no base96 encoding or whatever since I'm not concerned only for the memory use but also complexity and performance, I came to the following conclusions:

1) If you want pure speed, use integers, but the memory cost is huge from all the overhead. List performance may become an issue since long lists might be required to pack enough bytes. If you want ABSOLUTE speed, don't even pack the bytes and just store them as integers, but oh boy that's wasteful.

2) If you want pure memory, use strings; since the script memory representation is utf-16, a dead simple way of packing bytes is just llChar(0x100+bytevalue), and reverse for llOrd, for a ratio of 1/2 = 50%, much better than integers. The downside is that strings start slightly faster than lists, but their speed advantage seems to fall apart quickly; llOrd on a long string has a whole order of magnitude slower operation than a list seek, and modifying is no better.

3) If you want a balance of both, use rotations a.k.a. quaternions. The overhead per list entry stays the same as for integers but you can pack in 3 times more data per entry! A float can hold a 24-bit* integer i.e. 3 bytes without losing precision, which means a quaternion can hold 12 bytes of payload, while its list entry use is only 12+16 = 28 bytes, for a ratio of 12/28 = 43%, closer to strings than integers in efficiency, with somewhat slower performance than pure integers for reading (but integer reading is already so fast that it's probably not a bottleneck, and is still much faster than strings), but interestingly write performance is better due to the list lengths needed to store the same number of entries being lower. The logic needed for the component separation and byte packing is not too complicated, even if by far the most complex of the 3 considerations listed here.

4) Floats, vectors and keys are not useful. Keys end up using more memory than the equivalent string representation (I can't quite figure that one out why), floats are just worse integers, vectors are just worse quaternions.

*) Actually 25 bits since the sign bit is separate, but making use of it for just packing bytes adds too much complexity to be worth it. Yes, you could also use custom functions to convert a 32-bit integer into a float with identical representation and back, but again... too much additional complexity for me.

Of course for getting things to linkset data, there's a whole new set of considerations since you're limited to utf-8 strings.

TL;DR: using quaternion lists to store byte arrays is not normal, but in LSL it is.

[Quistess Alpha]

5 minutes ago, Frionil Fang said:

Keys end up using more memory than the equivalent string representation (I can't quite figure that one out why)

The story I've heard is keys store the 128 bits they represent when actually representing a key, in addition to their string representation.

Thanks for the testing and writeup!