JavaScript performance and a Webkit hotspot

Re:JavaScript performance and a Webkit hotspot by mraleph on Monday May 02, 2011 @05:37PM (#2507955)

Array is an appropriate datastructure for this algorithm. String is not.

    var dest = 'apple'.split('');
    var j = dest.length;
    var start = new Date();
    while (j < 100000) {
      var offs = j - 5;
      for (var i = offs; i < offs + 10; ++i)
        dest[j++] = dest[i];
    }
    dest = dest.join('');

=> 7-10ms in the latest Chrome.

[ Parent | on HN ]

Re:JavaScript performance and a Webkit hotspot by mjs on Monday May 02, 2011 @06:29PM (#2508184)

Arrays do seem to be the way to make Chrome happy, although unfortunately they're slower for everything else:

http://jsperf.com/backreference-copy

I don't see why you say an array is a more appropriate datastructure for the algorithm, though--that seems very much implementation dependent. And at the JS level, arrays support operations such as splice that strings do not, suggesting that they'd typically be implemented with a more sophisticated datastructure, and hence slower at primitive operations like index access. (Perhaps V8 notices that these expensive operations aren't actually used, and creates a fast, basic version instead.)

[ Parent | on HN ]

Re:JavaScript performance and a Webkit hotspot by mraleph on Tuesday May 03, 2011 @03:07AM (#2509256)

Array is intended to be a mutable storage with a fast random access and optimistic preallocation of backing store. String is intended to be an immutable storage. At least that's how I see these types.

I also would not expect that VM will use representation optimized for splicing --- you should _always_ expect that splicing will take O(arr.length) and use appropriate data structure when you want better time bounds.

There is a limit to how VM can optimize use of data structures. It can't magically guess that you wanted list or binary tree instead of an Array. Introducing many special cases/heuristics also leads to complexity and as a result to bugs.

[ Parent | on HN ]