Implement optimized objectInfo structure

src/object-observe.js

Index: src/object-observe.js
diff --git a/src/object-observe.js b/src/object-observe.js
index 1c147d95e30f9e82d45797d500b2d32bb198b064..49c0b85c0c83b0ac141ccc8e7637203bcdfb403c 100644
--- a/src/object-observe.js
+++ b/src/object-observe.js
@@ -32,7 +32,8 @@ if (IS_UNDEFINED(observationState.callbackInfoMap)) {
   observationState.callbackInfoMap = %ObservationWeakMapCreate();
   observationState.objectInfoMap = %ObservationWeakMapCreate();
   observationState.notifierTargetMap = %ObservationWeakMapCreate();
-  observationState.pendingObservers = new InternalArray;
+  observationState.pendingObservers = { __proto__: null };

[rafaelw, 2013/07/19 22:21:41]

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.

+  observationState.anyPendingObservers = false;
   observationState.nextCallbackPriority = 0;
 }
 
@@ -64,121 +65,153 @@ var notifierTargetMap =
 
 function CreateObjectInfo(object) {
   var info = {
-    changeObservers: new InternalArray,
+    changeObserver: null,
+    changeObservers: null,
     notifier: null,
-    inactiveObservers: new InternalArray,
-    performing: { __proto__: null },
+    performing: null,
     performingCount: 0,
   };
   objectInfoMap.set(object, info);
   return info;
 }
 
-var defaultAcceptTypes = {
-  __proto__: null,
-  'new': true,
-  'updated': true,
-  'deleted': true,
-  'prototype': true,
-  'reconfigured': true
-};
+function CreateTypeMap() {
+  return { __proto__: null };

[adamk, 2013/07/23 21:48:08]

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.

[rafaelw, 2013/08/02 20:10:32]

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:

+}
 
