buffer: optimize hex parsing. by chjj · Pull Request #7602 · nodejs/node · GitHub

Checklist

make -j4 test (UNIX), or vcbuild test nosign (Windows) passes
tests and/or benchmarks are included
commit message follows commit guidelines

Affected core subsystem(s)

buffer

Description of change

Hex parsing can be a slight bottle-neck for anyone who does Buffer.from(str, 'hex') or buf.write(str, 'hex') frequently. 6 potential comparisons as well as some arithmetic per character wasn't cutting it for me. A single pointer access per character is a lot faster (results in a near 2x speedup on 1kb hex strings).

# Current HEAD:
$ ./out/Release/node benchmark/buffers/buffer-hex.js
buffers/buffer-hex.js len="0" n="10000000": 6006950.59809
buffers/buffer-hex.js len="1" n="10000000": 1524912.32297
buffers/buffer-hex.js len="64" n="10000000": 1213341.44991
buffers/buffer-hex.js len="1024" n="10000000": 248060.16367

# With hex parsing optimized:
$ ./out/Release/node benchmark/buffers/buffer-hex.js
buffers/buffer-hex.js len="0" n="10000000": 6130801.93323
buffers/buffer-hex.js len="1" n="10000000": 1717385.59814
buffers/buffer-hex.js len="64" n="10000000": 1367649.36959
buffers/buffer-hex.js len="1024" n="10000000": 463809.34484

static const int8_t?

Does this still work with unhex()’s return type changed? It seems to me some of the speedup may come from the compiler eliminating this branch completely because it knows the upper bits of a and b will never be set:

$ ./node-master -p 'Buffer(10).write("abcdxx", "hex")'
2
$ ./node -p 'Buffer(10).write("abcdxx", "hex")'
3

(aka we need more tests to cover these cases?)

@addaleax, good catch. I didn't notice the type difference. It looks like you're right.

Applying this patch:

diff --git a/src/string_bytes.cc b/src/string_bytes.cc
index c216c5d..cb0e78a 100644
--- a/src/string_bytes.cc
+++ b/src/string_bytes.cc
@@ -173,9 +173,9 @@ size_t hex_decode(char* buf,
                   const size_t srcLen) {
   size_t i;
   for (i = 0; i < len && i * 2 + 1 < srcLen; ++i) {
-    unsigned a = unhex(src[i * 2 + 0]);
-    unsigned b = unhex(src[i * 2 + 1]);
-    if (!~a || !~b)
+    uint8_t a = unhex(src[i * 2 + 0]);
+    uint8_t b = unhex(src[i * 2 + 1]);
+    if ((a | b) & 0x80)
       return i;
     buf[i] = (a << 4) | b;
   }

Kills some of the gained perf, but large hex strings are still faster:

$ ./out/Release/node benchmark/buffers/buffer-hex.js
buffers/buffer-hex.js len="0" n="10000000": 5888692.25695
buffers/buffer-hex.js len="1" n="10000000": 1471220.48559
buffers/buffer-hex.js len="64" n="10000000": 1206331.66340
buffers/buffer-hex.js len="1024" n="10000000": 385088.76228

I'll see what else I can do, and probably add a test for bad hex strings.

const here please

CI: https://ci.nodejs.org/job/node-test-pull-request/3214/

@chjj Please run make lint :)

nit: assert.strictEqual is generally preferred over assert.equal, especially for comparisons with 0. :)

LGTM with nits and a happy linter.

Cleaned up and linted.

LGTM, nice work!

CI: https://ci.nodejs.org/job/node-test-commit/4027/

Landed in 151d316, thanks!

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

Notable changes: * **buffer**: * Improve performance of Buffer.from(str, 'hex') and Buffer#write(str, 'hex'). (Christopher Jeffrey) #7602 * Fix creating from zero-length ArrayBuffer. (Ingvar Stepanyan) #7176 * **deps**: Upgrade to V8 5.0.71.xx. (Ben Noordhuis) #7531 * **repl**: Fix issue with function redeclaration. (Prince J Wesley) #7794 * **util**: Fix inspecting of boxed symbols. (Anna Henningsen) #7641 PR-URL: #7782

