Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Parallel

Persistence in a Programming Environment


DEC92: PERSISTENCE IN A PROGRAMMING ENVIRONMENT

PERSISTENCE IN A PROGRAMMING ENVIRONMENT

An object-oriented database can make the difference

Richard P. Gabriel

Dick is a Fellow at Lucid where he can be contacted at [email protected].


Suppose you had a dog and were trying to teach it to roll over and play dead. And further suppose the dog forgot everything you taught it whenever you left it alone. As long as you were in front of the dog, it learned and remembered everything you taught it--even if this lasted for months and months--but the moment you left, he forgot it all. You'd think there was something wrong with the dog because it couldn't remember things, and maybe you'd try to return him for a refund or give him to some friends out in the country. If a person suffered from this, we'd take him to a doctor or put him in a hospital.

But a lot of programs are like this: When you're running them, they build up information about the task you're doing; when you kill the program and log out, that information is gone. Fortunately, most programs can be this stupid. However, in real-world applications (payroll systems, for instance), this behavior is unacceptable because the data stored represents people or objects that exist over time, and representations of them must persist as well.

In object-oriented programming, we come across this problem more often than in other traditions because objects created and maintained in object-oriented programs are more like people than like data structures--objects have state (instance variables, slots) and behavior (methods, member functions), and a typical program creates objects and manipulates them.

The solution is to put persistent data (data that exists longer than one incarnation of the program that manipulates it) in an object-oriented database that contains objects that a program creates; whenever the program is started up, those objects are available. Unlike in a relational database, however, a program does not need to perform queries to access those objects; instead, the process of ordinary object access--through pointers, array access, global variables, and the like--serves to access these persistent objects. In this sense, persistence is a characteristic of an object rather than a process for accessing objects.

When my group first started working on a programming environment for C and C++, there was no commercially available way to add persistence to objects. This article tells what we were trying to do, why we needed persistence, our first attempt at adding persistence, and finally, our solution. We'll show the situations in which persistence makes sense, how to implement a simple roll-your-own persistence, and the advantages of a commercial solution.

The Context: A Programming Environment

We initially set out to build a C and C++ programming environment based on an architecture of a central object repository connected to a variety of programming tools. We call the repository the environment server (server, for short), and the objects are kept persistently in an object-oriented database. The server contains objects that represent things in the programming domain: source code, object files, cross references, (hypertext-like) links to documentation, user-written notes, and semantic analyses of the source. A special kind of object called an annotation links semantically related parts of the source and serves as hypertext. Unlike other environments that represent parts of programs as objects, our environment operates on source code generated by an ordinary text editor rather than a structure editor.

In the environment, a piece of source text is represented by an object that describes the semantic relations of that source to other parts of the source. In other words, the environment tries to mimic the actions of a programmer taking a hardcopy listing of the program, circling parts of the source in red pen, and drawing labeled lines to other circled parts of the source or to documentation.

For example, a C++ function might be annotated as using the external interface of certain classes and calling certain functions. It's as though a function were circled in red, with a line connecting it to the definition of, say, a public member function.

In addition, that C++ function might be annotated with the portion of the specification to which it corresponds and an informal note about the state of debugging. Each of these things is an object, even the links representing relations.

Among the tools connected to the server is a compiler that sends messages to the server about the semantic contents of the source code. The compiler partitions the original source into meaningful sections and labels them. An object in the server is created for each section of partitioned source text, and for each labeled line. Objects that represent labels are called language elements; those that represent portions of the source code are called source elements.

The annotations referred to are also objects with attached methods. These annotations will figure into the user interface, but they must be persistent.

The user-interface part of the environment comprises a group of presentation tools that display information in textual, graphical, or mixed representations (text editors, graphers, and browsers, for example). In our environment, each presentation tool can: receive objects from the server for display; display objects; display the appropriate associated annotations; and engage the user in a dialog mediated by the server. This dialog shows the user the operations possible on an object and its annotations, notes the user's selection, and sends the result back to the server for action.

For example, a text editor is sent the text representing a C function along with annotations that represent its associated information. The text editor must display the source along with the "red circles and labeled lines." In our case, the text editor just makes the annotated text mouse sensitive and puts a special icon next to it. A region of text is mouse sensitive if moving the mouse over it highlights the region and a mouse-click brings up a menu.

When the user clicks the mouse on annotated text, the text editor opens a dialog with the user about the object represented by the text. From the user's perspective, the editor pops up a menu for the object and the annotations. The menu offers such choices as compiling the function (if that's what the section represents) or following the annotation to its destination. Suppose the user chose to look at the call graph starting at the function in the section. The environment would bring up a grapher with the selected function at the root along with the called functions.

