GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — src: use an array for faster binding data lookup by joyeecheung · Pull Request #46620 · nodejs/node

Conversation

@joyeecheung

@joyeecheung joyeecheung commented Feb 12, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

src: use an array for faster binding data lookup

Locally the hashing of the binding names sometimes has significant
presence in the profile of bindings, because there can be collisions,
which makes the cost of adding a new binding data non-trivial,
but it's wasteful to spend time on hashing them or dealing with
collisions at all, since we can just use the EmbedderObjectType
enum as the key, as the string names are not actually used beyond
debugging purposes and can be easily matched with a macro.
And since we can just use the enum as the key, we do not even
need the map and can just use an array with the enum as indices
for the lookup.

Background: I was trying to move the encoding-related bindings to a new binding with its own BindingData and noticed ~15% regression in some TextEncoder benchmarks, and the hashing showed up in the profile. With this patch the regression goes away and the hashing no longer has any presence in the profile.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

bricss reacted with eyes emoji
All reactions
  • 👀 1 reaction
@nodejs-github-bot

nodejs-github-bot commented Feb 12, 2023

Copy link
Copy Markdown
Collaborator

Review requested:

  • @nodejs/http
  • @nodejs/http2
  • @nodejs/net
  • @nodejs/startup
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@nodejs-github-bot nodejs-github-bot added c++ Issues and PRs that require attention from people who are familiar with C++. lib / src Issues and PRs involving general changes in the lib/ or src/ directories. needs-ci PRs that need a full CI run. labels Feb 12, 2023
@joyeecheung
joyeecheung force-pushed the type-int branch from e25375f to 0a0df16 Compare February 12, 2023 00:24
@addaleax

addaleax commented Feb 12, 2023

Copy link
Copy Markdown
Member

but it's wasteful to spend time on hashing them at all, since we can just use the numeric type as the key

Do you know where this hashing happens in the stack/can share how you profiled this? The whole point of FastStringKey is that you don’t need to do any hashing at runtime.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung

joyeecheung commented Feb 12, 2023

Copy link
Copy Markdown
Member Author

Do you know where this hashing happens in the stack/can share how you profiled this? The whole point of FastStringKey is that you don’t need to do any hashing at runtime.

I used perf to profile a new binding that calls Environment::GetBindingData(), and the hashing just showed up on top of that binding (others frames in between are probably just inlined).

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@addaleax

addaleax commented Feb 12, 2023

Copy link
Copy Markdown
Member

@joyeecheung Here’s my local assembly for http2::PackSettings:

in the fold
000000000098fba0 <node::http2::PackSettings(v8::FunctionCallbackInfo<v8::Value> const&)>:
  98fba0:       f3 0f 1e fa             endbr64 
  98fba4:       55                      push   %rbp
  98fba5:       48 89 e5                mov    %rsp,%rbp
  98fba8:       53                      push   %rbx
  98fba9:       48 89 fb                mov    %rdi,%rbx
  98fbac:       48 83 ec 08             sub    $0x8,%rsp
  98fbb0:       48 8b 07                mov    (%rdi),%rax
  98fbb3:       48 8b 78 08             mov    0x8(%rax),%rdi
  98fbb7:       e8 34 5f 1e 00          call   b75af0 <v8::Isolate::GetCurrentContext()>
  98fbbc:       31 d2                   xor    %edx,%edx
  98fbbe:       48 b9 97 8c 9a 0f 31    movabs $0x310f9a8c97,%rcx
  98fbc5:       00 00 00 
  98fbc8:       48 8b 00                mov    (%rax),%rax
  98fbcb:       48 8b 40 2f             mov    0x2f(%rax),%rax
  98fbcf:       48 8b b8 27 01 00 00    mov    0x127(%rax),%rdi
  98fbd6:       48 89 c8                mov    %rcx,%rax
  98fbd9:       48 f7 77 08             divq   0x8(%rdi)
  98fbdd:       48 89 d6                mov    %rdx,%rsi
  98fbe0:       48 8d 15 d9 23 39 04    lea    0x43923d9(%rip),%rdx        # 4d21fc0 <node::http2::Http2State::type_name>
  98fbe7:       e8 24 d1 f8 ff          call   91cd10 <std::_Hashtable<node::FastStringKey, std::pair<node::FastStringKey const, node::BaseObjectPtrImpl<node::BaseObject, false> >, std::allocator<std::pair<node::FastStringKey const, node::BaseObjectPtrImpl<node::BaseObject, false> > >, std::__detail::_Select1st, std::equal_to<node::FastStringKey>, node::FastStringKey::Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_before_node(unsigned long, node::FastStringKey const&, unsigned long) const>
  98fbec:       48 89 c7                mov    %rax,%rdi
  98fbef:       48 85 c0                test   %rax,%rax
  98fbf2:       74 0c                   je     98fc00 <node::http2::PackSettings(v8::FunctionCallbackInfo<v8::Value> const&)+0x60>
  98fbf4:       48 8b 38                mov    (%rax),%rdi
  98fbf7:       48 85 ff                test   %rdi,%rdi
  98fbfa:       74 04                   je     98fc00 <node::http2::PackSettings(v8::FunctionCallbackInfo<v8::Value> const&)+0x60>
  98fbfc:       48 8b 7f 20             mov    0x20(%rdi),%rdi
  98fc00:       48 8b 1b                mov    (%rbx),%rbx
  98fc03:       e8 78 94 fe ff          call   979080 <node::http2::Http2Settings::Pack(node::http2::Http2State*)>
  98fc08:       48 85 c0                test   %rax,%rax
  98fc0b:       74 13                   je     98fc20 <node::http2::PackSettings(v8::FunctionCallbackInfo<v8::Value> const&)+0x80>
  98fc0d:       48 8b 00                mov    (%rax),%rax
  98fc10:       48 89 43 18             mov    %rax,0x18(%rbx)
  98fc14:       48 8b 5d f8             mov    -0x8(%rbp),%rbx
  98fc18:       c9                      leave  
  98fc19:       c3                      ret    
  98fc1a:       66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  98fc20:       48 8b 43 10             mov    0x10(%rbx),%rax
  98fc24:       48 89 43 18             mov    %rax,0x18(%rbx)
  98fc28:       48 8b 5d f8             mov    -0x8(%rbp),%rbx
  98fc2c:       c9                      leave  
  98fc2d:       c3                      ret    
  98fc2e:       66 90                   xchg   %ax,%ax

