Does v8 optimize map()?

[Robert Eisele]

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!

[Ben Noordhuis]

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.

[Jakob Kummerow]

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.

[Robert Eisele]

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.

[Andreas Rossberg]

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.

[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.

[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`

}