Evaluation of a High-performance Object Reuse

Dynamic Memory Allocation Policy for C++ Programs

Woo Hyong Lee, J. Morris Chang and Yusuf Hasan

Dept. of Computer Science
Illinois Institute of Technology
Chicago IL USA 60616
E-mail: { leewoo, chang, hasan}@[Link]

Abstract deallocated through operator new and operator delete, re-

spectively. These operators are overloadable. Through the
Recently, the importance of dynamic memory man- overloading feature in C++, customized storage manage-
agement has been increased significantly as there is a ment policies can be applied. This off-line strategy pro-
growing number of development in object-oriented pro- vides an opportunity to improve the efficiency of memory
grams. Many studies show that dynamic memory manage- management in C++ programs.
ment is one of the most expensive components in many In this research, we have used mtrace++, which is a
software systems. Especially, in C++ programs, it tends to specialized memory tracing tool for C++ programs [4],to
have object creation and deletion prolifically. These ob- investigate the allocation behavior. As a result, many of
jects tend to have short life-spans. This paper presents a the objects exist for a very short period of time before they
dynamic memory allocation strategy to reuse these objects are deallocated. It has also been reported in other research
to speed up the object management. This object reuse [ 1, 31 that object life-spans tend to be very short in object-
scheme is implemented through the overloading C++ op- oriented systems. Moreover, many of these short life-span
erators, new and delete. objects are created and deleted repeatedly. This indicates
that the deleted object can be reused frequently in the near
The C++ allocation patterns are studied thoroughly
future for the request with the same object size. The object
in this paper. Over 90% of objects are not bigger than size
reusability is studied thoroughly in this paper.
51 2 bytes and allocated prolifically. The proposed scheme
is made feasible by reuse of these small objects. Our allo- We propose to exploit the object reusability in C++ to
cation scheme is simple and fast because it requires no speed up the dynamic memory management (DMM) The
splitting and no coalescing, and reduces number ofmal- object deletion process through the overloaded delete op-
loco calls. It maintains its own free-list which is used for erator will be deferred. The object to be deleted will be put
object reuse. The experimented results, based on the pro- back to a free-list which is maintained by the overloaded
posed allocation scheme, show that allocation speed is in- new operator. The free-list is simplified by eliminating co-
creased up to four times compared to other well-known alescing and splitting. When a new allocation request oc-
algorithms. Our scheme is purely source-code oriented curs, it tries to find out reusable object in the free-list. If it
and built on the top of malloc. Therefore, this approach is is not available, it will create a new object which uses the
portable to apply with existing code and safe to use with pre-occupied space. This allocation scheme can reduce the
different mallocs. total number of malloc() calls. Thus, it improves the per-
formance of allocation speed.

1. Introduction It is worth noting that the proposed strategy employs

global overloading. This global overloading will be over-
Dynamic storage allocation is an important part of written by any local overloading to the new operator. If the
many C++ programs, including language interpreters, sim- programmer had overloaded the new operator, the pro-
ulators, CAD tools, and interactive programs [1, 21. C++ posed scheme would not be effective. Thus, our scheme
has its unique style of memory allocation. It allocates will not affect the functionality of any program.
many small size objects prolifically rather than some large The remainder of this paper is organized as follows.
size objects [3]. In C++, dynamic memory is allocated and

386
0-7695-0589-2/00 $10.000 2000 IEEE

Authorized licensed use limited to: University of Pretoria. Downloaded on April 16,2026 at 16:27:03 UTC from IEEE Xplore. Restrictions apply.
Section 2 reviews memory allocation behavior in C++ most of the heap space. We have investigated where the
programs. Section 3 details the design of the allocation memory requests are originated from. Most of the requests
scheme. Section 4 shows the simulation results. The last fall into our five invocation scenarios. Especially, con-
section presents the conclusions of this paper. structors and copy constructors are major contributors to
allocate dynamic memories. Based on the benefits of over-
loading allocation interface in C++, we can develop inno-
2. Allocation Behavior vative algorithms for efficient dynamic memory
Memory operation in C++ is one of the most time management.
consuming processes. There are significant differences in
allocation behaviors between C and C++. C++ programs 3. Design of a Simple and Fast Dynamic
allocate a significant number of dynamic objects and fur- Memory Manager
thermore allocate same size objects repeatedly [ 5 , 6 ] .A re-
cent study shows that C++ programs can perform memory Running a C++ program is much less deterministic
operation almost ten times more than comparable C pro- and its performance is significantly affected by its memory
grams [3]. On the other hand, Many C programs allocate management. In C, the dynamic memory management is
very few objects. Some of C programs allocate little or no processed through malloc library function. Compared to
dynamic memory [7]. This section provides C++ dynamic C, C++ provides mechanism to overload operator new and
memory allocation analysis based on the scenarios of ob- operator delete which enable programmers to apply cus-
ject allocation. tomized allocation policies easily. This approach is purely
Typically, the dynamic memory allocation in C++ is source-code oriented and the modification of the original
invoked through the new operator [SI. The new operator is source code is not needed. The overloaded new and delete
implemented through malloc() function. C++ has five dis- process allocation/deallocation requests ahead of malloc.
tinctive allocation cases. They are constructor, copy con- Any kind of mallocs can be applied as a base memory al-
structor, overloading assignment operator=, and type location module.
conversion [6]. The first four scenarios are unique to ob- Our traced results show that C++ programs have high
ject-oriented programming in C++. The fifth case is user- rate of object reuse. Over 90% of the objects are reused in
defined member function which invokes new operator ex- all of our experimented C++ programs. Also, those objects
plicitly. In this case, it depends on the need of application. are very small in size. Most of the object sizes are not big-
The constructor may invoke the new operators explic- ger than 512 bytes. With the knowledge of the memory al-
itly or implicitly. The copy constructor, in contrast to the location pattern, we could develop a high-performance
constructor, can only invoke the new operators implicitly. memory management strategy, it is called 0-Reuse, which
The default copy constructor may only perform member- is a specialized dynamic memory allocator for reusable
wise copy while the user-defined copy constructor can objects. Using 0-Reuse, we can minimize memory alloca-
perform a deep copy. To overload the assignment opera- tion process time without excessive overhead in memory
tor= which implements a deep-copy like assignment be- usage.
tween class objects, dynamic memory allocation may be
invoked. Finally, type conversion is used in C++ to con- 3.1. Encapsulated Storage Structure.
vert a user-defined type to a built-in type. Such a conver- Accessing dynamic memory in a controlled and disci-
sion may also invoke the new operator. All these cases are plined way is one of the key factors of memory manage-
unique to C++ languages. ment. To access dynamic memory, we need some kind of
In contrast to the first four cases, the user-defined data structure to maintain information. 0-Reuse strategy
member functions of our fifth case are related to the nature encapsulates the data structure of the requested object to
of the application. Moreover, the dynamic memory invo- create and manipulate the object. By encapsulating alloca-
cations are quite straightforward. Most likely, the new op- tion data structure, we can store some manipulating infor-
erators are invoked directly in the program. mation. Using the information, we know the size of the
object and can decide whether this object can be reused.
We experimented five C++ applications that invoke
The following code segment shows the encapsulated data
dynamic memory intensively. While there is a huge num-
structure of 0-Reuse.
ber of allocation requests, over 95% of the memory re-
quests are under the size of 4KB. Their life-spans are
relatively short. Many of the small size objects occupy

387

Authorized licensed use limited to: University of Pretoria. Downloaded on April 16,2026 at 16:27:03 UTC from IEEE Xplore. Restrictions apply.
 In modem systems, heap is occupied in a range of virtual
I struct reuse-object
1
I addresses and grows "upward" through the address space
[9]. To request more memories, system call brk is used.
size-t ''return-pointer;
unsigned alloc-size; Brk is often called indirectly, via the library routine sbrk.
struct reuse-object 'next-free;
In 0-Reuse, memory chunks are obtained by mallocO in-
Iypedef struct reuse-object L;
typedef L *Lptr; stead of direct sbrk call. we setup the base block size of
each malloc() call as 8KB which is the base sbrk call block
new-structure = (Lptr)malloc(sireof(L)+requested-size); \\l
new-structure->return-pointer = \ size in Doug Lea's version 2.5 malloc.
(size-t ')((unsigned)(new-structure) +,sizeof(L)); \U
new-strurcture->alloc-sire = requested-sire; \\3 It is quite simple to get a new object space with O-Re-
I I use scheme. In 0-Reuse, we do not allocate objects via
mallocO call. The requested allocation will be located to
Statement 1 prepares an allocation space which in- the next of the previous allocation. Therefore, we know
cludes the data structure size of reuse-object and the re- the returning address before we allocate a memory. The
quested object size. This 0-Reuse data structure consumes
returning address of the allocation request would be (end-
extra memory space to store the manipulating information. ing address of previously allocated object (current ad-
However, the overall memory usage is not higher com- dress) + (structure block size) + I). The ending address
pared to conservative algorithms, e.g., Doug Lea's version can be easily counted because we know the size of the en-
2.6.5 malloc. The returning pointer of the requested size is capsulated 0-Reuse data structure, the requested object
calculated in statement 2. In statement 3, object size is size and the current address. Most allocators use a hidden
stored into 0-Reuse data structure. header field within each block to store some useful infor-
mation. Most commonly, the size of the block is recorded
3.2. Algorithm
in the header. The encapsulated data structure creates
0-Reuse strategy basically uses two policies: simple memory overhead. However, it can be ignored because the
allocation and object reuse. The simple allocation scheme header field of an object is replaced by the encapsulated
allows to allocate objects consecutively without memory data structure of 0-Reuse instead of the data structure of
fragmentation between objects. malloc.
Once an object is allocated and freed, it is placed into To reuse objects, we adapted the technique of segre-
0-ReuseS own free-list instead of malloc S free-list. gated storage [IO]. Indexed free-list holds free blocks of a
When there is a new allocation request, first, the allocator particular size. In the 0-Reuse's encapsulated block, it has
tries to find a reusable object in the free-list that exactly a link-list node that is the reusable free-list node. When a
matches the requested size. I f there is no matching object, block of memory is freed, it is simply linked together with
it will create a new object. All the dynamic objects are lo- the same size objects. When an allocation request arise,
cated inside 0-ReuseS allocated chunk. Each object has a the allocator tries to find out reusable object in the free-list
free-list node by its size after it is freed. Figure 2 illustrates to satisfy the request. This is a simple segregated strategy.
the diagram of the simple allocation. There is no splitting or coalescing of free blocks to satisfy
requests of variant sizes. Searching reusable free-list is
Figure 1. Simple object allocation very simple and very fast. It simply finds the given size
object in the first node of the free-list instead of searching
free-list for a block to find out the space which is large
enough to hold. Our traces show the allocation behavior of ,

the high frequency of allocations and deallocations of

I st 2d
same size objects.
3rd next
allnsatl"" allocation PllDCstiU" alln'ation
The behavior of memory allocation in C++ deter-
mines the effectiveness of the proposed scheme. For ex-
Our simple allocation scheme is an extremely fast al- ample, what will happen if there is a huge number of
location. It reduces the number of mallocO calls. When the invocations with different sizes and only few of them are
first allocation is requested, 0-Reuse allocates a chunk of reused? This represents the worst case in the memory re-
memory block to make consecutive allocation. The base use. At a certain point, heap space will be exhausted be-
chunk size of 0-Reuse is the same size as malloc's base cause heap size grows and finally occupies entire memory.
sbrk block size, e.g., 8KB. The total number of malloco However, after we studied C++ memory allocation behav-
calls in 0-Reuse is same as the total number of sbrk calls. ior, such a behavior was not encountered. Even if this case

388

Authorized licensed use limited to: University of Pretoria. Downloaded on April 16,2026 at 16:27:03 UTC from IEEE Xplore. Restrictions apply.
exist, it can be overcome easily by applying a maximum programs [4]. To measure the frequency of memory reus-
size threshold. If an object’s size is bigger than a pre-de- ability, we applied gprof version-2.9.1 which is a call
fined threshold, it’s allocation management will be passed graph execution profiler [ 111. It provides execution time
over to malloc instead of using 0-Reuse. By applying the distribution of all routines within an execution of a pro-
threshold, we can conserve memory for the objects which gram. Our experiments are tested on Linux platform with
are large size and rarely reused. In the worst case, 0-Reuse Pentium-111 5OOMhz CPU and 512MB RAM.
will not provide any benefit nor cause any performance
degradation. 4.1. Process Time Improvement
There is another potential memory overhead problem. To compare the performance of several DMM
If there are some very large objects that are short lived, schemes, we choose two high-performance mallocs writ-
they can create large unused memory gap that can cause ten by Doug Lea: version 2.5 and version 2.6.5 [ 121. Ver-
high memory overhead. For this problem, we can easily sion 2.5 malloc is one of the fastest mallocs which are
solve by relying on the behavior of C++ memory alloca- currently available. It uses segregated scheme with de-
tion. Our experimented results indicate that most reusable ferred coalescing algorithm. A common retumed-list is
objects are created from our five categorized cases and used to provide fast deallocation. Version 2.6.5 malloc is
over 90% of the allocation requests are not bigger than 5 12 not as fast as version 2.5 malloc. However, it is still among
bytes. The solution for the problem could be the same as the fastest while having less memory overhead than ver-
the previous one. Setting the threshold filters only for sion 2.5 malfoc. It provides much better portability and
small size objects. In this case, DMM can still take the ad- tunability compared to version 2.5 malloc. We applied 0-
vantage of 0-Reuse. The overall allocation performance is Reuse to both mallocs and found no difference in perfor-
not affected by the threshold because large objects are mance. In our scheme, malloco is only called to provide
rarely allocated and deallocated. allocation chunk. Once this space is allocated, our scheme
simply creates objects within this memory chunk. Gener-
ally, malloco is performed only few times during the en-
4. Results tire execution. Thus, the performance differences (version
We have chosen five C++ programs for the experi- 2.5 versus version 2.6.5) are minimal. In our experiment,
ment. Those are memory intensive programs and available we use version 2.6.5 malloc as the base malloc system be-
publicly. Those programs include 3D Graphic Engine cause it has better memory efficiency.
(Crystal Space), Object-oriented Robotics Tool Box (Ro- In Crystal Space, dynamic memory is heavily in-
boop), Ftp client (Lftp), Pdf file viewer (Xpdf) and Object- voked. In ten minutes of execution time, several million
oriented Benchmarks (Bench++). Crystal Space, Lftp and times of the new operator are invoked. The average reus-
Xpdf are screen interaction programs, Roboop uses pre- able rate is about 96%. 0-Reuse strategy is the fastest one.
defined user input, and Bench++ basically measures pro- In Figure 2, the average improvement is about 300% com-
cess time for each event. pared to Lea’s version 2.5 malloc and 150% compared to
Lea’s version 2.6.5 malloc.
Table 1. Experimented Programs
Figure 2. Crystal Space DMM process time
I

I I I
I I I
program line of
ftp site
name code 300
m”.7
250 SL.. 1 ,

__
.L.12 e 2
Ii
i
1I O

1 100

Roboop 10

5 0
“PYfl “Pull I”.“,,

- __

In Figure 3, the result using Xpdf shows that 0-Reuse

Bench++ is the second fastest because many of the memory alloca-
bench-plus-pl [Link]
tions are done directly through malloco instead of using
newo. Only about 30% of memory allocations are per-
All the memory traces were generated by a tool called formed by the new0 operator. More than half of the total
mtrace++ which was developed by our research laborato- allocations are controlled by malloco directly. Lea’s ver-
ry to investigate the memory allocation behavior of C++ sion 2.5 malloc shows the fastest allocation time. Howev-

389

Authorized licensed use limited to: University of Pretoria. Downloaded on April 16,2026 at 16:27:03 UTC from IEEE Xplore. Restrictions apply.
 er, it consumes two time more memories than 0-Reuse. 0- dered by the total number of dynamic memory invoca-
Reuse requires slightly more processing time but it is pref- tions. Most of dynamic invocations are occurred during
erable due to less memory overhead. Figure 4 displays transferring files.
memory usages of different algorithms.
Figure 6. Lftp DMM process time
Figure 3. Xpdf DMM process time

The result of Bench++ is presented in Figure 7. The

Figure 4. Xpdf memory usage first input is the Dhrystone benchmark. The Dhrystone in-
-~ dex numbers are 215K with 0-Reuse, 191K with Lea's
10000 I , 0-Reuse version 2.5, and 178K with Lea's version 2.6.5. The high-
er index number indicates the higher performance. The
'e other two tests have similar results as Dhrystone. There-
1 6000
4000
fore, using 0-Reuse strategy, we can minimize CPU pro-
g 2000
cess time when we execute various C++ applications.
0

Figure 7. Bench++ DMM process time

The result of Roboop is displayed in Figure 5 which

shows the explicit difference between 0-Reuse and others.
0-Reuse is the fastest. It is about four times faster than
Lea's version 2.6.5 malloc and two times faster than Lea's
version 2.5 malloc. The dynamic memory process time oc-
cupies 39% of the total execution time when we use Lea's
version 2.6.5 malloc. It means that DMM consumes more
than 1/3 of execution time in this program. However,
DMM time is reduced to 11% when 0-Reused is applied. 4.2. Summary of Results
Obviously, the overall process time is significantly im- Our results indicate that 0-Reuse is the fastest be-
proved. cause the algorithm reduces the number of malloc() calls
and requires no coalescing and no splitting. All of our test-
Figure 5. Roboop DMM process time ed programs allocate many small size objects which are re-
used very frequently. Over 96% of allocated objects are
reused in the experiment.
In every program, most objects are less than or equal
to 1KB. If object sizes are big and only few of them are re-
used, its memory usage will be the major overhead in 0-
Reuse. However, in C++ programs that we experimented,
less than 5% of the allocations are large objects, i.e., IKB.

In Figure 6, the behavior of Lftp is similar to the one The following table describes object reusability. It
contains the number of new() requests, the number of re-
in Roboop. The overall execution time highly depends on
used objects and the percentage of object reuse. There are
its dynamic memory process which can reach up to 47% of
the entire execution time with Lea's version 2.6.5 malloc. many allocation requests as well as high rate of object re-
use. Most of the memory invocation cases belong to our
Our simulation results indicate that DMM improvement
first four scenarios: constructor, copy constructor, opera-
can be as high as 325% (as compared to version 2.6.5) and
tor= overloading, and type conversion. The major invoca-
57% (as compared to version 2.5). Input 1, 2 and 3 are or-
tion scenario of the first four programs is in constructors.

390

Authorized licensed use limited to: University of Pretoria. Downloaded on April 16,2026 at 16:27:03 UTC from IEEE Xplore. Restrictions apply.
Bench++ allocation requests are mostly made by construc- bytes, short lived, and highly reused. Constructors and
tors and copy constructors. copy constructors are the two biggest contributors in dy-
namic memory allocation. 0 - R e u s e allocator utilizes these
Table 2. Object reusability. characteristics of C++ to deliver memory allocation per-
formance which in some cases are 300% faster than Lea‘s
cs roboop Iftp xpdf bench++ malloc. Since 0 - R e u s e allocates over 90% of objects in
new()requests 902 1952 158 205 18932 size below 512 bytes and over 99% of the objects are re-
(1000 times) used, it’s memory usage is not the problem to be con-
reusedobjects 869 1951 157 200 18931
cerned as an overhead. 0 - R e u s e could be an important
(1000 times) step towards improving the performance of dynamic mem-
ory management in C++.
percentage (%) 96.3 99.9 99.9 97.5 . 99.9
of object reuse
References
Our results show that DMM consumes a large portion
David Detlefs, AI Dosser and Benjamin Zom, “Memory al-
of overall execution time. The average portion is 26% in
location costs in large C and C++ programs”, Sofrware -
our experiments. When a program spends a large amount Practice and Experience, pp. 521-542, June 1994.
of time for DMM, its overall performance is significantly Benjamin Zom and Dirk Grunwald, “Empirical Measure-
improved by 0 - R e u s e . As a result, 0 - R e u s e improves ments of Six Allocation intensive C Programs”, Technical
overall performance up to 29% compared to Lea’s 2.5 Report CU-CS-604-92. CS Dept, Univ. of Colorado, Boul-
malloc. der, CO, July 1992.
Brad Calder, Dirk Grunwald and Benjamin Zom, “Quanti-
fying Behavioral Differences Between C and C++ Pro-
5. Conclusions grams”, Technical Report CU-CS-698-95, CS Dept, Univ.
of Colorado, Boulder, CO, January 1995.
Faster dynamic memory management strategies and Woo Hyong Lee, Moms Chang and Yusuf Hasan, “A Dy-
algorithms are needed to solve the problem of C++ ‘s large namic Memory Measuring Tool for C++ Programs”, To
number of dynamic memory invocations. This results in appear Proc. of IEEE Application-Specijic Systems and
high CPU time usage and degrades overall performance. Engineering Technology Symposium, Richardson, Texas,
In C++, dynamic memory is allocated through the n e w op- March, 2000.
erator and freed through the delete operator. The new op- J. Moms Chang, Woo Hyong Lee and Yusuf Hasan, “Mea-
erator allocates memory by calling the C language suring Dynamic Memory Invocations in Object-Oriented
function malloco and the delete operator deallocates Programs“, Proc. of IEEE International Performance Con-
ference on Computers and Communications, Phoenix, Ari-
memory by calling the C functionfree(). By overloading
zona, pp. 268-274, Feb. 1999.
these operators, we could develop the customized memory M. Chang and E. F. Gehringer, “A High-Performance
allocator, i.e., 0 - R e u s e . Memory Allocator for Object-Oriented Systems”, IEEE
We have identified certain characteristics of C++ dy- Transactions on Computers, pp. 351-366, March 1996.
namic memory allocation. They allow us to develop a dy- Kelvin D. Nilsen and Hong Gao, ‘The real-time behavior
namic memory management technique which has proven of dynamic memory management in C++”, Proc. of IEEE
Real-Time Technologies and Applications Symposium,
to be much faster than existing methods. Our empirical
Chicago, IL, pp. 142-153, 1995.
data from the tests conducted on five different C++ appli- Bjame StrouStrup, The C + + Programming Language,
cations revealed that 90% of the allocated objects are not Third Edition, Addison-Wesley, 1997.
bigger than size 512 bytes with short life-spans and high Paul R. Wilson, Mark S. Johnston, Michael Neely and
rates of reuse. This means that small objects less than 512 David Boles, “Dynamic Storage Allocation A Survey and
bytes are repeatedly allocated and freed during the course Critical Review”, Proc. of International Workshop on
of program execution. The results also show that the major Memory Management, Kinross, Scotland, UK, September
part of dynamic memory allocation comes from C++ lan- 1995.
guage’s constructor and copy-constructor. This discovery [ I O ] T. Comfort, “Multiword list items”, Communications of
has become the basis of our simple but fast dynamic mem- the ACM, 7(6), June 1964.
ory algorithm. [ 1 I ] Susan Graham, Peter Kessler and Mashall McKusick,
“gprof: a Call Graph Execution Profiler”, Proc. of ACM
We tested five C++ applications which can be ob- SIGPLAN Symposium on Compiler Construction, pp. 120-
tained publicly. The results from all of them bear out our 126, June 1982
hypotheses that most objects are of sizes less than 512 [ 121 http:l/[Link]/pub/misc/

391

Authorized licensed use limited to: University of Pretoria. Downloaded on April 16,2026 at 16:27:03 UTC from IEEE Xplore. Restrictions apply.