342252 - Make nsDocumentObserverList more generic (create nsTObserverArray)

Status: VERIFIED FIXED

(Core :: XPCOM, defect)

Description

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

bz just landed nsDocumentObserverList which is an array that supports iterators that are safe in the face of the array mutating below them.

However it is specific to storing |nsIDocumentObserver*|s. In an upcoming patch I will need to store another type, so I figured we should turn this into a generic class that is like nsTArray but supports stable iterators. Patch to implement this comming up.

I didn't add very many functions to this array since they all have to be manually forwarded (when can we start using |using|?). I just stuck to the ones actually needed by the current code.

Comment 1

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: Patch v1

I ended up with a bit more indirection then I wanted for the iterators (the inheritance chain is 3 classes long). However I couldn't figure out a better way without duplicating all of Iterator_common in both iterators, or making all of nsTMutationSafeArrayIterator_base inline. Suggestions welcome.

Comment 2

[Boris Zbarsky [:bzbarsky]]

I'll have more comments when I get a chance to look, but I purposefully didn't implement a ElementAt() method for the observer list -- I see no reason to support unsafe access to this list (which shouldn't even necessarily advertise the fact that it's an array, imo).

Comment 3

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I don't care very much about that, but I think it would be good to keep the array as a genuilly useful replacement for nsTArray

Comment 4

[Boris Zbarsky [:bzbarsky]]

I guess my point is that I don't see when the unsafe access would be useful, given that we know we're working with an array of things that are prone to remove themselves and add others...  Given that and the fact that the access is in fact unsafe, why even expose it?

Comment 5

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Sure, I could keep it private for now, we can always expose it later if there turns out to be valid uses for it.

Comment 6

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Want a new patch for that?

Comment 7

[Darin Fisher]

Maybe a linked list would be better?  Why use an array if you need to have iterators that survive mutation of the collection?  Having to store a collection of iterators on the array object that get updated with each array mutation seems somehow wrong.  Do you need random access and mutation-safe element pointers?  

Does STL or Boost provide this kind of mutation-safe random-access container as well?  If so, how do they implement it?

Comment 8

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

STL only seems to support stable iterators on lists.

I don't see an advantage to using lists. I plan to using this datastructure quite a bit so I want to make it as performant as possible. And even lists doesn't fully solve the problem since iterators pointing on the element that is being removed are invalid after the removal.

I agree that it's unusual to stick a list of iterators into the array itself, but I don't see a better way of solving this problem. If you'd rather that we didn't stick this into XPCOM i'm fine with leaving it in content.

Comment 9

[Boris Zbarsky [:bzbarsky]]

We probably don't need random access, but we want to be able to iterate in both directions (which means we'd need a doubly linked list, which uses more memory), and as Jonas said we'd still need to somehow notify iterators when the list mutates...

Comment 10

[Darin Fisher]

> We probably don't need random access, but we want to be able to iterate in both
> directions (which means we'd need a doubly linked list, which uses more
> memory), and as Jonas said we'd still need to somehow notify iterators when the
> list mutates...

If the iterator is the link node, then nulling out its "prev" and "next" members achieves the affect of notifying it.  The cost of that operation is O(1), whereas the cost in the proposed patch is O(N), where N is the number of iterators.

Suppose you have a mutation-safe array that has M elements and N iterators.  Now, imagine that you wish to remove each element of the array.  That becomes an O(M x N) operation.  The equivalent operation on a linked list is O(M).

I'm concerned that this patch hides an O(n^2) algorithm behind an attractive APIs that may be easily misused.

Comment 11

[Boris Zbarsky [:bzbarsky]]

> If the iterator is the link node, then nulling out its "prev" and "next"
> members achieves the affect of notifying it.

Sure, but then it needs to somehow tell the person doing the iterating that it needs to grab a different pointer, no?  Or something?

I have to admit that I designed the original code for the case of N <= 2 (which is what it was in all my testing) and the array very rarely mutating during iteration (also a good assumption in nsDocument)...

Comment 12

[Darin Fisher]

> Sure, but then it needs to somehow tell the person doing the iterating that it
> needs to grab a different pointer, no?  Or something?

I don't understand.  If the goal is to maintain an iterator to a particular element, and that element is contained by a link node, then an iterator can just reference the link node (or be the link node).  What am I missing?

Comment 13

[Boris Zbarsky [:bzbarsky]]

The point is to maintain an iterator to a particular place in the list, such that all things that haven't been iterated yet but were there when iteration started will be iterated.  We're not trying to maintain it at a particular element...  Specifically, the original use case is that there is a list of observers.  We want to notify them, but notifications can remove observers from the list and we need to deal with that sanely (without skipping over any observers when notifying and without notifying observers after removal).

Comment 14

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

The algorithm for removing or adding a single element from an M-element array with N iterators is O(N) time. I could even implement the ability to remove or add any number of consequtive elements in O(N) time if we want. However these functions would not be used yet.

Comment 15

[Boris Zbarsky [:bzbarsky]]

So Darin and I talked about this a bit.  His concern is the "iterate the array, then Clear() it" pattern, which can be expensive if there are lots of live iterators.

