IBM®
Skip to main content
    Country/region select      Terms of use
 
 
   
     Home      Products      Services & solutions      Support & downloads      My account     

developerWorks  >  Lotus  >  Forums & community  >  Best Practice Makes Perfect

Best Practice Makes Perfect

A collaboration with Domino developers about how to do it and how to get it right in Domino

I've been doing a lot of programming in LotusScript recently using linked lists, and refining my technique.  This might be old news to some of you but I thought I'd mention it.  And what I'm saying here in part applies specifically to LotusScript, but in part to any language that does reference counting.

LotusScript memory management is not perfect, and I've encountered situations where it gets hung up when deallocating memory, particularly when there are object references that go across script libraries (a class in Library A contains a reference to an object whose class is declared in Library B). The more you deallocate objects yourself with a Delete statement, the better your chances of not having a problem.

Of particular interest are doubly-linked lists, where you have a "previous" and a "next" pointer in each node, and somewhere else you have a "first" pointer to identify the start of the list. As in the example shown here, you have an Ocean object containing the location of a list of Fish.

Class Fish
     
' some properties of fish omitted here
      Public Prev As Fish
      Public Next As Fish
End Class

Class Ocean
      FirstFish As Fish
       ...
End Class

Sub Initialize
      Dim pedantic As New Ocean
      pedantic.AddFish
' method not shown
      pedantic.AddFish
...

In the example data depicted on the right, the Ocean object has a list of two Fishes. The Prev pointer of the first one points to Nothing, as does the Next pointer of the second one. This is great; we can create as long a list of Fish objects as we like, insert them in between existing elements of the list without having to shift other things around like we would with an array, search backwards and forwards until we find just the right fish.

LotusScript automatically keeps a reference counter to objects so that it knows when they are no longer referenced anywhere and it can delete them. The Ocean object pedantic is referred to once (in this example) because you declared it as a stack variable in the Initialize subroutine of an agent. The first Fish is referenced twice -- once by pedantic's FirstFish pointer, and once by the Prev pointer of the second Fish.  The second Fish is referenced once, by the Next pointer of the first fish.

The trouble comes when we're all done. If we let the default memory management handle things, when the Initialize sub terminates the last reference to the Ocean object, pedantic, goes away, so that memory is deleted. Then LotusScript looks around for any other objects whose reference counters have dropped to zero, because they can also be deallocated. But there are none. The two Fish objects refer to each other, so neither one can be deleted first -- their reference counters will never drop to zero.

If it were a singly linked list, things would be different. When the Ocean object went away, the first Fish would have no more references, and so it would get deleted, then the next Fish would be an orphan, and pop, pop, pop, all the way down the chain. At least in theory; as I mentioned, LotusScript sometimes manages to screw things up somehow. I wrote an SPR about it.

But anyway, in this situation, with the doubly linked list, two Fish objects cling desperately to each other to preserve their existence as all around them whirls off into chaos. Which of course, is not what we want.

That's why one must be aggressive about deallocating the objects when their parent container is freed. So for instance, in this case we could add a destructor to the Ocean class:

Sub Delete
      Dim aFish As Fish
      Do Until FirstFish Is Nothing
              Set aFish = FirstFish
              Set FirstFish = FirstFish.Next
              Delete aFish
      Loop
End Sub

To make things easier, a separate function, or a method of the Fish class, could do this list deallocation.  In a recent OpenNTF project I published, I took this approach, writing a function that returned a Fish object to the caller (essentially) and then expecting the caller to call my subroutine to deallocate the list when they were done with it.

I should've thought harder about that; then I would've realized that expecting a programmer to remember to call a special function at the end is doomed to failure. Of course they'll forget sometimes (I forgot once, myself), or they'll be debugging it and stop early, and then there's a little school of Fish that never go away. So in my next version of that tool (not yet published) my function wouldn't return a Fish, but a new class, FishList, which like the Ocean class above, has a FirstFish pointer and a Delete method to make sure all the Fish objects die, die, die. And it can contain other useful functions, like inserting into the list, sorting, whatever. In fact, to avoid duplication of code, if another object (like Ocean) also needs a list of Fish, it should have FishList as a property instead of a pointer to the first Fish in the list. That's an extra object you wouldn't otherwise need, but it's worth it to avoid having to track every exit point to make sure you've called all the right memory-freeing functions.

So -- like I said -- might have been a refresher for some of you, but I hope you found it useful.

Andre Guirard | 28 October 2009 07:00:00 AM ET | Man-Cave, Plymouth, MN, USA | Comments (4)


 Comments

1) Bad design?
Tommy Valand | 10/28/2009 12:29:29 PM

I know your example is just that, an example, but...

