Re: [v8-users] Does v8 optimize map()?
Question: would a call site optimization featuring pipelines work? Several Array prototype methods always return arrays, so that's why I'm thinking a pipeline would be feasible. It's probably not trivial to implement, especially considering lazy evaluation of a specific internal reference is necessary to make it work (no extra *JS closures* necessary, though), but I think it could really speed up a lot of cases, simply by virtue of reducing GC. // Unoptimized. let B = A .map(Math.abs) .map(x => x * 10) .map(function (x) { return new Foo(this, x) }, true) .filter(foo => foo.value > 10) let C = B .map(foo => foo.get()) .forEach(x => console.log(x)) assert(C === undefined) // Optimized, see below for code stubs { @initPipeline(A) @runMap(Math.abs, false) @runMap(x => x * 10, false) @runMap(x => new Foo(x), true, true) @runFilter(foo => foo.value > 10, false) @assignResult(B) } { @initPipeline(B) @runMap(foo => foo.get(), false) @runForEach(x => console.log(x)) @assignValue(C) } assert(C === undefined) This would significantly reduce garbage collection for such chains. Here's a set of code stubs for that idea, in pseudo-JS: // Legend: // $variable - internal variable // %Func - runtime function // @value - compile-time macro/value // `output` - output code, literal code // Note that the stubs implicitly create blocks, and their arguments are // implicitly evaluated. // This is just a helper. function %CloneArray(array) { const ret = [] const len = TO_LENGTH(array.length) for (let i = 0; i < len; i++) { if (HAS_INDEX(array, i, true)) { DefineIndexedProperty(ret, i, array[i]) } } return ret } stub @initPipeline(@init) { // The initial copy should be considered the master copy. `let $ret = {got: true, value: @init}` // This is a lazy value that, when initialized, does the equivalent of the // following code: // if (!$ret.got) { // $ret.got = true // $ret.value = %CloneArray($ret.value) // } `let $ref = %Ref($ret)` `let $len = @init.length` } // Return the actual result stub @assignResult(@dest) { `if ($ret.got) {` `@dest = $ret.value` `} else {` `@dest = %CloneArray($ret.value)` `}` } // Assign the result of the last part stub @assignValue(@dest) { `@dest = $ret.value` } // This is just a helper. stub @iterate(@passed, @receiver, stub @missing, stub @exists) { if (@passed) `if (IS_UNDEFINED(@receiver)) {` `for (let $i = 0; $i < $len; $i++) {` `if (HAS_INDEX($ret.value, $i, true)) {` @missing(`$i`, `$ret.value[$i]`) `}` `}` if (@passed) { `} else {` `for (let $i = 0; $i < $len; $i++) {` `if (HAS_INDEX($ret.value, $i, true)) {` @exists(`$i`, `$ret.value[$i]`, `$receiver`) `}` `}` `}` } } stub @runMap(@f, @passed, @receiver) { `let $f = @f` if (@passed) `let $receiver = @receiver` @iterate(@passed, @receiver, (@i, @entry) => { `@entry = $f(@entry, @i, $ref)` }, (@i, @entry, $receiver) => { `@entry = %Call($f, $receiver, @entry, @i, $ref)` }) } stub @runFilter(@f, @passed, @receiver) { `let $new = []` `let $newLen = 0` `let $f = @f` if (@passed) `let $receiver = @receiver` @iterate(@passed, @receiver, (@i, @entry) => { `let $entry = @entry` `if ($f($entry, @i, $ref)) {` `$new[$newLen++] = $entry` `}` }, (@i, @entry, $receiver) => { `let $entry = @entry` `if (%Call(@f, $receiver, $entry, $i, $ref)) {` `$new[$newLen++] = $entry` `}` }) `$ret.value = $new` `$ret.got = false` `$len = $newLen` } stub @runForEach(@f, @passed, @receiver) { `let $f = @f` if (@passed) `let $receiver = @receiver` @iterate(@passed, @receiver, (@i, @entry) => { `@f(@entry, @i, $ref)` }, (@i, @entry, $receiver) => { `%Call(@f, @receiver, @entry, @i, $ref)` }) // Terminate the chain `$ret.value = undefined` `$ret.got = true` } On Friday, March 4, 2016 at 9:55:36 AM UTC-5, Jakob Kummerow wrote: > > Also ES6 is mostly a burden for JS implementations, not much of an > opportunity. We have to invest some serious effort just to *maintain* > previous > performance as we're implementing ES6, and in some cases not even that is > possible. > > On Fri, Mar 4, 2016 at 3:49 PM, 'Andreas Rossberg' via v8-users < > v8-u...@googlegroups.com > wrote: > >> There is no refcount in JS implementation, and no affordable way to >> discover aliasing dynamically. And given the gazillion intersession and >> mutation points in JavaScript's semantics, it is also practically >> impossible to analyse aliasing at compile time, in all but the most trivial >> cases. Note also that the callback itself may have or acquire references to >> the same object as A and look at them during the execution of map itself. >> >> On 4 March 2016 at 15:34, 'Robert Eisele' via v8-users < >> v8-u...@googlegroups.com > wrote: >> >>> Sounds reasonable, but wouldn't it make sense to make this patter
Re: [v8-users] Does v8 optimize map()?
Also ES6 is mostly a burden for JS implementations, not much of an opportunity. We have to invest some serious effort just to *maintain* previous performance as we're implementing ES6, and in some cases not even that is possible. On Fri, Mar 4, 2016 at 3:49 PM, 'Andreas Rossberg' via v8-users < v8-users@googlegroups.com> wrote: > There is no refcount in JS implementation, and no affordable way to > discover aliasing dynamically. And given the gazillion intersession and > mutation points in JavaScript's semantics, it is also practically > impossible to analyse aliasing at compile time, in all but the most trivial > cases. Note also that the callback itself may have or acquire references to > the same object as A and look at them during the execution of map itself. > > On 4 March 2016 at 15:34, 'Robert Eisele' via v8-users < > v8-users@googlegroups.com> wrote: > >> Sounds reasonable, but wouldn't it make sense to make this pattern >> matching based on internal references (plus refcount) instead of >> variable-name matching? That would solve the issue probably. >> >> Above that, I agree that the limiting factors are based on function calls >> if it's implemented in a naive way. However, I think ES6 gives a huge >> opportunity introducing a lot of high-level semantic information, which can >> be used to infer what the user wants and execute it much faster. So even if >> the user writes down a function call, it can be a simple loop inside of v8. >> I thought it's already done this way, when I heard ES6 became much faster >> recently. >> >> On Friday, March 4, 2016 at 11:34:51 AM UTC+1, Jakob Kummerow wrote: >>> >>> On Thu, Mar 3, 2016 at 7:48 PM, 'Robert Eisele' via v8-users < >>> v8-u...@googlegroups.com> wrote: >>> Hi, I wonder if v8 is able to optimize the pattern A = A.map(x => ~x) In this case v8 can work on the array instead of creating a new object and replacing it with the original array. >>> >>> Counter-example: >>> var A = B; >>> A = A.map(...); >>> // B must not have been modified >>> >>> You can make these as complicated as you want: >>> var B = [1, 2, 3]; >>> (function(A) { >>> A = A.map(...); // How can this .map() call know that B exists? >>> })(B); >>> >>> In general, it's pretty much impossible to tell whether there are any >>> additional references to an object somewhere; the only exception is when >>> the object has just been allocated in the current function. >>> >>> Also, on the scale of machine instructions, the overhead of a function >>> call is pretty large, which affects many of the Array builtins like .map() >>> and .forEach(). In many real usage scenarios, that might not matter, >>> because the arrays in question are small enough and/or the callbacks >>> themselves expensive enough that call overhead doesn't make much of a >>> difference. But when you micro-benchmark simple cases like "A.map(x => >>> ~x)" vs. "for (var i = 0; i < A.length; i++) { A[i] = ~A[i]; }" for a >>> couple million elements, you'll see a pretty big difference, and the >>> majority of that will be caused by the function calls. >>> >>> Is such a behavior already implemented? >>> >>> No, because it's complicated, and the benefit is somewhat unclear. We >>> might be able to optimize some patterns in the (distant) future. >>> >>> Thanks! -- -- v8-users mailing list v8-u...@googlegroups.com http://groups.google.com/group/v8-users --- You received this message because you are subscribed to the Google Groups "v8-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+u...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. >>> >>> -- >> -- >> v8-users mailing list >> v8-users@googlegroups.com >> http://groups.google.com/group/v8-users >> --- >> You received this message because you are subscribed to the Google Groups >> "v8-users" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to v8-users+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/d/optout. >> > > -- > -- > v8-users mailing list > v8-users@googlegroups.com > http://groups.google.com/group/v8-users > --- > You received this message because you are subscribed to the Google Groups > "v8-users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to v8-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- -- v8-users mailing list v8-users@googlegroups.com http://groups.google.com/group/v8-users --- You received this message because you are subscribed to the Google Groups "v8-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [v8-users] Does v8 optimize map()?
There is no refcount in JS implementation, and no affordable way to discover aliasing dynamically. And given the gazillion intersession and mutation points in JavaScript's semantics, it is also practically impossible to analyse aliasing at compile time, in all but the most trivial cases. Note also that the callback itself may have or acquire references to the same object as A and look at them during the execution of map itself. On 4 March 2016 at 15:34, 'Robert Eisele' via v8-users < v8-users@googlegroups.com> wrote: > Sounds reasonable, but wouldn't it make sense to make this pattern > matching based on internal references (plus refcount) instead of > variable-name matching? That would solve the issue probably. > > Above that, I agree that the limiting factors are based on function calls > if it's implemented in a naive way. However, I think ES6 gives a huge > opportunity introducing a lot of high-level semantic information, which can > be used to infer what the user wants and execute it much faster. So even if > the user writes down a function call, it can be a simple loop inside of v8. > I thought it's already done this way, when I heard ES6 became much faster > recently. > > On Friday, March 4, 2016 at 11:34:51 AM UTC+1, Jakob Kummerow wrote: >> >> On Thu, Mar 3, 2016 at 7:48 PM, 'Robert Eisele' via v8-users < >> v8-u...@googlegroups.com> wrote: >> >>> Hi, >>> >>> I wonder if v8 is able to optimize the pattern >>> >>> A = A.map(x => ~x) >>> >>> In this case v8 can work on the array instead of creating a new object >>> and replacing it with the original array. >>> >> >> Counter-example: >> var A = B; >> A = A.map(...); >> // B must not have been modified >> >> You can make these as complicated as you want: >> var B = [1, 2, 3]; >> (function(A) { >> A = A.map(...); // How can this .map() call know that B exists? >> })(B); >> >> In general, it's pretty much impossible to tell whether there are any >> additional references to an object somewhere; the only exception is when >> the object has just been allocated in the current function. >> >> Also, on the scale of machine instructions, the overhead of a function >> call is pretty large, which affects many of the Array builtins like .map() >> and .forEach(). In many real usage scenarios, that might not matter, >> because the arrays in question are small enough and/or the callbacks >> themselves expensive enough that call overhead doesn't make much of a >> difference. But when you micro-benchmark simple cases like "A.map(x => >> ~x)" vs. "for (var i = 0; i < A.length; i++) { A[i] = ~A[i]; }" for a >> couple million elements, you'll see a pretty big difference, and the >> majority of that will be caused by the function calls. >> >> >>> Is such a behavior already implemented? >>> >> >> No, because it's complicated, and the benefit is somewhat unclear. We >> might be able to optimize some patterns in the (distant) future. >> >> >>> Thanks! >>> >>> -- >>> -- >>> v8-users mailing list >>> v8-u...@googlegroups.com >>> http://groups.google.com/group/v8-users >>> --- >>> You received this message because you are subscribed to the Google >>> Groups "v8-users" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to v8-users+u...@googlegroups.com. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- > -- > v8-users mailing list > v8-users@googlegroups.com > http://groups.google.com/group/v8-users > --- > You received this message because you are subscribed to the Google Groups > "v8-users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to v8-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- -- v8-users mailing list v8-users@googlegroups.com http://groups.google.com/group/v8-users --- You received this message because you are subscribed to the Google Groups "v8-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [v8-users] Does v8 optimize map()?
Sounds reasonable, but wouldn't it make sense to make this pattern matching based on internal references (plus refcount) instead of variable-name matching? That would solve the issue probably. Above that, I agree that the limiting factors are based on function calls if it's implemented in a naive way. However, I think ES6 gives a huge opportunity introducing a lot of high-level semantic information, which can be used to infer what the user wants and execute it much faster. So even if the user writes down a function call, it can be a simple loop inside of v8. I thought it's already done this way, when I heard ES6 became much faster recently. On Friday, March 4, 2016 at 11:34:51 AM UTC+1, Jakob Kummerow wrote: > > On Thu, Mar 3, 2016 at 7:48 PM, 'Robert Eisele' via v8-users < > v8-u...@googlegroups.com > wrote: > >> Hi, >> >> I wonder if v8 is able to optimize the pattern >> >> A = A.map(x => ~x) >> >> In this case v8 can work on the array instead of creating a new object >> and replacing it with the original array. >> > > Counter-example: > var A = B; > A = A.map(...); > // B must not have been modified > > You can make these as complicated as you want: > var B = [1, 2, 3]; > (function(A) { > A = A.map(...); // How can this .map() call know that B exists? > })(B); > > In general, it's pretty much impossible to tell whether there are any > additional references to an object somewhere; the only exception is when > the object has just been allocated in the current function. > > Also, on the scale of machine instructions, the overhead of a function > call is pretty large, which affects many of the Array builtins like .map() > and .forEach(). In many real usage scenarios, that might not matter, > because the arrays in question are small enough and/or the callbacks > themselves expensive enough that call overhead doesn't make much of a > difference. But when you micro-benchmark simple cases like "A.map(x => ~x)" > vs. "for (var i = 0; i < A.length; i++) { A[i] = ~A[i]; }" for a couple > million elements, you'll see a pretty big difference, and the majority of > that will be caused by the function calls. > > >> Is such a behavior already implemented? >> > > No, because it's complicated, and the benefit is somewhat unclear. We > might be able to optimize some patterns in the (distant) future. > > >> Thanks! >> >> -- >> -- >> v8-users mailing list >> v8-u...@googlegroups.com >> http://groups.google.com/group/v8-users >> --- >> You received this message because you are subscribed to the Google Groups >> "v8-users" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to v8-users+u...@googlegroups.com . >> For more options, visit https://groups.google.com/d/optout. >> > > -- -- v8-users mailing list v8-users@googlegroups.com http://groups.google.com/group/v8-users --- You received this message because you are subscribed to the Google Groups "v8-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [v8-users] Does v8 optimize map()?
On Thu, Mar 3, 2016 at 7:48 PM, 'Robert Eisele' via v8-users < v8-users@googlegroups.com> wrote: > Hi, > > I wonder if v8 is able to optimize the pattern > > A = A.map(x => ~x) > > In this case v8 can work on the array instead of creating a new object and > replacing it with the original array. > Counter-example: var A = B; A = A.map(...); // B must not have been modified You can make these as complicated as you want: var B = [1, 2, 3]; (function(A) { A = A.map(...); // How can this .map() call know that B exists? })(B); In general, it's pretty much impossible to tell whether there are any additional references to an object somewhere; the only exception is when the object has just been allocated in the current function. Also, on the scale of machine instructions, the overhead of a function call is pretty large, which affects many of the Array builtins like .map() and .forEach(). In many real usage scenarios, that might not matter, because the arrays in question are small enough and/or the callbacks themselves expensive enough that call overhead doesn't make much of a difference. But when you micro-benchmark simple cases like "A.map(x => ~x)" vs. "for (var i = 0; i < A.length; i++) { A[i] = ~A[i]; }" for a couple million elements, you'll see a pretty big difference, and the majority of that will be caused by the function calls. > Is such a behavior already implemented? > No, because it's complicated, and the benefit is somewhat unclear. We might be able to optimize some patterns in the (distant) future. > Thanks! > > -- > -- > v8-users mailing list > v8-users@googlegroups.com > http://groups.google.com/group/v8-users > --- > You received this message because you are subscribed to the Google Groups > "v8-users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to v8-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- -- v8-users mailing list v8-users@googlegroups.com http://groups.google.com/group/v8-users --- You received this message because you are subscribed to the Google Groups "v8-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [v8-users] Does v8 optimize map()?
On Thu, Mar 3, 2016 at 7:48 PM, 'Robert Eisele' via v8-users wrote: > Hi, > > I wonder if v8 is able to optimize the pattern > > A = A.map(x => ~x) > > In this case v8 can work on the array instead of creating a new object and > replacing it with the original array. Is such a behavior already > implemented? > > Thanks! I'm fairly sure it's not. Array#map() is currently implemented as a simple function in src/js/array.js, with no attempts to pattern-match call sites like V8 does for Math functions. -- -- v8-users mailing list v8-users@googlegroups.com http://groups.google.com/group/v8-users --- You received this message because you are subscribed to the Google Groups "v8-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[v8-users] Does v8 optimize map()?
Hi, I wonder if v8 is able to optimize the pattern A = A.map(x => ~x) In this case v8 can work on the array instead of creating a new object and replacing it with the original array. Is such a behavior already implemented? Thanks! -- -- v8-users mailing list v8-users@googlegroups.com http://groups.google.com/group/v8-users --- You received this message because you are subscribed to the Google Groups "v8-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.