Performance Optimization of Arrays - Part II
Hello Friends,
Hope you have read part I of this topic which I posted few days ago. If not then I would suggest going through that first as this post is just a continuation of that one.
So coming to the point, here is the second reason -
2. “JavaScript arrays are sparse arrays” – JavaScript allows arrays to be sparse therefore, when you write arrayObj = new Array(100); unlike C runtime, JScript doesn’t allocate any slot/memory for those 100 entries up front. It allocates slot for an index only when an index is to be populated with a value, for example…
arrayObj = new Array(100);
arrayObj[10] = 10;
In this example, the array size is 100, but in the actual physical memory there is only one slot allocated for this array. Remaining 99 slots don’t exist at all.
Wondering how this factor contributes to the bad performance? Not allocating memory for all the slots up front is good design. Isn’t it?
Well, JScript always assumed that all arrays are sparse. So even if you had a fully dense array in your code, JScript runtime would treat it like a sparse array only. So if you are going to do a pop() operation on a dense JScript array, JScript just won’t go and delete the last indexed entry and update the length attribute. It does something which is extremely performant for sparse arrays, but equally under-performant for dense arrays. Let‘s see what it is all about.
Internally, for each Array object, JScript runtime maintains a table (different from HashTable, let’s call it TrackerTable) which is nothing but a list of pointers to actual entries in the hash table. So if you just create an Array Object of size 100, and add 10 entries (indexed or named), the TrackerTable will have 10 pointers pointing to actual entries in the hash table. Let’s take one simple example…
arrayObj = new Array(100);
arrayObj[10] = 10;
arrayObj.length = 90;
In this example, I just create an Array of size 100, and populated index 10. Next I reduce length of array to 90. Since the length has been reduced, entries from 90 to 99 have to be deleted. The ideal thing to do would be to delete <key, value> pair from hash table for key = 90 to 99. That means 10 operations on Hash table. JScript is smart here and saves 9 out of 10 operations.
What JScript actually does is that it goes to the TrackerTable, iterates through it, for every entry it checks if it falls between deletion range (90-99 in this case), if yes then delete it. In above example, TrackerTable had only one entry. So instead of 10 operations on hash table, JScript does only one iteration and performs better.
However what if the array was a dense array and all the indexed entries from 0 to 100 were populated? Unfortunately in this case too, JScript would follow the same logic. Therefore it would do 100 iterations over TrackerTable and end up doing 90 more operations.
How it was fixed– As I said in the last post, in IE8 JScript we have the mechanism in place to decide whether an array is a sparse or dense. So we have changed the implementation to take sparse path only when the array is actually sparse. That means for operations on dense arrays, we don’t use TrackerTable anymore. We directly go to the right storage and get the things done in fast manner.
So this is all I had to tell about array improvements. Hope you got an idea of what was/is happening under the hood? If not, do leave a note and I would try to address that. And yes, I have lot many interesting things to share with you all, so keep checking this blog.
-JP