Array#join - better to special case for Array/etc.?

[Isiah Meadows]

I profiled various native methods, comparing them to equivalent polyfills and special-cased ones. I compared the following functions:

• Math.abs(x)
• Array.prototype.pop()
• Math.ceil(x)
• Array.prototype.join(sep)

I found the following things from testing in various browsers:

• Math.abs(x)
• Webkit is about twice as fast as V8 in the native implementation.
• Webkit's performance in the rest is on par with V8's.
• Similar performance between type-ignorant polyfills and native implementation (on all browsers)
• Array.prototype.pop()
• Firefox clearly hasn't optimized the special case for arrays natively.
• JS polyfills are insanely slow, with type checking making little difference.
• Math.ceil(x)
• JS polyfills significantly slower, but that is explainable with the better bitwise ability with floats/doubles/etc. in C/C++.
• Mine does it without branching, but a potentially better way is to decrement if less than 0 and truncate it.
• Webkit is a little faster, but not a lot.
• Array.prototype.join(sep)
• JS standards polyfill rather slow
• JS polyfill assuming an array is over twice as fast as the native implementation (If it optimizes for this case, it should structurally resemble a Java Object[] internally).
• This really needs a special case (or better special case) for Arrays.

I can't a patch for this yet, because of current CLA confusion (off-topic), but it should be relatively simple.

[Jacob G]

You should take a look at this too: https://github.com/codemix/fast.js - Functions written in JS are faster than the native functions. Is there something to be done?

[Isiah Meadows]

That library rarely does type checking. This contributes a lot of
speed to their overall algorithm. If you look at my benchmarks,
clearly, removing type checking helps, but it doesn't help for all
applications. Another thing is that they use 99% C-style for loops
with numerical indices instead of for-in loops (which always require
some type checking because they work with all Objects and Arrays). The
code actually resembles Asm.js in its heavy use of numbers.

Array#[push|pop]() is easily optimized for array instances, because
they each compile down to a single common assembly instruction. Also,
in the case of Array#pop(), if the value isn't used, then it can
simply pop to the same register over and over again, making it easily
surpass 100 million operations per second if properly optimized.

Back to the initial topic, my main request isn't to remove
type-checking, but to make a special case (or more optimal case) for
Arrays in Array#join(), and especially if it is an array of Strings.
This is a relatively fast snippet of C++ code:

std::string join(std::string* array, int len) {
std::string str = '';
while (len) {
str += *(array + --len);
}
return str;
}

The Fast library could speed up some of their methods easily by
reversing the iteration order for some methods (and I'm about to draft
a quick patch to it).

> --
> --
> v8-users mailing list
> v8-u...@googlegroups.com
> http://groups.google.com/group/v8-users
> ---
> You received this message because you are subscribed to a topic in the
> Google Groups "v8-users" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/v8-users/FoK9X52cIDs/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> v8-users+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.



--
Isiah Meadows

[Vyacheslav Egorov]

> Array#[push|pop]() is easily optimized for array instances, because
> they each compile down to a single common assembly instruction

Last time I checked Intel manual it did not have jsapop/jsapush instructions.

You need to do a bit of checks (length underflow, lack holes in the array, etc). So a single instruction is unlikely (though potentially possible in a loop under certain conditions --- but those conditions require sophisticated optimizations to achieve, e.g. you need to hoist bounds checks and sink update of length out of the loop, etc.).

> but to make a special case (or more optimal case) for Arrays in Array#join(), and especially if it is an array of Strings.

There is such case. It's called _FastAsciiArrayJoin.

> This is a relatively fast snippet of C++ code:

This might have O(n^2) runtime complexity or waste memory for result (if library does capacity doubling on appends, which is common strategy) depending on how your C++ library reserves capacity for std::string. 

std::string join(const std::vector<std::string>& array) {

  size_t total_length = 0;

  for (auto& s : array) total_length += s.length();

  std::string str;

  str.reserve(total_length);

  for (auto& s : array) str.append(s);

  return str;

}

which is btw exactly what _FastAsciiArrayJoin attempts to do.

Vyacheslav Egorov

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.

[Isiah Meadows]

On Mon, Sep 1, 2014 at 9:12 AM, Vyacheslav Egorov <veg...@chromium.org> wrote:
>> Array#[push|pop]() is easily optimized for array instances, because
>> they each compile down to a single common assembly instruction
>
> Last time I checked Intel manual it did not have jsapop/jsapush
> instructions.
>
> You need to do a bit of checks (length underflow, lack holes in the array,
> etc). So a single instruction is unlikely (though potentially possible in a
> loop under certain conditions --- but those conditions require sophisticated
> optimizations to achieve, e.g. you need to hoist bounds checks and sink
> update of length out of the loop, etc.).

I'll recind that statement. It still is easily optimizable to a low
level. An array of numbers can
be compiled eventually to push/pop (pushf/popf for floats).

>
>> but to make a special case (or more optimal case) for Arrays in
>> Array#join(), and especially if it is an array of Strings.
>
> There is such case. It's called _FastAsciiArrayJoin.

Is there a reason why the special case is faster in JS than native
(even taking into account coercion)?

>
>> This is a relatively fast snippet of C++ code:
>
> This might have O(n^2) runtime complexity or waste memory for result (if
> library does capacity doubling on appends, which is common strategy)
> depending on how your C++ library reserves capacity for std::string.
>
> std::string join(const std::vector<std::string>& array) {
> size_t total_length = 0;
> for (auto& s : array) total_length += s.length();
>
> std::string str;
> str.reserve(total_length);
> for (auto& s : array) str.append(s);
> return str;
> }

Amend that to "simple". I'm not usually coding in C++.

[Toon Verwaest]

I'll recind that statement. It still is easily optimizable to a low
level. An array of numbers can
be compiled eventually to push/pop (pushf/popf for floats).

Even though technically possible, I'm willing to bet it's going to take you a *really* *really* long time to get to exactly one instruction. And in that case you'll probably only be able to apply it to 1% of the cases (popping from sparse arrays; arrays with holes, potentially with getters installed on the prototype chain; non-JSArrays; ...).

So no, V8 never generates code that good. And we are already pretty clever at specializing.

[Vyacheslav Egorov]

> It still is easily optimizable to a low
> level. An array of numbers can
> be compiled eventually to push/pop (pushf/popf for floats).

Which architecture are we talking about here? x86? pushf pushes flags register, not floats.

All of the above (push/pop) have a fixed register ESP --- which means that either your array somehow ended up on the top of the stack or you pointed ESP into your array. Neither of this makes much sense. 

> Is there a reason why the special case is faster in JS than native

> (even taking into account coercion)?

When you say "faster" --- you probably mean some specific benchmark that you wrote. If you share this benchmark, I can approximately tell you why you see what you see there.

I can tell you that on average it is expected to be faster as it is implemented natively.

Common mistake for measuring these things is that join() is compared against `+` --- where is `+` does not actually produce precisely the same result as join() - `+` creates a cons-string and thus lazyly delays the cost of actual character copying to the place where `+` result is used in a way that requires flattening. join() produces flattened string from the start.

Take for example a look at: http://jsperf.com/join-faster-than-concat

Vyacheslav Egorov