buffer: improve `base64` and `base64url` performance by anonrig · Pull Request #52428 · nodejs/node · GitHub

The work is mostly done by @lemire.

Suggested changes improves the performance of base64 and base64url operations.

Benchmarks

                                                                                confidence improvement accuracy (*)   (**)  (***)
buffers/buffer-base64-decode-wrapped.js n=32 linesCount=524288 charsPerLine=76        ***    196.05 %       ±2.25% ±3.03% ±4.01%
buffers/buffer-base64-decode.js size=8388608 n=32                                     ***    218.27 %       ±3.45% ±4.65% ±6.16%
buffers/buffer-base64-encode.js n=32 len=67108864                                     ***      2.95 %       ±0.67% ±0.89% ±1.16%
buffers/buffer-base64url-decode.js size=8388608 n=32                                  ***    218.32 %       ±4.34% ±5.84% ±7.74%
buffers/buffer-base64url-encode.js n=32 len=67108864                                  ***    246.27 %       ±2.68% ±3.61% ±4.79%

Be aware that when doing many comparisons the risk of a false-positive result increases.
In this case, there are 5 comparisons, you can thus expect the following amount of false-positive results:
  0.25 false positives, when considering a   5% risk acceptance (*, **, ***),
  0.05 false positives, when considering a   1% risk acceptance (**, ***),
  0.01 false positives, when considering a 0.1% risk acceptance (***)

Note that gains are not expected for buffers/buffer-base64-encode.js so the 2.95% result is probably approximately 0%. (I am only pointing out that this is not an issue.)

can we have a btoa too, please?

@lemire there are some test cases failing. would you mind looking into them?

Co-authored-by: Daniel Lemire <daniel@lemire.me>

@Uzlopak @anonrig

can we have a btoa too, please?

This should be "easy".

@anonrig I pushed a commit.

@anonrig I did some additional optimizations.

lgtm

@anonrig If you get around to it, it would be nice to revisit your benchmarks. I bet that you'd get better numbers with the latest changes.

@anonrig If you get around to it, it would be nice to revisit your benchmarks. I bet that you'd get better numbers with the latest changes.

The benchmarks didn't show anything, but I'm pretty sure, it has a flaw.

                                                                                confidence improvement accuracy (*)   (**)  (***)
buffers/buffer-base64-decode-wrapped.js n=32 linesCount=524288 charsPerLine=76        ***    191.75 %       ±1.82% ±2.45% ±3.25%
buffers/buffer-base64-decode.js size=8388608 n=32                                     ***    213.25 %       ±2.59% ±3.49% ±4.63%
buffers/buffer-base64-encode.js n=32 len=67108864                                     ***      3.57 %       ±1.21% ±1.61% ±2.10%
buffers/buffer-base64url-decode.js size=8388608 n=32                                  ***    216.97 %       ±0.87% ±1.17% ±1.54%
buffers/buffer-base64url-encode.js n=32 len=67108864                                  ***    244.58 %       ±2.97% ±4.00% ±5.31%

Be aware that when doing many comparisons the risk of a false-positive result increases.
In this case, there are 5 comparisons, you can thus expect the following amount of false-positive results:
  0.25 false positives, when considering a   5% risk acceptance (*, **, ***),
  0.05 false positives, when considering a   1% risk acceptance (**, ***),
  0.01 false positives, when considering a 0.1% risk acceptance (***)

The benchmarks didn't show anything, but I'm pretty sure, it has a flaw.

Hmmm...

The notable-change PRs with changes that should be highlighted in changelogs. label has been added by @anonrig.

Please suggest a text for the release notes if you'd like to include a more detailed summary, then proceed to update the PR description with the text or a link to the notable change suggested text comment. Otherwise, the commit will be placed in the Other Notable Changes section.

For people who want profiling... here are the numbers for the base64 decoding prior to this PR:

Here are the results after...

So the main bottleneck after this PR is merged will be memmove. Unless we find a way to move less data, this function is unlikely to ever get much faster.

Landed in 4221631

Co-authored-by: Daniel Lemire <daniel@lemire.me> PR-URL: #52428 Reviewed-By: Matteo Collina <matteo.collina@gmail.com> Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com> Reviewed-By: James M Snell <jasnell@gmail.com>

