Nigamanth Sridhar
Computer and Information Science
Ohio State University
2015 Neil Ave
Columbus OH 43210 USA
nsridhar@cis.ohio-state.edu
Phone: +1 614 292 8234
URL: http://www.cis.ohio-state.edu/~nsridhar
Keywords. Lazy initialization, modularization, dynamic reconfiguration, parameterization.
Paper Category: Position paper.
Emphasis: Research.
Among a set of implementations of a given component, all other things being equal, the fastest implementation is preferred. We are therefore, constantly looking for ways to make our software components more efficient. Lazy initialization is one technique that improves the performance of components [4,5]. Component implementations that use lazy initialization typically do not allocate memory and initialize variables when they are declared by a client program. Instead, they wait for the client to actually use the variable, and on the first such use, allocate the requisite amount of memory and initialize the variable. After this, the actual operation is performed.
It is easy to see that this approach greatly reduces the startup cost of the application, because there is no time spent in initializing variables at startup. So the time taken to initialize a bunch of variables at one time has now been spread over a longer period of time while the application has been making useful progress.
However, the downside to lazy initialization is that in long-running systems, the cost of checking whether the variable has been initialized in every operation could become very high. If we can find some way by which the component could stop checking once its variables have been initialized, then we can exploit the low startup cost of lazy initialization and the low cost of an implementation that assumes initialized variables.
This paper examines the use of dynamic reconfiguration to achieve just this. In Section 2, we present a more detailed introduction to lazy initialization including some instances where the performance improvement is surprisingly great. We describe dynamic reconfiguration in some detail, and the specific domain of dynamic reconfiguration we use in this paper -- module replacement in Section 3. After presenting some ideas on how dynamic reconfiguration can be included in component implementations in Section 4, we conclude in Section 5.
Consider an operating system, which at startup, creates and initializes a number of processes and data stores. The startup time for any operating system is considerably large given the number of services that need to be started up. These services really need to be started up when the machine is booted up. For example, the FTP server on a machine cannot really be started as response to any user action, since the ftp requests come from outside the machine, and the user at the machine typically may not even know about the requests until they arrive.
So while it cannot be avoided that startup costs of certain applications will be high, the effort on our part should be on reducing such a cost to as little as possible. Lazy initialization is a technique that greatly helps in this respect. The creation of services and objects cannot be avoided, but they need not be necessarily initialized at the time they are created. The initialization of these data stores can be postponed until they are used for the first time. And if some objects never get used during the lifetime of the application, all the better - we need not waste the time it takes to initialize the object, and further to finalize and destroy the object.
But is the cost of initialization typically that large in order to realize an appreciable gain in performance using lazy initialization? Consider an Array component that creates generic Array objects of arbitrary size. Let us suppose that a client program instantiates this component to create Arrays of Array objects to create two dimensional Arrays. When the client creates an object of this type, look at how long it takes to initialize it. The top level array needs to be allocated memory, which is linear in the amount of time it takes to initialize each of the second-level arrays. This time is itself linear in the time it takes to initialize each item in the array. The cost of initializing a 100 x 100 array of this type could be considerably large depending on the initialization cost of the individual items!
As an alternative, consider an implementation of this component that is represented as follows. An Array object is just a logical reference1 to an array of logical references to object of the item type that the Array is instantiated with. The cost of creation for such a structure is still linear in the number of elements in the array. However, the cost of creating any single reference is extremely small. So regardless of what the actual item type in the array is, the cost of creation is still linear in the cost of creating a single reference.
So what happens with this array going forward? Every time an operation tries to access a particular location in the array, that location is initialized and the access is done. So instead of paying the cost of initializing the entire data store up front, the cost is amortized over multiple accesses to the data store.
If lazy initialization is such a great improvement in performance, why don't we use it all the time? What are the downsides to using lazy initialization for all applications?
The problem crops up only in systems that have a long running time. On the first access to any part of the data store, that part is initialized. However, in spite of this, every access to this data store entry in the future will also have to go through the check to see if the entry has been initialized or not. Though this is just a simple check, it could turn out to be a considerable cost that overtakes the benefit of lazy initialization. In a system that runs for a very long time - days, or even months - such a cost at every access proves very expensive. In the next section, we examine the use of dynamic reconfiguration to address this problem.
Dynamic reconfiguration [1] broadly refers to changing (adding, deleting or modifying) some part of a software system while the system is running. The change is performed without disrupting the running of the system in any way. Dynamic reconfiguration is essential for supporting the operation and evolution of long-lived and highly-available systems for which it is either not possible or not economic to terminate execution in order to carry out invasive maintenance activities. For such applications, systems must be reconfigured ``on-the-fly'' at runtime.
Several dimensions of an application's configuration can be changed at runtime. In this paper, we focus on a common mode of dynamic reconfiguration known as module replacement. Module replacement -- also called hot swapping -- involves rebinding or substituting the implementation of a module at runtime. Module replacement is a very powerful technique when software is decomposed into modules that encapsulate independent design decisions that are likely to change over the lifetime of an application [2].
In the particular case in hand, how do we reconfigure the Array component? In other words, what modules do we replace in order to achieve the desired change? At the outset, it seems like we need to change the entire implementation of the Array component. This might not be so easy, since this might mean that there has to be a way for the new component to acquire ``knowledge'' from the old component about the objects already created, and their state and representations.
Further, if the representations used by the old and new implementations of Array are not the same, the reconfiguration may require that the representations of all the objects created so far be changed to correspond to the new representation. Such a change only seems like a whole performance loss, and defeats the whole purpose of the reconfiguration.
A more clever way to do this would be to recognize that the initialization and finalization of data objects are independent design decisions. So the component could be parameterized by Initializer and Finalizer modules. In the beginning, the Array component is instantiated with a Lazy_Initializer implementation which just creates objects but uses a lazy scheme for initialization. Later on in the lifetime of the application, the component could be reconfigured to replace the Initializer module with a regular implementation that does not check if an object is initialized on every access.
The question that remains to be answered is when does this reconfiguration get triggered, and who does this. This can be done in a variety of ways. The component could itself be coded in such a way that it somehow ``senses'' that lazy initialization is proving to be a performance burden on the system and ``heal'' itself. On the other hand, the client program could make the change, by instructing the component to change itself. Or, the user could provide some kind of external stimulus to the application - such as a console command - to trigger the change.
How do we go about implementing the ideas that have been described in the preceding sections? This section presents a way in which dynamically reconfigurable components can be implemented in popular languages and component technologies such as Java and .NET.
In previous work, we introduced the service facility pattern [3] as a way of implementing parameterized software components in languages and environments that did not support generic programming through first-class language constructs. A service facility exports zero or more data types, plus the operations defined on the data types it exports. A client can create a service facility object, request data objects from the service facility, and also use the facility to perform operations on the data objects it uses. In effect, a service facility object acts just like a RESOLVE facility, except that the service facility is a runtime entity that gets created, instantiated and destroyed during the lifetime of an application.
Languages like C++ and Ada have language constructs (templates and generics, respectively) that allowed the programmer to create a single component that could be specialized at compile-time by supplying appropriate template parameters. In languages like Java, however, which do not support a generic programming mechanism, creating parameterized components is quite a challenge. The service facility pattern provides a way for creating parameterized software components in such languages.
The C++ preprocessor uses a template and its actual parameters to create a new type that can be used in the program. This step is called template instantiation. Once a template has been instantiated, variables of that type can be declared and used. The service facility pattern also involves two steps: (1) ``instantiating'' the service facility by supplying the appropriate parameters and (2) creating and using variables of the type exported by the service facility. Each parameter to the service facility are supplied by invoking a method of the form setParameterName on the service facility object. A client using service facilities first performs this step, similar to the template instantiation stage in C++.
Since template parameters are bound to the service facility at runtime, they can also be changed at runtime. In fact, the change is as simple as re-invoking the correct setParameterName method with the new parameter. In our Array example, the Array_SerF service facility would have operations setInitializer and setFinalizer to set the initialize and finalize modules respectively. So at some point in the application's lifetime, the client program could make a call on the Array_SerF object to change the initialization strategy from lazy initialization to regular initialization.
So how does this reconfiguration affect the client program? Since the change in the initialization strategy does not really affect how the rest of the component functions, no other change is necessary in the component. The representations of the existing data can remain the same. Since the service facility object acts as a wrapper to the actual Array variables, it presents a nice abstraction barrier behind which the configuration can be changed, while still presenting a view to the client that nothing has changed. The client still depends only on the published interface of the component, and as long as that remains intact, the client does not see the change.
In this paper we have presented a way for component implementers to effectively use the lazy initialization approach to improving the performance of software components, while at the same time, keeping the potential performance penalties of the approach to a minimum. By dynamically changing a part of a component's implementation, we are able to leverage the fast startup guaranteed by lazy initialization, and the long term benefits of not having to (unnecessarily) checking on whether a particular data object has been initialized or not.
The idea of dynamic reconfiguration can be extended to other similar areas. For instance, in components that have state that only changes monotonically, it may be possible to dynamically change the checking of preconditions of operations depending on how the system is behaving over its lifetime.