Case Study 2: Build the Growable Array

"The right data structure is the one that disappears into the hardware."

Executive Summary

The first case study fixed a pointer structure and concluded it should have been an array. This one builds that array — a general-purpose growable buffer: an allocatable array that starts small and doubles its capacity as you append, giving you the "I do not know how many elements there will be" flexibility of a linked list with the contiguous speed of an array. You will design the doubling policy, implement the append with move_alloc, prove the per-append cost is $O(1)$ amortized, and expose the buffer's storage to a fast sweep through a contiguous dummy argument. The result is the structure real scientific codes reach for when a collection grows at run time — and a concrete demonstration of why, in Fortran, "dynamic" almost never means "pointer."

Skills applied: the allocatable-over-pointer rule and its consequences (§11.4); move_alloc for an $O(1)$ storage hand-off; the contiguous attribute on a dummy argument (§11.5); amortized-cost reasoning; type-bound procedures on a derived type (Ch. 9) organized in a module (Ch. 8).

Background

Simulations constantly produce collections whose size is unknown in advance: every particle that crosses a boundary this step, every cell flagged for refinement, every event above a threshold. You cannot size an array up front, and you do not want to over-allocate a huge fixed array "just in case." The linked-list instinct — allocate a node per element — is exactly the wrong reflex in Fortran (§11.3): it scatters the data, defeats prefetching and vectorization, and pays an allocation per element.

The growable array solves the same problem the right way. Keep an allocatable array as backing storage and a separate integer for the logical size (how many slots are in use). Append into the next free slot; when the storage fills, allocate a bigger block, copy the live elements over, and hand the new block back. Amortized over many appends, the copying is cheap, and between reallocations every append is a single store into contiguous memory. This is how a Python list, a C++ std::vector, and a Fortran stdlib growable type all work under the hood — and building one yourself, once, demystifies all of them.

Our design target: a buffer_t holding real(dp) values, with a push that doubles capacity when full.

Phase 1 — Design the Structure and the Growth Policy

Two pieces of state, and one decision. The state: a backing array data(:) (allocatable, so it owns its memory and frees itself — §11.4) and an integer n for the logical size. The decision: the growth policy, i.e. how much bigger to make the array when it fills.

The choice that matters is geometric growth — multiply the capacity by a constant factor (we use 2) each time it fills — rather than arithmetic growth (add a fixed number of slots). The reason is the amortized cost, which we prove in Phase 3: doubling makes $n$ appends cost $O(n)$ total, while growing by a constant increment makes them cost $O(n^2)$. Geometric growth is the whole trick, and 2× is the canonical factor.

type :: buffer_t
  real(dp), allocatable :: data(:)   ! backing storage — owns its memory
  integer :: n = 0                   ! logical size (slots in use)
contains
  procedure :: push
end type buffer_t

Note what we did not write: no pointer, anywhere. The backing store is allocatable, so a buffer_t that goes out of scope frees its storage automatically, cannot dangle, and cannot leak. The bug classes of Case Study 1 are absent by construction.

Phase 2 — Implement push with move_alloc

Appending is three steps: if the storage is full, grow it; then place the new value; then bump the logical size. Growing is where move_alloc earns its place — it transfers an allocation from one variable to another without copying the array a second time, an $O(1)$ hand-off:

module buffer_mod
  use, intrinsic :: iso_fortran_env, only: dp => real64
  implicit none
  private
  public :: buffer_t

  type :: buffer_t
    real(dp), allocatable :: data(:)
    integer :: n = 0
  contains
    procedure :: push
  end type buffer_t

contains

  subroutine push(self, x)
    class(buffer_t), intent(inout) :: self
    real(dp),        intent(in)    :: x
    real(dp), allocatable :: tmp(:)
    integer :: cap
    if (.not. allocated(self%data)) allocate(self%data(1))   ! first push: capacity 1
    cap = size(self%data)
    if (self%n == cap) then               ! full: double the capacity
      allocate(tmp(2*cap))                ! the only per-growth allocation
      tmp(1:self%n) = self%data(1:self%n) ! copy the live elements over
      call move_alloc(tmp, self%data)     ! O(1) hand-off; tmp is left deallocated
    end if
    self%n = self%n + 1
    self%data(self%n) = x
  end subroutine push

end module buffer_mod

move_alloc(tmp, self%data) deallocates the old self%data, moves tmp's allocation into self%data (no element copy — just a transfer of ownership), and leaves tmp deallocated. Without it you would need a manual deallocate(self%data) and an allocatable-assignment that might copy again; move_alloc is the idiom that makes the grow both correct and cheap.

Phase 3 — Prove the Cost: Doubling Is $O(1)$ Amortized

The worry with a growable array is the copying: every time it fills, we copy every live element into the new block. Does that make appends expensive? Count the copies. Starting from capacity 1 and doubling, the reallocations that occur while growing to hold $m$ elements copy

$$ 1 + 2 + 4 + \dots + 2^{k} \;<\; 2 \cdot 2^{k} \;\le\; 2m $$

elements in total — a geometric series that sums to less than twice the final size. So $m$ appends do fewer than $2m$ element-copies between them: $O(m)$ total work, hence $O(1)$ amortized per push. Most appends copy nothing at all; the occasional one that triggers a doubling copies a lot, but those grow rarer exactly as fast as they grow costlier, and it all averages out to a constant. (Contrast arithmetic growth by a fixed $c$: the copies are $c + 2c + 3c + \dots \sim m^2/2c$, quadratic — which is why nobody grows by a constant increment.)

Drive the buffer and watch the capacity double, then confirm the totals by hand:

