Re: [v8-users] Does v8 optimize map()?

[Isiah Meadows]

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 

Re: [v8-users] Does v8 optimize map()?

[Jakob Kummerow]

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()?

['Robert Eisele' via v8-users]

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()?

[Jakob Kummerow]

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()?

[Ben Noordhuis]

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.