(inline) On Sun, Feb 5, 2012 at 11:36, sloisel <[email protected]> wrote:
> 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. > Well, I compared dense vs. sparse JS arrays. My point was that when you need to store only three elements in a JS array (such as the three entries in one row of a tridiagonal 10,000x10,000 matrix), putting them at indices 0, 1, 2 of an array with length 3 will result in considerably faster access once the function gets optimized than putting them at indices 5551, 5552, 5553 of an array with length 10000 of which all other indices are unused, while memory usage will be roughly the same due to the 10,000 elements array going into dictionary mode. If you know in advance which indices will be used in each row, you can easily do this trick by adding/subtracting an appropriate offset. 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! > Yes, if a fixed assumption about which indices you need in the sparse arrays is not sufficient, then implementing fully fledged sparse arrays with arbitrary indices in JS could indeed make sense (and shouldn't be a whole lot of effort). 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 > -- v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev
