optimized TypeMap

src/object-observe.js

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 49 matching lines @@
     new ObservationWeakMap(observationState.callbackInfoMap);
 var objectInfoMap = new ObservationWeakMap(observationState.objectInfoMap);
 var notifierTargetMap =
     new ObservationWeakMap(observationState.notifierTargetMap);
 
 function CreateObjectInfo(object) {
   var info = {
     changeObservers: new InternalArray,
     notifier: null,
     inactiveObservers: new InternalArray,
-    performing: { __proto__: null },
+    performing: 0,
     performingCount: 0,
   };
   objectInfoMap.set(object, info);
   return info;
 }
 
-var defaultAcceptTypes = {
-  __proto__: null,
-  'new': true,
-  'updated': true,
-  'deleted': true,
-  'prototype': true,
-  'reconfigured': true
-};
+var typeConstants = { __proto__: null };
+var nextTypeConstant = 1;
+var MAX_BITFIELD_CONSTANT = 1 << 30;
 
-function CreateObserver(callback, accept) {
-  var observer = {
+function NormalizeTypeMap(typeMap) {
+  if (IS_NUMBER(typeMap)) {
+    var bitfield = typeMap;
+    var typeMap = [];
+    var constant = 1;
+    while (true) {
+      if (bitfield & constant)
+        typeMap[constant] = 1;
+      if (constant == MAX_BITFIELD_CONSTANT)
+        break;
+      constant = constant << 1;
+    }
+  }
+
+  return typeMap;
+}
+
+function GetTypeConstant(type) {
+  var constant = typeConstants[type];
+  if (!constant) {
+    constant = nextTypeConstant;
+    typeConstants[type] = constant;
+    nextTypeConstant = nextTypeConstant < MAX_BITFIELD_CONSTANT ?
+        nextTypeConstant << 1 : nextTypeConstant + 1;
+  }
+
+  return constant;
+}
+
+function AddToTypeMap(typeMap, type, ignoreDuplicate) {
+  var typeConstant = GetTypeConstant(type);
+  if (IS_NUMBER(typeMap) &&
+      typeConstant <= MAX_BITFIELD_CONSTANT &&
+      (ignoreDuplicate || !(typeMap & typeConstant))) {
+    typeMap |= typeConstant;
+    return typeMap;
+  }
+
+  typeMap = NormalizeTypeMap(typeMap);
+  var value = ignoreDuplicate ? 1 : (typeMap[typeConstant] || 0) + 1;
+  typeMap[typeConstant] = value;
+  return typeMap;
+}
+
+function RemoveFromTypeMap(typeMap, type) {
+  var typeConstant = GetTypeConstant(type);
+  if (IS_NUMBER(typeMap)) {
+    if (typeConstant <= MAX_BITFIELD_CONSTANT && (typeMap & typeConstant))
+      typeMap -= typeConstant;
+  } else if (typeMap[typeConstant] > 0) {
+    typeMap[typeConstant]--;
+  }
+
+  return typeMap;
+}
+
+function CreateTypeMap(typeList) {
+  var typeMap = 0;
+  for (var i = 0; i < typeList.length; i++) {
+    typeMap = AddToTypeMap(typeMap, typeList[i], true);
+  }
+
+  return typeMap;
+}
+
+function TypeMapHasType(typeMap, type) {
+  return TypeMapHasConstant(typeMap, GetTypeConstant(type));
+}
+
+function TypeMapHasConstant(typeMap, constant) {
+  if (IS_NUMBER(typeMap))
+    return constant > MAX_BITFIELD_CONSTANT ? false : typeMap & constant;
+  else
+    return typeMap[constant] > 0;
+}
+
+function TypeMapsIntersect(typeMap1, typeMap2) {
+  if (IS_NUMBER(typeMap1) && IS_NUMBER(typeMap2))
+    return typeMap1 & typeMap2;
+
+  var checkMap = IS_NUMBER(typeMap1) ? typeMap1 : typeMap2;
+  var iterateMap = IS_NUMBER(typeMap1) ? typeMap2 : typeMap1;
+
+  for (var constant in iterateMap) {
+    if (TypeMapHasConstant(checkMap, constant))
+      return true;
+  }
+
+  return false;
+}
+
+var defaultAcceptTypes = CreateTypeMap([
+  'new',
+  'updated',
+  'deleted',
+  'prototype',
+  'reconfigured'
+]);
+
+GetTypeConstant('splice');
+
+
+function CreateObserver(callback, acceptList) {
+  return {
     __proto__: null,
     callback: callback,
-    accept: defaultAcceptTypes
+    acceptMap: IS_UNDEFINED(acceptList) ?
+        defaultAcceptTypes : CreateTypeMap(acceptList)
   };
-
-  if (IS_UNDEFINED(accept))
-    return observer;
-
-  var acceptMap = { __proto__: null };
-  for (var i = 0; i < accept.length; i++)
-    acceptMap[accept[i]] = true;
-
-  observer.accept = acceptMap;
-  return observer;
 }
 
 function ObserverIsActive(observer, objectInfo) {
-  if (objectInfo.performingCount === 0)
-    return true;
-
-  var performing = objectInfo.performing;
-  for (var type in performing) {
-    if (performing[type] > 0 && observer.accept[type])
-      return false;
-  }
-
-  return true;
+  return objectInfo.performingCount === 0 ?
+      true : !TypeMapsIntersect(objectInfo.performing, observer.acceptMap);
 }
 
 function ObserverIsInactive(observer, objectInfo) {
   return !ObserverIsActive(observer, objectInfo);
 }
 
 function RemoveNullElements(from) {
   var i = 0;
   var j = 0;
   for (; i < from.length; i++) {
@@ skipping 16 matching lines @@
       anyRemoved = true;
       from[i] = null;
       to.push(observer);
     }
   }
 
   if (anyRemoved)
     RemoveNullElements(from);
 }
 
+function ObjectAddPerformingType(objectInfo, type) {
+  if (!objectInfo.performing) {
+    objectInfo.performing = AddToTypeMap(0, type);
+    objectInfo.performingCount = 1;
+    return true;
+  }
+
+  var hadType = TypeMapHasType(objectInfo.performing, type);
+  objectInfo.performing = AddToTypeMap(objectInfo.performing, type);
+  objectInfo.performingCount++;
+  return !hadType;
+}
+
+function ObjectRemovePerformingType(objectInfo, type) {
+  if (objectInfo.performingCount == 1) {
+    objectInfo.performing = 0;
+    objectInfo.performingCount = 0;
+    return true;
+  }
+
+  objectInfo.performing = RemoveFromTypeMap(objectInfo.performing, type);
+  objectInfo.performingCount--;
+  return !TypeMapHasType(objectInfo.performing, type);
+}
+
 function BeginPerformChange(objectInfo, type) {
-  objectInfo.performing[type] = (objectInfo.performing[type] || 0) + 1;
-  objectInfo.performingCount++;
-  RepartitionObservers(ObserverIsInactive,
-                       objectInfo.changeObservers,
-                       objectInfo.inactiveObservers,
-                       objectInfo);
+  if (ObjectAddPerformingType(objectInfo, type)) {
+    RepartitionObservers(ObserverIsInactive,
+                         objectInfo.changeObservers,
+                         objectInfo.inactiveObservers,
+                         objectInfo);
+  }
 }
 
 function EndPerformChange(objectInfo, type) {
-  objectInfo.performing[type]--;
-  objectInfo.performingCount--;
-  RepartitionObservers(ObserverIsActive,
-                       objectInfo.inactiveObservers,
-                       objectInfo.changeObservers,
-                       objectInfo);
+  if (ObjectRemovePerformingType(objectInfo, type)) {
+    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;
       }
     }
@@ skipping 30 matching lines @@
   var callbackInfo = callbackInfoMap.get(callback);
   if (IS_NUMBER(callbackInfo)) {
     var priority = callbackInfo;
     callbackInfo = new InternalArray;
     callbackInfo.priority = priority;
     callbackInfoMap.set(callback, callbackInfo);
   }
   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);
