Array Internals (JS Centric)
Array’s, are mine favourite data structure at least.
Until, you talk about
-
issues with visualizing 0 indexes
-
sorting array, searching array, permutations within array
-
making arrays complex
But at the core, they are simple.
A contiguous space in memory.
1Index → 0 1 2 3 ...
2Address → 0x7FFE1000 0x7FFE1004 0x7FFE1008 0x7FFE100C ...
3Value → 99 76 42 13 ...
So do we need to complicate it?
At first let’s agree, Javascript arrays are weird, they are some sort of resizable lists cause arrays are supposed to have a fixed size.
1Traditional Fixed Array
2
3Index -> 0 1 2
4 +-----+-----+-----+
5Value -> | A | B | C |
6 +-----+-----+-----+
7
8Capacity: Fixed (3)
9Cannot expand
10
11
12JavaScript Dynamic Array
13
14Index -> 0 1 2 3 4
15 +-----+-----+-----+-----+-----+
16Value -> | A | B | C | D | E |
17 +-----+-----+-----+-----+-----+
18
19Capacity: Dynamic
20Can grow or shrink (push / pop)
Feelin like Hero
Can we get into the boots of JS creators tho we aren’t that good, Let’s try
Here, our array starts and points at some starting element, index 0 let’s say
1Index → << 0 >> 1 2 3 ...
2Address → 0x7FFE1000 0x7FFE1004 0x7FFE1008 0x7FFE100C ...
3Value → 99 76 42 13 ...
Every element within a traditional array occupies a specific size. Like numbers can have 4 bytes and strings might have, idk more than 8 bytes.
This size is used as an offset and it allows traversing to that element so easy.
Target_Address = Start_Address + ( Index Offset)
This is why arrays have constant time read and write.
Optimizing Different Arrays
You can not though insert or remove an element within traditional arrays, you’ll have to clone and create a new array for it.
1Inserting X at Index 1 (Traditional Arrays)
2-------------------------------------------
3
4Before
5
6Index → 0 1 2
7 +-----+-----+-----+
8Value → | A | B | C |
9 +-----+-----+-----+
10
11Attempt to insert "X" at index 1
12
13After (New Array Cloned)
14
15Index → 0 1 2 3
16 +-----+-----+-----+-----+
17Value → | A | X | B | C |
18 +-----+-----+-----+-----+
19
20Traditional arrays cannot expand in place.
21A new array had to be created.
Now, how Javascript engines manage to have dynamic arrays and how it decides the offset (size). I guess it will be bad to have a large offset if you are just storing integers.
Perhaps yes, and to mitigate this JS engine classifies arrays based on elements
-
SMI (Small Integers) If your arrays just carry numbers, the engine makes the offset suitable for integers.
-
Double (Floating Point Numbers) If any element in your array consists a floating point number, the engine optimises it to deal with them.
-
Packed Elements Arrays that carry complex data types like Strings and Objects.
So, suppose our simple array [99,76] was chilling on its own.
It will be a SMI array, but let’s push a string within it.
Now our array is [99,76,“push”], I don’t had to upgrade the array manually, the engine did it for me and now I have an Packed Elements Array.
1SMI Array Packed Elements Array
2+-------+-------+ +-------+-------+---------+
3| 99 | 76 | | 99 | 76 | "push" |
4+-------+-------+ +-------+-------+---------+
1Clone SMI Array → Create Packed Array → Copy Elements
2
3Old Array (SMI):
4 +-------+-------+
5 | 99 | 76 |
6 +-------+-------+
7
8New Array (Packed):
9 +-------+-------+---------+
10 | 99 | 76 | "push" |
11 +-------+-------+---------+
They cloned previous array,
Created new array with new offset (size per element).
Inserted elements into new array.
One thing to know, if I pop the string, it won’t downgrade the array, why would it clone the array again?
1Before Pop After Pop
2+-------+-------+---------+ +-------+-------+---------+
3| 99 | 76 | "push" | → | 99 | 76 | empty |
4+-------+-------+---------+ +-------+-------+---------+
5
6Packed Elements Still Packed Elements
There is a way to have traditional arrays in JS, something with ArrayBuffer.
1const buffer = new ArrayBuffer(16);
2const int32View = new Int32Array(buffer);
3int32View[0] = 42;
4int32View[1] = 100;
Another type of arrays JS engines optimise is for holey arrays.
Suppose you make an array, it looks something like [“hi”].
And for some reason you decide to do arr[92637937] = “bye”
1Dense Array
2
3Index → 0 1 2
4 +-------+-------+-------+
5Value → | "hi" | "yo" | "ok" |
6 +-------+-------+-------+
7
8
9Holey Array
10
11Index → 0 1 2 3 ... 999
12 +-------+-------+-------+-------+---+-------+
13Value → | "hi" | empty | empty | empty |...| "bye" |
14 +-------+-------+-------+-------+---+-------+
Now, your array consists of holes, should the engine carry that whole empty space within it.
It would be bad and the engines optimize for it, we just need to know that holes within array are bad.