Recycle Bin

Pattern Name:

Recycle Bin

Also Known As

Pool, Free List

Problem

How do you reduce the overhead of creation and destruction of resources ?

Context

A number of resources are requested and released while the system is running.

Forces

Resource allocation if left to the OS may be expensive
Resource allocation if left to the OS may be shared with others
Resource allocation if left to the OS may fragment
Dynamic allocation of resources may be unsafe or unavailable on some systems
Small resource requests may have high overhead
You are forced to work in one of those archaic languages that do not support garbage collection.

Solution

You can store freed resources in a local bin so that subsequent requests for these resources can reuse the ones in the bin. A client requests resources through the bin. The bin will reuse an existing one if available or create a new one if necessary . The recycle bin may request more resources than actually needed to optimize performance. When the use of the resource is complete, it should be returned to the bin. A bridge (Gamma, 96) may be introduced to separate the client?s view of the resource and the actual resources so that the concept of the recycling bin can be completely hidden from the client. A recycle bin may create a fixed amount of resources up-front or request them on demand.

Resulting Context

We now have a system where resource allocation and deallocation may be controlled to whatever level the situation calls for.

Rationale

Resource requests normally go through the operating system. Kernel requests for resources are among the most expensive calls that can be made. Specifically, memory requests in a UNIX system can cause havoc on real-time system performance. In addition, users often misunderstand the overhead related to managing dynamic memory allocation. For example, a malloc of 2 bytes may carry an overhead which is at least 2 pointers in memory. The overhead cost is then more than the actual storage cost. Additionally, many operating systems use a minimum size block so even more is wasted. By utilizing a Recycle Bin and managing the resources ourselves, no OS calls are required by the client increasing our portability. All requests are essentially pointer assignments and calculations. Any additional overhead is completely controlled by the Recycle Bin. The Recycle Bin can then take advantage of low-level optimizations without sacrificing portability of the clients.

Known Uses

This pattern has been used successfully for memory management in many systems which use memory pools [Goldfedder, 94].

Related Patterns

Bridge [GOF], Flyweight[GOF], MemoryPool? [Goldfedder, 94]

Sketch

Haven't translated from Visio to text yet

Author(s)

BrandonGoldfedder

Precisely how does RecycleBin differ from GOF's flyweight? --- are they synonymous?

I don't think so. Flyweight hides the implementation of an aggregate object behind a Facade so that the children of the object can be treated as objects but implemented more efficiently if they are very fine-grained. A RecycleBin can be used with coarser grained objects -- it is concerned with reducing allocation time, rather than allocation space.

-- NatPryce

I HaveThisPattern -- RonJeffries

Examples

There are examples of this pattern in MFC. When it makes a linked list, it keeps a private list of free nodes. Getting a node from the free list is much faster than using malloc(). (And it doesn't look much like Facade to me.)

In fact, "Free List" may be an alternative name for this pattern. I've not heard of it as a pattern, but if you say to someone, "We'll keep a free list", they'll probably know what you mean.

Hmmm... or is that a different pattern? Unix keeps track of unused inodes (and disk blocks) in what might losely be called a free list. In that case, there is no question of leaving it to a higher authority, ie operating system - Unix is the operation system. Does this count?

A potential problem with this pattern is that it requires you to free stuff explicitly. This means you need to know all references to the stuff have done with it. In effect, you are giving up automated garbage collection, with all that that entails. Is that why not having GC is part of the context? Sometimes this pattern is useful even if you do have GC.

Another potential problem is that the O/S cannot see your unused resources. There may be another application which needs them. If the O/S manages the resources, it can take them away from you and give them to the other app, but if you are holding onto them in a recycle bin, the other app is starved. So this can be an anti-social pattern. -- DaveHarris

I have used this pattern in a language with garbage collection (Java) in order to dramatically increase execution time in a critical path algorithm. Nice thing about the memory allocator, when CPU usage is 100%, it would rather allocate more memory than collect garbage. This leads to pathelogical paging behavior. Doing it by hand reduced paging by an order of magnitue (I *still* couldn't get it to free image buffer objects in a timely fashon. Nice objects there, only a few bytes, but they allocate several hundred kbytes of memory in the X server process). -- AnonymousDonor

Some database applications/libraries use ConnectionPools to reduce the cost of creating connections, instead of creating them anew for each db transaction. The idea generalizes to other situations wherein the cost of resource creation was high compared to resource lifetime.

One case when this pattern may be appropriate in a garbage-collected environment is when there are specific resources which have a specific known usage pattern. If you know a priori how the objects/resources will be used - for instance, if you know your application will periodically discard a large number of them and soon after reallocate a similar number - *and* if performance is critical, you may be able to do much better than the default garbage collector would. Antisocial affects can be avoided if your language supports "weak references", you can have your Recycle bin or Free list hold "weak references" to the resource objects, allowing them to be garbage-collected only if necessary to avoid starving other applications or components. -- (A different) AnonymousDonor