View RSS Feed

Development Team Blog

Arrays & Structs in-depth Part VI

Rate this Entry
In Part V we realized that there's a very common mistake one can make when working with array properties and trying to write code designed after the old Array class interface, which can cause performance issues. When making changes to array properties, and you're concerned about performance, the key thing is to coalesce/combine all changes into one transaction. Remember that a Get property is always super-fast. There's no copy whatsoever when you get an array property to a local variable. Here's the kicker, a Set property is most of the time also very fast. What's potentially slow is the combination of Get-Modify-Set. But, and this is important, it has virtually a one-time cost hit per Get-Modify-Set.

Think of a Get-Modify-Set combination as a transaction. It's the transaction as a whole that has a performance cost, not so much what you do in the transaction. This means that the more transactions you have, the worse the performance gets. And obviously the fewer transactions you have, the better performance you get.

Code:
    Procedure SetTestItem Integer indx String sValue
        String[] myArray
        Get pTestArray to myArray
        Move sValue to myArray[indx]
        Set pTestArray to myArray
    End_Procedure

    Procedure DoStuff
        ...
        For i from 0 to 2000
            Send SetTestItem i "string test"
        Loop
        ...
    End_Procedure
Notice that the highlighted code is one Get-Modify-Set transaction. Notice how this is called repeatedly in the loop, causing over 2000 Get-Modify-Set transactions. This will lead to very poor performance.

The Fast One Transaction Solution
The very simple, and some might say intuitive and perhaps even easier to read, alternative is something like this:
Code:
    Procedure DoStuff
        ...
        Get pTestArray to testArray
        For i from 0 to 2000
            Move "string test" to testArray[i]
        Loop
        Set pTestArray to testArray
        ...
    End_Procedure
Notice that with this trivial change, the number of Get-Modify-Set transactions has gone from 2001 to just one, that's right, only one transaction. Keep in mind that our only concern at the moment is the array property. This is the difference between a quadratic algorithm, O(n2), which in worst case scenario could be touching and copying n*n elements, down to a linear algorithm, O(n), which in worst case scenario could be touching and copying n elements.

Notice also how the original code wasn't any simpler or easier to read/follow or even write. We removed the access methods, resulting in less code overall. And the For loop is still exactly the same number of lines. We traded one line of code for another in the actual loop, where the original line of code in the loop arguably was not easier to read/follow than the new line of code (some might even argue that the intent and side effects of the new line of code is clearer than the original one).

And here's the chart for populating the array with the new code:



As you can see, the performance is now linear as we expected from the beginning. Notice also the actual difference in time, the old-school solution takes 460ms to populate the array with 2000 elements, whereas the new One-Transaction code takes only 1.25ms to populate the array with 2000 elements, that's a huge win. If you're still not convinced, look at the below chart comparing total performance for both methods side by side:



No Access Methods
So it's much faster without the access methods, but they seemed so neat, isn't this bad coding? This can be a little tricky to get used to, but it's really the old screw and hammer issue all over again. Think of it this way; you're not adding an access method for the property, you're adding an access method for the individual elements of the array property. That's a rather odd thing to do when you think about it. The native array type is a full-fledged type like any other data type. If you have a struct property for example, you wouldn't add access methods for getting/setting individual members/elements of the struct, would you? A DateTime property can be considered to consist of month, day, year and a time portion, but you wouldn't provide access methods for setting the individual elements of the DateTime property separately, it would be ridiculous. You consider all the parts of a DateTime property together, getting/setting the property as an atomic operation. Same thing with a struct type property, you get/set the struct property as a whole, why should an array type property be any different?

The tricky thing about this is that it changes the way you think about working with the array, which is really the whole point, changing from Array object to the native array type. This changes the way you design code working with the array. In most cases if you think it won't work because you're working with one element at a time, then either a) it's not a performance issue because there really is no loop, or b) you just need to move up one abstraction level to find the actual loop and push the code up.

I know this can be difficult to grasp, we're so used to the old Array class interface. Another way to look at it is to consider the purpose of the access methods, which is to provide a higher level abstraction and hide the low-level details. In the Array class for example, the access methods are hiding the low-level details of calculating memory address offsets, reallocating memory for the array and copying elements.

The native array type has dedicated syntax for exactly the same purpose, Move 1234 to myArray[4], provides the exact same abstraction, just a different syntax (some might say a more intuitive and easier syntax). The important thing to realize is that it's really the same abstraction, and providing another wrapper for the same abstraction level with just a different syntax is in most cases not adding much value. We're just so tempted to do it because it makes the code look like the old familiar Array class.

Does this mean that you should now change all your code and remove access methods? No, not at all. There's nothing wrong with providing access methods for individual elements of an array property. In fact, in some cases it actually really does make things easier and provides a higher abstraction level. Sometimes you want to hide the details of an array property altogether, by for example providing an access method that always returns the last element for some purpose. Marcia's cStack class is an excellent example of where such a wrapper hides the details of how the stack is implemented and provides appropriate access methods for manipulating the stack.

Remember that it all depends on the level of abstraction required from the calling code. If the calling code is working with the whole array, getting/setting multiple elements in a loop, then the proper abstraction is at the array type level. The tricky part is looking far enough to see if there is such a loop or not, and deciding on the appropriate abstraction level. That was something you couldn't do with the old Array class, you didn't have that choice because there was no such thing as a native array type for array variables. So the native array type gives you more choice and greater flexibility, and that's a good thing.