program grow_demo
  use, intrinsic :: iso_fortran_env, only: dp => real64
  use buffer_mod, only: buffer_t
  implicit none
  type(buffer_t) :: b
  integer :: k

  do k = 1, 6
    call b%push(real(k*k, dp))       ! push 1, 4, 9, 16, 25, 36
    print '(a, i0, a, i0, a, i0)', 'push ', k*k, ' -> n = ', b%n, &
                                   ', capacity = ', size(b%data)
  end do

  print '(a, i0)',   'final logical size = ', b%n
  print '(a, i0)',   'final capacity     = ', size(b%data)
  print '(a, f0.1)', 'sum                = ', sum(b%data(1:b%n))
  print '(a, f0.1)', 'checksum(contig)   = ', checksum(b%data(1:b%n))

contains
  real(dp) function checksum(a) result(s)
    real(dp), intent(in), contiguous :: a(:)   ! promise: solid block -> vectorize
    s = sum(a)
  end function checksum
end program grow_demo

$ gfortran -std=f2018 -Wall buffer_mod.f90 grow_demo.f90 -o grow && ./grow
push 1 -> n = 1, capacity = 1
push 4 -> n = 2, capacity = 2
push 9 -> n = 3, capacity = 4
push 16 -> n = 4, capacity = 4
push 25 -> n = 5, capacity = 8
push 36 -> n = 6, capacity = 8
final logical size = 6
final capacity     = 8
sum                = 91.0
checksum(contig)   = 91.0

Trace the capacities: it doubles only on the pushes that find the array full — at logical sizes 1, 2, 4, and 8 — so the capacity sequence is 1, 2, 4, 4, 8, 8 across the six pushes, exactly as printed. Six pushes triggered three doublings (copying $1 + 2 + 4 = 7$ elements total, comfortably under $2 \times 6 = 12$), and the values $1, 4, 9, 16, 25, 36$ sum to $91$.

Phase 4 — Expose the Storage to a Fast Sweep with contiguous

The payoff of building on an array instead of a list is that the data is right there, contiguous, ready to be swept at full speed. The checksum function above shows the professional pattern: it takes the buffer's live slice through a contiguous assumed-shape dummy argument. Because b%data(1:b%n) is a leading section of a contiguous allocatable, it is contiguous, so the promise holds — and the contiguous attribute lets the compiler treat a as a solid block and vectorize the reduction, rather than emitting the general strided-access code it must assume for a plain a(:).

This is exactly the lever Chapter 29 pulls to speed up the heat solver's stencil: contiguous on the kernel's dummy argument, promising the caller always hands it solid storage. A linked list can offer no such promise — there is no contiguous slice to pass. The growable array does not just match the list's flexibility; it hands the optimizer a guarantee the list could never make.

Phase 5 — When (Rarely) a List Still Wins

Honesty, as always. The growable array is the right default, but it is not universal. Its weakness is insertion or deletion in the middle: to insert at position $j$, you must shift every later element, an $O(m)$ operation, whereas a linked list splices in $O(1)$ once you hold the spot. So if your workload is dominated by mid-sequence insert/delete on a large collection — a rope of text edited in the middle, a scheduler queue with frequent cancellations — a linked structure (or a more specialized structure) can genuinely win.

But notice how narrow that window is, and how often even it closes in Fortran: if you also sweep the collection numerically, the array's cache and vectorization advantage on the sweep frequently outweighs the list's cheaper splices, and an index-based structure (links stored as integer indices into an array, §11.3) recovers the $O(1)$ splice and keeps contiguity. Append-and-sweep — by far the commonest scientific pattern, and the one our buffer serves — belongs to the array without contest.

Discussion Questions

  1. Why is geometric (doubling) growth $O(1)$ amortized while arithmetic (fixed-increment) growth is $O(n)$ amortized? Reproduce the two series and identify precisely where the quadratic term enters.
  2. move_alloc is described as an "$O(1)$ hand-off." What exactly is $O(1)$ about it, given that the array it transfers may hold millions of elements? What did the $O(m)$ copy that preceded it accomplish?
  3. The checksum function promises contiguous. What would happen — to correctness and to performance — if a caller passed a strided section to it? Why can b%data(1:b%n) never be that caller?

Your Turn: Extensions

  • Option A. Add a pop (remove and return the last element) and a shrink policy that halves capacity when the buffer falls below one-quarter full. Why quarter, not half? (Hint: avoid "thrashing" — repeated grow/shrink at a single boundary.)
  • Option B. Generalize buffer_t to store a derived type (say a particle_t) instead of a real(dp). What changes in push, and what does not? Connect to the parameterized/allocatable-component ideas of Chapter 9.
  • Option C. Instrument push to count total element-copies, run it for $m = 1000$ appends, and check the count against the $< 2m$ bound from Phase 3. (This is Exercise 11.28, and it is worked in code/exercise-solutions.f90.)

Key Takeaways

  • The growable array — an allocatable backing store plus a logical-size counter, doubled on overflow — is Fortran's answer to "a collection whose size I learn at run time." It is the structure to reach for, not a linked list.
  • move_alloc transfers an allocation in $O(1)$, making the grow step correct and cheap; it is the idiom for handing a freshly sized block back to the buffer.
  • Geometric growth makes append $O(1)$ amortized ($< 2m$ copies over $m$ appends); arithmetic growth is quadratic. Double, do not increment.
  • Building on an array keeps the data contiguous, so you can hand a contiguous slice to a vectorized sweep — a guarantee a linked list can never make. Flexibility and speed, with no pointer in sight.