Mapping Shared Objects to Arrays
..or how to fill a list box from a shared object

A common programming task when building communication applications is to list the contents of a remote shared object within a list box or data grid component. People lists and lists of available streams are two common examples. Whenever a remote shared object changes, the list box or data grid has to be updated. Updating the list or data grid can be done right in a shared object's onSync() method or in a function or method called by onSync(). This short tutorial explores two common difficulties in updating list-like components from shared objects. The first problem is that there is a mismatch between shared objects and the numbered item list model of list components. Lists and DataGrids rely on a default DataProvider array that stores items in indexed slots. Shared objects store data in unordered slots by property name. The second problem is that the methods most often employed to update a list or data grid always make a redraw request of the list or data grid. Calling several of these methods one after the other results in multiple and unnecessary redraw requests. The List and DataGrid classes are smart enough that they will not redraw themselves whenever a redraw request is made. They will wait until the next frame of the movie has to be displayed and redraw themselves once. Nevertheless, there is still a serious performance penalty to be paid for making unnecessary redraw requests.The first problem is a difficult one that requires some judgment about how big the shared object is likely to get and how often it will be updated before being tackled. Fortunately, the second problem is easy to fix.

Mapping Shared Objects to Arrays

The basic problem of filling a list box or data grid with shared object data is that the shared object is an unordered associative array that keeps data in slots accessed by property names. The List and DataGrid components store items by number in an array with some extra features that make the array into a DataProvider. For the List or DataGrid to work they need to access each item by index number. So there is no obvious one-to-one mapping of data in shared object slots to the numbered slots in an array. The usual approach to this problem is simple: delete anything in the list or data grid and then fill the list or grid with items by copying every slot in the shared object into the list. Here is a simple and fairly typical SharedObject onSync() method:

/** onSync version A */
function onSync_a(list){
  lb.removeAll();
  for (var p in so.data) {
    lb.addItem(p, so.data[p]);
  }
}

Note: the method is named onSync_a in this example because it is called from another onSync() method that was used to time how long it takes to update the list.

In the onSync_a code, a List instance named lb is cleared by calling removeAll() and is filled by retrieving each item in the shared object and adding an item in the list for it. In this example the property name of each shared object slot p is retrieved in a for in loop and is used as the item label. Whatever is in the slot becomes the data property of the list item. This is just one way to do it. The shared object slot name does not have to be used as an item label. For example if the shared object slot contained a user record object you might add and item this way:

lb.addItem(so.data[p].userName, so.data[p]);

I'll show a simple example later for a DataGrid. However, for now I'll use the case where the property name of each shared object slot is assigned to the item label.

In theory, if remote shared objects were never updated this simple onSync() method would not be a problem - it could be used once to fill the list and that would be it. However, what happens if one item changes in a shared object? When onSync() is called the entire contents of the list are deleted and the list is refilled. Every time the shared object changes the entire list is deleted and refilled. It would be much more efficient if the onSync() method could easily find the list item that needs to be updated and just replace that one item. Lists and DataGrids have a method called replaceItemAt() that can be used to replace an item once you know its index number. However, the problem is finding the item to replace. To find an item by its label for example, you have to search through the list one item at a time because the List and DataGrid classes do not keep a separate index of what item contains a given label. When several items in a shared object change, searching for each one in the list could take a long time. This is no surprise either. Lists may be used in other circumstances and contain identical labels. Or the key that uniquely identifies an item in a list may be part of the data property of the item - not the label. DataGrids have multiple columns and there is no reason they should assume one is the unique property name of a remote shared object. There are two basic approaches to this problem: search through the list/data grid or write a custom indexed DataProvider for the list. I'll discuss these possibilities shortly and implement the first one. However, in order to talk about DataProviders lets look at the second problem.

Redundant List Update Requests

The main problem with the version A onSync is that every method of the List component not only updates the list's dataProvider array but also sends a message to the list that it needs to redraw itself. In fact the list doesn't need to redraw itself until the very last item has been inserted into its dataProvider. Fortunately, the v2 List component provides a dataProvider property that allows you to retrieve its DataProvider and manipulate it directly. The version B onSync method below does exactly that. It gets the dataProvider and uses array methods (splice and push) directly on the dataProvider to remove everything in it and add in new items. When all the items have been inserted into the dataProvider array it sends a single message that will result in the list being redrawn.

/** onSync version B */
function onSync_b(list){
  // Get the list's dataProvider and truncate it.
  var dp = lb.dataProvider;
  dp.splice(0);
  // Fill the dataProvider using the native array method
  // or your choice. In this example: push()
  for (var p in so.data) {
    dp.push({label:p, data:so.data[p]});
  }
  dp.dispatchEvent({target:dp, type:"modelChanged"});
}

