First instinct (before digging deeply): it's possible that we won't be able to get the binding overhead to be small compared to the cost of a matrix multiply (ultimately there's a lot of state to set up).

It might be easier to ship this using extras and a plain JS array, or possibly the internal FixedArray wrapper. The most extreme measure possible would be to actually create a V8 stub for this, but that seems radical.

Why does this profile show creating strings, computing hashes and doing SlowEquals? Are you sure it's looking at the right thing?

The way the bindings work for this is:

  ExceptionState exceptionState(info.GetIsolate(), ExceptionState::ExecutionContext, "DOMMatrixReadOnly", "multiply");

  DOMMatrixReadOnly* impl = V8DOMMatrixReadOnly::toImpl(info.Holder());

  DOMMatrixInit other;
  if (!isUndefinedOrNull(info[0]) && !info[0]->IsObject()) {
    exceptionState.throwTypeError("parameter 1 ('other') is not an object.");

    return;
  }
  V8DOMMatrixInit::toImpl(info.GetIsolate(), info[0], other, exceptionState);
  if (exceptionState.hadException())
    return;

  DOMMatrix* result = impl->multiply(other, exceptionState);
  if (exceptionState.hadException()) {
    return;
  }
  v8SetReturnValue(info, result);

V8DOMMatrixInit::toImpl does this:
https://cs.chromium.org/chromium/src/out/Debug/gen/blink/bindings/core/v8/V8DOMMatrixInit.cpp?q=V8DOMMatrixInit::toImpl&sq=package:chromium&l=27

which does:

  if (isUndefinedOrNull(v8Value)) {
    return;
  }
  if (!v8Value->IsObject()) {
    exceptionState.throwTypeError("cannot convert to dictionary.");
    return;
  }

  v8::TryCatch block(isolate);


doing all the same checks again, and creating another try catch block.

It's also doing toDouble(isolate, aValue, exceptionState); repeatedly for each element, but this is a packed number array, so that's not needed. We could have a fast path that notices it's a non-sparse array of numbers and just copies them out instead.

I'd be curious how slow the C++ version would be if you wrote custom bindings and just mimicked exactly what this polyfill is doing.

Good questions. I've got no idea.

It almost certainly shows string table lookup because it needs to read all of the members by their string key (because DOMMatrixInit can be anything with those named properties).

That could almost certainly be made faster by simply having a quick check if the DOMMatrixInit happens to already be a DOMMatrixReadOnly, and casting in that case. (The lookups are needed in the general case, though.)

Upon further thought, I don't think that fast path is legal without still checking for the properties. I could do this:

var matrix;
matrix instanceof DOMMatrix; // true
Object.defineProperty(matrix, 'm11', { value: 0 });
otherMatrix.multiply(matrix);

And I think the spec as written requires us to use the overridden m11 property, rather than the one internal to the DOM object.

Is it feasible to mark the object as "tainted" when it's not a pure DOMMatrix?

I think V8 knows this internally (a check of the prototype + a check of the object's map), but I don't think it's exposed (aside from querying its own properties, of course).

Wasn't the plan/suggestion to implement this via v8 extras ? (cf. intent-to-implement, https://groups.google.com/a/chromium.org/forum/#!topic/blink-dev/V_bJNtOg0oM )

if there's a fixed set of strings, you could also internalize them, so you don't have to create new ones all the time.

otoh, depending on how the JS side invokes the code, they also might end up constantly creating the same string, and then it's slow no matter what :/

Internalizing the strings is probably something the dictionary bindings code should be doing regardless, though we'll still pay the cost of a lookup in the V8 string table (the V8PerIsolateData one would be better, but probably requires creating static copies of the keys which would be more work).

That still doesn't skip the string table lookup and property lookup that are larger in chrishtr's profile, though.

#10: There was some back-and-forth about whether it should be implemented with extras or traditional Blink bindings. Maybe someone more familiar can summarize how we got to here?

> #10: There was some back-and-forth about whether it should be implemented with extras or traditional Blink bindings. Maybe someone more familiar can summarize how we got to here?

My understanding is that certain people in Chrome want to require that any Web IDL-using specs implemented with V8 extras have part of their JS generated from the .idl files, to ensure that the .idl files stay as a valid source of truth.

As such I spent some time exploring what that would look like in https://github.com/domenic/v8-extras-geometry. If we were to go down that route it would involve actually writing and maintaining such a code generator, which I'm excited about, but hasn't had a lot of discussion yet.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/de5f94759b81ede2952f75f8eb63ca917d2bb2aa

commit de5f94759b81ede2952f75f8eb63ca917d2bb2aa
Author: jbroman <jbroman@chromium.org>
Date: Fri Jan 27 20:56:07 2017

[Bindings] Internalize generated dictionary keys using v8AtomicString.

These are small, fixed strings frequently used for property access.
It makes sense for them to be internalized.

BUG=685748

Review-Url: https://codereview.chromium.org/2658173003
Cr-Commit-Position: refs/heads/master@{#446763}

[modify] https://crrev.com/de5f94759b81ede2952f75f8eb63ca917d2bb2aa/third_party/WebKit/Source/bindings/templates/dictionary_v8.cpp.tmpl
[modify] https://crrev.com/de5f94759b81ede2952f75f8eb63ca917d2bb2aa/third_party/WebKit/Source/bindings/tests/results/core/V8TestDictionary.cpp
[modify] https://crrev.com/de5f94759b81ede2952f75f8eb63ca917d2bb2aa/third_party/WebKit/Source/bindings/tests/results/core/V8TestDictionaryDerived.cpp
[modify] https://crrev.com/de5f94759b81ede2952f75f8eb63ca917d2bb2aa/third_party/WebKit/Source/bindings/tests/results/core/V8TestInterfaceEventInit.cpp
[modify] https://crrev.com/de5f94759b81ede2952f75f8eb63ca917d2bb2aa/third_party/WebKit/Source/bindings/tests/results/core/V8TestPermissiveDictionary.cpp

While we should consider things like v8 bindings in js, we also need to make the C++ bindings faster, and having js bindings puts a large complexity and performance burden on C++ side features that need to use the same objects. 

ex. We need to create typed arrays inside C++ code too, and that results in the very complicated split between the C++ core/dom/DOMTypedArray code and the code inside v8.

ex. Making DOMMatrix be in JS means accessing it from inside the style system becomes much slower since the v8 API boundary is expensive. So while it makes this micro benchmark better it makes the TypedOM API slower.

I'm also curious if the overhead we see here matters for real pages. We're running a very intense benchmark that easily ends up inside Turbofan or Crankshaft. Most content may never even get there, so the C++ bindings might not matter.

Are those properties read using the same v8 string over and over again? It's possible that the incoming string needs to be internalized which we currently need to do over and over again if we can't do it inplace (which is common). Jakob's ThinStrings should fix this though.

Note that internally we're moving away from implementing builtins in JS since it doesn't result in predictible good performance.

#16: Moving from JS to Turbofan stubs, though, right? Or is that including the overhead of setting up v8::FunctionCallbackInfo and the rest?

Discussing with verwaest@ one thing that occurs to me is this is benchmarking code that's running in a very tight loop and hasn't had to deal with varied inputs that can result in de-opts and going megamorphic. For example what happens when we do .multiply() with dictionaries having various subsets of keys and also passing a DOMMatrix directly?

Good question. I updated the benchmark to test that (let me know what you think of the changes) and am now seeing closer results, with the polyfill clocking in at ~450 ms to native's ~500 ms. So yeah, the advantage does definitely drop, although it's still faster (and certainly not slower as might have been predicted).

Those numbers seem legit. Lets focus on trying to close the 11% gap you have there which seems like a tractable amount.

I also don't think that gap is large enough to prevent shipping. We should ship the C++ implementation and focus on making the bindings faster with time. Keeping all the specs that want to depend on DOMRect/DOMMatrix/DOMQuad/DOMPoint, etc. blocked without a real world benchmark where this binding overhead is the bottleneck seems bad. Looking at many pages over the past year I've not seen one where this kind of bindings overhead is the problem. If these bindings turn out to be a problem in real world content we can explore code stub or JS bindings.

#17: Yes, to TF stubs for the fastest version. Internal C++ is already faster too in many cases though.

Where can I see the changes? Just making it megamorphic isn't enough though. The megamorphic cache in the real-world is less effective than in a typical micro-benchmark because it's a central cache shared between all code running in a native context. Whenever the cache misses you have to go through the runtime which is very expensive. If you need to do that for each inline cache performance degenerates. That's where staying in C++ is cheaper: you don't need to cross the boundary that frequently.

That's also the reasoning behind having a more declarative API: the longer we can stay within one world the faster it will be.

The changes are in https://rawgit.com/domenic/v8-extras-geometry/master/bench/index.html from the OP. You can see the diff at https://github.com/domenic/v8-extras-geometry/commit/b26732f2bd0dea4c4cd1a23b1a7de99c620c0058

In that case you'll still hit the polymorphic case, not the megamorphic case; which is much faster. The reason why you get a large slowdown is because you're additionally optimizing the JS which is much worse in the polymorphic case. However, that's still much more optimal than what you'd get if it's megamorphic.

You can try >4 object types to end up with worse optimized code. Additionally, you'd need to run other code in between to see the final perf you'd end up with.

This type of microbenchmarking just leads to confused performance understanding.

I just re-ran the perf profile, and it's still dominated by what look to me like bindings
overhead.

My main concern with shipping this design is whether it prevents peak-performance
matrix math primitives to be built on top of it. But looking at the API, I can imagine
various optimizations that get rid of the overhead if it becomes important...so I guess it's
ok to to ship as is.

I looked a bit into this, and have some questions:

- would it be possible to cache those atomic strings in per-isolate-storage somewhere so you can avoid reinternalizing them?

- in #7 you discussed that the spec is written such that we need to take actual properties into account. I haven't read the spec, but I suppose this is true on both sides? The current implementation does not respect this, however:

var a = new DOMMatrixReadOnly([2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]);
var b = new DOMMatrixReadOnly([4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]);
Object.defineProperty(b, "a", {value: 100})
Object.defineProperty(b, "m11", {value: 100})
a.multiply(b) -> [200, ...]
b.multiply(a) -> [8, ...]

If this needs to be fix, to fix this you'll probably make it 2x slower though :)


If point 1 works, I could imagine extending this in a kind of API inline cache that can store information about how V8 accessed properties for subsequent runs. That would improve perf to similar to the JS version. The cache object would need to be stored by Blink though. And it just makes V8 the fast path from blink back into blink. I presume we actually want the problem highlighted in #7 somehow; come up with a solution that allows blink to figure out that we're dealing with a pristine DOMMatrixReadOnly object... I'll have to think about this.

1. I've thought about doing that (if it's worth doing, it's probably worth doing for all dictionaries). I have not gotten around to implementing it or checking whether constructing strings is really the slow part (as opposed, say, entering V8 and doing the property lookup).

2. My reading of the spec is that the current implementation is correct (i.e. the receiver looks directly at its own internal values, but treats the argument as a dictionary and thus goes through property lookup). I agree that this asymmetry is weird. I think it's intended to allow you to multiply by some matrix you constructed in JS without explicitly creating a DOMMatrixReadOnly yourself.

I could imagine it being modified to treat instances of DOMMatrixReadOnly specially (and look at their internal values), but I'm not a spec expert.

Sounds good, but odd, on the spec part. It would definitely be easier if we didn't have to read out those properties as regular JS properties.

There's quite some overhead from internalizing strings:

3.28%	3.79%	C++v8::internal::StringTable::LookupKey(v8::internal::Isolate*, v8::internal::HashTableKey*)
2.70%	3.12%	C++v8::internal::String::IsOneByteEqualTo(v8::internal::Vector<unsigned char const>)
1.35%	1.56%	C++unsigned int v8::internal::StringHasher::HashSequentialString<unsigned char>(unsigned char const*, int, unsigned int)
0.77%	0.89%	C++v8::internal::StringHasher::GetHashField()
0.77%	0.89%	C++v8::String::NewFromOneByte(v8::Isolate*, unsigned char const*, v8::String::NewStringType, int)
0.58%	0.67%	C++v8::internal::SequentialStringKey<unsigned char>::Hash()
0.19%	0.22%	C++v8::internal::OneByteStringKey::IsMatch(v8::internal::Object*)

The spec is quite intentional here. In general on the web platform, inputs are assumed to be arbitrary objects of a particular shape ("dictionaries"), and there are certain platform classes ("interfaces") that happen to have that shape.

This is more obvious with cases like DOMPoint: anything that accepts a a conceptual point should accept a { x, y, z, w } object of any type, not just instances of DOMPoint.

It would be possible to introduce a special-case path that brand-checks the input and treats DOMPoint instances specially by looking at their internal values. But that would be weird and inconsistent with the rest of the platform, which uniformly treats inputs as just JavaScript objects.

Why isn't this the case for the receiver in that case, though?

By the receiver you mean the this value? I guess because that isn't thought of as "input". You're dealing with a known type, not arbitrary input.

In any case, I guess the best ways forward are:
1) cache atomic strings in blink to avoid repeated internalization
2) implement a kind of API IC to speed up property access through the API similarly to property access within V8
3) think about a way to be able to quickly do a larger structure verification, so we can just cast the object to a DOMMatrixReadOnly.

