Performance

Pools help only classes where memory allocation is a substantial fraction of run time. Such classes tend to be small and have simple operations. Classes with a lot of members will necessarily spend a lot of time dealing with those members and relatively less time on memory allocation.

Because pools are most useful with small classes, they are implemented so that alloc and free can often be executed inline.

The present implementation uses a singly-linked list of free elements for each Pool object. Once an element has been allocated, its link is no longer needed; hence the links share space with the elements themselves and take no space overhead.

The only time alloc is done out of line is when the list is exhausted. In that case, alloc requests a new block from the operating system and uses it to augment the free list.

Because elements are so simply linked, there is no efficient way to determine whether freeing an element has emptied a block. Therefore, once a block has been added to a Pool, it is returned to the system only when the Pool itself is destroyed.

In other words, the amount of memory occupied by a Pool is the amount occupied by the largest number of elements that have ever been simultaneously allocated in that Pool, rounded up to the size of a block. The system memory allocator imposes its own overhead, which varies from system to system, on each block, but there is no additional overhead per element. Blocks are presently about 1,000 bytes.

The time performance of pools depends heavily on the application and on the speed of the system memory allocator. As an example, consider the following program fragment:

   Thinglist* head = 0;
   for (register int j = 0; j < N; j++) {
       Thinglist* tp = new Thinglist;
       tp->next = head;
       head = tp;
   }
   while (head) {
       Thinglist* tp = head->next;
       delete head;
       head = tp;
   }

This code allocates a linked list of N Thinglist nodes and then deletes it again. Here are execution times, in milliseconds, for various values of N on two different machines:

N	VAX 8550, System V Release 2		MicroVAX, Ninth Edition
	with pools	without pools	with pools	without pools
1	0.008	0.03	0.036	0.229
10	0.066	0.286	0.290	2.31
100	0.65	2.86	2.85	23.4
1000	6.6	30.1	28.5	232
10000	69	288	285	2400

These numbers give an idea of how much can be gained by using pools in one particular context. However, applications vary widely, so you should not assume that any particular application will show such dramatic improvements.