We thought of the following possible solution:

1)  Store an array of struct { nsIDocumentObserver* obs; PRBool dead; }
2)  On removal just set the |dead| boolean and increment a counter on the
    array.
3)  On end of outermost iteration (just keep track on the array via another
    counter, probably?) check the first counter.  If it's nonzero, go through
    and remove all structs with dead == PR_TRUE.

The cost is an extra branch per step and an increment/decrement to keep track of outermost iterators, but we can NS_LIKELY(!dead) in the document case; in the document case step 3 would typically be a single check and nothing else since observers are not usually removed.

Also, if we decide we care about space we can store |dead| in the low bit of the pointer...

sicking, what do you think?

Comment 16

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

I really think this is overengineering since in almost all cases we're only going to have a single iterator. I can't think of any algorithm that would produce a large number of iterators for the same list. Especially considering that iterators are expected to live on the stack, so you'd have to do very deep recursion for it to happen.

Calling Clear() is a very cheap operation even with a large number of iterators. It is already O(N).

Worst case, if this datatype becomes heavily used, we could look at optimizing it for how it's used later, all we can do now is guess.

Comment 17

[Darin Fisher]

jonas, i agree that the current application has those characteristics, but the patch introduces something generic that could be misused in other applications.  that worries me.

it also occured to me that the "dead" flag is not needed: you can just set the observer entry in the array to null.  then you could skip over null entries in the array as you are enumerating it and clean up the nulls after you finish enumerating (taking care to check for recursion depth as bz suggested).

instead of a mutation-safe array, maybe it would be better to create a generic "ObserverList" class.  we tend to do array copies in other places (nsObserverService) when enumerating and calling out to observers, but perhaps all of these observer lists need the same treatment as nsDocumentObserverList.

Comment 18

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Yeah, i understand your concern about making this generic. That's why I suggested that we can keep this in /content. Note that using the LSB or null to indicate 'dead' will not work with the class written as-is since it supports storing any type that nsTArray supports.

I'm fine with making this into an 'nsObserverList' class rather than a generic mutation-safe-array. What changes (other than a name-change) do you propose for that?

Comment 19

[Darin Fisher]

Hmm, I think that an "ObserverList" class would provide methods to add, remove,  remove all, and enumerate observers.

There are some choices when it comes to how you might express enumeration.  The visitor pattern is interesting:

  template <class Observer>
  class ObserverList {
  public:
    template <class Visitor>
    void Visit(const Visitor& v) {
      for (PRUint32 i = 0; i < mObservers.Length(); ++i) {
        if (mObservers[i])
          v(mObservers[i]);
      }
    }
  private:
    nsTArray<Observer*> mObservers;
  };

Then, as a consumer you might write:

  class NotifyStuffHappened {
  public:
    void operator()(nsIDocumentObserver *obs) const {
      obs->StuffHappened();
    }
  };
  observerList.Visit(NotifyStuffHappened());

But, maybe iterators are easier to work with.

Comment 20

[Darin Fisher]

Comment on attachment 226466 [details] [diff] [review]
Patch v1

OK, discussed this more with jonas, and he convinced me that the linked list approach is good for stack based recursion.  The depth of that list should always be low, so my performance concerns should be minor.  

We also agreed that a nsObserverList class is probably better than a generic mutation-safe array class since the latter might tempt people into other usage patterns that it isn't designed to handle very well.

Comment 21

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Attachment: Patch v2

This creates an nsTObserverArray which lives in content/base/src

Comment 22

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Darin: I realized that it'll be hard to make the observer-service use this since it does a bunch of things with weakpointers and such, so i decided to stick this in content for now. You are of course welcome to give input on the patch anyway.

Comment 23

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 227334 [details] [diff] [review]
Patch v2

>Index: content/base/src/nsTObserverArray.h

> +        // This function exists soly to avoid having to make the subclasses

"Solely".

>+        // The current position of the iterator
>+        PRInt32 mPosition;

We should probably document what this member means.  Since it's different for the two subclasses, document in the subclasses?

>+     * Adjusts iterators after an element has been inserted or removed
>+     * from the array.
>+     * @param modPos     Position where elements were added or removed.

s/elements were/an element was/

>+    Iterator_base* mIterators;

Shouldn't we init this to nsnull in the constructor?  I don't see us doing that....

>+class nsTObserverArray : public nsTObserverArray_base {

>+     * Adds an observer to the beginning of the array
>+     * @param aObserver Observer to add
>+     * @return True on success, false otherwise
>+     */
>+    PRBool AppendObserver(T* aObserver) {

Fix the "Adds an ..." part of the comment?

r+sr=bzbarsky with that.

Comment 24

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

This was checked in a few days ago

Comment 25

[Brendan Eich [:brendan]]

See js/src/jsxml.[ch], JSXMLArrayCursor and array->cursors for an example of parallel evolution (unless sicking was inspired by it; it was part of the E4X implementation I did in fall, 2004).

/be

Comment 26

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Heh, looks like it works pretty much exactly the same way, except that iterators (cursors) are set up in a double-linked list so that they can be destroyed in any order.