So instead of lb.removeAll() the version B onSync calls dp.splice(0) to remove all the items in the array. Instead of lb.addItem(p, so.data[p]); it calls dp.push({label:p, data:so.data[p]}); to add a new item to the array. An item is an object with a label and data property that is normally created from the parameters passed into addItem(label, data). In the statement dp.push({label:p, data:so.data[p]}); the item is created as an anonymous object and pushed onto the array. The list's dataProvider is also an event broadcaster that the list has been setup to listen to. To tell the list to redraw itself, after the last change has been made to the array, the DataProvider only has to dispatch a "modelChanged" event this way: dp.dispatchEvent({target:dp, type:"modelChanged"}); and the list will redraw itself.

How much of a performance difference does this make? It turns out the difference is huge! Consider the case where there are ten items in a list and one slot of the shared object changes. On one 800 MHz test machine the version A onSync took eight milliseconds to update the list while the version B onSync only took one. When the list had 40 items in it and one slot was changed, version A took 26 milliseconds versus version B's 3 milliseconds. The full test results are below. One more statistic: it took version A 53 milliseconds to add 100 items to an empty list and version B only 4 milliseconds. When you consider that there are only 83 milliseconds between frames in a 12 fps movie and that every Flash movie has other things to do between frames the difference between 8 and 1 or 26 and 3 milliseconds is really significant. In fact for lists that will hold no more than 50 items the version B onSync works very well. It also has the advantage of being very simple and short. In fact version B is so good that it may be all you need. However, it will not handle large shared objects very well. For example version B took 24 milliseconds to update a list of 400 items when one shared object slot changed. It took 72 milliseconds to update the list when there were 1000 slots. (Of course version A took 585 milliseconds!)

The problem is that even version B is still deleting all the data in the array and then adding all the current items back in. There has to be a better way to deal with updating lists for shared objects between 50 and 1000 slots in size. The version C onSync below works differently. It searches for items in the array that need to be deleted or replaced and either deletes the individual items from the array or replaces them. Then, it adds any new elements to the array. In the special case where a shared object has been cleared and synchronized version C just calls the version B onSync to fill the list. Have a look at the version C code to see how it works. A more detailed explanation follows.

/** onSync version C */
function onSync_c(list){
  // If the shared object has been cleared rewrite the list
  // using version B.
  if (list[0].code == "clear") {
    onSync_b(list);
    return;
  }

  // If it hasn't just been cleared, update it.
  // Start by building a hash of slot names so we only have to
  // walk down the dataProvider array once looking for slots
  // that need to be updated or deleted.
  var names = {};
  for (var i in list){
    var info = list[i];
    // Put the info object into the names hash
    names[info.name] = info;
  }

  // Walk through the dataProvider array
  // looking for the items in the names hash by name:
  var dp = lb.dataProvider;
  for (var i = 0; i < dp.length; i++){
    var label = dp[i].label;   // Get the label of item i in the array
    var info = names[label];   // Look it up in the names hash.
    if (info){                 // If it's in the names hash
      // If the info object code is delete remove it from the array.
      if (info.code == "delete"){
        dp.splice(i, 1);       // delete the item from the list.
        i--;                   // decrement i to adjust for splice
      }
      // Otherwise the info object code is change, success, or reject
      // so update the array by replacing the item in it.
      else{
        dp[i] = {label:label, data:so.data[label]};
      }
      // Delete this entry in the names hash so we are only left with
      // entries that were not found in the array.
      delete names[label];
    }
  }

  // Add any new records that are left in the names hash.
  for (var p in names){
        dp.push({label:p, data:so.data[p]});
  }
  // Tell the list that the model has changed and to redraw itself now.
  dp.dispatchEvent({target: dp, type:"modelChanged"});
}

The onSync() method is always passed an array of information objects. The information objects always have a code property. If the code value is clear that means that any data that was in the shared object has been deleted and that all the data in the object now is new. Otherwise the code property of each information object will be one of changed, rejected, deleted, or success. These codes all provide information about what has happened to a particular slot so the information object also contains a name property to identify the slot.

In the special case where the shared object has been cleared the first information object will have a code value of clear. The version C onSync tests for it this way:

