Search code examples
javascriptarraysv8

Could someone help describe the two types of array storage in Javascript?

I'm reading this article about V8 on HTML5Rocks. The article is old but I understand almost none of it and it bothers me. I'm taking this 1 step at a time but could someone help me with the Arrays section?

The article states:

Arrays

In order to handle large and sparse arrays, there are two types of array storage internally:

  • Fast Elements: linear storage for compact key sets

  • Dictionary Elements: hash table storage otherwise

It's best not to cause the array storage to flip from one type to another.

Question:

What would a Fast Elements linear storage array look like?

What would a Dictionary Elements hash table array look like?

For prevention purposes, how would I "flip from one type to another"?

Solution

  • I will go a little other way round.

    2) What would Dictionary Elements hash table Array look like?

    A JavaScript object is a map from string to values. e.g.

    var obj = {
  "name": "Sherlock Holmes",
  "address": "221B Baker Street"
}

    V8 uses hash tables to represent objects unless using an optimized representation for special cases. This is much like a dictionary uses (words, meaning) pair.

    Now, this hash table access is slow because initially all the keys and values in a hash table are undefined. On inserting a new pair, a hash is computed and the pair inserted at the insertion index. If there's already a key at that index, attempt to insert at next one and so on.

    1) What would Fast Elements Linear storage Array look like?

    In V8, an element is a property whose key is a non-negative integer (0, 1, 2, ...) i.e. a simple linear array whose properties can be accessed via a numerical index.

    Fast elements are stored in a contiguous array. e.g.

    var arr = [1, 2, 3];

    They are a special case that is optimised for faster access as the index is already known and not to be computed.

    3) For prevention purposes, How would I flip from one type to another?

    For fast element, if you assign an index that's way past the end of the elements array, V8 may downgrade the elements to dictionary mode.

    Reference: http://jayconrod.com/posts/52/a-tour-of-v8-object-representation