The hash (0x310f9a8c97) is hardcoded here (as it should be – it’s constexpr), so I’m wondering in what situations this would work differently?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung

joyeecheung commented Feb 12, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

This is the branch I used to find out the profile, by the way, revert the last two commits to go back to type_name, and use --prof/--prof-process to profile script like this:

See code
'use strict';

const encoder = new TextEncoder('utf-8');
const arr = new Uint8Array(1000);
const str = new Date().toISOString();

let result = [];
for (let i = 0; i < 1000000; ++i) {
  result = encoder.encodeInto(str, arr);
}

console.log(result);

And I'd get:

See code
 [C++]:
   ticks  total  nonlib   name
     22   11.4%   12.4%  node::builtins::BuiltinLoader::CompileFunction(v8::FunctionCallbackInfo<v8::Value> const&)
     21   10.9%   11.8%  node::encoding_binding::BindingData::EncodeInto(v8::FunctionCallbackInfo<v8::Value> const&)
     14    7.3%    7.9%  fputc@@GLIBC_2.2.5
     12    6.2%    6.7%  __write@@GLIBC_2.2.5
      7    3.6%    3.9%  std::_Hashtable<node::FastStringKey, std::pair<node::FastStringKey const, node::BaseObjectPtrImpl<node::BaseObject, false> >, std::allocator<std::pair<node::FastStringKey const, node::BaseObjectPtrImpl<node::BaseObject, false> > >, std::__detail::_Select1st, std::equal_to<node::FastStringKey>, node::FastStringKey::Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::_M_find_before_node(unsigned long, node::FastStringKey const&, unsigned long) const

(and some regressions, even without the AliasedBuffer change)

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung

joyeecheung commented Feb 12, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

My guess is hard-coding is not the same as the hashing still needs to be done (e.g. it still needs to do what it does to handle collisions? so extra overhead). I didn't check out the STL implementation but now come to think of it, why do we even need a map when the keys are all just..sequential numbers (starting from 0, even)?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung

joyeecheung commented Feb 12, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

Updated the patch to just use an std::array. Also I think I found why the original hash was slow - there are collisions (notice how in the profile the actual function where time is spent is std::_Hashtable::_M_find_before_node which deals with collisions). Some logging showed:

See logs
AddBindingData node::process::BindingData
Bucket count 2
Bucket #0:
Bucket #1: [node::process::BindingData]
AddBindingData node::fs::BindingData
Bucket count 2
Bucket #0:
Bucket #1: [node::fs::BindingData][node::process::BindingData]
AddBindingData node::BlobBindingData
Bucket count 5
Bucket #0: [node::fs::BindingData]
Bucket #0:
Bucket #0:
Bucket #0:
Bucket #0: [node::BlobBindingData][node::process::BindingData]
AddBindingData node::encoding_binding::BindingData
Bucket count 5
Bucket #0: [node::encoding_binding::BindingData][node::fs::BindingData]
Bucket #1:
Bucket #2:
Bucket #3:
Bucket #4: [node::BlobBindingData][node::process::BindingData]

