User:Becky Pippen/Memory Efficiency
Information Content and Memory Efficiency
For a refresher on relevant information theory, see this tutorial.
It's useful to understand the "information content" of data so that you can calculate the theoretical minimum number of bits needed to store the data. Typically it's the logarithm base two of the total number of possible values the data can have. Here are some examples:
- coin toss: log2(2) = 1 bit per toss
- 6-sided die toss: log2(6) = 2.585 bits per toss
- integers 0 through 100: log2(101) = 6.66 bits each
- 32-bit integers, non-negative values: log2(2147483648) = 31 bits each
- 32-bit integers, all possible values: log2(4294967296) = 32 bits each
The actual memory space used by various LSL data types can be found here:
The memory efficiency is simply the information content divided by the actual memory used. Here are some examples:
Example #1 - ASCII text
In classic LSO (the old LSL compiler), it takes one byte of memory (8 bits) to hold one ASCII character (7 bits) for an efficieny of 7/8 = 88%. In Mono, it takes two bytes (16 bits) to hold each character for an efficiency of 7/16 = 44%.
Example #2 - Vectors in a global list
The information content of a vector is the equivalent of three floats, or 3 * 32 bits = 96 bits per vector. A list in Mono consumes 224 bits for each vector element for an efficiency of 96 / 224 = 43%. Note that if you only need to store a smaller range of values in each vector component, the information content will be smaller. For example, suppose you need to store a color vector with two decimal digits of accuracy for each component. In other words, instead of precision like <0.567876, 0.198273, 0.993656>, it's sufficient for your purposes if the data gets rounded off to <0.57, 0.20, 0.99>. In that case, each of the three components can take one of 101 possible values (0.00 through 1.00 with 0.01 resolution), and the information content is then 3 * log2(101) = 20 bits. If stored in a list, the efficiency would drop to 20 / 224 = 9%. Ouch.
Example #3 - UUIDs in a global list
The information content of a UUID is 128 bits. In a global list in Mono, each key takes up to 106 bytes (848 bits) for an efficiency of 128 / 848 = 15%. Suppose your script needs to store up to 1000 avatar UUIDs in a global list. That's going to use up 1000*106 bytes = 106,000 bytes, more than the memory available to a single Mono script. However, since each UUID contains only 16 bytes (128 bits) of information, the theoretical minimum memory requirement would be 1000*16 = 16000 bytes, well within the capacity of a Mono script. Now all we need is to find some way to get closer to that theoretical minimum. For some suggestions, see this checklist of things you can do.