Notable changes: buffer: * improve `base64` and `base64url` performance (Yagiz Nizipli) #52428 dns: * (SEMVER-MINOR) add order option and support ipv6first (Paolo Insogna) #52492 events,doc: * mark CustomEvent as stable (Daeyeon Jeong) #52618 lib, url: * (SEMVER-MINOR) add a `windows` option to path parsing (Aviv Keller) #52509 module: * (SEMVER-MINOR) implement NODE_COMPILE_CACHE for automatic on-disk code caching (Joyee Cheung) #52535 net: * (SEMVER-MINOR) add CLI option for autoSelectFamilyAttemptTimeout (Paolo Insogna) #52474 src: * (SEMVER-MINOR) add `string_view` overload to snapshot FromBlob (Anna Henningsen) #52595 src,permission: * throw async errors on async APIs (Rafael Gonzaga) #52730 test_runner: * (SEMVER-MINOR) add --test-skip-pattern cli option (Aviv Keller) #52529 url: * (SEMVER-MINOR) implement parse method for safer URL parsing (Ali Hassan) #52280 PR-URL: TODO

Notable changes: buffer: * improve `base64` and `base64url` performance (Yagiz Nizipli) #52428 dns: * (SEMVER-MINOR) add order option and support ipv6first (Paolo Insogna) #52492 events,doc: * mark CustomEvent as stable (Daeyeon Jeong) #52618 lib, url: * (SEMVER-MINOR) add a `windows` option to path parsing (Aviv Keller) #52509 module: * (SEMVER-MINOR) implement NODE_COMPILE_CACHE for automatic on-disk code caching (Joyee Cheung) #52535 net: * (SEMVER-MINOR) add CLI option for autoSelectFamilyAttemptTimeout (Paolo Insogna) #52474 src: * (SEMVER-MINOR) add `string_view` overload to snapshot FromBlob (Anna Henningsen) #52595 src,permission: * throw async errors on async APIs (Rafael Gonzaga) #52730 test_runner: * (SEMVER-MINOR) add --test-skip-pattern cli option (Aviv Keller) #52529 url: * (SEMVER-MINOR) implement parse method for safer URL parsing (Ali Hassan) #52280 PR-URL: #52768

Co-authored-by: Daniel Lemire <daniel@lemire.me> PR-URL: #52428 Reviewed-By: Matteo Collina <matteo.collina@gmail.com> Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com> Reviewed-By: James M Snell <jasnell@gmail.com>

Notable changes: benchmark: * add AbortSignal.abort benchmarks (Raz Luvaton) #52408 buffer: * improve `base64` and `base64url` performance (Yagiz Nizipli) #52428 crypto: * deprecate implicitly shortened GCM tags (Tobias Nießen) #52345 deps: * (SEMVER-MINOR) update simdutf to 5.0.0 (Daniel Lemire) #52138 * (SEMVER-MINOR) update undici to 6.3.0 (Node.js GitHub Bot) #51462 * (SEMVER-MINOR) update undici to 6.2.1 (Node.js GitHub Bot) #51278 dns: * (SEMVER-MINOR) add order option and support ipv6first (Paolo Insogna) #52492 doc: * update release gpg keyserver (marco-ippolito) #52257 * add release key for marco-ippolito (marco-ippolito) #52257 * add UlisesGascon as a collaborator (Ulises Gascón) #51991 * (SEMVER-MINOR) deprecate fs.Stats public constructor (Marco Ippolito) #51879 events,doc: * mark CustomEvent as stable (Daeyeon Jeong) #52618 fs: * add stacktrace to fs/promises (翠 / green) #49849 lib, url: * (SEMVER-MINOR) add a `windows` option to path parsing (Aviv Keller) #52509 net: * (SEMVER-MINOR) add CLI option for autoSelectFamilyAttemptTimeout (Paolo Insogna) #52474 report: * (SEMVER-MINOR) add `--report-exclude-network` option (Ethan Arrowood) #51645 src: * (SEMVER-MINOR) add `string_view` overload to snapshot FromBlob (Anna Henningsen) #52595 * (SEMVER-MINOR) add C++ ProcessEmitWarningSync() (Joyee Cheung) #51977 * (SEMVER-MINOR) add uv_get_available_memory to report and process (theanarkh) #52023 * (SEMVER-MINOR) preload function for Environment (Cheng Zhao) #51539 stream: * (SEMVER-MINOR) support typed arrays (IlyasShabi) #51866 test_runner: * (SEMVER-MINOR) add suite() (Colin Ihrig) #52127 * (SEMVER-MINOR) support forced exit (Colin Ihrig) #52038 * (SEMVER-MINOR) add `test:complete` event to reflect execution order (Moshe Atlow) #51909 util: * (SEMVER-MINOR) support array of formats in util.styleText (Marco Ippolito) #52040 v8: * (SEMVER-MINOR) implement v8.queryObjects() for memory leak regression testing (Joyee Cheung) #51927 watch: * mark as stable (Moshe Atlow) #52074 PR-URL: #52793