Behind the scenes, the environment does the following: When the user indicates that dialog is required, the editor sends a message to the server which computes the list of operations available and sends it back to the editor. The editor then offers the choices, the user selects one, and the editor sends the choice to the server, which invokes the operation. In this case, the operation selected is invoking the call grapher. It is executed by the environment server, which sends nodes and arcs to the grapher tool, along with the annotations to display.

When the grapher displays a node that represents a function, it is displaying the same object as the text editor. In both tools, all the annotations are displayed and the same operations can be performed on the displayed object, because each tool simply communicates user-initiated requests to the server, which computes the response independently of the tool. The only difference is in the presentation.

If the user alters the information displayed for the object by using a tool (for example, by editing the text with the text editor), those changes must percolate back to the object, causing a side effect. Thus, the text editor seems to operate knowledgeably on source code, although in fact it can only display active regions and engage in what is to it a meaningless dialog. Therefore, the program is strongly modularized, with only narrow communication between the parts.

The Problem

The problem we faced is this: The compiler produces a large number of language elements, each representing some part of the user's program. Furthermore, annotations, which are objects, are created to represent the network of relationships between the language elements and between the language and source elements. This information is used to drive incremental compilation (the relationships stored about dependencies are used to determine what needs to be recompiled when a change to the source is made) and the browsers. Users want to access this information without going through a lengthy importation or startup process, and the environment's knowledge of a program is viewed through objects whose identities are shared by various presentation tools. Therefore, it would make the most sense for the user to simply never exit the environment and never log out.

Of course, people must log out and exit their programs, so each of these objects--language elements, source elements, and annotations--must be made persistent. This requires each object to reside in a file external to the program. Because the number of objects could be large (we estimated that the size of the file containing the persistent objects would be about as large as the a.out file for the entire program), we did not think it reasonable to read in the entire file at program startup. For instance, we wanted the environment to be able to work on itself, which implied that the running server would be a dozen or so megabytes. Since most of these objects would rarely be touched, it made more sense to think in terms of paging the objects in and out, much like a virtual-memory system.

We wanted to impose a further requirement: that the existence of persistent objects be invisible to a certain level of client code. Here's what I mean: Suppose I am writing a program to search through a network of objects that have pointers to other objects. Then I do not want anything in my code to be contingent on persistent objects. In fact, I want no evidence at all that objects are persistent. In particular, I don't want to call special functions to follow pointers or access parts of the object.

When we decided to work on this problem no commercial object-oriented database existed, so we rolled our own persistent-object system using a commercial ISAM (indexed sequential access mechanism).

The Solution

First, the class hierarchy for persistent objects must be determined, and within the environment, objects that "know" their class must be created. That is, class_of(obj) should return at run time something that represents the class of which obj is an instance. To achieve this, we defined a class called classed_object that represents all such objects. The class we're interested in--pos_object--is a subclass of classed_object. The class res_pos_object is a subclass of pos_object that represents objects allocated out of a resource pool of such objects. (This allocation technique can also be good for solving certain performance problems.) Figure 1 illustrates this hierarchy.

Figure 1: The persistence hierarchy.

  classed_object-->pos_object-->res_pos_object

In some situations, you have a type of object or data structure you both create and destroy frequently. General-purpose memory-allocation routines--malloc and free, garbage collection, and the like--are often tuned for infrequent allocations. For high-frequency allocation and deallocation, it is usually better to keep a resource--a free list--of storage that can be used for allocating objects of a particular kind. When allocating, the client program takes a free piece of storage off of the free list; when deallocating, it returns that storage to the free list. Suppose you were going to frequently allocate and deallocate vectors of length 3. If you had a list of length-3 vectors, allocating one would just take one or two instructions rather than a system call; returning the vector would involve a similar number of instructions to append it onto the free list.