It might be possible to optimize the hash function of FastStringKey, but in the case of binding data, that's an overkill for problem as we could really just use the enums as keys and do not need to worry about collisions at all. And also because we could just use the enums as keys, we could just use an array, and that's as fast as it gets.

addaleax reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung
joyeecheung force-pushed the type-int branch from 4aae96e to c841b77 Compare February 12, 2023 21:57
@joyeecheung joyeecheung changed the title src: use type_int as binding data store key src: use an array for faster binding data lookup Feb 12, 2023
mcollina
mcollina approved these changes Feb 13, 2023
View reviewed changes

@mcollina mcollina left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

impressive, lgtm

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@addaleax

addaleax commented Feb 13, 2023

Copy link
Copy Markdown
Member

It might be possible to optimize the hash function of FastStringKey

I suspect that wouldn’t make much of a difference here – the problem isn’t that the hashes collide directly, it’s that the number of buckets is on the lower end and therefore collisions are to be expected regardless of the exact hash function.

why do we even need a map

The goal of that was just to make the individual implementations more self-contained/avoid the need for global lists of all possible objects of that type.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

addaleax
addaleax reviewed Feb 13, 2023
View reviewed changes
Comment thread src/env.h Resolved

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung

joyeecheung commented Feb 13, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

The goal of that was just to make the individual implementations more self-contained/avoid the need for global lists of all possible objects of that type.

Yeah although in the case of binding data, there is already a global list for the bindings, so another global list for the wrapper of the binding object probably isn't that much of a big deal anyway..eventually it might be nicer to just have C++ wrappers for all the bindings (and merge the lists), then we can move more things off the Environment object and make the global states more self-contained, like the TODO I added in #46579 about moving immediate info and timeout info to the binding, which also helps the per-realm/context built-in effort (#46558) I assume

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

addaleax
addaleax approved these changes Feb 13, 2023
View reviewed changes
legendecas
legendecas approved these changes Feb 14, 2023
View reviewed changes
@addaleax addaleax added the request-ci Add this label to start a Jenkins CI on a PR. Only starts once the PR has an approving review. label Feb 14, 2023
@joyeecheung joyeecheung mentioned this pull request Feb 14, 2023
encoding: use AliasedUint32Array for encodeInto results #46658
Closed
@github-actions github-actions Bot removed the request-ci Add this label to start a Jenkins CI on a PR. Only starts once the PR has an approving review. label Feb 16, 2023
@nodejs-github-bot

nodejs-github-bot commented Feb 16, 2023

Copy link
Copy Markdown
Collaborator

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@github-actions github-actions Bot mentioned this pull request Feb 18, 2023
CI Reliability 2023-02-18 nodejs/reliability#499
Open
32 tasks
@nodejs-github-bot

nodejs-github-bot commented Feb 20, 2023

Copy link
Copy Markdown
Collaborator

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@github-actions github-actions Bot mentioned this pull request Feb 21, 2023
CI Reliability 2023-02-21 nodejs/reliability#502
Open
26 tasks
@nodejs-github-bot

nodejs-github-bot commented Feb 21, 2023

Copy link
Copy Markdown
Collaborator

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@github-actions github-actions Bot mentioned this pull request Feb 22, 2023
CI Reliability 2023-02-22 nodejs/reliability#503
Open
34 tasks
@joyeecheung
src: use an array for faster binding data lookup
4becc8f
Locally the hashing of the binding names sometimes has significant
presence in the profile of bindings, because there can be collisions,
which makes the cost of adding a new binding data non-trivial,
but it's wasteful to spend time on hashing them or dealing with
collisions at all, since we can just use the EmbedderObjectType
enum as the key, as the string names are not actually used beyond
debugging purposes and can be easily matched with a macro.
And since we can just use the enum as the key, we do not even
need the map and can just use an array with the enum as indices
for the lookup.
@joyeecheung

joyeecheung commented Feb 22, 2023

Copy link
Copy Markdown
Member Author

Rebased after #46556

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung
joyeecheung force-pushed the type-int branch from 8a46ff7 to 4becc8f Compare February 22, 2023 11:20
@nodejs-github-bot

nodejs-github-bot commented Feb 22, 2023

Copy link
Copy Markdown
Collaborator

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@nodejs-github-bot

nodejs-github-bot commented Feb 22, 2023

Copy link
Copy Markdown
Collaborator

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

joyeecheung added a commit that referenced this pull request Feb 22, 2023
@joyeecheung
src: use an array for faster binding data lookup
f32aa19
Locally the hashing of the binding names sometimes has significant
presence in the profile of bindings, because there can be collisions,
which makes the cost of adding a new binding data non-trivial,
but it's wasteful to spend time on hashing them or dealing with
collisions at all, since we can just use the EmbedderObjectType
enum as the key, as the string names are not actually used beyond
debugging purposes and can be easily matched with a macro.
And since we can just use the enum as the key, we do not even
need the map and can just use an array with the enum as indices
for the lookup.