Just verifying: does anyone think the current spec is incompatible with a
performant implementation? Or is it just a matter of optimizing it?

The comments about "2x slower" worry me.

With this kind of spec we have to jump through a lot of hoops to make it fast. We've done this before; e.g., RegExp has similar issues. But with DOMMatrix crossing the V8/Blink boundary it becomes especially challenging since we don't want to expose too many details. I'm sure that if the incoming argument conversion wasn't part of multiply, it would be 10x faster *at least*.

Making it that fast is going to be very tricky. We can make property access spend almost no time in V8 (with the suggested API ICs) but then there'll always still be the boundary crossing from Blink to V8 back to Blink. We're still talking probably at least 3x overhead compared to the optimal performance. And it requires a lot more machinery than e.g., just requiring the argument to be a DOMMatrixReadOnly object from which we just read internal fields.

To just pass the DOMMatrixReadOnly object as argument would require conversion of non-DOMMatrixReadOnly objects before passing it to multiply. Just like for the receiver (this value); it would ignore actual properties on the object but just read internal slots.

Actually implement the fastest path could even be done with conversion of non-DOMMatrixReadOnly objects. This was already suggested in #6: if we are allowed to ignore regular named properties if the argument ends up being a DOMMatrixReadOnly, we can just do the multiply after verifying the type. This obviously changes behavior, but I somewhat doubt anybody would ever care (someone might try for fun, realized it doesn't work and say "meh".)

