Revision: 16343
Author: [email protected]
Date: Mon Aug 26 21:37:21 2013 UTC
Log: This 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
[email protected]
Review URL: https://codereview.chromium.org/19541010
Patch from Rafael Weinstein <[email protected]>.
http://code.google.com/p/v8/source/detail?r=16343
Modified:
/branches/bleeding_edge/src/object-observe.js
/branches/bleeding_edge/test/cctest/test-object-observe.cc
=======================================
--- /branches/bleeding_edge/src/object-observe.js Tue Aug 6 13:49:10 2013
UTC
+++ /branches/bleeding_edge/src/object-observe.js Mon Aug 26 21:37:21 2013
UTC
@@ -27,12 +27,41 @@
"use strict";
+// Overview:
+//
+// This file contains all of the routing and accounting for Object.observe.
+// User code will interact with these mechanisms via the Object.observe
APIs
+// and, as a side effect of mutation objects which are observed. The V8
runtime
+// (both C++ and JS) will interact with these mechanisms primarily by
enqueuing
+// proper change records for objects which were mutated. The Object.observe
+// routing and accounting consists primarily of three participants
+//
+// 1) ObjectInfo. This represents the observed state of a given object. It
+// records what callbacks are observing the object, with what options,
and
+// what "change types" are in progress on the object (i.e. via
+// notifier.performChange).
+//
+// 2) CallbackInfo. This represents a callback used for observation. It
holds
+// the records which must be delivered to the callback, as well as the
global
+// priority of the callback (which determines delivery order between
+// callbacks).
+//
+// 3) observationState.pendingObservers. This is the set of observers which
+// have change records which must be delivered. During "normal" delivery
+// (i.e. not Object.deliverChangeRecords), this is the mechanism by
which
+// callbacks are invoked in the proper order until there are no more
+// change records pending to a callback.
+//
+// Note that in order to reduce allocation and processing costs, the
+// implementation of (1) and (2) have "optimized" states which represent
+// common cases which can be handled more efficiently.
+
var observationState = %GetObservationState();
if (IS_UNDEFINED(observationState.callbackInfoMap)) {
observationState.callbackInfoMap = %ObservationWeakMapCreate();
observationState.objectInfoMap = %ObservationWeakMapCreate();
- observationState.notifierTargetMap = %ObservationWeakMapCreate();
- observationState.pendingObservers = new InternalArray;
+ observationState.notifierObjectInfoMap = %ObservationWeakMapCreate();
+ observationState.pendingObservers = null;
observationState.nextCallbackPriority = 0;
}
@@ -59,126 +88,191 @@
var callbackInfoMap =
new ObservationWeakMap(observationState.callbackInfoMap);
var objectInfoMap = new ObservationWeakMap(observationState.objectInfoMap);
-var notifierTargetMap =
- new ObservationWeakMap(observationState.notifierTargetMap);
+var notifierObjectInfoMap =
+ new ObservationWeakMap(observationState.notifierObjectInfoMap);
-function CreateObjectInfo(object) {
- var info = {
- changeObservers: new InternalArray,
- notifier: null,
- inactiveObservers: new InternalArray,
- performing: { __proto__: null },
- performingCount: 0,
- };
- objectInfoMap.set(object, info);
- return info;
+function TypeMapCreate() {
+ return { __proto__: null };
}
-var defaultAcceptTypes = {
- __proto__: null,
- 'new': true,
- 'updated': true,
- 'deleted': true,
- 'prototype': true,
- 'reconfigured': true
-};
+function TypeMapAddType(typeMap, type, ignoreDuplicate) {
+ typeMap[type] = ignoreDuplicate ? 1 : (typeMap[type] || 0) + 1;
+}
-function CreateObserver(callback, accept) {
- var observer = {
- __proto__: null,
- callback: callback,
- accept: defaultAcceptTypes
- };
+function TypeMapRemoveType(typeMap, type) {
+ typeMap[type]--;
+}
- if (IS_UNDEFINED(accept))
- return observer;
+function TypeMapCreateFromList(typeList) {
+ var typeMap = TypeMapCreate();
+ for (var i = 0; i < typeList.length; i++) {
+ TypeMapAddType(typeMap, typeList[i], true);
+ }
+ return typeMap;
+}
- var acceptMap = { __proto__: null };
- for (var i = 0; i < accept.length; i++)
- acceptMap[accept[i]] = true;
-
- observer.accept = acceptMap;
- return observer;
+function TypeMapHasType(typeMap, type) {
+ return !!typeMap[type];
}
-function ObserverIsActive(observer, objectInfo) {
- if (objectInfo.performingCount === 0)
+function TypeMapIsDisjointFrom(typeMap1, typeMap2) {
+ if (!typeMap1 || !typeMap2)
return true;
- var performing = objectInfo.performing;
- for (var type in performing) {
- if (performing[type] > 0 && observer.accept[type])
+ for (var type in typeMap1) {
+ if (TypeMapHasType(typeMap1, type) && TypeMapHasType(typeMap2, type))
return false;
}
return true;
}
-function ObserverIsInactive(observer, objectInfo) {
- return !ObserverIsActive(observer, objectInfo);
+var defaultAcceptTypes = TypeMapCreateFromList([
+ 'new',
+ 'updated',
+ 'deleted',
+ 'prototype',
+ 'reconfigured'
+]);
+
+// An Observer is a registration to observe an object by a callback with
+// a given set of accept types. If the set of accept types is the default
+// set for Object.observe, the observer is represented as a direct
reference
+// to the callback. An observer never changes its accept types and thus
never
+// needs to "normalize".
+function ObserverCreate(callback, acceptList) {
+ return IS_UNDEFINED(acceptList) ? callback : {
+ __proto__: null,
+ callback: callback,
+ accept: TypeMapCreateFromList(acceptList)
+ };
}
-function RemoveNullElements(from) {
- var i = 0;
- var j = 0;
- for (; i < from.length; i++) {
- if (from[i] === null)
- continue;
- if (j < i)
- from[j] = from[i];
- j++;
+function ObserverGetCallback(observer) {
+ return IS_SPEC_FUNCTION(observer) ? observer : observer.callback;
+}
+
+function ObserverGetAcceptTypes(observer) {
+ return IS_SPEC_FUNCTION(observer) ? defaultAcceptTypes : observer.accept;
+}
+
+function ObserverIsActive(observer, objectInfo) {
+ return TypeMapIsDisjointFrom(ObjectInfoGetPerformingTypes(objectInfo),
+ ObserverGetAcceptTypes(observer));
+}
+
+function ObjectInfoGet(object) {
+ var objectInfo = objectInfoMap.get(object);
+ if (IS_UNDEFINED(objectInfo)) {
+ if (!%IsJSProxy(object))
+ %SetIsObserved(object);
+
+ objectInfo = {
+ object: object,
+ changeObservers: null,
+ notifier: null,
+ performing: null,
+ performingCount: 0,
+ };
+ objectInfoMap.set(object, objectInfo);
}
+ return objectInfo;
+}
- if (i !== j)
- from.length = from.length - (i - j);
+function ObjectInfoGetFromNotifier(notifier) {
+ return notifierObjectInfoMap.get(notifier);
}
-function RepartitionObservers(conditionFn, from, to, objectInfo) {
- var anyRemoved = false;
- for (var i = 0; i < from.length; i++) {
- var observer = from[i];
- if (conditionFn(observer, objectInfo)) {
- anyRemoved = true;
- from[i] = null;
- to.push(observer);
- }
+function ObjectInfoGetNotifier(objectInfo) {
+ if (IS_NULL(objectInfo.notifier)) {
+ objectInfo.notifier = { __proto__: notifierPrototype };
+ notifierObjectInfoMap.set(objectInfo.notifier, objectInfo);
}
- if (anyRemoved)
- RemoveNullElements(from);
+ return objectInfo.notifier;
}
-function BeginPerformChange(objectInfo, type) {
- objectInfo.performing[type] = (objectInfo.performing[type] || 0) + 1;
- objectInfo.performingCount++;
- RepartitionObservers(ObserverIsInactive,
- objectInfo.changeObservers,
- objectInfo.inactiveObservers,
- objectInfo);
+function ObjectInfoGetObject(objectInfo) {
+ return objectInfo.object;
}
-function EndPerformChange(objectInfo, type) {
- objectInfo.performing[type]--;
- objectInfo.performingCount--;
- RepartitionObservers(ObserverIsActive,
- objectInfo.inactiveObservers,
- objectInfo.changeObservers,
- objectInfo);
+function ChangeObserversIsOptimized(changeObservers) {
+ return typeof changeObservers === 'function' ||
+ typeof changeObservers.callback === 'function';
}
-function EnsureObserverRemoved(objectInfo, callback) {
- function remove(observerList) {
- for (var i = 0; i < observerList.length; i++) {
- if (observerList[i].callback === callback) {
- observerList.splice(i, 1);
- return true;
- }
- }
+// The set of observers on an object is called 'changeObservers'. The first
+// observer is referenced directly via objectInfo.changeObservers. When a
second
+// is added, changeObservers "normalizes" to become a mapping of callback
+// priority -> observer and is then stored on objectInfo.changeObservers.
+function ObjectInfoNormalizeChangeObservers(objectInfo) {
+ if (ChangeObserversIsOptimized(objectInfo.changeObservers)) {
+ var observer = objectInfo.changeObservers;
+ var callback = ObserverGetCallback(observer);
+ var callbackInfo = CallbackInfoGet(callback);
+ var priority = CallbackInfoGetPriority(callbackInfo);
+ objectInfo.changeObservers = { __proto__: null };
+ objectInfo.changeObservers[priority] = observer;
+ }
+}
+
+function ObjectInfoAddObserver(objectInfo, callback, acceptList) {
+ var callbackInfo = CallbackInfoGetOrCreate(callback);
+ var observer = ObserverCreate(callback, acceptList);
+
+ if (!objectInfo.changeObservers) {
+ objectInfo.changeObservers = observer;
+ return;
+ }
+
+ ObjectInfoNormalizeChangeObservers(objectInfo);
+ var priority = CallbackInfoGetPriority(callbackInfo);
+ objectInfo.changeObservers[priority] = observer;
+}
+
+function ObjectInfoRemoveObserver(objectInfo, callback) {
+ if (!objectInfo.changeObservers)
+ return;
+
+ if (ChangeObserversIsOptimized(objectInfo.changeObservers)) {
+ if (callback === ObserverGetCallback(objectInfo.changeObservers))
+ objectInfo.changeObservers = null;
+ return;
+ }
+
+ var callbackInfo = CallbackInfoGet(callback);
+ var priority = CallbackInfoGetPriority(callbackInfo);
+ delete objectInfo.changeObservers[priority];
+}
+
+function ObjectInfoHasActiveObservers(objectInfo) {
+ if (IS_UNDEFINED(objectInfo) || !objectInfo.changeObservers)
return false;
+
+ if (ChangeObserversIsOptimized(objectInfo.changeObservers))
+ return ObserverIsActive(objectInfo.changeObservers, objectInfo);
+
+ for (var priority in objectInfo.changeObservers) {
+ if (ObserverIsActive(objectInfo.changeObservers[priority], objectInfo))
+ return true;
}
- if (!remove(objectInfo.changeObservers))
- remove(objectInfo.inactiveObservers);
+ return false;
+}
+
+function ObjectInfoAddPerformingType(objectInfo, type) {
+ objectInfo.performing = objectInfo.performing || TypeMapCreate();
+ TypeMapAddType(objectInfo.performing, type);
+ objectInfo.performingCount++;
+}
+
+function ObjectInfoRemovePerformingType(objectInfo, type) {
+ objectInfo.performingCount--;
+ TypeMapRemoveType(objectInfo.performing, type);
+}
+
+function ObjectInfoGetPerformingTypes(objectInfo) {
+ return objectInfo.performingCount > 0 ? objectInfo.performing : null;
}
function AcceptArgIsValid(arg) {
@@ -198,12 +292,31 @@
return true;
}
-function EnsureCallbackPriority(callback) {
- if (!callbackInfoMap.has(callback))
- callbackInfoMap.set(callback, observationState.nextCallbackPriority++);
+// CallbackInfo's optimized state is just a number which represents its
global
+// priority. When a change record must be enqueued for the callback, it
+// normalizes. When delivery clears any pending change records, it
re-optimizes.
+function CallbackInfoGet(callback) {
+ return callbackInfoMap.get(callback);
+}
+
+function CallbackInfoGetOrCreate(callback) {
+ var callbackInfo = callbackInfoMap.get(callback);
+ if (!IS_UNDEFINED(callbackInfo))
+ return callbackInfo;
+
+ var priority = observationState.nextCallbackPriority++
+ callbackInfoMap.set(callback, priority);
+ return priority;
+}
+
+function CallbackInfoGetPriority(callbackInfo) {
+ if (IS_NUMBER(callbackInfo))
+ return callbackInfo;
+ else
+ return callbackInfo.priority;
}
-function NormalizeCallbackInfo(callback) {
+function CallbackInfoNormalize(callback) {
var callbackInfo = callbackInfoMap.get(callback);
if (IS_NUMBER(callbackInfo)) {
var priority = callbackInfo;
@@ -214,32 +327,18 @@
return callbackInfo;
}
-function ObjectObserve(object, callback, accept) {
+function ObjectObserve(object, callback, acceptList) {
if (!IS_SPEC_OBJECT(object))
throw MakeTypeError("observe_non_object", ["observe"]);
if (!IS_SPEC_FUNCTION(callback))
throw MakeTypeError("observe_non_function", ["observe"]);
if (ObjectIsFrozen(callback))
throw MakeTypeError("observe_callback_frozen");
- if (!AcceptArgIsValid(accept))
+ if (!AcceptArgIsValid(acceptList))
throw MakeTypeError("observe_accept_invalid");
- EnsureCallbackPriority(callback);
-
- var objectInfo = objectInfoMap.get(object);
- if (IS_UNDEFINED(objectInfo)) {
- objectInfo = CreateObjectInfo(object);
- %SetIsObserved(object);
- }
-
- EnsureObserverRemoved(objectInfo, callback);
-
- var observer = CreateObserver(callback, accept);
- if (ObserverIsActive(observer, objectInfo))
- objectInfo.changeObservers.push(observer);
- else
- objectInfo.inactiveObservers.push(observer);
-
+ var objectInfo = ObjectInfoGet(object);
+ ObjectInfoAddObserver(objectInfo, callback, acceptList);
return object;
}
@@ -253,7 +352,7 @@
if (IS_UNDEFINED(objectInfo))
return object;
- EnsureObserverRemoved(objectInfo, callback);
+ ObjectInfoRemoveObserver(objectInfo, callback);
return object;
}
@@ -268,41 +367,52 @@
return ObjectUnobserve(object, callback);
}
-function EnqueueToCallback(callback, changeRecord) {
- var callbackInfo = NormalizeCallbackInfo(callback);
+function ObserverEnqueueIfActive(observer, objectInfo, changeRecord) {
+ if (!ObserverIsActive(observer, objectInfo) ||
+ !TypeMapHasType(ObserverGetAcceptTypes(observer),
changeRecord.type)) {
+ return;
+ }
+
+ var callback = ObserverGetCallback(observer);
+ var callbackInfo = CallbackInfoNormalize(callback);
+ if (!observationState.pendingObservers)
+ observationState.pendingObservers = { __proto__: null };
observationState.pendingObservers[callbackInfo.priority] = callback;
callbackInfo.push(changeRecord);
%SetObserverDeliveryPending();
}
-function EnqueueChangeRecord(changeRecord, observers) {
+function ObjectInfoEnqueueChangeRecord(objectInfo, changeRecord) {
// TODO(rossberg): adjust once there is a story for symbols vs proxies.
if (IS_SYMBOL(changeRecord.name)) return;
- for (var i = 0; i < observers.length; i++) {
- var observer = observers[i];
- if (IS_UNDEFINED(observer.accept[changeRecord.type]))
- continue;
+ if (ChangeObserversIsOptimized(objectInfo.changeObservers)) {
+ var observer = objectInfo.changeObservers;
+ ObserverEnqueueIfActive(observer, objectInfo, changeRecord);
+ return;
+ }
- EnqueueToCallback(observer.callback, changeRecord);
+ for (var priority in objectInfo.changeObservers) {
+ var observer = objectInfo.changeObservers[priority];
+ ObserverEnqueueIfActive(observer, objectInfo, changeRecord);
}
}
function BeginPerformSplice(array) {
var objectInfo = objectInfoMap.get(array);
if (!IS_UNDEFINED(objectInfo))
- BeginPerformChange(objectInfo, 'splice');
+ ObjectInfoAddPerformingType(objectInfo, 'splice');
}
function EndPerformSplice(array) {
var objectInfo = objectInfoMap.get(array);
if (!IS_UNDEFINED(objectInfo))
- EndPerformChange(objectInfo, 'splice');
+ ObjectInfoRemovePerformingType(objectInfo, 'splice');
}
function EnqueueSpliceRecord(array, index, removed, addedCount) {
var objectInfo = objectInfoMap.get(array);
- if (IS_UNDEFINED(objectInfo) || objectInfo.changeObservers.length === 0)
+ if (!ObjectInfoHasActiveObservers(objectInfo))
return;
var changeRecord = {
@@ -315,19 +425,19 @@
ObjectFreeze(changeRecord);
ObjectFreeze(changeRecord.removed);
- EnqueueChangeRecord(changeRecord, objectInfo.changeObservers);
+ ObjectInfoEnqueueChangeRecord(objectInfo, changeRecord);
}
function NotifyChange(type, object, name, oldValue) {
var objectInfo = objectInfoMap.get(object);
- if (objectInfo.changeObservers.length === 0)
+ if (!ObjectInfoHasActiveObservers(objectInfo))
return;
var changeRecord = (arguments.length < 4) ?
{ type: type, object: object, name: name } :
{ type: type, object: object, name: name, oldValue: oldValue };
ObjectFreeze(changeRecord);
- EnqueueChangeRecord(changeRecord, objectInfo.changeObservers);
+ ObjectInfoEnqueueChangeRecord(objectInfo, changeRecord);
}
var notifierPrototype = {};
@@ -336,17 +446,16 @@
if (!IS_SPEC_OBJECT(this))
throw MakeTypeError("called_on_non_object", ["notify"]);
- var target = notifierTargetMap.get(this);
- if (IS_UNDEFINED(target))
+ var objectInfo = ObjectInfoGetFromNotifier(this);
+ if (IS_UNDEFINED(objectInfo))
throw MakeTypeError("observe_notify_non_notifier");
if (!IS_STRING(changeRecord.type))
throw MakeTypeError("observe_type_non_string");
- var objectInfo = objectInfoMap.get(target);
- if (IS_UNDEFINED(objectInfo) || objectInfo.changeObservers.length === 0)
+ if (!ObjectInfoHasActiveObservers(objectInfo))
return;
- var newRecord = { object: target };
+ var newRecord = { object: ObjectInfoGetObject(objectInfo) };
for (var prop in changeRecord) {
if (prop === 'object') continue;
%DefineOrRedefineDataProperty(newRecord, prop, changeRecord[prop],
@@ -354,15 +463,16 @@
}
ObjectFreeze(newRecord);
- EnqueueChangeRecord(newRecord, objectInfo.changeObservers);
+ ObjectInfoEnqueueChangeRecord(objectInfo, newRecord);
}
function ObjectNotifierPerformChange(changeType, changeFn, receiver) {
if (!IS_SPEC_OBJECT(this))
throw MakeTypeError("called_on_non_object", ["performChange"]);
- var target = notifierTargetMap.get(this);
- if (IS_UNDEFINED(target))
+ var objectInfo = ObjectInfoGetFromNotifier(this);
+
+ if (IS_UNDEFINED(objectInfo))
throw MakeTypeError("observe_notify_non_notifier");
if (!IS_STRING(changeType))
throw MakeTypeError("observe_perform_non_string");
@@ -375,15 +485,11 @@
receiver = ToObject(receiver);
}
- var objectInfo = objectInfoMap.get(target);
- if (IS_UNDEFINED(objectInfo))
- return;
-
- BeginPerformChange(objectInfo, changeType);
+ ObjectInfoAddPerformingType(objectInfo, changeType);
try {
%_CallFunction(receiver, changeFn);
} finally {
- EndPerformChange(objectInfo, changeType);
+ ObjectInfoRemovePerformingType(objectInfo, changeType);
}
}
@@ -393,18 +499,8 @@
if (ObjectIsFrozen(object)) return null;
- var objectInfo = objectInfoMap.get(object);
- if (IS_UNDEFINED(objectInfo)) {
- objectInfo = CreateObjectInfo(object);
- %SetIsObserved(object);
- }
-
- if (IS_NULL(objectInfo.notifier)) {
- objectInfo.notifier = { __proto__: notifierPrototype };
- notifierTargetMap.set(objectInfo.notifier, object);
- }
-
- return objectInfo.notifier;
+ var objectInfo = ObjectInfoGet(object);
+ return ObjectInfoGetNotifier(objectInfo);
}
function CallbackDeliverPending(callback) {
@@ -417,7 +513,9 @@
var priority = callbackInfo.priority;
callbackInfoMap.set(callback, priority);
- delete observationState.pendingObservers[priority];
+ if (observationState.pendingObservers)
+ delete observationState.pendingObservers[priority];
+
var delivered = [];
%MoveArrayContents(callbackInfo, delivered);
@@ -435,9 +533,9 @@
}
function DeliverChangeRecords() {
- while (observationState.pendingObservers.length) {
+ while (observationState.pendingObservers) {
var pendingObservers = observationState.pendingObservers;
- observationState.pendingObservers = new InternalArray;
+ observationState.pendingObservers = null;
for (var i in pendingObservers) {
CallbackDeliverPending(pendingObservers[i]);
}
=======================================
--- /branches/bleeding_edge/test/cctest/test-object-observe.cc Mon Jul 15
22:16:30 2013 UTC
+++ /branches/bleeding_edge/test/cctest/test-object-observe.cc Mon Aug 26
21:37:21 2013 UTC
@@ -435,14 +435,14 @@
i::Handle<i::JSWeakMap> objectInfoMap =
i::Handle<i::JSWeakMap>::cast(
i::GetProperty(observation_state, "objectInfoMap"));
- i::Handle<i::JSWeakMap> notifierTargetMap =
+ i::Handle<i::JSWeakMap> notifierObjectInfoMap =
i::Handle<i::JSWeakMap>::cast(
- i::GetProperty(observation_state, "notifierTargetMap"));
+ i::GetProperty(observation_state, "notifierObjectInfoMap"));
CHECK_EQ(1, NumberOfElements(callbackInfoMap));
CHECK_EQ(1, NumberOfElements(objectInfoMap));
- CHECK_EQ(1, NumberOfElements(notifierTargetMap));
+ CHECK_EQ(1, NumberOfElements(notifierObjectInfoMap));
HEAP->CollectAllGarbage(i::Heap::kAbortIncrementalMarkingMask);
CHECK_EQ(0, NumberOfElements(callbackInfoMap));
CHECK_EQ(0, NumberOfElements(objectInfoMap));
- CHECK_EQ(0, NumberOfElements(notifierTargetMap));
+ CHECK_EQ(0, NumberOfElements(notifierObjectInfoMap));
}
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