Notable changes: buffer: * improve `base64` and `base64url` performance (Yagiz Nizipli) #52428 dns: * (SEMVER-MINOR) add order option and support ipv6first (Paolo Insogna) #52492 events,doc: * mark CustomEvent as stable (Daeyeon Jeong) #52618 lib, url: * (SEMVER-MINOR) add a `windows` option to path parsing (Aviv Keller) #52509 module: * (SEMVER-MINOR) implement NODE_COMPILE_CACHE for automatic on-disk code caching (Joyee Cheung) #52535 net: * (SEMVER-MINOR) add CLI option for autoSelectFamilyAttemptTimeout (Paolo Insogna) #52474 src: * (SEMVER-MINOR) add `string_view` overload to snapshot FromBlob (Anna Henningsen) #52595 src,permission: * throw async errors on async APIs (Rafael Gonzaga) #52730 test_runner: * (SEMVER-MINOR) add --test-skip-pattern cli option (Aviv Keller) #52529 url: * (SEMVER-MINOR) implement parse method for safer URL parsing (Ali Hassan) #52280 PR-URL: #52768

Co-authored-by: Daniel Lemire <daniel@lemire.me> PR-URL: #52428 Reviewed-By: Matteo Collina <matteo.collina@gmail.com> Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com> Reviewed-By: James M Snell <jasnell@gmail.com>

Notable changes: benchmark: * add AbortSignal.abort benchmarks (Raz Luvaton) #52408 buffer: * improve `base64` and `base64url` performance (Yagiz Nizipli) #52428 crypto: * deprecate implicitly shortened GCM tags (Tobias Nießen) #52345 deps: * (SEMVER-MINOR) update simdutf to 5.0.0 (Daniel Lemire) #52138 * (SEMVER-MINOR) update undici to 6.3.0 (Node.js GitHub Bot) #51462 * (SEMVER-MINOR) update undici to 6.2.1 (Node.js GitHub Bot) #51278 dns: * (SEMVER-MINOR) add order option and support ipv6first (Paolo Insogna) #52492 doc: * update release gpg keyserver (marco-ippolito) #52257 * add release key for marco-ippolito (marco-ippolito) #52257 * add UlisesGascon as a collaborator (Ulises Gascón) #51991 * (SEMVER-MINOR) deprecate fs.Stats public constructor (Marco Ippolito) #51879 events,doc: * mark CustomEvent as stable (Daeyeon Jeong) #52618 fs: * add stacktrace to fs/promises (翠 / green) #49849 lib, url: * (SEMVER-MINOR) add a `windows` option to path parsing (Aviv Keller) #52509 net: * (SEMVER-MINOR) add CLI option for autoSelectFamilyAttemptTimeout (Paolo Insogna) #52474 report: * (SEMVER-MINOR) add `--report-exclude-network` option (Ethan Arrowood) #51645 src: * (SEMVER-MINOR) add `string_view` overload to snapshot FromBlob (Anna Henningsen) #52595 * (SEMVER-MINOR) add C++ ProcessEmitWarningSync() (Joyee Cheung) #51977 * (SEMVER-MINOR) add uv_get_available_memory to report and process (theanarkh) #52023 * (SEMVER-MINOR) preload function for Environment (Cheng Zhao) #51539 stream: * (SEMVER-MINOR) support typed arrays (IlyasShabi) #51866 test_runner: * (SEMVER-MINOR) add suite() (Colin Ihrig) #52127 * (SEMVER-MINOR) add `test:complete` event to reflect execution order (Moshe Atlow) #51909 util: * (SEMVER-MINOR) support array of formats in util.styleText (Marco Ippolito) #52040 v8: * (SEMVER-MINOR) implement v8.queryObjects() for memory leak regression testing (Joyee Cheung) #51927 watch: * mark as stable (Moshe Atlow) #52074 PR-URL: #52793