-function CreateObserver(callback, accept) {
-  var observer = {
-    __proto__: null,
-    callback: callback,
-    accept: defaultAcceptTypes
-  };
+function AddToTypeMap(typeMap, type, ignoreDuplicate) {
+  typeMap[type] = ignoreDuplicate ? 1 : (typeMap[type] || 0) + 1;;
+}
 
-  if (IS_UNDEFINED(accept))
-    return observer;
+function RemoveFromTypeMap(typeMap, type) {
+  typeMap[type]--;
+}
 
-  var acceptMap = { __proto__: null };
-  for (var i = 0; i < accept.length; i++)
-    acceptMap[accept[i]] = true;
+function CreateTypeMapFromList(typeList) {
+  var typeMap = CreateTypeMap();
+  for (var i = 0; i < typeList.length; i++) {
+    AddToTypeMap(typeMap, typeList[i], true);

[adamk, 2013/07/23 21:48:08]

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.

[rafaelw, 2013/08/02 20:10:32]

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:

+  }
+  return typeMap;
+}
 
-  observer.accept = acceptMap;
-  return observer;
+function TypeMapHasType(typeMap, type) {
+  return typeMap[type];
 }
 
-function ObserverIsActive(observer, objectInfo) {
-  if (objectInfo.performingCount === 0)
+function TypeMapsAreDisjoint(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 defaultAccept = CreateTypeMapFromList(new InternalArray(

[adamk, 2013/07/23 21:48:08]

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.

[rafaelw, 2013/08/02 20:10:32]

Both done.

On 2013/07/23 21:48:08, adamk wrote:

+  'new',
+  'updated',
+  'deleted',
+  'prototype',
+  'reconfigured'
+));
+
+// An Observer is a registration to observe an object by a callback with a
+// 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 CreateObserver(callback, acceptList) {
+  return IS_UNDEFINED(acceptList) ? callback : {
+    __proto__: null,
+    callback: callback,
+    accept: CreateTypeMapFromList(acceptList)
+  };
+}
+
+function ObserverGetCallback(observer) {
+  return IS_SPEC_FUNCTION(observer) ? observer : observer.callback;
+}
+
+function ObserverGetAcceptTypes(observer) {
+  return IS_SPEC_FUNCTION(observer) ? defaultAccept : observer.accept;
+}
+
+function ObserverIsActive(observer, objectInfo) {
+  return TypeMapsAreDisjoint(ObjectGetPerformingTypes(objectInfo),

[adamk, 2013/07/23 21:48:08]

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).

[rafaelw, 2013/08/02 20:10:32]

Again, I want to keep TypeMap methods encapsulated for a follow-on patch.

On 2013/07/23 21:48:08, adamk wrote:

+                             ObserverGetAcceptTypes(observer));
+}
+
+// The set of observers on an object is called 'changeObservers'. The first
+// observer is referenced directly via objectInfo.changeObserver. When a second
+// is added, changeObservers "normalizes" to become a mapping of callback
+// priority -> observer and is then stored on objectInfo.changeObservers.
+function NormalizeChangeObservers(objectInfo) {
+  var observer = objectInfo.changeObserver;
+  objectInfo.changeObserver = null;
+  objectInfo.changeObservers = { __proto__: null };
+  var priority = GetCallbackPriority(ObserverGetCallback(observer));
+  objectInfo.changeObservers[priority] = observer;
 }
 
-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 ObjectAddObserver(objectInfo, observer, priority) {
+  if (!objectInfo.changeObserver && !objectInfo.changeObservers) {
+    objectInfo.changeObserver = observer;
+    return;
   }
 
-  if (i !== j)
-    from.length = from.length - (i - j);
+  if (objectInfo.changeObserver)
+    NormalizeChangeObservers(objectInfo);
+
+  objectInfo.changeObservers[priority] = observer;
 }
 
-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 ObjectRemoveObserver(objectInfo, priority) {
+  if (objectInfo.changeObserver) {
+    var callback = ObserverGetCallback(objectInfo.changeObserver);
+    if (GetCallbackPriority(callback) === priority)
+      objectInfo.changeObserver = null;
+
+    return;
   }
 
-  if (anyRemoved)
-    RemoveNullElements(from);
+  delete objectInfo.changeObservers[priority];
 }
 
-function BeginPerformChange(objectInfo, type) {
-  objectInfo.performing[type] = (objectInfo.performing[type] || 0) + 1;
+function ObjectHasActiveObservers(objectInfo) {
+  if (IS_UNDEFINED(objectInfo))
+    return false;
+
+  if (objectInfo.changeObserver)
+    return ObserverIsActive(objectInfo.changeObserver, objectInfo);
+
+  for (var priority in objectInfo.changeObservers) {
+    if (ObserverIsActive(objectInfo.changeObservers[priority], objectInfo))
+      return true;
+  }
+
+  return false;
+}
+
+function ObjectAddPerfomingType(objectInfo, type) {

[adamk, 2013/07/23 21:48:08]

Typo: s/Perfoming/Performing/

[rafaelw, 2013/08/02 20:10:32]

Done.

+  objectInfo.performing = objectInfo.performing || CreateTypeMap();
+  AddToTypeMap(objectInfo.performing, type);
   objectInfo.performingCount++;
-  RepartitionObservers(ObserverIsInactive,
-                       objectInfo.changeObservers,
-                       objectInfo.inactiveObservers,
-                       objectInfo);
 }
 
-function EndPerformChange(objectInfo, type) {
-  objectInfo.performing[type]--;
+function ObjectRemovePerformingType(objectInfo, type) {
   objectInfo.performingCount--;
-  RepartitionObservers(ObserverIsActive,
-                       objectInfo.inactiveObservers,
-                       objectInfo.changeObservers,
-                       objectInfo);
-}
-
-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;
-      }
-    }
-    return false;
-  }
+  if (objectInfo.performingCount)

[adamk, 2013/07/23 21:48:08]

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.