For my own edufication, I prototyped a couple approaches to slim down the dictionary access (hacked into custom bindings, but would probably just be changed in the bindings templates for all dictionaries if adopted):

1. Keeping an array of eternal handles on the dictionary keys around (held statically in my prototype patch, but obviously would be in V8PerIsolateData in a landable patch).

Blink patch: https://codereview.chromium.org/2750763005

2. Going further, and holding one eternal handle on a V8 object holding all of the dictionary keys, and passing that object to V8 so that it can read one after another, generally not needing to return to Blink (for a typical DOMMatrixInit, it does this all in one V8 API call -- in general, multiple can be needed so that the WebIDL type conversion happens in the right order).

V8 side: https://codereview.chromium.org/2756523004
Blink side: https://codereview.chromium.org/2749403002
(yes, both would need changes to be remotely landable)


https://rawgit.com/domenic/v8-extras-geometry/master/bench/index.html yields (N.B. these results are rather noisy)

master

count	Polyfill	Native
10	0.09500000000116415ms	0.17000000001280569ms
100	0.2900000000081491ms	0.6699999999982538ms
1000	3.150000000008731ms	6.365000000005239ms
10000	28.319999999992433ms	64.19000000000233ms
100000	275.93000000000757ms	656.8050000000076ms

count	Polyfill	Native
10	0.06999999997788109ms	0.17000000001280569ms
100	0.27999999999883585ms	0.6499999999941792ms
1000	2.845000000001164ms	6.324999999982538ms
10000	26.95999999999185ms	66.33999999999651ms
100000	271.445000000007ms	621.039999999979ms


