Project: v8 Issues People Development process History Sign in
New issue
Advanced search Search tips
Starred by 5 users
Status: Fixed
Owner:
Closed: Sep 11
Cc:
Components:
HW: All
OS: All
Priority: 2
Type: Bug
ES5

Blocking:
issue 6807



Sign in to add a comment
String.fromcharCode.apply(undefined, uint8Array) is super-slow
Project Member Reported by danno@chromium.org, Nov 29 2012 Back to list
Firefox is faster than V8 at the following operations:

// convert a typed array to a js string
function ar2str(uint16arr) {

  // break the computation into smaller arrays to avoid browser limits on array size for .apply() call
  var res = [], i = 0, len = uint16arr.length, MAX_ELEMENTS_PER_CALL = 100000;
  while (i < len) {
    res.push(String.fromCharCode.apply(null, uint16arr.subarray(i, i += MAX_ELEMENTS_PER_CALL)));
  }
  var r = res.join("");

  return r;
}

// base64 decode
function b64_to_utf8( str ) {
      return decodeURIComponent(escape(window.atob( str )));
}

A bit of digging shows that fromCharCode for arrays of codes is implemented on the C++ side in Runtime_StringFromCharCodeArray, which is sub-optimal because it uses general-purpose code [JSArray->Get() and String->Set()]. String escaping also uses String->Set(), even though the result is guaranteed to be single-byte. The generic implementation carry a big overhead: simply replacing the JSArray->Get()s with a more specialized ElementsAccessor->Get() call improve performance on ar2str by ~20%.

 
Owner: yangguo@chromium.org
https://codereview.chromium.org/11348349/ is under review and should yield considerable performance improvements for String.fromCharCode and decodeURI* functions. encodeURI* also improve slightly, but there seems to be some potential left.
Comment 2 by habl...@google.com, Apr 29 2015
Status: Assigned
Labels: Priority-2
Cc: bmeu...@chromium.org danno@chromium.org
Components: Runtime
Labels: Performance ES5 HW-All OS-All
Checking this again, with a simple micro-benchmark:

================================================================================
// convert a typed array to a js string
function ar2str(uint16arr) {
  // break the computation into smaller arrays to avoid browser limits on array
  // size for .apply() call
  var res = [], i = 0, len = uint16arr.length, MAX_ELEMENTS_PER_CALL = 100000;
  while (i < len) {
    res.push(String.fromCharCode.apply(
        null, uint16arr.subarray(i, i += MAX_ELEMENTS_PER_CALL)));
  }
  var r = res.join('');

  return r;
}

var s = 'ABCDEFGHIJK';
var a = new Uint16Array(1024 * 1024);
for (var i = 0; i < a.length; ++i) {
  a[i] = s.charCodeAt(i % s.length);
}

for (var i = 0; i < 10; ++i) s = ar2str(a);

console.time('ar2str');
for (var i = 0; i < 100; ++i) s = ar2str(a);
console.timeEnd('ar2str');
================================================================================

Firefox Nightly on my MBP completes in 2178ms whereas Chrome Canary takes like 2841ms. Running in d8 with --runtime-call-stats shows that CreateListFromArrayLike takes up 89.73% of the time, so it's dominated by the Function#apply slow-path. The actual string operations seem to be fine(ish).
Cc: -bmeu...@chromium.org cbruni@chromium.org
Owner: bmeu...@chromium.org
Ok, here's an even better micro-benchmark to highlight the fundamental problem:

================================================================================
// Micro-benchmark to highlight the Function#apply overhead for the
// commonly used combination of String.fromCharCode and apply. See
// issue: https://bugs.chromium.org/p/v8/issues/detail?id=2435
if (typeof console === 'undefined') console = {log:print};

function stringFromCharCode(o) {
  return String.fromCharCode.apply(this, o);
}

function stringFromCodePoint(o) {
  return String.fromCodePoint.apply(this, o);
}

var TESTS = [
    stringFromCharCode,
    stringFromCodePoint
];