Notable changes: buffer: * improve `base64` and `base64url` performance (Yagiz Nizipli) nodejs#52428 dns: * (SEMVER-MINOR) add order option and support ipv6first (Paolo Insogna) nodejs#52492 events,doc: * mark CustomEvent as stable (Daeyeon Jeong) nodejs#52618 lib, url: * (SEMVER-MINOR) add a `windows` option to path parsing (Aviv Keller) nodejs#52509 module: * (SEMVER-MINOR) implement NODE_COMPILE_CACHE for automatic on-disk code caching (Joyee Cheung) nodejs#52535 net: * (SEMVER-MINOR) add CLI option for autoSelectFamilyAttemptTimeout (Paolo Insogna) nodejs#52474 src: * (SEMVER-MINOR) add `string_view` overload to snapshot FromBlob (Anna Henningsen) nodejs#52595 src,permission: * throw async errors on async APIs (Rafael Gonzaga) nodejs#52730 test_runner: * (SEMVER-MINOR) add --test-skip-pattern cli option (Aviv Keller) nodejs#52529 url: * (SEMVER-MINOR) implement parse method for safer URL parsing (Ali Hassan) nodejs#52280 PR-URL: nodejs#52768

Notable changes: benchmark: * add AbortSignal.abort benchmarks (Raz Luvaton) nodejs#52408 buffer: * improve `base64` and `base64url` performance (Yagiz Nizipli) nodejs#52428 crypto: * deprecate implicitly shortened GCM tags (Tobias Nießen) nodejs#52345 deps: * (SEMVER-MINOR) update simdutf to 5.0.0 (Daniel Lemire) nodejs#52138 * (SEMVER-MINOR) update undici to 6.3.0 (Node.js GitHub Bot) nodejs#51462 * (SEMVER-MINOR) update undici to 6.2.1 (Node.js GitHub Bot) nodejs#51278 dns: * (SEMVER-MINOR) add order option and support ipv6first (Paolo Insogna) nodejs#52492 doc: * update release gpg keyserver (marco-ippolito) nodejs#52257 * add release key for marco-ippolito (marco-ippolito) nodejs#52257 * add UlisesGascon as a collaborator (Ulises Gascón) nodejs#51991 * (SEMVER-MINOR) deprecate fs.Stats public constructor (Marco Ippolito) nodejs#51879 events,doc: * mark CustomEvent as stable (Daeyeon Jeong) nodejs#52618 fs: * add stacktrace to fs/promises (翠 / green) nodejs#49849 lib, url: * (SEMVER-MINOR) add a `windows` option to path parsing (Aviv Keller) nodejs#52509 net: * (SEMVER-MINOR) add CLI option for autoSelectFamilyAttemptTimeout (Paolo Insogna) nodejs#52474 report: * (SEMVER-MINOR) add `--report-exclude-network` option (Ethan Arrowood) nodejs#51645 src: * (SEMVER-MINOR) add `string_view` overload to snapshot FromBlob (Anna Henningsen) nodejs#52595 * (SEMVER-MINOR) add C++ ProcessEmitWarningSync() (Joyee Cheung) nodejs#51977 * (SEMVER-MINOR) add uv_get_available_memory to report and process (theanarkh) nodejs#52023 * (SEMVER-MINOR) preload function for Environment (Cheng Zhao) nodejs#51539 stream: * (SEMVER-MINOR) support typed arrays (IlyasShabi) nodejs#51866 test_runner: * (SEMVER-MINOR) add suite() (Colin Ihrig) nodejs#52127 * (SEMVER-MINOR) add `test:complete` event to reflect execution order (Moshe Atlow) nodejs#51909 util: * (SEMVER-MINOR) support array of formats in util.styleText (Marco Ippolito) nodejs#52040 v8: * (SEMVER-MINOR) implement v8.queryObjects() for memory leak regression testing (Joyee Cheung) nodejs#51927 watch: * mark as stable (Moshe Atlow) nodejs#52074 PR-URL: nodejs#52793

