Skip to content

util,assert: improve comparison performance #22197

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
BridgeAR wants to merge 2 commits into from
Closed

util,assert: improve comparison performance #22197

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
6e7cf50
util,assert: improve performance
BridgeAR Aug 6, 2018
3c83e47
fixup: handle c++ error properly
BridgeAR Aug 19, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
util,assert: improve performance 
This significantly improves regular and typed array performance by
not checking the indices keys anymore. This can be done with a V8
API that allows to only retrieve the non indices property keys.
  • Loading branch information
@BridgeAR
BridgeAR committed Aug 19, 2018
commit 6e7cf50dc8e4ca4e7da0276d1e158763783d1b74
81 changes: 37 additions & 44 deletions lib/internal/util/comparisons.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4,6 +4,7 @@ const { compare } = process.binding('buffer');
const { isArrayBufferView } = require('internal/util/types');
const { internalBinding } = require('internal/bootstrap/loaders');
const { isDate, isMap, isRegExp, isSet } = internalBinding('types');
const { getOwnNonIndicesProperties } = process.binding('util');
Comment thread
BridgeAR marked this conversation as resolved.

const ReflectApply = Reflect.apply;

Expand Down Expand Up @@ -106,24 +107,11 @@ function strictDeepEqual(val1, val2, memos) {
if (val1.length !== val2.length) {
return false;
}
const keys = objectKeys(val1);
if (keys.length !== objectKeys(val2).length) {
const keys1 = getOwnNonIndicesProperties(val1);
if (keys1.length !== getOwnNonIndicesProperties(val2).length) {
return false;
}
// Fast path for non sparse arrays (no key comparison for indices
// properties).
// See https://tc39.github.io/ecma262/#sec-ordinaryownpropertykeys
if (val1.length === keys.length) {
if (keys.length === 0 || keys[val1.length - 1] === `${val1.length - 1}`) {
return keyCheck(val1, val2, kStrict, memos, kIsArray, []);
}
} else if (keys.length > val1.length &&
keys[val1.length - 1] === `${val1.length - 1}`) {
const minimalKeys = keys.slice(val1.length);
return keyCheck(val1, val2, kStrict, memos, kIsArray, minimalKeys);
}
// Only set this to kIsArray in case the array is not sparse!
return keyCheck(val1, val2, kStrict, memos, kNoIterator, keys);
return keyCheck(val1, val2, kStrict, memos, kIsArray, keys1);
}
if (val1Tag === '[object Object]') {
return keyCheck(val1, val2, kStrict, memos, kNoIterator);
Expand All @@ -148,18 +136,14 @@ function strictDeepEqual(val1, val2, memos) {
if (!areSimilarTypedArrays(val1, val2)) {
return false;
}
// Buffer.compare returns true, so val1.length === val2.length
// if they both only contain numeric keys, we don't need to exam further.
const keys = objectKeys(val1);
if (keys.length !== objectKeys(val2).length) {
// Buffer.compare returns true, so val1.length === val2.length. If they both
// only contain numeric keys, we don't need to exam further than checking
// the symbols.
const keys1 = getOwnNonIndicesProperties(val1);
if (keys1.length !== getOwnNonIndicesProperties(val2).length) {
return false;
}
if (keys.length === val1.length) {
return keyCheck(val1, val2, kStrict, memos, kNoIterator, []);
}
// Only compare the special keys.
const minimalKeys = keys.slice(val1.length);
return keyCheck(val1, val2, kStrict, memos, kNoIterator, minimalKeys);
return keyCheck(val1, val2, kStrict, memos, kNoIterator, keys1);
} else if (isSet(val1)) {
if (!isSet(val2) || val1.size !== val2.size) {
return false;
Expand All @@ -173,21 +157,10 @@ function strictDeepEqual(val1, val2, memos) {
// TODO: Make the valueOf checks safe.
} else if (typeof val1.valueOf === 'function') {
const val1Value = val1.valueOf();
if (val1Value !== val1) {
if (typeof val2.valueOf !== 'function') {
return false;
}
if (!innerDeepEqual(val1Value, val2.valueOf(), true))
return false;
// Fast path for boxed primitive strings.
if (typeof val1Value === 'string') {
const keys = objectKeys(val1);
if (keys.length !== objectKeys(val2).length) {
return false;
}
const minimalKeys = keys.slice(val1.length);
return keyCheck(val1, val2, kStrict, memos, kNoIterator, minimalKeys);
}
if (val1Value !== val1 &&
(typeof val2.valueOf !== 'function' ||
!innerDeepEqual(val1Value, val2.valueOf(), kStrict))) {
return false;
}
}
return keyCheck(val1, val2, kStrict, memos, kNoIterator);
Expand Down Expand Up @@ -277,7 +250,7 @@ function keyCheck(val1, val2, strict, memos, iterationType, aKeys) {
}
}

if (strict) {
if (strict && arguments.length === 5) {
const symbolKeysA = getOwnPropertySymbols(val1);
if (symbolKeysA.length !== 0) {
let count = 0;
Expand Down Expand Up @@ -310,7 +283,7 @@ function keyCheck(val1, val2, strict, memos, iterationType, aKeys) {
if (aKeys.length === 0 &&
(iterationType === kNoIterator ||
iterationType === kIsArray && val1.length === 0 ||
val1.size === 0)) {
val1.size === 0)) {
return true;
}

Expand Down Expand Up @@ -578,8 +551,28 @@ function objEquiv(a, b, strict, keys, memos, iterationType) {
}
} else if (iterationType === kIsArray) {
for (; i < a.length; i++) {
if (!innerDeepEqual(a[i], b[i], strict, memos)) {
if (hasOwnProperty(a, i)) {
if (!hasOwnProperty(b, i) ||
!innerDeepEqual(a[i], b[i], strict, memos)) {
return false;
}
} else if (hasOwnProperty(b, i)) {
return false;
} else {
// Array is sparse.
const keysA = objectKeys(a);
i++;
for (; i < keysA.length; i++) {
const key = keysA[i];
if (!hasOwnProperty(b, key) ||
!innerDeepEqual(a[key], b[i], strict, memos)) {
return false;
}
}
if (keysA.length !== objectKeys(b).length) {
return false;
}
return true;
}
}
}
Expand Down
18 changes: 18 additions & 0 deletions src/node_util.cc
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -16,6 +16,22 @@ using v8::Proxy;
using v8::String;
using v8::Value;

static void GetOwnNonIndicesProperties(
const FunctionCallbackInfo<Value>& args) {
Environment* env = Environment::GetCurrent(args);
Local<Context> context = env->context();

v8::Local<v8::Object> object = args[0].As<v8::Object>();
Copy link
Copy Markdown
Contributor

@ryzokuken ryzokuken Aug 17, 2018

Choose a reason for hiding this comment

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

I couldn't see if we have a check for this in-place. Will we crash if this fails? That said, does it ever really realistically fail?

Copy link
Copy Markdown
Member Author

@BridgeAR BridgeAR Aug 17, 2018

Choose a reason for hiding this comment

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

Yes, it would crash. But this API is only used internally and not exposed. That's why I did not add a safeguard against wrong input values.

Copy link
Copy Markdown
Member Author

@BridgeAR BridgeAR Aug 19, 2018

Choose a reason for hiding this comment

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

I added a check for that as well.


// Return only non-enumerable properties by default.
v8::Local<v8::Array> properties = object
->GetPropertyNames(context, v8::KeyCollectionMode::kOwnOnly,
v8::ONLY_ENUMERABLE,
v8::IndexFilter::kSkipIndices)
.ToLocalChecked();
Copy link
Copy Markdown
Contributor

@ryzokuken ryzokuken Aug 17, 2018

Choose a reason for hiding this comment

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

Same as above, does this ever fail? Instead, you could try something like

if(!object->GetPropertyNames(...).ToLocal(&properties)) return;

Copy link
Copy Markdown
Member Author

@BridgeAR BridgeAR Aug 17, 2018

Choose a reason for hiding this comment

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

I am not aware about this. I use it as it's done in the V8 tests. @nodejs/v8 do we have to add a guard against this?

Copy link
Copy Markdown
Contributor

@ryzokuken ryzokuken Aug 17, 2018

Choose a reason for hiding this comment

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

I think you do, yes. The whole point of ToLocalChecked is that you must've checked the value earlier. You could either add a CHECK statement before this one, in which case it'll still crash (probably in a much better manner, but crash nonetheless) or use ToLocal as I did above.

Copy link
Copy Markdown
Member

@joyeecheung joyeecheung Aug 17, 2018 •
edited
Loading

Choose a reason for hiding this comment

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

Since the original behavior of Object.keys is to throw if the keys cannot be collected, it makes more sense to return if the maybe is empty and throw in the JS land. (I guess this should fail if you throw an error in the enumerate proxy handler, though it is deprecated? EDIT: nope, it's not in V8 anymore)

Copy link
Copy Markdown
Contributor

@ryzokuken ryzokuken Aug 17, 2018

Choose a reason for hiding this comment

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

Exactly. Returning (throwing) if the MaybeLocal is empty seems to be the most logical thing to do. In V8, one would use the macro ASSIGN_RETURN_FAILURE_ON_EXCEPTION which is essentially:

if (!call(...)->ToLocal(&result) {
  DCHECK(isolate->has_pending_exception());
  return;
}

Copy link
Copy Markdown
Member

@addaleax addaleax Aug 19, 2018

Choose a reason for hiding this comment

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

Yes, please use @ryzokuken’s suggestion here, I think this could otherwise fail when inspecting Proxies with an ownKeys handler. A CHECK() would have the same behaviour as ToLocalChecked(), so that’s not enough either.

Copy link
Copy Markdown
Member Author

@BridgeAR BridgeAR Aug 19, 2018

Choose a reason for hiding this comment

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

Thanks a lot! I learned something through your comments 👍. It is now handled as suggested.

args.GetReturnValue().Set(properties);
}

static void GetPromiseDetails(const FunctionCallbackInfo<Value>& args) {
// Return undefined if it's not a Promise.
if (!args[0]->IsPromise())
Expand Down Expand Up @@ -177,6 +193,8 @@ void Initialize(Local<Object> target,
env->SetMethodNoSideEffect(target, "getProxyDetails", GetProxyDetails);
env->SetMethodNoSideEffect(target, "safeToString", SafeToString);
env->SetMethodNoSideEffect(target, "previewEntries", PreviewEntries);
env->SetMethodNoSideEffect(target, "getOwnNonIndicesProperties",
GetOwnNonIndicesProperties);

env->SetMethod(target, "startSigintWatchdog", StartSigintWatchdog);
env->SetMethod(target, "stopSigintWatchdog", StopSigintWatchdog);
Expand Down