Driving Range Pooled Allocator

A number of projects that I’ve worked on over the years involve processing data in some kind of batch: a file, a message, the contents of a database, etc. One recurring design need in these scenarios is a means of allocating large, but variable, numbers of small, simple instances which are allocated over the life of the batch, but which can all be released when the batch is finished. Large numbers of small allocations can be brutal on a memory management system, especially in terms of CPU time (and in terms of fragmentation on non-GC systems). This post presents an F# implementation of a pooling algorithm I’ve used for many years, and in various languages from C onwards, to solve this problem.

In a nutshell, it sub-allocates fixed-size batches of instances. Instances are dispensed from these batches, with more batches being added as required. When the run is complete, the batches are “virtually de-allocated” by resetting various indices, but the instances themselves are not de-allocated.

I don’t know whether this algorithm has a formal name and history. I’m sure it does, but I’ll call it the “Driving Range Pooled Allocator.” This is because it reminds me of a golf driving range. The main kiosk at the range sub-allocates golf balls in little buckets, golfers then take the golf balls from these buckets one at a time and drive them out onto the range. The algorithm is like a really low-budget operation that only has one customer at a time and a golf-ball recovery tractor with no safety cage. The customer represents a batch run, allocating golf-balls over the life of the run. When the customer is finished, the tractor goes out and sweeps up all the golf balls at once.

This algorithm is not designed to be a general purpose allocator. It works best when the instances are small, have no special creation, disposal, or finalization concerns, and can be easily reset to a fresh state. Additionally, the algorithm will be most efficient when the standard deviation in allocation count is large enough to make pre-allocation an issue, but small enough that over-allocation is not an issue.

One more caveat: 99% of the time, when you think you can build a better allocator on top of the system-provided allocator, you're wrong. This algorithm is no exception. Use if for that rare remaining 1%; make sure it's applicable and -- if in doubt -- benchmark your application of it.

I named the sub-allocation array classes “Bucket” and the main class “Barrel.” The interfaces are fairly straightforward. I would like to point out that Barrel has two Reset functions. The first, Reset(), does a simple reset of the indices. The second, Reset(n), resets the indices, but also shrinks the allocation to a size as small as possible while retaining a capacity of at least n. This is handy for scenarios where the allocation size can occasionally grow huge and you want to scale it back to something closer to the median allocation size without reallocating the whole Barrel. Barrel.Count and Barrel.Capacity are not unit-time algorithms; they are generally rarely used. If you need faster versions, you can compute and cache these values.

I did my best to test for errors, but this is a generation 1.0 F# implementation. For one thing, it is designed mainly for internal use and so does minimal error-checking (i.e. not library-level error checking). Also, I re-wrote it from scratch rather than porting-it, and I may have let a bug or two slip by. If any are found, I’ll post a correction.

And, as always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.

///<summary>Pooled array allocator.</summary>
type Bucket<'a when 'a:(new:unit->'a)> (size:int) = 

  //<summary>The array.</summary>
  let b = Array.init size (fun i->new 'a())

  //<summary>Current allocation point.</summary>
  let mutable cursor = size

  //<summary>Chain for use in Barrel<'a>.</summary>
  let mutable next:Bucket<'a> option = None

  //<summary>Get capacity.</summary>
  member this.Capacity = 
    size

  //<summary>Get current allocation count.</summary>
  member this.Count 
    with get() = size-cursor

  //<summary>Get current allocation item.</summary>
  member this.Current 
    with get() = b.[cursor]

  //<summary>Move to next allocation item.</summary>
  member this.MoveNext () =
    match cursor with
    | 0 -> false
    | _ ->
       cursor<-cursor-1
       true 

  //<summary>Chain for use in Barrel<'a>.</summary>
  member this.Next 
    with get() = next
    and set v = next<-v

  ///<summary>Reset allocation.</summary>
  member this.Reset() = cursor<-size


///<summary>Pooled batch allocator.</summary>
///<param name="s0">First bucket capacity.</param>
///<param name="sn">Nth bucket capacity.</param>
type Barrel<'a when 'a:(new:unit->'a)> (s0:int, sn:int) = 

  ///<summary>First bucket (always instantiated).</summary>
  let head = (Bucket<'a> s0)

  ///<summary>Tail for quick appends.</summary>
  let mutable tail = head

  ///<summary>Current allocation bucket.</summary>
  let mutable cursor = head

  ///<summary>Helper for this.Capacity.</summary>
  let rec capacity (b:Bucket<'a>) s =
    match b.Next with
    | None -> s+b.Capacity
    | Some(b') -> capacity b' (s+b.Capacity)

  ///<summary>Helper for this.Count.</summary>
  let rec count (b:Bucket<'a>) s =
    match b.Count with
    | 0 -> s
    | _ ->
        match b.Next with
        | None -> s+b.Count
        | Some(b') -> count b' (s+b.Count)

  ///<summary>Helper for this.Reset.</summary>
  let rec reset (b:Bucket<'a>) =
    if b.Count>0 then
      b.Reset()
      if b.Next.IsSome then
        reset b.Next.Value 

  ///<summary>Helper for this.Reset(n).</summary>
  let rec resetCapacity c0 cs (b:Bucket<'a>) =
    b.Reset()
    match cs>=c0 with
    | true -> 
        tail<-b
        tail.Next<-None
    | false -> 
        match b.Next with
        | None -> 
            tail<-b
            tail.Next<-None
        | Some(b') ->
            resetCapacity c0 (cs+b.Capacity) b'
  
  ///<summary>Get current capacity.</summary>
  member this.Capacity 
    with get() = 
      capacity head 0
  
  ///<summary>Get current allocation count.</summary>
  member this.Count 
    with get() =
      count head 0
  
  ///<summary>Reset allocation.</summary>
  member this.Reset () =
    reset head
    cursor<-head
  
  ///<summary>Reset allocation and capacity.</summary>
  ///<param name="n">New minimum capacity.</param>
  member this.Reset n =
    if n<0 then
      raise (new System.ArgumentException())
    resetCapacity n head.Capacity head
    cursor<-head
  
  ///<summary>Allocate an item.</summary>
  member this.Take () =
    match cursor.MoveNext() with
    | true -> cursor.Current
    | false ->
        match cursor.Next with
        | Some(b) -> cursor<-b
        | None ->
            cursor<-Bucket<'a> sn
            tail.Next<-Some(cursor)
            tail<-cursor
        cursor.MoveNext() |> ignore
        cursor.Current

  
///<summary>Simple test class.</summary>
type Indexed () =
  
  static let mutable instances = 0

  let index = instances

  do instances<-instances+1

  member this.Index with get() = index


// Perform some tests.

let bb = Barrel<Indexed>(10,5)

for i=1 to 12 do
  printfn "(%i %i %i)" ((bb.Take()).Index) bb.Count bb.Capacity

bb.Reset()
printfn "Clear"

for i=1 to 22 do
  printfn "(%i %i %i)" ((bb.Take()).Index) bb.Count bb.Capacity

bb.Reset 11
printfn "Reset"

for i=1 to 12 do
  printfn "(%i %i %i)" ((bb.Take()).Index) bb.Count bb.Capacity

bb.Reset 0
printfn "Reset"

for i=1 to 22 do
  printfn "(%i %i %i)" ((bb.Take()).Index) bb.Count bb.Capacity