function onSync_c(list){
  if (list[0].code == "clear") {
    onSync_b(list);
    return;
  }
  //...

Then it just calls the version B onSync method and returns. If the shared object has not been cleared the list array contains information objects that describe what has happened to each slot in the shared object. To help visualize what is in the information list passed into the shared object onSync() method here is how you might create a similar list using ActionScript:

list = [
{code:"change", name: "blesser"},
{code:"delete", name: "rob"},
{code:"success", name:"peldi"}
]

To avoid searching through the list for each item that has changed, one item at a time, an object is created called names that contains the name of every slot that has been updated, added, or deleted in the shared object. Here is how the names object is built:

var names = {};
for (var i in list){
var info = list[i];
// Put the info object into the names hash
names[info.name] = info;
}

Remember list is the list of information objects passed into onSync - not the listbox.

Once we have all the names in one object we can start searching through the dataProvider array to see if any of the names match the labels in the array one-by-one:

var dp = lb.dataProvider;
for (var i = 0; i < dp.length; i++){
var label = dp[i].label; // Get the label of item i in the array
var info = names[label]; // Look it up in the names hash.
if (info){ // If it's in the names hash
// Do something here with item number i in the dp array.
}
}

The code above gets an information object from the names object if one is there:

var info = names[label];

If the label matches and entry in the name object, info will be an information object, otherwise it will be undefined and the following if(info) test will fail. Once we've paired up an information object with a list item there are two possibilities. Either the item in the list should be deleted or it should be replaced with the most recent data from the shared object. The follow code uses the array splice() method to delete a slot from the array and directly assigns a new information object to a slot in the array if the item must be replaced.

if (info){ 
// If the info object code is delete remove it from the array.
if (info.code == "delete"){
dp.splice(i, 1); // delete the item from the list.
i--; // decrement i to adjust for splice
}
// Otherwise the info object code is change, success, or reject
// so update the array by replacing the item in it.
else{
dp[i] = {label:label, data:so.data[label]};
}
// Delete this entry in the names hash so we are only left with
// entries that were not found in the array.
delete names[label];
}

This snippet of code does one more thing. After a list item has been deleted or replaced the entry in the names object for it is deleted. After every list item is checked any entries in the names object represent new slots in the array that have to be added to the list:

// Add any new records that are left in the names hash.
for (var p in names){
      dp.push({label:p, data:so.data[p]});
}

After any items in the list have been deleted or replaced, and any new items have been added, the dataProvider informs the list that it has changed:

dp.dispatchEvent({target: dp, type:"modelChanged"});

and the list redraws itself.

The version C onSync provides better over-all performance for large shared objects than version B. Even better performance might be possible by creating a customized DataProvider that indexes each item by label so that every item can be found without a linear item-by-item search. Building and maintaining an index of labels would increase the time it takes to insert and delete individual items but would speed up finding them. A custom DataProvider has not been created for this tutorial.

List Test Results

These test results were run on my 800 MHz laptop and are not meant to give a complete performance picture of the behaviour of the three onSync methods. The numbers are the milliseconds it took for the onSync method to update a list after a change. Updates were run against shared objects with different numbers of preexisting slots.

 

Time in milliseconds to complete an onSync() call after 10 records were added or after one record was updated.
Existing
Slots
onSync A onSync B onSync C
update 1 add 10 update 1 add 10 update 1 add 10
0   8   1   2
10 8 14 1 2 1 2
20 14 20 2 3 1 2
30 20 27 2 3 1 2
40 26 34 3 4 1 2
50 33 40 4 4 2 2
60 39 45 4 5 2 3
70 45 51 5 5 2 3
80 53 62 6 6 2 3
90 57 64 6 7 2 3
100 64   7   2  

 

Time in milliseconds to complete an onSync() call after 100 records were added or after one record was updated.
Existing
Slots
onSync A onSync B onSync C
update 1 add 100 update 1 add 100 update 1 add 100
0   53   4   6
100 54 109 6 9 2 8
200 109 165 11 17 3 9
300 177 219 17 21 4 10
400 220 276 24 28 5 11
500 278 341 29 34 6 13
600 344 405 35 40 8 14
700 400 467 54 47 8 15
800 462 508 60 52 9 16
900 524 588 65 59 10 18
1000 585   72   11  

DataGrid Updates

The options in updating DataGrids aren't much different from updating lists. Here is a very simple version of the version B onSync that refills a DataGrid. However, you should not use this as it produces redundant shared object updates. Avoiding redundant updates is described later.

function onSync_b(list){
  // Get the DataGrid's dataProvider and truncate it.
  var dp = dg.dataProvider;
  dp.splice(0);
  // Fill the dataProvider using the native array method
  // of your choice. In this example: push()
  for (var p in so.data) {
    dp.push(so.data[p]); // PROBLEM: this line leads to redundant shared object updates!
  }
  dp.dispatchEvent({target:dp, type:"modelChanged", eventName: "updateAll"});
}

Before fixing the problems with this code, there are a few things to note about it. First dg is an instance of DataGrid. Second, the contents of each shared object slot is added directly to the DataProvider. DataGrids expect objects in each slot of the DataProvider so if the slot does not contain an object this will not work. By default the property names of the object are used for column headers and the values of each property appear in each row of that column. In this example we are therefore assuming that the shared object slot contains an object. Third, and most important is that the eventName property has been added to the event that is dispatched. The DataGrid will not scroll properly unless it is told to "updateAll." This is a very simple, generic, and as we'll see problematic example of filling a DataGrid. (See Macromedia's DataGrid documentation on how to setup and format a DataGrid.)