Finally, remember that unless you have determined that there really is a performance issue, there really is nothing wrong with using access methods for individual array elements. Even in the extreme case above, 450ms out of something in real code that maybe takes 5 seconds or more to complete, is not something your user is going to notice one way or another anyway. It's all about trade-offs and priorities, there may be other things in the program that are far more important and where some other performance improvement can make a more significant difference. But for those really performance critical areas, you will now have a better understanding of how you can make array properties super fast.

Bonus trivia: One might think that the Get-Modify-Set combination means that both the Get and the Modify are super fast, and all the performance cost is incurred by the Set. But that's not really true. The cost is actually at the Modify operation in the middle. But then how can it be faster? It get's really complicated, but it's related to that the cost occurs when copying elements, which only occurs the very first time that you modify the local array variable (copy-on-write, remember?) within the Get-Modfy-Set transaction (one-time cost per transaction). This means that in the code above, the cost is incurred the first time the local variable is modified in the loop. All the other times an element is added to the local array variable in the loop are then for free so to speak. A helpful way to understand copy-on-write is to think of passing array values via parameters and return values as by-value like any other data type, that is the value is copied every time and changes do not affect the original array, but with the added twist that the copy operation is deferred until it's absolutely necessary. In most cases the copy operation isn't necessary (as long as you don't attempt to modify the value), and then you have gained performance as you avoided the potentially expensive and useless copy operation. There's an additional cost when destroying elements which occurs at the Set (it destroys the old array property value), but that's usually negligible.
Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	without-access-methods.jpg 
Views:	2036 
Size:	40.3 KB 
ID:	3773   Click image for larger version. 

Name:	array-property-comparison.jpg 
Views:	2055 
Size:	46.0 KB 
ID:	3774  
Attached Thumbnails Attached Files

Comments

  1. Mike Peat's Avatar
    Sonny - I just tried the same thing, but comparing doing 2,000 tests:
    1. Using an a access method which gets/sets>
    2. Just setting the array elements in the loop
    3. Combining, but doing the get/set just once and passing the array variable by reference to the setter (see code below)

    Results were as you described (but slower, because I'm using my old, crufty laptop):
    1. 6,176ms
    2. 16ms
    3. 16ms


    Of course the example is trivial, but shows that you can pass ByRef arrays around with no extra cost.

    Mike

    Code:
       Procedure SetItem String[] ByRef asTest Integer idx String sVal
          Move sVal to asTest[idx]
       End_Procedure
       
       Procedure RunTest Integer iTimes
          Integer i
          String[] asTest
          
          Get pasTest to asTest
          
          For i from 0 to iTimes
             Send SetItem (&asTest) i ("Item" * String(i))
          Loop
          
          Set pasTest to asTest
       End_Procedure
  2. Frank Cheng's Avatar
    The examples were all good and dandy. However in some of our cases the modification happens during an event and there is no way to group it. Here are some examples I have

    Buliding a color tree

    In our software we added code to allow different fonts and text color / background color for EACH tree node. Each tree node represents a record in the database. In order to determine the font/color of that node, one would have to do quite a bit of "Find" in other tables. In a color tree that has many items (thousands), the initial building of the tree would take way to long because of the other table "Find". Therefore we are relying on the event OnGetDispInfo (TVN_GETDISPINFO) to determine the color of the node, some kind of "delay load" if you will. During the initial population of the tree, the calls "AddTreeItem" would store the item number of the treenodes property to ItemData. As you can see, we are now attaching more info than just the recnum to each node. We would now have a struct for each node

    Code:
    Struct ColorTreeNode
       Integer iBgColor
       Integer iColor
       Integer iFontStyle // Bold/Underline/Italic
       Integer iRecnum
    End_Struct
    Therefore we have a property like this

    Code:
    Class cColorTree is a Tree
    ....
        Property ColorTreeNode[] ctnNodes
    ...
    End_Class
    As you can see, during the "OnGetDispInfo", I would then have to get the property, modify it, and set it back. For the most part it wasn't bad because the tree can only display so many items at a time. The killer comes when the user decides to do a expand all to the tree, and the event OnGetDispInfo gets hit one by one. I ended up have to write a virtual memory style of C Array in a dll to solve this problem.

    Totals in big report

    Another example would be keeping track of totals (using array property) for each record during a big report. Here I am with a parent-child-grandchild relationships. Doing a report on the parent, and keeping track of the totals (more than one) for each parent record. In order to calculate the totals, I would have to look up many records in "unrelated" tables as well as child tables. However "Body" is more like an event getting called for each record is found, and I haven't found a way to "group" the transaction.

    Giangantic BPO with nested procedures and functions

    Final example would be similar to the previous one. A giangatic BPO that will calculate a bunch of totals for each record (not just parent records) and keep track for many other different things. For this one I know how to solve it, but it would be painful. First of all lump every array to a giangantic struct. Then within the BPO every single procedure and function would have to expect a pass-by-reference struct to fill in the information as they are totalling up things. This approach bypasses all the setting/getting/modifying of properties.

    Frank Cheng
    Updated 25-Sep-2009 at 09:38 AM by Frank Cheng (Spelling)