Notable changes: * **buffer**: * Improve performance of Buffer.from(str, 'hex') and Buffer#write(str, 'hex'). (Christopher Jeffrey) #7602 * Fix creating from zero-length ArrayBuffer. (Ingvar Stepanyan) #7176 * **deps**: * Upgrade to V8 5.0.71.xx. (Ben Noordhuis) #7531 * Backport V8 instanceof bugfix (Franziska Hinkelmann) #7638 * **repl**: Fix issue with function redeclaration. (Prince J Wesley) #7794 * **util**: Fix inspecting of boxed symbols. (Anna Henningsen) #7641 PR-URL: #7782

### Notable changes * **buffer**: * Improve performance of Buffer.from(str, 'hex') and Buffer#write(str, 'hex'). (Christopher Jeffrey) [#7602](nodejs/node#7602) * Fix creating from zero-length ArrayBuffer. (Ingvar Stepanyan) [#7176](nodejs/node#7176) * **deps**: * Upgrade to V8 5.0.71.xx. (Ben Noordhuis) [#7531](nodejs/node#7531) * Backport V8 instanceof bugfix (Franziska Hinkelmann) [#7638](nodejs/node#7638) * **repl**: Fix issue with function redeclaration. (Prince J Wesley) [#7794](nodejs/node#7794) * **util**: Fix inspecting of boxed symbols. (Anna Henningsen) [#7641](nodejs/node#7641)

This test was recently (at the time of writing) introduced in 151d316 and could be cleaned up a bit. Refs: nodejs#7602 PR-URL: nodejs#7773 Reviewed-By: Anna Henningsen <anna@addaleax.net> Reviewed-By: Colin Ihrig <cjihrig@gmail.com> Reviewed-By: Minwoo Jung <jmwsoft@gmail.com> Reviewed-By: Ilkka Myller <ilkka.myller@nodefield.com> Reviewed-By: James M Snell <jasnell@gmail.com>

This test was recently (at the time of writing) introduced in 151d316 and could be cleaned up a bit. Refs: #7602 PR-URL: #7773 Reviewed-By: Anna Henningsen <anna@addaleax.net> Reviewed-By: Colin Ihrig <cjihrig@gmail.com> Reviewed-By: Minwoo Jung <jmwsoft@gmail.com> Reviewed-By: Ilkka Myller <ilkka.myller@nodefield.com> Reviewed-By: James M Snell <jasnell@gmail.com>

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

This test was recently (at the time of writing) introduced in 151d316 and could be cleaned up a bit. Refs: #7602 PR-URL: #7773 Reviewed-By: Anna Henningsen <anna@addaleax.net> Reviewed-By: Colin Ihrig <cjihrig@gmail.com> Reviewed-By: Minwoo Jung <jmwsoft@gmail.com> Reviewed-By: Ilkka Myller <ilkka.myller@nodefield.com> Reviewed-By: James M Snell <jasnell@gmail.com>

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

This test was recently (at the time of writing) introduced in 151d316 and could be cleaned up a bit. Refs: #7602 PR-URL: #7773 Reviewed-By: Anna Henningsen <anna@addaleax.net> Reviewed-By: Colin Ihrig <cjihrig@gmail.com> Reviewed-By: Minwoo Jung <jmwsoft@gmail.com> Reviewed-By: Ilkka Myller <ilkka.myller@nodefield.com> Reviewed-By: James M Snell <jasnell@gmail.com>

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

This test was recently (at the time of writing) introduced in 151d316 and could be cleaned up a bit. Refs: #7602 PR-URL: #7773 Reviewed-By: Anna Henningsen <anna@addaleax.net> Reviewed-By: Colin Ihrig <cjihrig@gmail.com> Reviewed-By: Minwoo Jung <jmwsoft@gmail.com> Reviewed-By: Ilkka Myller <ilkka.myller@nodefield.com> Reviewed-By: James M Snell <jasnell@gmail.com>

buffer: optimize hex_decode.

5a8b48e

nodejs-github-bot added the c++ Issues and PRs that require attention from people who are familiar with C++. label Jul 7, 2016

addaleax reviewed Jul 7, 2016
View reviewed changes

Trott added buffer Issues and PRs related to the buffer subsystem. benchmark Issues and PRs related to the benchmark subsystem. labels Jul 7, 2016

addaleax reviewed Jul 7, 2016
View reviewed changes

buffer: fix hex parsing and add bad hex string test.

ae21267

jasnell reviewed Jul 8, 2016
View reviewed changes

addaleax reviewed Jul 8, 2016
View reviewed changes

buffer: lint for hex parsing optimization.

1627283

addaleax closed this Jul 17, 2016

addaleax pushed a commit that referenced this pull request Jul 17, 2016

