Many data types of LEDA are implemented as collections of small objects for which memory is allocated dynamically. So, for example, a list is built up from containers; the containers only “arise” if elements are added to the list. Construction and destruction of these small objects happen in C++ via the operators new and delete, respectively, and require considerable computing time.

To accelerate the memory management, LEDA has an efficient memory manager, which is used for all node, edge, and item types. The basic idea is to amortize the expensive calls, which alternate again and again in a long sequence of new and delete, for small memory blocks. For this purpose, the memory manager manages (free) blocks up to a size of 255 bytes in one of 255 respective lists. If a block of size i is freed by delete, it joins list i; if a block of the size i is needed, it is taken from the list i if this list is not empty. new is invoked only if list i is empty and a block of size i is needed; then, however, approximately 8 kilobytes are allocated all in one go, which then are split into partial blocks of an appropriate size and appended to list i. This way queries for memory blocks of up to 255 bytes can be handled fast in most cases because, all in all, new and delete are only seldom invoked, actually. In contrast, blocks that are larger than 255 bytes are requested directly from new.

Self-defined data types can also be subjected to this memory manager. This is worthwhile (concerning the computing time) when the data types are “small”, that is, if their data members do not use up more than 255 bytes altogether.

To subject a self defined data type T to LEDA's memory manager, merely the macro

LEDA_MEMORY(T);

has to be added to the definition of the class. This macro redefines new and delete for T so that the two operators pass queries for T on to the memory manager.

Our class pair from Section 2.8.3 is a typical candidate for a type that should be subjected to the LEDA memory manager. This class has only 2 data members of type int; an instance therefore needs 8 bytes (on today's common architectures). By including the macro LEDA_MEMORY(pair) in the class definition we make the LEDA memory manager take care of allocation and deallocation of storage for objects of this type:

class pair {
private:
  int  x;
  int  y;

public:
 pair() { x = y = 0; }
 pair(const pair& p) { x = p.x; y = p.y; }
 pair& operator=(const pair& p) {
       if(this != &p) { x = p.x; y = p.y; }
       return *this;
       }
 friend std::istream& operator>> (std::istream& is, pair& p) 
   { is >> p.x >> p.y; return is; }
 friend std::ostream& operator<< (std::ostream& os, const pair& p) 
   { os << p.x << " " << p.y; return os; }
 
 pair(int a, int b) { x = a;  y = b; }

 LEDA_MEMORY(pair); // use LEDA memory manager for this class
};

Which practical consequences does this have? We make an experiment: We fill a list with one million pairs and empty it again. This we do 10 times:

#include <LEDA/list.h>
#include <LEDA/misc.h>
#include <iostream>
#include "pair_memory_managed.h"

using leda::list;
using leda::print_statistics;

int main()
{
  list<pair> L;
  
  for(int j = 1; j <= 10; j++) {
    for(int i = 0; i < 1000000; i++)
      L.append(pair(i,i));
    L.clear();
  }

  print_statistics();
}

The function

print_statistics();

belongs to the useful small auxiliary functions that are declared in the header file misc.h; these functions are explained in more detail in Section 2.11.5. In the above program, print_statistics() outputs the following:

         STD_MEMORY_MGR (memory status)
        +--------------------------------------------------+
        |   size     used     free     blocks     bytes    |
        +--------------------------------------------------+
        |     8        27   1000511       979    8004304   |
        |    12        24   1000365      1469   12004668   |
        |    24         1      339         1       8160    |
        |    36         5      221         1       8136    |
        | > 255         -        -         2        100    |
        +--------------------------------------------------+
        |   time:  7.32 sec              space:19590.53 kb |
        +--------------------------------------------------+

The table printed by print_statistics() says that altogether LEDA allocated 27 + 1,000,511 partial blocks of a length of 8 bytes, 24 + 1,000,365 partial blocks of a length of 12 bytes, 1 + 339 partial blocks of a length of 24 bytes and 5 + 221 partial blocks of a length of 36 bytes. Here the second line results from the 1 million containers of the list L, the first line from the 1 million partial blocks that are additionally managed for the pairs by the LEDA memory manager.

print_statistics() also gives information about which of these partial blocks are still being used at present and which are free again. Nearly all blocks are free again here because the last statement of the loop reads L.clear(); thereby, the partial blocks the list physically consists of are given back to the memory manager for reutilization.

As already explained, storage is always allocated by LEDA in large blocks of approximately 8 kilobytes. The penultimate column indicates the number of blocks allocated for the partial blocks of different size. The last column shows the overall memory consumption in bytes. The last line means that the program ran for a total of 7.32 seconds and that the LEDA memory manager used up 19,590.87 kilobytes of memory.

	Note
	In general, the number behind the label space: does not stand for the storage that was used up altogether because not all calls of new or delete in a program use the LEDA memory manager!

Let us compare the above output with the output of print_statistics() for the original class pair, which lacks the macro LEDA_MEMORY(pair):

         STD_MEMORY_MGR (memory status)
        +--------------------------------------------------+
        |   size     used     free     blocks     bytes    |
        +--------------------------------------------------+
        |     8        27      995         1       8176    |
        |    12        24   1000365      1469   12004668   |
        |    24         1      339         1       8160    |
        |    36         5      221         1       8136    |
        | > 255         -        -         2        100    |
        +--------------------------------------------------+
        |   time: 13.69 sec              space:11770.35 kb |
        +--------------------------------------------------+

As we see, the running time is almost twice as long here in contrast to the version with LEDA_MEMORY(pair)! So the allocation and deallocation of memory in large blocks have definitely amortized themselves in the above version. Here however, the memory manager uses up considerably less storage since the objects for the administration of the partial blocks are no longer necessary.