nodejs-github-bot added buffer Issues and PRs related to the buffer subsystem. c++ Issues and PRs that require attention from people who are familiar with C++. needs-ci PRs that need a full CI run. labels Apr 8, 2024

rluvaton added the needs-benchmark-ci PR that need a benchmark CI run. label Apr 8, 2024

lemire reviewed Apr 8, 2024

View reviewed changes

Comment thread src/string_bytes.cc Outdated

lemire mentioned this pull request Apr 8, 2024

performance of encodings (hex, base64, base64url) nodejs/performance#128

Open

anonrig force-pushed the improve-base64-operations branch from b9b5d45 to 4fe9aa6 Compare April 8, 2024 18:26

addaleax mentioned this pull request Apr 8, 2024

buffer: improve btoa performance #52427

Merged

anonrig force-pushed the improve-base64-operations branch 2 times, most recently from 57db503 to 4adcf8b Compare April 8, 2024 19:39

buffer: improve base64 and base64url performance

a1670bc

Co-authored-by: Daniel Lemire <daniel@lemire.me>

anonrig force-pushed the improve-base64-operations branch from 4adcf8b to a1670bc Compare April 8, 2024 19:50

lemire added 2 commits April 8, 2024 21:30

fix: replace base64_to_binary to account for short inputs

8e88778

lint

a2b60ac

anonrig added the request-ci Add this label to start a Jenkins CI on a PR. label Apr 9, 2024

lemire added 2 commits April 8, 2024 23:28

optimization: fast one-byte case

edbeb50

lint

c3d6e4d

mcollina approved these changes Apr 9, 2024

View reviewed changes

anonrig added the notable-change PRs with changes that should be highlighted in changelogs. label Apr 10, 2024

anonrig added the commit-queue-squash Add this label to instruct the Commit Queue to squash all the PR commits into the first one. label Apr 12, 2024

nodejs-github-bot removed the commit-queue Add this label to land a pull request using GitHub Actions. label Apr 12, 2024

nodejs-github-bot merged commit 4221631 into nodejs:main Apr 12, 2024

aduh95 mentioned this pull request Apr 30, 2024

2024-05-02, Version 22.1.0 (Current) #52768

Merged

marco-ippolito mentioned this pull request May 2, 2024

v20.13.0 proposal #52793

Merged

mgaudet mentioned this pull request Jun 11, 2024

Node unconditionally uses AVX512 instructions (illegal instruction starting Extension Host agent) microsoft/vscode#214630

Open

mildsunrise mentioned this pull request Jun 22, 2024

buffer: Reallocate() instead of creating a new backing store #53552

Closed

buffer: improve `base64` and `base64url` performance by anonrig · Pull Request #52428 · nodejs/node · GitHub

Uh oh!

Uh oh!

buffer: improve base64 and base64url performance - #52428

buffer: improve base64 and base64url performance#52428nodejs-github-bot merged 5 commits intonodejs:mainnodejs/node:mainfrom anonrig:improve-base64-operationsanonrig/node:improve-base64-operationsCopy head branch name to clipboard

Conversation

anonrig commented Apr 8, 2024

Benchmarks

Uh oh!

lemire commented Apr 8, 2024

Uh oh!

Uh oh!

Uzlopak commented Apr 8, 2024

Uh oh!

anonrig commented Apr 8, 2024

Uh oh!

lemire commented Apr 9, 2024

Uh oh!

lemire commented Apr 9, 2024

Uh oh!

lemire commented Apr 9, 2024

Uh oh!

mcollina left a comment

Choose a reason for hiding this comment

Uh oh!

lemire commented Apr 9, 2024

Uh oh!

anonrig commented Apr 9, 2024

Uh oh!

lemire commented Apr 10, 2024

Uh oh!

github-actions Bot commented Apr 10, 2024

Uh oh!

lemire commented Apr 10, 2024

Uh oh!

nodejs-github-bot commented Apr 12, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

8 participants

buffer: improve base64 and base64url performance#52428
nodejs-github-bot merged 5 commits into
nodejs:mainfrom
anonrig:improve-base64-operations