+  var observer = CreateObserver(callback, acceptList);
   if (ObserverIsActive(observer, objectInfo))
     objectInfo.changeObservers.push(observer);
   else
     objectInfo.inactiveObservers.push(observer);
 
   return object;
 }
 
 function ObjectUnobserve(object, callback) {
   if (!IS_SPEC_OBJECT(object))
@@ skipping 20 matching lines @@
   return ObjectUnobserve(object, callback);
 }
 
 function EnqueueToCallback(callback, changeRecord) {
   var callbackInfo = NormalizeCallbackInfo(callback);
   observationState.pendingObservers[callbackInfo.priority] = callback;
   callbackInfo.push(changeRecord);
   %SetObserverDeliveryPending();
 }
 
+function ObserverAcceptsType(observer, type) {
+  return TypeMapHasType(observer.acceptMap, type);
+}
+
 function EnqueueChangeRecord(changeRecord, observers) {
   // 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;
-
-    EnqueueToCallback(observer.callback, changeRecord);
+    if (ObserverAcceptsType(observer, changeRecord.type))
+      EnqueueToCallback(observer.callback, changeRecord);
   }
 }
 
 function BeginPerformSplice(array) {
   var objectInfo = objectInfoMap.get(array);
   if (!IS_UNDEFINED(objectInfo))
     BeginPerformChange(objectInfo, 'splice');
 }
 
 function EndPerformSplice(array) {
@@ skipping 155 matching lines @@
     "observe", ArrayObserve,
     "unobserve", ArrayUnobserve
   ));
   InstallFunctions(notifierPrototype, DONT_ENUM, $Array(
     "notify", ObjectNotifierNotify,
     "performChange", ObjectNotifierPerformChange
   ));
 }
 
 SetupObjectObserve();