eternal keys

count	Polyfill	Native
10	0.14500000000407454ms	0.09500000000116415ms
100	0.7200000000011642ms	0.46000000000640284ms
1000	6.69999999999709ms	4.369999999995343ms
10000	27.125ms	43.88500000000931ms
100000	266.6850000000122ms	447.2600000000093ms

count	Polyfill	Native
10	0.1150000000197906ms	0.11499999999068677ms
100	0.3099999999976717ms	0.4100000000180444ms
1000	3.5200000000186265ms	3.779999999998836ms
10000	33.32500000001164ms	38.375ms
100000	264.3549999999959ms	400.61499999997613ms


dictionary schema

count	Polyfill	Native
10	0.08499999999185093ms	0.09500000000116415ms
100	0.235000000015134ms	0.33999999999650754ms
1000	2.279999999998836ms	3.305000000007567ms
10000	22.86500000000524ms	33.33999999999651ms
100000	208.13499999999476ms	335.62499999998545ms

count	Polyfill	Native
10	0.14500000000407454ms	0.10500000001047738ms
100	0.6549999999988358ms	0.4250000000029104ms
1000	8.444999999999709ms	4.105000000003201ms
10000	30.489999999990687ms	40.25999999999476ms
100000	254.13500000000204ms	407.0699999999997ms