Shouldn't it be the oceans "responsibility" to know of it's fishes? If I read your example correctly, the ocean is the container of a given number of fishes. The fishes are added to the ocean, so the ocean would be the logical place to go to for when looking for the next/previous fish.

I can't think of any kinds of maps/arrays/trees in any programming language I've encountered where you can navigate the items from the items themselves. It doesn't seem logical nor beneficial.

2) Linked Lists Best Practice
Andre Guirard | 10/28/2009 4:20:28 PM

@Tommy, it's an interesting point. One of the challenges in working with LotusScript custom classes is that there are only two degrees of privacy: totally public and "Private" (meaning, accessible within the class and derived classes). So if an object contains a "Next" pointer that's used by a separate "Container" class, it's also accessible to everybody else. The solution would seem to be to have three classes: one to represent the actual data (Fish), a Private class to represent the data as part of a list (FishNode, members Data As Fish, Next As FishNode, Prev As FishNode) and the container class (FishList or Ocean, member First As FishNode). This makes the Fish object more flexible and floppy, since it can also be used in contexts where it's part of a different structure (e.g. a tree showing which fish ate which other fish). In fact, in many cases it's rather nice if you can use the SAME Fish object in both contexts, since a particular fish might be part of the list of all fishes in the ocean, and also be part of a transaction of eating or being eaten.

The reason you might want two separate classes, FishList and Ocean (members including fishes As FishList) is that you might easily have use for a list of fishes in other contexts. For instance, I have these other classes, Pond and FishMarketStall, which also need to keep track of a collection of fishes. So now we're up to four classes (even not counting the two I just mentioned).

The obvious danger to making the chain pointers public members of Fish, is that someone is likely to mess with your internal data, writing their own deleteFish function or what have you and setting those values in ways which may cause you problems if you want to change something about this representation that you thought you owned absolutely; for instance, if you change a single-linked list to doubly-linked, someone's old custom function that doesn't know about the Prev pointer will mess up your chain. That's the beauty of private members and helper classes.

In the example, Ocean could have a method FirstFish() and NextFish(cur As Fish). Of course there's more complexity to implementing NextFish when the Fish object doesn't contain a Next pointer. You can be smart and assume that in most cases they'll be passing you the same Fish you last returned to them, so cache the last FishNode used. But in general, it's not possible to implement this method as effishently as you could if the Fish knew its own neighbors.

Or, you could declare derived classes of Fish, e.g. Private Class FishInAList As Fish, with added members Prev and Next. This would allow NextFish method to be speedy, but still hide the extra members from the caller by your NextFish method having the base class as its declared return type. But then you lose flexibility, because you can't use that same Fish object as part of that food chain hierarchy if it has used the same technique.

So, if you're being formally correct and wanting to produce the ideal object-oriented design, you need more classes. There's a tradeoff in terms of performance and code complexity, versus flexibility and maintainability. If you know the Fish is only being used in one context, there's not a lot to be gained by pushing the OO Formal Design lever all the way up to maximum. But there is a definite payoff to coding so as to make memory management errors less likely, which is the point of what I was writing.

3) Thanks Andre
Erik Brooks | 10/29/2009 12:55:02 PM

Wow, thanks for posting this. I've suspected this problem with LS for a long, long time.

A few years ago I completely rewrote thousands of lines of reporting code we use simply because memory leaks were out of control. It used a linked-list style approach, and was hitting memory problems left and right.

I never bothered to investigate or report it because... well, how could I? The LS engine is a black-box. How did you notice the problem? Is there some console command we can issue to see memory currently allocated to LS?

4) What about a private internal array?
Tommy Valand | 10/29/2009 2:53:20 PM

Why not write a generalized ObjectTree Class that the Pond, the Ocean, and the FishMarketStall could use?

The ObjectTree class contains an Array of keys (for positioning), and a List of ObjectNodes. The keys would be the ListTags in the List. The keys would have to be generated dynamically in the constructor of the ObjectNode, to avoid duplicate keys.

The ObjectNodes contain a key, and a Variant (the object).

All manipulations would be of the array of keys.

This adds the overhead of a wrapper object (the ObjectNodes), but since the objects themselves only are referenced by the wrapper, you avoid rampaging pointers?

I've created a simple agent (ugly code due to laziness) that lets you add/navigate the nodes (supports scalar and complex data types) without having to deal with an internal index-variable. It shouldn't be much work to rewrite it to let you manipulate the list (move, delete).

Download here: { Link }

 Add a Comment
Subject:
   
Name:
Comment:  (No HTML - Links will be converted if prefixed http://)
 
Remember Me?     Cancel

Search this blog 

Disclaimer 

    About IBM Privacy Contact