There are two problems here that may not be immediately apparent. The first is that the slot name is not being added into the item. In the previous list examples the label property of each list item determined what showed up in the list. In the previous examples the slot name was used for the label:

for (var p in so.data) {
  dp.push({label:p, data:so.data[p]}); // Add an item to the list's DataProvider
}

In the list example above an anonymous object is created with a label property based on the name of the slot and a data property that contains whatever is in the slot However in the DataGrid example the slot name was not used:

for (var p in so.data) {
  dp.push(so.data[p]); // PROBLEM: this line leads to redundant shared object updates!
}

If the slot name is duplicated within the object this is not a problem. Otherwise we have to create a new object and add in the property name of the slot. Here is one way of many to do this. For illustration purposes I assume each slot contains a user record and that the slot name is a unique user name:

function onSync_b(list){
  // Get the DataGrid's dataProvider and truncate it.
  var dp = dg.dataProvider;
  dp.splice(0);
  // Fill the dataProvider using the native array method
  // of your choice. In this example: push()
  for (var p in so.data) {
     var obj = so.data[p];
     // compose an anonymous object from data in the shared object slot.
     dp.push({userName:p, firstName:obj.firstName, lastName:obj.lastName}); // No Problem.
  }
  dp.dispatchEvent({target:dp, type:"modelChanged", eventName: "updateAll"});
}

In other words the answer is to go back to composing an anonymous object but in this case to copy all the data from the slot and the slot name into the anonymous object before adding it to the data provider. One drawback to this approach is that all the data in the shared object is being duplicated in each item. In the case of the list we could at least set each item's data property to point directly at the shared object slot.

As mentioned earlier there is a second problem with using shared object slots directly as items in a DataProvider. After an item is added to a DataProvider, at some point the DataProvider adds a hidden __ID__ property to each item. It uses the ASSetPropFlags() function to hide it, but it is still there. When the __ID__ property is added to the item, and the item is also an object in a shared object slot, the shared object will detect that the slot has been updated. So the new data will be sent to the server, copied to all the other clients, and onSync() will be called on the other clients. To avoid this happening you can follow this simple rule:

Never place a shared object slot value directly into a DataProvider.

Instead, create a separate DataProvider item and copy data from the shared object slot into it. You can use anonymous objects or named objects. In other words never do this:

dp.push(so.data[p]); // PROBLEM: this line leads to redundant shared object updates!

But this is OK:

var obj = so.data[p];
// compose an anonymous object from data in the shared object slot.
dp.push({userName:p, firstName:obj.firstName, lastName:obj.lastName});

and this is OK too:

// Create an object to copy slot data into:
var myClone = {};
// Get a reference to the object in a shared object slot:
var slotValue = so.data[p]; // Copy all the data in the slot to myClone:
for (var propertyName in slotValue){
myClone[propertyName] = slotValue[propertyName];
} //For good measure add in the userName in p: myClone.userName = p; // Now push the cloned object into the DataProvider: dp.push(myClone);

Summary and Conclusions

For most applications the versions B onSync performs reasonably well. For small shared objects it even performs better than the more complex version C onSync. In real applications the onSync methods shown here will have to be adapted to do other things. Adapting version B will be a lot easier than adapting version C and will minimize the possibility of introducing bugs. If you need to work with large shared objects consider version C or writing your own custom DataProvider. And finally, never use a shared object slot as a DataProvider item.

Credits

Thanks to Nigel Pegg, Justin Watkins, Peter Hall, and Chafic Kazoun for either sending me corrections/suggestions/information or for their posts on the Flashcomm mailing list. Most of the thread on redundant updates is available here: http://chattyfig.figleaf.com/ezmlm/ezmlm-cgi/3/13845 Also, of note is Justin Watkins way of pre assigning __ID__ values to avoid redundant updates: http://chattyfig.figleaf.com/ezmlm/ezmlm-cgi/3/13862


Post or read comments for this page.


Document first posted January 10, 2004 by Brian Lesser
Updated with corrections and small additions January 11, 2004.
Updated with corrections and additions (especially about redundant updates) April 30, 2004.