[rafaelw, 2013/08/02 20:10:32]

The comparison is now gone.

On 2013/07/23 21:48:08, adamk wrote:

+    RemoveFromTypeMap(objectInfo.performing, type);
+  else
+    objectInfo.performing = null;

[adamk, 2013/07/23 21:48:08]

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?

[rafaelw, 2013/08/02 20:10:32]

Fair enough. Removing.

On 2013/07/23 21:48:08, adamk wrote:

+}
 
-  if (!remove(objectInfo.changeObservers))
-    remove(objectInfo.inactiveObservers);
+function ObjectGetPerformingTypes(objectInfo) {
+  return objectInfo.performingCount ? objectInfo.performing : null;

[adamk, 2013/07/23 21:48:08]

Maybe a > 0 here too?

[rafaelw, 2013/08/02 20:10:32]

Done.

 }
 
 function AcceptArgIsValid(arg) {
@@ -198,9 +231,24 @@ function AcceptArgIsValid(arg) {
   return true;
 }
 
+function GetCallbackPriority(callback) {
+  var callbackInfo = callbackInfoMap.get(callback);
+  if (IS_UNDEFINED(callbackInfo))
+    return;
+  else if (IS_NUMBER(callbackInfo))
+    return callbackInfo;
+  else
+    return callbackInfo.priority;
+}
+
 function EnsureCallbackPriority(callback) {
-  if (!callbackInfoMap.has(callback))
-    callbackInfoMap.set(callback, observationState.nextCallbackPriority++);
+  var priority = GetCallbackPriority(callback);

[adamk, 2013/07/23 21:48:08]

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);

[rafaelw, 2013/08/02 20:10:32]

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:

[rafaelw, 2013/08/02 20:10:32]

So this is really CallbackInfoGetPriority(callback). Hopefully this is clearer
now.


On 2013/07/23 21:48:08, adamk wrote:

+  if (IS_UNDEFINED(priority)) {
+    priority = observationState.nextCallbackPriority++
+    callbackInfoMap.set(callback, priority);
+  }
+
+  return priority;
 }
 
 function NormalizeCallbackInfo(callback) {
@@ -214,17 +262,17 @@ function NormalizeCallbackInfo(callback) {
   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 priority = EnsureCallbackPriority(callback);
 
   var objectInfo = objectInfoMap.get(object);
   if (IS_UNDEFINED(objectInfo)) {
@@ -232,14 +280,8 @@ function ObjectObserve(object, callback, accept) {
     %SetIsObserved(object);
   }
 
-  EnsureObserverRemoved(objectInfo, callback);
-
-  var observer = CreateObserver(callback, accept);
-  if (ObserverIsActive(observer, objectInfo))
-    objectInfo.changeObservers.push(observer);
-  else
-    objectInfo.inactiveObservers.push(observer);
-
+  var observer = CreateObserver(callback, acceptList);
+  ObjectAddObserver(objectInfo, observer, priority);
   return object;
 }
 
@@ -253,7 +295,8 @@ function ObjectUnobserve(object, callback) {
   if (IS_UNDEFINED(objectInfo))
     return object;
 
-  EnsureObserverRemoved(objectInfo, callback);
+  var priority = GetCallbackPriority(callback);
+  ObjectRemoveObserver(objectInfo, priority);
   return object;
 }
 
@@ -268,41 +311,51 @@ function ArrayUnobserve(object, callback) {
   return ObjectUnobserve(object, callback);
 }
 
-function EnqueueToCallback(callback, changeRecord) {
+function ObserverEnqueueIfActive(observer, objectInfo, changeRecord) {
+  if (!ObserverIsActive(observer, objectInfo) ||
+      !TypeMapHasType(ObserverGetAcceptTypes(observer), changeRecord.type)) {
+    return;
+  }
+
+  var callback = ObserverGetCallback(observer);
   var callbackInfo = NormalizeCallbackInfo(callback);
   observationState.pendingObservers[callbackInfo.priority] = callback;
+  observationState.anyPendingObservers = true;
   callbackInfo.push(changeRecord);
   %SetObserverDeliveryPending();
 }
 
-function EnqueueChangeRecord(changeRecord, observers) {
+function EnqueueChangeRecordToObservers(changeRecord, objectInfo) {
   // 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 (objectInfo.changeObserver) {
+    var observer = objectInfo.changeObserver;
+    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');
+    ObjectAddPerfomingType(objectInfo, 'splice');
 }
 
 function EndPerformSplice(array) {
   var objectInfo = objectInfoMap.get(array);
   if (!IS_UNDEFINED(objectInfo))
-    EndPerformChange(objectInfo, 'splice');
+    ObjectRemovePerformingType(objectInfo, 'splice');
 }
 
 function EnqueueSpliceRecord(array, index, removed, addedCount) {
   var objectInfo = objectInfoMap.get(array);
-  if (IS_UNDEFINED(objectInfo) || objectInfo.changeObservers.length === 0)
+  if (!ObjectHasActiveObservers(objectInfo))
     return;
 
   var changeRecord = {
@@ -315,19 +368,19 @@ function EnqueueSpliceRecord(array, index, removed, addedCount) {
 
   ObjectFreeze(changeRecord);
   ObjectFreeze(changeRecord.removed);
-  EnqueueChangeRecord(changeRecord, objectInfo.changeObservers);
+  EnqueueChangeRecordToObservers(changeRecord, objectInfo);
 }
 
 function NotifyChange(type, object, name, oldValue) {
   var objectInfo = objectInfoMap.get(object);
-  if (objectInfo.changeObservers.length === 0)
+  if (!ObjectHasActiveObservers(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);
+  EnqueueChangeRecordToObservers(changeRecord, objectInfo);
 }
 
 var notifierPrototype = {};
@@ -343,7 +396,7 @@ function ObjectNotifierNotify(changeRecord) {
     throw MakeTypeError("observe_type_non_string");
 
   var objectInfo = objectInfoMap.get(target);
-  if (IS_UNDEFINED(objectInfo) || objectInfo.changeObservers.length === 0)
+  if (!ObjectHasActiveObservers(objectInfo))
     return;
 
   var newRecord = { object: target };
@@ -354,7 +407,7 @@ function ObjectNotifierNotify(changeRecord) {
   }
   ObjectFreeze(newRecord);
 
-  EnqueueChangeRecord(newRecord, objectInfo.changeObservers);
+  EnqueueChangeRecordToObservers(newRecord, objectInfo);
 }
 
 function ObjectNotifierPerformChange(changeType, changeFn, receiver) {
@@ -379,11 +432,11 @@ function ObjectNotifierPerformChange(changeType, changeFn, receiver) {
   if (IS_UNDEFINED(objectInfo))
     return;
 
-  BeginPerformChange(objectInfo, changeType);
+  ObjectAddPerfomingType(objectInfo, changeType);
   try {
     %_CallFunction(receiver, changeFn);
   } finally {
-    EndPerformChange(objectInfo, changeType);
+    ObjectRemovePerformingType(objectInfo, changeType);
   }
 }
 
@@ -432,9 +485,10 @@ function ObjectDeliverChangeRecords(callback) {
 }
 
 function DeliverChangeRecords() {
-  while (observationState.pendingObservers.length) {
+  while (observationState.anyPendingObservers) {
     var pendingObservers = observationState.pendingObservers;
-    observationState.pendingObservers = new InternalArray;
+    observationState.pendingObservers = { __proto__: null };
+    observationState.anyPendingObservers = false
     for (var i in pendingObservers) {

[adamk, 2013/07/23 21:48:08]

Can you change this 'i' to 'priority' to match elsewhere?

[rafaelw, 2013/08/02 20:10:32]

Done.

       CallbackDeliverPending(pendingObservers[i]);
     }