// Some random awesomeness generated by https://jsipsum.lunarlogic.io
var o = Uint8Array.from('Ember is a JavaScript code linter. V8 is a package manager with a JavaScript testing framework for other languages, even though JavaScript transformation toolkit which started as Gmail take advantage of functions of the two are explicitly exposed JS framework for manipulating documents based on a JavaScript engine is the server. XML-like syntax extension to dynamically access and possibly complex tasks. Animation of plug-ins. ECMAScript 3. Facade Pattern is a library for JavaScript code can detect user actions that compiles into JavaScript outside the Netscape Navigator Web form to represent the web apps. I/O, such as some kind of JavaScript engines has some kind of referencing variables from Node. NoSQL database. Mediator Pattern is a fast and MongoDB. Prototype Pattern is a Javascript NoSQL database. SJSJ is a structural framework to replace individual documentations, but that a technology for building user interfaces based on data between JavaScript engines has an application more recent browsers without having to VMs and browsing activities to be used with its code. Facebook for Node. Applications such as Dynamic HTML pages. Cordova is a social network programming language that uses factory methods. 3D and executes the goal of a list of JavaScript was influenced by JavaScript was influenced by the language a design. Flux is a language that allows you write powerful and manipulate and display dates and scripts to build system and used when its Edge browser used with run-time environments such as Dynamic Hapi is a framework to be isomorphic universal module pattern used by caching the desired DOM manipulation. Mediator Pattern is a library for other projects like Node. CORS is a pure JavaScript outside the browser-compatibility specific code translator transpiler. Modernizr is a JavaScript program could also used to pages frequently do this usage are: Loading new page. Object Model DOM is a library for developing server-side applications. Four is a function calls by the use of common tasks. Navigator Web browsers without the page interaction. Bluebird is another common use the server would typically create is a package manager with a library that HTML and HTTP requests for example, on improved data between JavaScript. Because JavaScript transformation toolkit which a term for the popularity of creating user actions quickly, making an interpreter that the browser used by the DOM is a way of deployment-ready files. JS framework based on a JavaScript. Newer and 2D graphics within any compatible web framework that can run multiple versions of deployment-ready files from development. Babel is the client side, JavaScript virtual machines VMs and notifies them automatically of the production of objects without the server.', s => s.codePointAt(0));

var n = 1e5;

function test(fn) {
  var result;
  for (var i = 0; i < n; ++i) result = fn(o);
  return result;
}

for (var j = 0; j < TESTS.length; ++j) {
  test(TESTS[j]);
}

for (var j = 0; j < TESTS.length; ++j) {
  var startTime = Date.now();
  test(TESTS[j]);
  console.log(TESTS[j].name + ':', (Date.now() - startTime), 'ms.');
}
================================================================================

Skimming through the code it seems that just adding an appropriate handler for the CreateListFromArrayLike operation in the ElementAccessor for typed arrays should already give a nice performance boost (potentially more speed-ups are possible by specializing the FunctionPrototypeApply builtin for String.fromCharCode as target and a typed array as argArray).
Status: Started
Blockedon: 6807
Project Member Comment 9 by bugdroid1@chromium.org, Sep 11
The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/f31bae0330e5787aab3e46af8e72342cb470cc3a

commit f31bae0330e5787aab3e46af8e72342cb470cc3a
Author: Benedikt Meurer <bmeurer@chromium.org>
Date: Mon Sep 11 06:21:58 2017

[builtins] Add fast-path for JSTypedArray to CreateListFromArrayLike.

It's quite common today to use Function#apply together with typed
arrays, for example to construct a String from character codes (or code
points) within a Uint8Array or Uint16Array, i.e.

  String.fromCharCode.apply(undefined, uint8array)

is seen quite often on the web. But there are other interesting cases
like

  Math.max.apply(undefined, float64array)

to compute the maximum value in a Float64Array, which is definitely not
the fastest implementation, but quite convenient and readable.
Unfortunately these cases hit the super-slow-path of the Function#apply
machinery in V8 currently, because Function#apply doesn't have any
fast-path for TypedArrays.

This CL adds a proper fast-path to CreateListFromArrayLike to the
ElementsAccessor, which can be used as long as the typed array that's
passed wasn't neutered. With this fast-path in place, the performance on
the micro-benchmark mentioned in the issue improves from

  stringFromCharCode: 6386 ms.
  stringFromCodePoint: 8752 ms.

to

  stringFromCharCode: 1932 ms.
  stringFromCodePoint: 4262 ms.

which corresponds to a 2.0x-3.3x improvement.

Bug:  v8:2435 
Change-Id: I4d39666e53644b11d5856982b005928e26f296fe
Reviewed-on: https://chromium-review.googlesource.com/657405
Reviewed-by: Yang Guo <yangguo@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#47936}
[modify] https://crrev.com/f31bae0330e5787aab3e46af8e72342cb470cc3a/src/elements.cc
[modify] https://crrev.com/f31bae0330e5787aab3e46af8e72342cb470cc3a/src/elements.h
[modify] https://crrev.com/f31bae0330e5787aab3e46af8e72342cb470cc3a/src/objects.cc
[add] https://crrev.com/f31bae0330e5787aab3e46af8e72342cb470cc3a/test/mjsunit/regress/regress-2435.js

Status: Fixed
Summary: String.fromcharCode.apply(undefined, uint8Array) is super-slow (was: Some string operations perform sub-optimally (e.g String.fromCharCode, escape))
Blockedon: -6807
Blocking: 6807
Sign in to add a comment