Writing methods for new and delete implements the special behavior. Of course, the free list is initially empty, so if new needs to make a new item and none are available to reuse, it just mallocs up the storage as usual. In this sense, the resource is self-adjusting. The sample C++ code in Example 1 implements this behavior. Example 1(a) shows that the resources are linked together by a linked list threaded through the resources themselves. This structure is used to cast the resource to a form where we can uniformly refer to the link cell as "next." The function in Example 1(b) is used to allocate segment_size new resources when the free list runs out. The resources are allocated in a big block (result = new char[...), then threaded into a list from back to front (for(i = 0, p = res ...). Notice the use of casting in this function.free_list is a data member of res_pos_class; each class object contains the free list for new instances of itself. The function in Example 1(c) takes an object and returns it to the free list. This function uses casts, too, and is inlined because it is called from exactly one place and eliminates cast to void*. Example 1(d) is the overload of new. It first checks whether there are any free resources; if not, it creates some; if so, it just takes the first of them. The class of the instance is passed in as an argument, so a call to this new would look like Example 1(e). Example 1(f) is the overload for delete; it just puts the object back in the resource.

Example 1: Resource allocation.

  (a)

  struct resource_cast {
  resource_cast* next;
  };

  (b)

  void
  res_pos_class::allocate_resource (int object_size){
    /* free_list is NULL on entry */
    /* On exit, a new segment of object is allocated and free_list is
     * updated
     */
    char* result = NULL;
    result = new char [segment-size * object-size];
    char* res = result;
    int i;
    char *p;
    for (i=0, p=res; i<segment_size; i++, p+=object_size)  {
      ((resource_cast*)p)->next = (resource_cast*)free_list;
      free_list= (res_pos_object*)p;
    }
  }

  (c)

  inline void
  put_back_in_resource (res_pos_object* obj){
    res_pos_class* cl = (res_pos_class *)class_of(obj);
    ((resource_cast*)obj)->next = (resource_cast*)cl->free_list;

    cl->free-List = obj;
  }

  (d)

  void*
  res_pos_object::operator new (new_type s, res_pos_class& cl){
    res_pos_object* newinst;

    if (!cl.free_list)
      cl.allocate_resource(s);

    newinst = cl.free_list;
    cl.free_list = ((resource_cast*)newinst)->next;
    return newinst;
  }

  (e)

  my_instance = new (cl) a_class;

  (f)

  void
  res_pos_object::operator delete (void* obj){
      put_back_in_resource (obj);
  }

Because C++ lets us write methods for new and delete, the behavior of the resource is transparent--you never have to write code with the knowledge that resources are used: The methods handle that. In fact a person writing code for the server only needs to create a subclass of res_pos_object.

The First Implementation (ISAM)

The first implementation of providing persistence was based on an ISAM, not an object-oriented database.

The persistent-object system (POS) is a layered program, each layer having different responsibilities. The layers, from highest to lowest level, are as follows:

  • Application-programming layer.
  • Persistent-object class definition layer.
  • Database-interface layer.
  • Database-implementation layer.
At the application-programming layer, programmers must merely use object types and corresponding pointer types defined at lower levels. They need never be concerned about whether or not objects are in memory, or about explicitly accessing the database.

At the persistent-object class definition layer, new object classes are defined to the POS, and methods are defined for loading and storing objects in their corresponding database file or files. The database-interface layer provides the next-higher level with a portable functional interface to the underlying database system. Finally, the database-implementation layer is the underlying database system.

By defining new classes of objects that inherit from persistent classes defined in the POS, the programmer can create smart objects and associated classes of smart pointers, which have properties of persistence, resource-allocation, reference-counting garbage collection, and a least-recently used (LRU) object-swapping capability. The fundamental implementation technique is to distribute the work between the smart-pointer classes and the persistent-object classes to which such pointers point.

The C++ operators -> and * are defined on smart pointers to transparently reference objects that might only be in the external database prior to the reference. The operator = and constructors on the pointer classes are used to manage reference-count and LRU bookkeeping information. The operators new and delete are specialized on the persistent-object classes to implement resource allocation of objects.

To implement persistent objects, there must be a uniform way of referring to objects in the database. This is done by introducing a new data type for objects: IDs. An ID can be translated into a pointer after the referent object is brought into memory. Currently an ID is a 32-bit integer subdivided into some bits of class information, from which the identity of the database file can be determined, and some bits of object ID within that file. Objects stored in the database can refer to each other by means of such object IDs. Other ad hoc cross-referencing mechanisms can also be used in an application-specific manner, but the object ID provides a unique handle on each object in the database, as well as a convenient key that other objects and clients can use to refer to that object.

All pointers to persistent objects, whether in memory or in the database, are actually pointers to surrogates--objects used to reference other objects.

When an object is first accessed, it is read in from the database. The object's surrogate is modified to point to the actual object, and the surrogate is flagged to indicate that its object is in memory. A hash table maps from object IDs to the address of the surrogate; references can be resolved by using this hash table. When an object is brought in from the database, its references to other persistent objects are replaced by references to their surrogates--if the object has already been referenced, the surrogate exists; if not, the surrogate is created.

The operators -> and * are coded as inline member functions on the smart pointer classes to use surrogate objects and to call methods for swapping in the nonresident objects. Example 2 shows sample C++ code that implements this behavior, but the code is suggestive only. The class surrogate_res_pos_ptr contains one data member, which is the union of an ID and a pointer. When p is a pointer, it points to an object that is half-word aligned; when it is an ID, it's an odd number. Thus, by using in_memory_p to check the low-order bit, you can tell at run time which sort of object in the union it is. Furthermore, since reading in an object from the ISAM is method driven, an elaborate table lookup (buried in fault_in_object and not included here) is used to determine the class of the object not yet in memory.

Example 2: Smart objects and pointers.

  res_pos_object*
  ensure_in_memory (small_surrogate* ss) {
    if (ss) {
      if (! in_memory_p(ss->pos_object_id))
        ss->fault_in_object();
      return ss-> pos_object_id.pos_object_ptr;
    } else
      return NULL;
  }
  res_pos_object*
  surrogate_res_pos_ptr::_operator_arrow () CONST_MEMBER{
    if (!p) return NULL;
    return ensure_in_memory(p);
  }
  surrogate_res_pos_ptr::surrogate_res_pos_ptr () {
    p = NULL;
  }
  surrogate_res_pos_ptr:: surrogate_res_ptr (res_pos_object* obj){
    p = get_surrogate (obj);
  }
  surrogate_res_pos_ptr::surrogate_res_pos_ptr
    (surrogate_res_pos_ptr CONST_REF ptrref){
     p = ptrref.p;
  }
  surrogate_res_pos_ptr::operator res_pos_object* () CONST_MEMBER{
    if (!p) return NULL;
    return ensure_in_memory (p);
  }
  res_pos_object&
  surrogate_res_pos_ptr::operator* () CONST_MEMBER{
    return ensure_in_memory(p);
  }
  res_pos_object*
  surrogate_res_pos_ptr::operator-> () CONST_MEMBER{
    return ensure_in_memory (p);
  }

Surrogates require an extra indirection compared to ordinary object references. However, this overhead is acceptable because access methods can be coded inline for the fast case (the object is already in memory), and because the persistent-object class writer can determine the granularity of objects to be stored in the database. In particular, a persistent object may turn into a complex data structure in memory with only one persistent handle. In this case the programmer must take care with nonsmart pointers to the internal components of the structure.

Describing the manner in which data structures are flattened for database storage and retrieval is difficult, so we adopted a method-driven approach. Thus, when a new persistent-object class is defined, methods for storing and retrieving it must be defined as well. Though more complex to use, this approach lets the application designer tune the representation of objects in the database, possibly distributing them over multiple files or relations or condensing a large, in-memory data structure into one or a few database records. The designer can also put more keys into the database representation of objects, allowing associative access.

This layered approach initially proved effective, and the first POS system was implemented on top of a simple sequential-access database (NetISAM and C-ISAM). However, we soon discovered three essential problems:

  • Performance was not good enough when searching and compiling. Basically, the smart-object scheme sets granularity too small; whenever the code tried to access a particular part of the network of objects for searching, for example, each object had to be individually read in. Although reading was method driven and methods could be written to read in multiple objects, we never hit upon a general method that would read in the "right" number of nearby objects--enough when searching, not too many when accessing--with the performance we needed.
  • We needed to checkpoint the objects occasionally to find the "dirty" objects (those altered since the last checkpoint) and this proved too costly at the granularity at which we were working.
  • The server's working set size--the memory size required to handle all the frequently handled objects--was too large when we tuned it for performance.
So we turned to an object-oriented database.

The Second Implementation: ObjectStore

We chose the ObjectStore database from Object Design, primarily because it uses a page-based scheme rather than a smart-object scheme. In the page-based scheme, new persistent objects are allocated on particular pages of memory, and dirty pages are written out at check-points. When the program using persistent objects is started up, these pages are associated with the process but not read in. When the program accesses an object not in memory, the object is paged in from the database. This causes all the other objects on that page to come in simultaneously, so the granularity is better.

To effect the page-in, the operating system must support some level of user-controllable paging. In SunOS, the page-fault mechanism has a hook in which the user process (the client program with ODI's libraries loaded) is notified of a paging request. The hook controls reading the data, which comes from the database. The process of paging in is not trivial, since it involves relocating the objects and knowing the class of each persistent object at run time, just as with our simple initial scheme.

As far as client code is concerned, the use of persistent objects is once again transparent to the programmer. The C++ code in Example 3 implements new and delete for ObjectStore's persistent objects. Figure 2 shows the full class hierarchy for persistent objects.

Example 3: new and delete for ObjectStore. These are the two definitions. All other operators on persistent objects are as usual. delete just invokes the version in the ObjectStore library.

  void*
  pos-object::operator new (size_t 1, basis_pos_class* cl){
    /* get the Objeststore type identifier for the type being allocated */
    /* We cache it in the class object for efficiency */
    os_typespes* tx = ((pos_object*) (cl ->prototype)) ->get_typespec();
    /* allocate one instance in cadillac_database */
    return ::operator new (1, cadillac_database, 1 tx);
  }

  void
  pos-object::operator delete (void* ob){
    /* just call the normal operator delete provided by Objectstore */
    ::operator delete (ob);
  }

Commercial databases accrue additional benefits:

  • Database locking: Databases are kept safe from several users writing to them simultaneously.
  • Queries: We don't use this facility yet.
  • Distributed servers: Performance is improved by putting all the code for relocation and other activities for several database clients on one dedicated computer.
  • Database integrity: The database makes sure checkpoints are done correctly.

Conclusion

Consider carefully whether your application needs persistence, and, if so, whether it requires the machinery presented here. Remember that our goals included very fast performance for databases with hundreds of thousands of objects, along with transparent programming for the developers--so it was worth it for us to develop the right machinery. But sometimes you can get away with just reading and writing data to a file, so don't let the cachet of sexy new techniques or concepts sway you to use them unnecessarily.



_PERSISTENCE IN A PROGRAMMING ENVIRONMENT_
by Richard P. Gabriel


Example 1

(a)

struct resource_cast {
resource_cast* next;
};



(b)

void
res_pos_class::allocate_resource (int object_size){
  /* free_list is NULL on entry */
  /* On exit, a new segment of object is allocated and free_list is
   * updated
   */
  char* result = NULL;
  result = new char[segment_size * object_size];
  char* res = result;
  int i;
  char *p;
  for(i=0, p=res; i<segment_size; i++, p+=object_size) {
    ((resource_cast*)p)->next = (resource_cast*)free_list;
    free_list= (res_pos_object*)p;
  }
}

(c)


inline void
put_back_in_resource (res_pos_object* obj){
  res_pos_class* cl = (res_pos_class *)class_of(obj);
  ((resource_cast*)obj)->next = (resource_cast*)cl->free_list;

  cl->free_list = obj;
}


(d)

void*
res_pos_object::operator new (new_type s, res_pos_class& cl){
  res_pos_object* newinst;

  if (!cl.free_list)
    cl.allocate_resource(s);

  newinst = cl.free_list;
  cl.free_list = ((resource_cast*)newinst)->next;
  return newinst;
}



(e)

my_instance = new (cl) a_class;

void
res_pos_object::operator delete (void* obj){
    put_back_in_resource (obj);
}




Example 2:

res_pos_object*
ensure_in_memory(small_surrogate* ss) {
  if (ss) {
    if (!in_memory_p(ss->pos_object_id))
      ss->fault_in_object();
    return ss->pos_object_id.pos_object_ptr;
  } else
    return NULL;
}
res_pos_object*
surrogate_res_pos_ptr::_operator_arrow () CONST_MEMBER{
  if (!p) return NULL;
  return ensure_in_memory(p);
}
surrogate_res_pos_ptr::surrogate_res_pos_ptr (){
  p = NULL;
}
surrogate_res_pos_ptr::surrogate_res_pos_ptr (res_pos_object* obj){
  p = get_surrogate(obj);
}
surrogate_res_pos_ptr::surrogate_res_pos_ptr
 (surrogate_res_pos_ptr CONST_REF ptrref){
  p = ptrref.p;
}
surrogate_res_pos_ptr::operator res_pos_object* () CONST_MEMBER{
  if (!p) return NULL;
  return ensure_in_memory(p);
}
res_pos_object&
surrogate_res_pos_ptr::operator* () CONST_MEMBER{
  return ensure_in_memory(p);
}
res_pos_object*
surrogate_res_pos_ptr::operator-> () CONST_MEMBER{
  return ensure_in_memory(p);

}


Example 3:

void*
pos_object::operator new (size_t l, basic_pos_class* cl){
  /* get the Objectstore type identifier for the type being allocated */
  /* We cache it in the class object for efficiency */
  os_typespec* ts = ((pos_object*)(cl->prototype))->get_typespec();
  /* allocate one instance in cadillac_database */
  return ::operator new (l, cadillac_database, 1, ts);
}

void
pos_object::operator delete (void* ob){
  /* just call the normal operator delete provided by Objectstore */
  ::operator delete (ob);
}


Copyright © 1992, Dr. Dobb's Journal


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.