Dear Jakob, Thanks for your reply.
The main point that I took from your answer is that v8 has no optimization for "for...in". That does explain what I am seeing. The other elements of your reply suggest you may be misappreciating the benchmark. 1) You suggest that I'm comparing JS sparse arrays to C dense arrays. I am not. I am comparing JS sparse arrays to C sparse arrays. 2) You suggest to use a dense loop. The benchmark you are looking at is a sparse LU decomposition. Here's a chart summarizing the performance of dense vs sparse treatments in C: 1,000x1,000 2d Laplacian matrix: Dense FLOPS: 1,000,000,000. Running time: fraction of a second. Storage space: 8 megabytes. Sparse FLOPS: 1,000,000. Running time: 1 millisecond? Storage space: ~300 kilobytes. 10,000x10,000 2d Lacplacian matrix: Dense FLOPS: 1,000,000,000,000. Running time: half an hour? Storage space: 800 megabytes. Sparse FLOPS: 100,000,000. Running time: milliseconds. Storage space: ~10 megabytes. The algorithms you're looking at really do use sparse data structures in an essential way. These algorithms, when implemented in C using sparse data structures in C, run about 500 times faster than v8's JS engine, which is unlike the other performance I have observed for other algorithms. The performance is so poor that what might make sense is to reimplement sparse Arrays in pure javascript! Thanks, Sébastien Loisel On Feb 4, 11:09 pm, Jakob Kummerow <[email protected]> wrote: > 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