So locally, I see about 2.4x slower (native vs polyfill) at master, and only 1.6x slower (native vs polyfill) with either approach of caching the keys. It looks like the dictionary schema approach might be _slightly_ faster, but it's well within measurement noise and adds complexity to the V8 API which the plain "just-hold-lots-of-eternal-handles" does not. This suggests to me that the cost of re-entering V8 for each Get isn't too bad for this use case.

Polyfill still handily beats native without yet further optimizations, though. (I bet a brand check would be super-duper fast, but it seems from what Domenic says the spec is unlikely to change to allow a brand check.)

For completeness, also prototyped a brand-check (regardless of whether or not we want to change the spec, it seems a reasonable point of reference). Slowdown becomes 1.3-1.4x across all three different kinds of inputs (two of which are dictionaries which fail the brand-check and have to read properties).

count	Polyfill	Native
10	0.08499999999912689ms	0.09499999999752617ms
100	0.2900000000008731ms	0.30500000000029104ms
1000	2.5750000000007276ms	2.9950000000026193ms
10000	22.340000000000146ms	29.18000000000029ms
100000	219.4900000000016ms	307.12500000000364ms

count	Polyfill	Native
10	1.8999999999941792ms	0.10499999999592546ms
100	4.949999999982538ms	0.36999999998079147ms
1000	16.73499999998603ms	2.94000000001688ms
10000	38.43499999999767ms	29.464999999996508ms
100000	279.66500000000815ms	365.320000000007ms

If we zoom in on the case of a native DOMMatrixReadOnly instance, the brand check makes native beat Domenic's polyfill easily, 5-6x:

count	Polyfill	Native
10	0.13500000000021828ms	0.05499999999847205ms
100	0.6650000000008731ms	0.0750000000007276ms
1000	6.69499999999789ms	0.5849999999991269ms
10000	26.595000000001164ms	4.844999999999345ms
100000	266.0499999999993ms	47.37499999999818ms

count	Polyfill	Native
10	0.11999999999898137ms	0.040000000000873115ms
100	0.2999999999992724ms	0.05499999999665306ms
1000	2.889999999999418ms	0.3949999999967986ms
10000	28.489999999997963ms	3.930000000000291ms
100000	213.72999999999956ms	38.875ms

In this patch, our handling of other kinds of matrix is not optimized (we could still use an approach to improve the speed of reading other dictionaries).

Patch: https://codereview.chromium.org/2747383003

Awesome! I presume we could use something similar to the eternal keys if we want to implement API inline caches; which likely much more significantly boost performance than bulk-reading properties. Currently there's no real fast way to read properties in C++; but we're close to transforming all our ICs to a data-driven approach. They have the advantage that we could use them in C++ as well to fast-access objects.

I discussed offline with some of the people on this bug. From the discussions,
it sounds like:

