Basically, the issue you're hitting is the fact that JS arrays a way more
complicated objects than C arrays. This is a necessary consequence of the
specifications of these two languages. To be more specific, I can see two
reasons why your code runs slow:
1.) As you've guessed yourself in the comment section of the benchmark,
sparsely filled JS arrays are represented as dictionaries (a.k.a. hashmaps)
in memory. The reason is that it's completely legal JavaScript to create an
empty array and then use only the billionth element of it -- it would be a
huge waste of memory if a billion elements were actually allocated for
that. On the other hand, fast access to array elements is only possible
when the index can be used as memory offset, i.e. when the array is stored
as an actual (C-like) array in memory. Every JS engine implementation will
have some heuristics internally that decide when to use one representation
over the other.
2.) V8's optimizing compiler currently has no support for the "for...in"
statement, meaning any function containing a for...in loop cannot be
optimized. This, again, is due to the JS specification making it pretty
complicated to enumerate all properties of an object.
So, here are a few suggestions how to make your code faster:
- Use your arrays in a dense fashion by making index calculations yourself,
just as you would in C (i.e., something along the lines of "var array = new
Array(len); for (var i = n; i < n+len; i++) {do_something_with(array[i-n]);
}"). As an alternative, use typed arrays (Float64Array and friends), as
these will always allocate array-like memory (they don't have a dictionary
mode).
- When you create an array, always specify its size, thereby avoiding
out-of-bounds accesses (which are legal, but slow).
- Don't use for...in loops. To iterate over arrays, use "for(i=0; i <
array.length; i++) {...}" instead.
On Sat, Feb 4, 2012 at 18:17, sloisel <[email protected]> wrote:
> Dear v8 contributors,
>
> I hope that I found the right place to send my inquiry -- this is the
> group that was linked from the main v8 page.
>
> I have discovered a poor performance case for v8 as well as Firefox
> and the other browsers. My intuition is that this poor performance is
> caused by the use of lots of moderately sparse Arrays. I discovered
> this while implementing standard numerical analysis routines. For most
> of my routines, I can get 50-300MFLOPS (millions of floating points
> instructions per second), which is not too bad (C would yield some
> GFLOPS). When I started implementing sparse linear algebra, the use of
> sparse Arrays was natural. However, I found that, at least when the
> sparse Arrays get a little bit dense, the FLOP rate is only about
> 1-2MFLOPS.
>
> In order to show this behavior in a self-contained example, I've made
> a self-contained benchmark here:
> http://jsperf.com/sparse-array-performance
>
> What do you think?
>
> Thanks,
>
> Sébastien Loisel
>
> --
> v8-dev mailing list
> [email protected]
> http://groups.google.com/group/v8-dev
>
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