buffer: optimize hex_decode

151d316

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

Fishrock123 mentioned this pull request Jul 17, 2016

test: clean up test-buffer-badhex #7773

Merged

2 tasks

evanlucas pushed a commit that referenced this pull request Jul 19, 2016

buffer: optimize hex_decode

ba6ab7c

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

evanlucas mentioned this pull request Jul 19, 2016

v6.3.1 Release Proposal #7782

Merged

evanlucas pushed a commit that referenced this pull request Jul 20, 2016

buffer: optimize hex_decode

4158272

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

cjean-fr mentioned this pull request Jul 24, 2016

Upgrade node to 6.3.1 ScoopInstaller/Scoop#966

Merged

MylesBorins pushed a commit that referenced this pull request Sep 30, 2016

buffer: optimize hex_decode

f2916f8

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

MylesBorins added the land-on-v4.x label Sep 30, 2016

rvagg pushed a commit that referenced this pull request Oct 18, 2016

buffer: optimize hex_decode

df4f845

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

MylesBorins pushed a commit that referenced this pull request Oct 26, 2016

buffer: optimize hex_decode

17c4187

PR-URL: #7602 Reviewed-By: Anna Henningsen <anna@addaleax.net>

MylesBorins mentioned this pull request Oct 26, 2016

V4.6.2 proposal #9298

Closed

+                assert.deepStrictEqual(buf4, new Buffer([0, 0, 0, 0]));
+                assert.equal(buf4.write('xxabcd', 0, 'hex'), 0);
+                assert.deepStrictEqual(buf4, new Buffer([0, 0, 0, 0]));
+                assert.equal(buf4.write('xxab', 1, 'hex'), 0);

buffer: optimize hex parsing. by chjj · Pull Request #7602 · nodejs/node · GitHub

Uh oh!

Uh oh!

buffer: optimize hex parsing. - #7602

buffer: optimize hex parsing.#7602
chjj wants to merge 3 commits into
nodejs:masterfrom
chjj:hex_parsing

chjj commented Jul 7, 2016

Uh oh!

addaleax Jul 7, 2016

Uh oh!

addaleax Jul 7, 2016

Uh oh!

chjj Jul 7, 2016

Uh oh!

jasnell Jul 8, 2016

Uh oh!

Fishrock123 commented Jul 8, 2016

Uh oh!

Fishrock123 commented Jul 8, 2016

Uh oh!

addaleax Jul 8, 2016

Uh oh!

addaleax commented Jul 8, 2016

Uh oh!

chjj commented Jul 8, 2016

Uh oh!

addaleax commented Jul 8, 2016

Uh oh!

addaleax commented Jul 8, 2016

Uh oh!

addaleax commented Jul 17, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

-                  return 10 + (c - 'a');
-                return static_cast<unsigned>(-1);
-              }
+              const int8_t unhex_table[256] =

+              var common = require('../common');
+              var assert = require('assert');
+              var Buffer = require('buffer').Buffer;

buffer: optimize hex parsing. by chjj · Pull Request #7602 · nodejs/node · GitHub

Uh oh!

Uh oh!

buffer: optimize hex parsing. - #7602

buffer: optimize hex parsing.#7602chjj wants to merge 3 commits intonodejs:masternodejs/node:masterfrom chjj:hex_parsingchjj/node:hex_parsingCopy head branch name to clipboard

Conversation

chjj commented Jul 7, 2016

Checklist

Affected core subsystem(s)

Description of change

Uh oh!

addaleax Jul 7, 2016

Choose a reason for hiding this comment

Uh oh!

addaleax Jul 7, 2016

Choose a reason for hiding this comment

Uh oh!

chjj Jul 7, 2016

Choose a reason for hiding this comment

Uh oh!

jasnell Jul 8, 2016

Choose a reason for hiding this comment

Uh oh!

Fishrock123 commented Jul 8, 2016

Uh oh!

Fishrock123 commented Jul 8, 2016

Uh oh!

addaleax Jul 8, 2016

Choose a reason for hiding this comment

Uh oh!

addaleax commented Jul 8, 2016

Uh oh!

chjj commented Jul 8, 2016

Uh oh!

addaleax commented Jul 8, 2016

Uh oh!

addaleax commented Jul 8, 2016

Uh oh!

addaleax commented Jul 17, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

buffer: optimize hex parsing.#7602
chjj wants to merge 3 commits into
nodejs:masterfrom
chjj:hex_parsing