* A fast path (checking whether the developer did anything to mess with the
"regular" DOMMatrixReadOnly") that is about as fast as the brand check should be feasible.
* It should be ok to expose an API from v8 to bindings to make that happen,
and internally to v8 there is already information computed to this effect.

To check that we need a way to check that an instance still has the initial map of DOMMatrixReadOnly (since there are no properties on the object itself right?). That's easy to do. Is this a reusable optimization?

We also need to check that its prototype is still in the original state (otherwise accessors could have been replaced by other things I presume). We internally only track whether a prototype was modified by invalidating a "cell". We would probably need to cache and verify that cell on the blink side before taking the fast path. Just adding a new method to the prototype or receiver would invalidate the cell as well and put you on the slow path.

I don't know how common it is for people to modify the prototype or receiver in ways that wouldn't actually require going off the fast path (like adding extra methods to the prototype, or adding expandos to the object).

Worth noting that here we actually want the initial map of DOMMatrixReadOnly _or any derived IDL interface_ (at the moment, that's just DOMMatrixReadOnly and DOMMatrix, I think). I don't think this affects the V8 API (we should be able to handle it on the Blink side), but just in case I figured I'd mention it.

As far as re-use, I can't think of another case where we have this thing happening (where we accept a dictionary which is often a DOM object implementing the dictionary interface). domenic@, do you know if this is a common pattern?

> As far as re-use, I can't think of another case where we have this thing happening (where we accept a dictionary which is often a DOM object implementing the dictionary interface). domenic@, do you know if this is a common pattern?

This is fairly common. A first approximation is to find all dictionaries named "init": https://codesearch.chromium.org/search/?q=file:Init.idl+package:%5Echromium$&type=cs . Events account for a lot of those results, and it's somewhat rare to actually use an event instance to initialize another event, although not unheard of. Discounting events, we still have TouchInit, DOMQuadInit/DOMRectInit/DOMPointInit/DOMMatrixInit, ResponseInit, and MediaMetadataInit all within the first few pages.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/53d467c4d4be2da1882d9c17a4384906a7f6d7e2

commit 53d467c4d4be2da1882d9c17a4384906a7f6d7e2
Author: jbroman <jbroman@chromium.org>
Date: Thu Mar 30 18:11:49 2017

[Bindings] Cache handles for dictionary keys on V8PerIsolateData.

This reduces APK size by about 20 KiB (because the work to make the dictionary
keys exists in one place, out-of-line) and saves work looking up keys in the
internalized string table. On the DOMMatrix multiply benchmark, this reduces
the overhead compared to the polyfill from 2.4x to 1.6x (on my workstation).

BUG=685748

Review-Url: https://codereview.chromium.org/2751263002
Cr-Commit-Position: refs/heads/master@{#460824}

[modify] https://crrev.com/53d467c4d4be2da1882d9c17a4384906a7f6d7e2/third_party/WebKit/Source/bindings/core/v8/V8PerIsolateData.cpp
[modify] https://crrev.com/53d467c4d4be2da1882d9c17a4384906a7f6d7e2/third_party/WebKit/Source/bindings/core/v8/V8PerIsolateData.h
[modify] https://crrev.com/53d467c4d4be2da1882d9c17a4384906a7f6d7e2/third_party/WebKit/Source/bindings/templates/dictionary_v8.cpp.tmpl
[modify] https://crrev.com/53d467c4d4be2da1882d9c17a4384906a7f6d7e2/third_party/WebKit/Source/bindings/tests/results/core/V8TestDictionary.cpp
[modify] https://crrev.com/53d467c4d4be2da1882d9c17a4384906a7f6d7e2/third_party/WebKit/Source/bindings/tests/results/core/V8TestDictionaryDerived.cpp
[modify] https://crrev.com/53d467c4d4be2da1882d9c17a4384906a7f6d7e2/third_party/WebKit/Source/bindings/tests/results/core/V8TestInterfaceEventInit.cpp
[modify] https://crrev.com/53d467c4d4be2da1882d9c17a4384906a7f6d7e2/third_party/WebKit/Source/bindings/tests/results/core/V8TestPermissiveDictionary.cpp

This issue has been Available for over a year. If it's no longer important or seems unlikely to be fixed, please consider closing it out. If it is important, please re-triage the issue.

Sorry for the inconvenience if the bug really should have been left as Available.

For more details visit https://www.chromium.org/issue-tracking/autotriage - Your friendly Sheriffbot

Jeremy, could you triage this?