Optimization of long lists of logical values ​​in JavaScript

Very often in web development (and in programming in general) you need to save a long list of Boolean values ​​(yes / no, true / false, checked / unchecked, and the like) as strings. For example, you want to write such data using localStorage, in a cookie, or send them in the body of an HTTP request. I had such a need hundreds of times.

Use array

We have two reasonable ways to organize logical data in an array.
The first is to store true / false values:

[false, true, true, false, false, true, true] 

The second is to store an array of zeros and ones:

 [0, 1, 1, 0, 0, 1, 1] 

Whatever method we choose, in any case, we will have to convert such an array into a string, and then convert this string back to an array when reading data. To do this, we can use the old Array#join() (or Array#toString() ) and String#split() JSON.stringify() , or the more elegant JSON.stringify() and JSON.parse() .

If we go along the JSON path, the code will be a bit shorter, although using JSON in this case is the same as cutting the bread with a chainsaw. In some browsers, this approach will have a noticeable effect on performance , and this will also worsen the support of older browsers.

The main disadvantage of using array-based strings is their size in bytes. If you choose the option of storing an array of zeros and ones, you will have to use 2 characters per value (or, to be precise, 2n-1, one separator after each value except the last):

 [0, 1, 1, 0, 0, 1, 1].toString().length // 13   7  

Thus, 523 values ​​require 1023 characters or 2 KB, because JavaScript uses UTF-16 .
')
If we keep an array of true / false values, then everything gets worse:

 [false, true, true, false, false, true, true].toString().length // 37   7  

This is 5 or 6 characters per value, from 2560 to 3072 characters at 512 values ​​(from 5 to 6 KB).
JSON.stringify() spends another 2 characters in each case on opening and closing parentheses, but its advantage is that as a result of JSON.parse() we get the original value types instead of strings.

Use string

The string allows you to save characters, since there is no need to use delimiters. For example, if we chose the digital approach and store the string '01001101010111', then we use one character per value, which is much better than the approach using arrays. You can put our values ​​into an array using String#split :

 '01001101010111'.split(''); // ['0','1','0','0','1','1','0','1','0','1','0','1','1','1'] 

Also, you can simply string.charAt(i) over characters in a string using a loop, using string.charAt(i) or even string indices (string[i]) , if you do not need to worry about the support of older browsers.

Using Bit Fields

Did you also think about binary code, considering the previous example? The concept of bit fields is quite popular in other programming languages, but not in JavaScript. In a nutshell, bitfields are used to package a set of logical values ​​into bits of a logical representation of a number. For example, we have 8 values ​​(true, false, false, true, false, true, true, false). In binary code, this will be 10010110, 150 in decimal and 96 in hex. Thus, 2 symbols are used instead of 8, saving 75% . One number in hexadecimal representation exactly corresponds to 4 bits. (Because 16 = 2 ^4. In the number system with a base of 2 ⁿ , you can pack n bits in each number.)
Thus, instead of storing an entire string and using a single character per value, we can go a smarter way and convert such a string into a hexadecimal number. How to do it? Like this:

 parseInt('10010110', 2).toString(16); //  '96' 

How to return data to a readable view? Easier nowhere:

 parseInt('96', 16).toString(2); //  '10010110' 

Now, like last time, we can loop through the values ​​using the loop and do something useful with them.

Is it possible to do even better?

Actually you can! Why convert to hexadecimal notation, which uses only 6 Latin letters out of 26? The Number#toString() method allows you to use base 36 - a number system with a base of 36 (for >= 37 we get a RangeError ), which effectively uses all letters from the Latin alphabet. Thus, we can compress 32 values ​​into 6 characters, which means a saving of 81.25% compared with the method of using a simple string. The code is still simple:

 parseInt( '1001011000', 2).toString(36); //  'go' ( '258'   ) parseInt('go', 36).toString(2); //  '1001011000' 

Many will stop at this. But the more inquisitive will say: “We also have capital letters and other symbols, we still do not use the full potential!” And they will be right. Not for nothing when opening a binary file in a text editor, you see strange characters on the screen, mixed with numbers and letters - uppercase and lowercase. Each character in the UTF-16 encoding takes 2 bytes (16 bits), which means that when using the correct compression algorithm, we will be able to save 93.75%.
The problem is that JavaScript has no built-in functionality for using such an algorithm, so the code becomes somewhat more complicated.

Packing 16 values ​​in one character

We need the String.fromCharCode method. It takes a numeric value up to 65535 and returns a character (and for values ​​greater than 65535, it returns an empty string).
We divide our string into fragments of 16 characters each.
You can do this with .match(/.{1,16}/g) . All code will look like this:

 function pack(/* string */ values) { var chunks = values.match(/.{1,16}/g), packed = ''; for (var i=0; i < chunks.length; i++) { packed += String.fromCharCode(parseInt(chunks[i], 2)); } return packed; } function unpack(/* string */ packed) { var values = ''; for (var i=0; i < packed.length; i++) { values += packed.charCodeAt(i).toString(2); } return values; } 

Not so difficult, right?
These few lines of code allow you to pack the above 512 values ​​in (drum roll) 32 characters (64 bytes) ! Much better than the original 2 KB (with storage in a simple array), isn't it?

Restrictions

Numbers in JavaScript have their limits. For the methods described here, which include intermediate conversions to numbers, the limit is set to 1023 logical values, because parseInt('1111…1111', 2) will return Infinity for more. This restriction does not apply to the latter method, because we convert blocks of bits instead of the entire string. And, of course, this restriction is not imposed on the first two methods (array and string) because they do not include the packing of values ​​at all.

"I think we went too far"

Yes, in some cases this optimization may be unnecessary. But if you need to save a bunch of logical values ​​in a limited place that only strings support, these methods will be very useful. And the optimization of something that is transmitted through the wires with great frequency is never superfluous. For example, cookies are sent in almost every request, so they should be as small as possible. Another example is multiplayer online games, for which the server’s response should be lightning-fast, otherwise playing such a game would be no fun at all.

And even if such a profound optimization is not for you, I hope that this article has given you food for thought and, perhaps, taught you something.

Transfer. Original (en): Optimizing Long Lists Of Yes / No Values ​​With JavaScript
Original author: Lea Verou