March 20, 2010


Filed under: Uncategorized — frameworker @ 7:52 pm

I’d been testing PDQForms and hadn’t seen any performance problems, but then I saw a noticable recalculation delay when certain fields were changed in a particular form.

After a moment of doubt whether my approach was simply wrong, I sucked it up and asked myself “What would Mike Ash do?”

So I jumped into the debugger, and after tracing the flow of execution – aided by liberal logging of intermediate results – I realized that I was seeing a cascading dependency problem.

I was adding a notifier for each cell reference in a formula, so when it had more than one reference to the same cell, I was creating duplicate notifiers. And if that cell was referenced more than once in another cell’s formula, there would be duplicated recalculations. This is what I was seeing*. And the problem could become arbitrarily worse than this, since there could be an indefinite coupling of such formulae. Ouch!

* Formula A, of cell a, has n references to cell b, who’s formula B contains m references to cell c. So when cell c changes, formula B would be recalculated m times and formula A would be recalculated m * n times.

The solution to this cascading dependency problem was to allow only one notifier for any cell reference in a formula, even if the cell was referenced more than once in that formula.


When a PDQ document is opened, its form widgets are “internalized.” One step in this process is, for widgets that have a formula, to add observers to cells referenced by that formula. This stack-trace depicts the widget internalization pattern.

-[PDQDocument windowControllerDidLoadNib:]
Code added here is executed when the windowController has loaded the document’s window.

  -[PDQDocument internalizeWidgets]
  This contains the widgets’ internalization logic.

    -[PDQDocument observeReferencedCells]
    This document method calls observeReferencedCells for each widget.

      -[PDQAbstractWidget observeReferencedCells]
      Adds notifications to observe each cell referenced by this widget.

        -[NSString coalesceObservers]
        Constructs the observer list and removes duplicates, before adding notifications.


Here is the add/coalesceObservers code associated with the widget internalization pattern.

observeReferencedCells creates an array of the referenced cell IDs. Then it finds the object referenced by each ID and adds an observer to it.

- (void) observeReferencedCells
    if ([self hasExpression])
        NSMutableArray * observers = [[self expression] coalesceObservers];

        int index;
        for (index = 0; index < [observers count]; index++) // Work OK for empty array?
            NSString * theToken =  [observers objectAtIndex:index];
            // iterate the document's widgets (a global variable)

            PDQAbstractWidget *referencedCell = [self findWidgetWithID:theToken];
            [self addObserverToReferencedCell:(PDQAbstractWidget *)referencedCell];

coalesceObservers constructs the observer list, avoiding duplicates, by copying one instance of each cellRef token into coalescedObservers before adding notifications

- (NSMutableArray *) coalesceObservers
    NSMutableArray * theTokens = [self createTokensForExpression];
    NSMutableArray * coalescedObservers = [NSMutableArray array];

    int index = 0;
    while (index < [theTokens count])
        NSString * theToken = [theTokens objectAtIndex:index];

        if ([theToken tokenType] == eCellRefToken)
            [coalescedObservers addObject:theToken];
            // Remove all occurrences of theToken from theTokens.
            [theTokens removeObject:theToken];

    return coalescedObservers;

When theReferencedCell changes value addObserverToReferencedCell tells the dependent cell to handleVariableChanged by sending the NSNotificationCenter a changed message.

The NSNotificationCenter then sends the observer a PDQReferencedCellChanged message with an object reference to the cell that changed.

- (void) addObserverToReferencedCell:(PDQAbstractWidget *)theReferencedCell
    NSNotificationCenter* nc = [NSNotificationCenter defaultCenter];

    [nc addObserver:self
           name    :@"PDQReferencedCellChanged"
           object  :theReferencedCell];

handleReferencedCellChanged is the “action procedure” being set by addObserverToReferencedCell.

// Update the cell's value since a cell it depends on has changed.
- (void) handleReferencedCellChanged:(NSNotification *)notification
    [self recalculate];
    // Now say "changed" to tell the cells that depend on me to update also. 
    NSNotificationCenter* nc = [NSNotificationCenter defaultCenter];
    [nc postNotificationName:@"PDQReferencedCellChanged" object:self];


Blog at