Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
19541010:
Implement optimized objectInfo structure (Closed)
|
Created:
7 years, 5 months ago by rafaelw Modified:
7 years, 3 months ago Base URL:
https://github.com/v8/v8.git@bleeding_edge Visibility:
Public. |
DescriptionThis patch implements optimized objectInfo structure which manages the set of observers associated with an object and the changeRecord types which they accept.
Observation in the normal case (Object.observe, default accept types, one observer) now allocates fewer objects and unobservation no longer needs to scan and splice an InternalArray -- making the combined speed of observe/unobserve about 200% faster.
This patch implements the following optimizations:
-objectInfo is initially created without any connected objects or arrays. The first observer is referenced directly by objectInfo, and when a second observer is added, changeObservers converts to a mapping of callbackPriority->observer, which allows for constant time registration/de-registration.
-observer.accept and objectInfo.performing are conceptually the same data-structure. This is now directly represented as an abstract "TypeMap" which can later be optimized to be a smi in common cases, (e.g: https://codereview.chromium.org/19269007/).
-objectInfo observers are only represented by an object with an accept typeMap if the set of accept types is non-default
R=rossberg@chromium.org
Committed: https://code.google.com/p/v8/source/detail?r=16629
Patch Set 1 #Patch Set 2 : dont use closure for delivery #Patch Set 3 : added comments #
Total comments: 22
Patch Set 4 : cr comments, more refactoring #Patch Set 5 : rebase #
Total comments: 18
Patch Set 6 : cr changes #Patch Set 7 : moar #Patch Set 8 : cr changes #Patch Set 9 : whitespace #Patch Set 10 : fix cctest #Messages
Total messages: 17 (0 generated)
https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:35: observationState.pendingObservers = { __proto__: null }; Note that this patch removes all uses of InternalArrays where a mapping of priority->object is needed. The appears to be a bug related specifically with InternalArray which causes them to allocate too much memory when used this way.
I have to say this code is getting a little bit hard to read. I've got one suggestion below for making it a little clearer (making TypeMap into a class), and I think you might want to do the same for ObjectInfo. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:79: return { __proto__: null }; Have you thought about making this a proper class? You have 'add', 'remove', and 'has' methods below, they just happen to have free-function syntax at the moment. It's possible ObjectInfo might benefit from similar treatment. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:93: AddToTypeMap(typeMap, typeList[i], true); Not sure it's worth calling AddToTypeMap here since you need to pass the ignoreDuplicate argument. I think typeMap[type] = 1 would be clearer, and drop the ignoreDuplicate arg on AddToTypeMap. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:114: var defaultAccept = CreateTypeMapFromList(new InternalArray( No need to use an InternalArray here, you can just use [] for readability. CreateTypeMapFromList already has to work properly on regular arrays since you pass in the user-supplied acceptList from CreateObserver (and moreover, this is happening at bootstrapping time). I'd also give this a somewhat longer name (defaultAcceptTypes) since you're in the builtin-global namespace here. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:144: return TypeMapsAreDisjoint(ObjectGetPerformingTypes(objectInfo), This is the only call to TypeMapsAreDisjoint(); I think it'd be clearer to inline it here (especially since you have more info about what typeMap1 and typeMap2 are in this case, e.g., typeMap1 is likely to be smaller, and typeMap2 cannot be null). https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:199: function ObjectAddPerfomingType(objectInfo, type) { Typo: s/Perfoming/Performing/ https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:207: if (objectInfo.performingCount) a "> 0" would make this clearer to me; and this and the above could be combined: if (--objectInfo.performingCount > 0) but maybe that's just my C brain talking. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:210: objectInfo.performing = null; Is it worth nulling this out? It seems like that'll just force us to allocate the performing typemap again next time an array operation occurs. I guess the idea is to save us steady-state memory? https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:214: return objectInfo.performingCount ? objectInfo.performing : null; Maybe a > 0 here too? https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:245: var priority = GetCallbackPriority(callback); I don't think calling GetCallbackPriority() makes sense here; I had to read it a couple times to make sure you weren't going to overwrite an actual callbackInfo object. Instead, I'd access the map directly (which isn't breaking any encapsulation since you're already calling set() on it below). Just change this line to var priority = callbackInfoMap.get(callback); https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:492: for (var i in pendingObservers) { Can you change this 'i' to 'priority' to match elsewhere?
https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:79: return { __proto__: null }; I have a follow-on patch that optimizes TypeMap to be a smi in the common case. In general, the pattern I'm trying to create this this file is that there are "classes" which have varying representations (a default one and an "optimized" one for the common cases). I've done more refactoring so that most of the code now follows a "C-style-class" convention. e.g. var tm = TypeMapCreate(); TypeMapAddType(tm, 'foo'); TypeMapRemoveType(tm, 'foo'); Hopefully, this makes it more clear. Note that I tried implementing JS class structure with ObjectInfo (which I don't think needs an optimized representation), but it badly regressed perf. It looks to me like creating an object with a non-default Object prototype is substantially slower (including null). Also the new operator appears to substantively impact the setup time. On 2013/07/23 21:48:08, adamk wrote: > Have you thought about making this a proper class? You have 'add', 'remove', and > 'has' methods below, they just happen to have free-function syntax at the > moment. > > It's possible ObjectInfo might benefit from similar treatment. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:93: AddToTypeMap(typeMap, typeList[i], true); I'd like to keep the method calls for all "classes", a) for clarity, and b) in this case, because I plan a follow-up patch which allows TypeMap to be a smi (and the method will handle the polymorphism). On 2013/07/23 21:48:08, adamk wrote: > Not sure it's worth calling AddToTypeMap here since you need to pass the > ignoreDuplicate argument. I think > > typeMap[type] = 1 > > would be clearer, and drop the ignoreDuplicate arg on AddToTypeMap. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:114: var defaultAccept = CreateTypeMapFromList(new InternalArray( Both done. On 2013/07/23 21:48:08, adamk wrote: > No need to use an InternalArray here, you can just use [] for readability. > CreateTypeMapFromList already has to work properly on regular arrays since you > pass in the user-supplied acceptList from CreateObserver (and moreover, this is > happening at bootstrapping time). > > I'd also give this a somewhat longer name (defaultAcceptTypes) since you're in > the builtin-global namespace here. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:144: return TypeMapsAreDisjoint(ObjectGetPerformingTypes(objectInfo), Again, I want to keep TypeMap methods encapsulated for a follow-on patch. On 2013/07/23 21:48:08, adamk wrote: > This is the only call to TypeMapsAreDisjoint(); I think it'd be clearer to > inline it here (especially since you have more info about what typeMap1 and > typeMap2 are in this case, e.g., typeMap1 is likely to be smaller, and typeMap2 > cannot be null). https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:199: function ObjectAddPerfomingType(objectInfo, type) { On 2013/07/23 21:48:08, adamk wrote: > Typo: s/Perfoming/Performing/ Done. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:207: if (objectInfo.performingCount) The comparison is now gone. On 2013/07/23 21:48:08, adamk wrote: > a "> 0" would make this clearer to me; and this and the above could be combined: > > if (--objectInfo.performingCount > 0) > > but maybe that's just my C brain talking. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:210: objectInfo.performing = null; Fair enough. Removing. On 2013/07/23 21:48:08, adamk wrote: > Is it worth nulling this out? It seems like that'll just force us to allocate > the performing typemap again next time an array operation occurs. I guess the > idea is to save us steady-state memory? https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:214: return objectInfo.performingCount ? objectInfo.performing : null; On 2013/07/23 21:48:08, adamk wrote: > Maybe a > 0 here too? Done. https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:245: var priority = GetCallbackPriority(callback); The issue here is that CallbackInfo is polymorphic. If you look at the impl of the GetCallbackPriority, it needs to detect what state it's in. I'm g On 2013/07/23 21:48:08, adamk wrote: > I don't think calling GetCallbackPriority() makes sense here; I had to read it a > couple times to make sure you weren't going to overwrite an actual callbackInfo > object. > > Instead, I'd access the map directly (which isn't breaking any encapsulation > since you're already calling set() on it below). Just change this line to > > var priority = callbackInfoMap.get(callback); https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:245: var priority = GetCallbackPriority(callback); So this is really CallbackInfoGetPriority(callback). Hopefully this is clearer now. On 2013/07/23 21:48:08, adamk wrote: > I don't think calling GetCallbackPriority() makes sense here; I had to read it a > couple times to make sure you weren't going to overwrite an actual callbackInfo > object. > > Instead, I'd access the map directly (which isn't breaking any encapsulation > since you're already calling set() on it below). Just change this line to > > var priority = callbackInfoMap.get(callback); https://codereview.chromium.org/19541010/diff/4001/src/object-observe.js#newc... src/object-observe.js:492: for (var i in pendingObservers) { On 2013/07/23 21:48:08, adamk wrote: > Can you change this 'i' to 'priority' to match elsewhere? Done.
andreas, ptal
Looks mostly good, although I think that by now this file could use an introductory overview comment that explains the data structures and their invariants. It has gotten difficult to follow from the code alone, even with the pseudo class structure (which is an improvement). https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:71: typeMap[type] = ignoreDuplicate ? 1 : (typeMap[type] || 0) + 1; Hm, this hack could be avoided if AcceptArgIsValid flagged duplicates as errors. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:87: return typeMap[type]; Nit: !!typeMap[type] https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:111: // a given set of accept types. If the set of accept types is the default Nit: duplicate "a" https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:155: function ObjectInfoGet(object) { Is this still used at all? If not, you could as well drop the 'OrCreate' suffix from the above function. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:177: // observer is referenced directly via objectInfo.changeObserver. When a second Wouldn't it be slightly simpler to use only 'changeObservers' and distinguish based on whether it's a function? https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:501: while (observationState.anyPendingObservers) { I don't think you need to make this flag part of the global state. To detect a fix point it should be enough to have a local flag that gets set in the for-loop below (without a bit of extra logic you will redundantly create an extra pendingObservers object, but I don't think that matters).
I've added some overview commentary at the top of the file, and also made sure that structures which have optimized and normalized state also all have commentary. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:71: typeMap[type] = ignoreDuplicate ? 1 : (typeMap[type] || 0) + 1; That's not the issue. objectInfo.performing is a typeMap and it needs to have a *count* of each active type. On 2013/08/07 13:02:14, rossberg wrote: > Hm, this hack could be avoided if AcceptArgIsValid flagged duplicates as errors. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:87: return typeMap[type]; On 2013/08/07 13:02:14, rossberg wrote: > Nit: !!typeMap[type] Done. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:111: // a given set of accept types. If the set of accept types is the default On 2013/08/07 13:02:14, rossberg wrote: > Nit: duplicate "a" Done. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:155: function ObjectInfoGet(object) { On 2013/08/07 13:02:14, rossberg wrote: > Is this still used at all? If not, you could as well drop the 'OrCreate' suffix > from the above function. Done. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:177: // observer is referenced directly via objectInfo.changeObserver. When a second The problem is that an "observer" can be normal (an object with a .callback property) or optimized (just the callback). All of the places which touch the set of observers will need to test for if typeof objectInfo.changeObserver === 'function' || typeof objectInto.changeObserver.callback === 'function' (which can obvious be a utility function), but at that point, I feel like it violates the encapsulation of the optimized/normalized structures. If you feel strongly about it, I'm happy to do it (preferably in a follow-on patch). On 2013/08/07 13:02:14, rossberg wrote: > Wouldn't it be slightly simpler to use only 'changeObservers' and distinguish > based on whether it's a function? https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:501: while (observationState.anyPendingObservers) { I don't understand. observationState.anyPendingObservers is set to true in ObserverEnqueueIfActive. This is handling the case that an observer gets "re-activated" because of mutations to an observed object. I don't think there's a way to retrieve that information locally in this function. If you object to the flag, we can enqueue the fact that there are any pending with pendingObservers being null in that case. That, however, means that several other places in the code need to check it for being null (and i don't think it buys us anything perf-wise). On 2013/08/07 13:02:14, rossberg wrote: > I don't think you need to make this flag part of the global state. To detect a > fix point it should be enough to have a local flag that gets set in the for-loop > below (without a bit of extra logic you will redundantly create an extra > pendingObservers object, but I don't think that matters).
https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:177: // observer is referenced directly via objectInfo.changeObserver. When a second On 2013/08/07 20:36:28, rafaelw wrote: > The problem is that an "observer" can be normal (an object with a .callback > property) or optimized (just the callback). > > All of the places which touch the set of observers will need to test for > > if typeof objectInfo.changeObserver === 'function' || > typeof objectInto.changeObserver.callback === 'function' > > (which can obvious be a utility function), but at that point, I feel like it > violates the encapsulation of the optimized/normalized structures. > > If you feel strongly about it, I'm happy to do it (preferably in a follow-on > patch). I don't feel too strongly about it. But I would argue that contrary to what you say, the current version actually violates abstraction, because it points to a piece of information in two different ways, depending solely on that information's normalization state. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:501: while (observationState.anyPendingObservers) { What I mean is that all you are really implementing here is a local fixpoint iteration. And all the flag really does is helping you detect when you have reached that fixpoint. But since the fixpoint iteration is a concern of this function only, it would be better to implement it without having an implementation detail (the flag) leak into the global state and make it a concern of other code. I'd implement the fixpoint iteration using only local logic: var changed do { changed = false var pendingObservers = observationState.pendingObservers observationState.pendingObservers = { __proto__: null } for (var i in pendingObservers) { changed = true CallbackDeliverPending(pendingObservers[i]) } } while(changed) The only extra cost here is that you allocate a fresh pendingObservers object even when it was empty. But I highly doubt that cost is measurable at all, given that this function is only called once per turn. Or am I missing something?
PTAL https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:177: // observer is referenced directly via objectInfo.changeObserver. When a second Fair enough. Done. On 2013/08/09 11:26:51, rossberg wrote: > On 2013/08/07 20:36:28, rafaelw wrote: > > The problem is that an "observer" can be normal (an object with a .callback > > property) or optimized (just the callback). > > > > All of the places which touch the set of observers will need to test for > > > > if typeof objectInfo.changeObserver === 'function' || > > typeof objectInto.changeObserver.callback === 'function' > > > > (which can obvious be a utility function), but at that point, I feel like it > > violates the encapsulation of the optimized/normalized structures. > > > > If you feel strongly about it, I'm happy to do it (preferably in a follow-on > > patch). > > I don't feel too strongly about it. But I would argue that contrary to what you > say, the current version actually violates abstraction, because it points to a > piece of information in two different ways, depending solely on that > information's normalization state. https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:501: while (observationState.anyPendingObservers) { I tried & profiled this version, but it made deliveringAll in the noop case 5x more expensive. This doesn't matter much now, but we'll soon have a microtask delivery queue and we may have to repeatedly deliverAll when there is nothing to deliver. Instead I implemented the version where observationState.pendingObservers is null when there are no pending observers (getting rid of the anyPendingObservers flag). On 2013/08/09 11:26:51, rossberg wrote: > What I mean is that all you are really implementing here is a local fixpoint > iteration. And all the flag really does is helping you detect when you have > reached that fixpoint. But since the fixpoint iteration is a concern of this > function only, it would be better to implement it without having an > implementation detail (the flag) leak into the global state and make it a > concern of other code. > > I'd implement the fixpoint iteration using only local logic: > > var changed > do { > changed = false > var pendingObservers = observationState.pendingObservers > observationState.pendingObservers = { __proto__: null } > for (var i in pendingObservers) { > changed = true > CallbackDeliverPending(pendingObservers[i]) > } > } while(changed) > > The only extra cost here is that you allocate a fresh pendingObservers object > even when it was empty. But I highly doubt that cost is measurable at all, given > that this function is only called once per turn. > > Or am I missing something?
LGTM, but deferring land til tree is open again https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:501: while (observationState.anyPendingObservers) { On 2013/08/09 14:14:37, rafaelw wrote: > I tried & profiled this version, but it made deliveringAll in the noop case 5x > more expensive. Hm, that sounds like a lot. Did you try a version that avoids the unnecessary allocation? var changed do { changed = false var pendingObservers = observationState.pendingObservers for (var i in pendingObservers) { if (!changed) { changed = true observationState.pendingObservers = { __proto__: null } } CallbackDeliverPending(pendingObservers[i]) } } while(changed) But maybe the cost actually is in initialising the for-in. > This doesn't matter much now, but we'll soon have a microtask delivery queue and > we may have to repeatedly deliverAll when there is nothing to deliver. > > Instead I implemented the version where observationState.pendingObservers is > null when there are no pending observers (getting rid of the anyPendingObservers > flag). OK, it still doesn't look ideal to me, and I find it somewhat hard to believe that such a micro optimisation should matter. But since I don't really understand the microtask story yet, I'll shut up. :)
I'm assuming the tree is still closed. Please land when you are able. Thanks https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js File src/object-observe.js (right): https://codereview.chromium.org/19541010/diff/14001/src/object-observe.js#new... src/object-observe.js:501: while (observationState.anyPendingObservers) { That one is 3x more expensive. On 2013/08/13 09:19:25, rossberg wrote: > On 2013/08/09 14:14:37, rafaelw wrote: > > I tried & profiled this version, but it made deliveringAll in the noop case 5x > > more expensive. > > Hm, that sounds like a lot. Did you try a version that avoids the unnecessary > allocation? > > var changed > do { > changed = false > var pendingObservers = observationState.pendingObservers > for (var i in pendingObservers) { > if (!changed) { > changed = true > observationState.pendingObservers = { __proto__: null } > } > CallbackDeliverPending(pendingObservers[i]) > } > } while(changed) > > But maybe the cost actually is in initialising the for-in. > > > This doesn't matter much now, but we'll soon have a microtask delivery queue > and > > we may have to repeatedly deliverAll when there is nothing to deliver. > > > > Instead I implemented the version where observationState.pendingObservers is > > null when there are no pending observers (getting rid of the > anyPendingObservers > > flag). > > OK, it still doesn't look ideal to me, and I find it somewhat hard to believe > that such a micro optimisation should matter. But since I don't really > understand the microtask story yet, I'll shut up. :)
Was about to land this (as the tree now seems to be open), but it looks like one of the cctests is failing. See the output of: ./tools/run-tests.py --no-presubmit --arch-and-mode=x64.debug cctest/test-object-observe I'm guessing that the ObservationWeakMap tests is now making incorrect assumptions about the types of objects stored in the observation state.
fixed. thanks.
Message was sent while issue was closed.
Committed patchset #10 manually as r16343 (presubmit successful).
Message was sent while issue was closed.
Committed patchset #10 manually as r16539 (presubmit successful).
Message was sent while issue was closed.
On 2013/09/04 19:21:35, adamk wrote: > Committed patchset #10 manually as r16539 (presubmit successful). Failed again under GC stress (see http://build.chromium.org/p/client.v8/builders/V8%20GC%20Stress%20-%203/build...). Reproduceable crash running: ./tools/run-tests.py --arch-and-mode=ia32.debug --timeout=900 --extra-flags "--gc-interval=500 --stress-compaction --concurrent-recompilation-queue-length=64 --concurrent-recompilation-delay=500 --concurrent-recompilation" --shard-count=3 --shard-run=3
Message was sent while issue was closed.
On 2013/09/04 20:39:16, adamk wrote: > On 2013/09/04 19:21:35, adamk wrote: > > Committed patchset #10 manually as r16539 (presubmit successful). > > Failed again under GC stress (see > http://build.chromium.org/p/client.v8/builders/V8%2520GC%2520Stress%2520-%252...). > Reproduceable crash running: > > ./tools/run-tests.py --arch-and-mode=ia32.debug --timeout=900 --extra-flags > "--gc-interval=500 --stress-compaction > --concurrent-recompilation-queue-length=64 --concurrent-recompilation-delay=500 > --concurrent-recompilation" --shard-count=3 --shard-run=3 Reverted as https://code.google.com/p/v8/source/detail?r=16540
Message was sent while issue was closed.
Committed patchset #10 manually as r16629 (presubmit successful). |