PR-URL: #46620
Reviewed-By: Matteo Collina <[email protected]>
Reviewed-By: Anna Henningsen <[email protected]>
Reviewed-By: Chengzhong Wu <[email protected]>
@joyeecheung

joyeecheung commented Feb 22, 2023

Copy link
Copy Markdown
Member Author

Landed in f32aa19

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@joyeecheung joyeecheung closed this Feb 22, 2023
This was referenced Feb 23, 2023
CI Reliability 2023-02-23 nodejs/reliability#504
Open
CI Reliability 2023-02-24 nodejs/reliability#505
Open
@juanarbol juanarbol added the backport-requested-v18.x label Mar 1, 2023
@juanarbol

juanarbol commented Mar 1, 2023

Copy link
Copy Markdown
Member

Would you mind backporting this to v18.x

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

targos pushed a commit that referenced this pull request Mar 13, 2023
@joyeecheung @targos
src: use an array for faster binding data lookup
c0fcad3
Locally the hashing of the binding names sometimes has significant
presence in the profile of bindings, because there can be collisions,
which makes the cost of adding a new binding data non-trivial,
but it's wasteful to spend time on hashing them or dealing with
collisions at all, since we can just use the EmbedderObjectType
enum as the key, as the string names are not actually used beyond
debugging purposes and can be easily matched with a macro.
And since we can just use the enum as the key, we do not even
need the map and can just use an array with the enum as indices
for the lookup.

PR-URL: #46620
Reviewed-By: Matteo Collina <[email protected]>
Reviewed-By: Anna Henningsen <[email protected]>
Reviewed-By: Chengzhong Wu <[email protected]>
@targos targos mentioned this pull request Mar 14, 2023
v19.8.0 release proposal #47087
Merged
targos pushed a commit that referenced this pull request Nov 10, 2023
@joyeecheung @targos
src: use an array for faster binding data lookup
629fc77
Locally the hashing of the binding names sometimes has significant
presence in the profile of bindings, because there can be collisions,
which makes the cost of adding a new binding data non-trivial,
but it's wasteful to spend time on hashing them or dealing with
collisions at all, since we can just use the EmbedderObjectType
enum as the key, as the string names are not actually used beyond
debugging purposes and can be easily matched with a macro.
And since we can just use the enum as the key, we do not even
need the map and can just use an array with the enum as indices
for the lookup.

PR-URL: #46620
Reviewed-By: Matteo Collina <[email protected]>
Reviewed-By: Anna Henningsen <[email protected]>
Reviewed-By: Chengzhong Wu <[email protected]>
@targos targos mentioned this pull request Nov 28, 2023
v18.19.0 release proposal #50953
Merged
sercher added a commit to sercher/graaljs that referenced this pull request Apr 25, 2024
@sercher
src: use an array for faster binding data lookup
a7d28a5
Locally the hashing of the binding names sometimes has significant
presence in the profile of bindings, because there can be collisions,
which makes the cost of adding a new binding data non-trivial,
but it's wasteful to spend time on hashing them or dealing with
collisions at all, since we can just use the EmbedderObjectType
enum as the key, as the string names are not actually used beyond
debugging purposes and can be easily matched with a macro.
And since we can just use the enum as the key, we do not even
need the map and can just use an array with the enum as indices
for the lookup.

PR-URL: nodejs/node#46620
Reviewed-By: Matteo Collina <[email protected]>
Reviewed-By: Anna Henningsen <[email protected]>
Reviewed-By: Chengzhong Wu <[email protected]>
sercher added a commit to sercher/graaljs that referenced this pull request Apr 25, 2024
@sercher
src: use an array for faster binding data lookup
c334df1
Locally the hashing of the binding names sometimes has significant
presence in the profile of bindings, because there can be collisions,
which makes the cost of adding a new binding data non-trivial,
but it's wasteful to spend time on hashing them or dealing with
collisions at all, since we can just use the EmbedderObjectType
enum as the key, as the string names are not actually used beyond
debugging purposes and can be easily matched with a macro.
And since we can just use the enum as the key, we do not even
need the map and can just use an array with the enum as indices
for the lookup.

PR-URL: nodejs/node#46620
Reviewed-By: Matteo Collina <[email protected]>
Reviewed-By: Anna Henningsen <[email protected]>
Reviewed-By: Chengzhong Wu <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@mcollina mcollina mcollina approved these changes
@addaleax addaleax addaleax approved these changes
@legendecas legendecas legendecas approved these changes

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

c++ Issues and PRs that require attention from people who are familiar with C++. lib / src Issues and PRs involving general changes in the lib/ or src/ directories. needs-ci PRs that need a full CI run.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

6 participants

@joyeecheung @nodejs-github-bot @addaleax @juanarbol @mcollina @legendecas
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.