Choosing the Right Array Type

The decision in one diagram

The choice reduces to three questions: is the size known at compile time, does the collection grow and shrink during the run, and is the index space dense or sparse? Answer those and the container picks itself. Getting this wrong rarely breaks functionality — every container can be abused into doing the others' jobs — but it breaks performance and memory , which is why “when would you use each array type?” is a near-universal verification interview question.

ARRAY TYPE DECISION MATRIX

  Size known at compile time?
        │
        ├── YES ──► need synthesis or pure speed?
        │              └──► FIXED ARRAY  logic [7:0] m [0:255]
        │                   (only family synthesis accepts)
        │
        └── NO ───► index space dense or sparse?
                       │
                       ├── SPARSE (huge, few used) ──► ASSOCIATIVE
                       │        byte mem [longint]
                       │        e.g. 64-bit address space models
                       │
                       └── DENSE ──► elements flow in/out over time?
                                        │
                                        ├── YES ──► QUEUE  int q[$]
                                        │     FIFOs, scoreboards, logs
                                        │
                                        └── NO (size set once,
                                              then random access)
                                              ──► DYNAMIC  int d[]
                                              packet payloads, mems
                                              sized from plusargs

Performance and memory trade-offs

Fixed arrays are the fastest: contiguous storage, constant-time indexing, zero allocation overhead. Dynamic arrays add one allocation but keep contiguous O(1) access — resizing is the expensive operation because new[n](old) copies everything. Queues pay a small per-element overhead for O(1) growth at the ends but punish middle insertion. Associative arrays carry the largest per-entry cost (hash bookkeeping per key) and O(log n) or hashed access, but win outright when the index space is sparse — storing 100 entries of a 4 GB space costs ~100 entries, not 4 GB.

The comparison interviewers expect, in words

• Fixed array — size: compile-time constant; access: O(1); growth: none; memory: full footprint always allocated; use: RTL memories, lookup tables, synthesis.

• Dynamic array — size: set at runtime via new[n]; access: O(1); growth: O(n) copy on resize; memory: contiguous, exactly n elements; use: payloads and models sized from config/plusargs.

• Queue — size: grows per push; access: O(1) at ends, O(n) middle insert/delete; memory: small per-element overhead; use: FIFOs, scoreboards, monitor logs, anything streaming.

• Associative array — size: grows per written key; access: hashed/ordered lookup, slower than indexed; memory: per-entry overhead, but only touched keys; use: sparse memories, ID-keyed lookup, out-of-order scoreboards.

// All four families in one testbench, each doing its natural job
class dut_env_storage;
  logic [31:0] rom [0:255];       // fixed: known lookup table
  byte         payload[];         // dynamic: length from config
  packet       inflight_q[$];     // queue: in-order FIFO traffic
  packet       by_id [int];       // associative: out-of-order tags

  function void build(int payload_len);
    payload = new[payload_len];
  endfunction

  function void issue(packet p);
    inflight_q.push_back(p);      // in-order stream
    by_id[p.id] = p;              // random-access by tag
  endfunction
endclass

Common mis-uses and how to spot them

Reviewers can usually spot a wrong container from one symptom. A loop calling new[size+1](arr) every iteration means a dynamic array doing a queue's job — quadratic. An associative array indexed 0..N-1 densely means hash overhead for nothing — should be dynamic. A queue searched by ID with find_first on every response means O(n) lookups doing an associative array's job. And a giant fixed array of which 1% is touched means megabytes wasted that an associative array would avoid.

// SMELL: dynamic array growing one element at a time  → use a queue
data = new[data.size() + 1](data);   // O(n) copy EVERY append
data[data.size() - 1] = next_val;

// SMELL: queue searched by key on every response → use associative
hits = inflight_q.find_first(t) with (t.id == rsp.id);  // O(n) each time

// FIX:
packet by_id [int];
by_id[req.id] = req;            // O(1)-ish insert
if (by_id.exists(rsp.id)) ...   // O(1)-ish lookup, then delete(rsp.id)

Key takeaways

• Three questions pick the container: compile-time size? grow/shrink at runtime? dense or sparse index?

• Fixed is fastest and the only synthesizable family; associative is the only sane sparse model.

• Queues for streaming/FIFO patterns; dynamic arrays for size-once-then-index patterns.

• Know the per-family size/access/growth/memory comparison verbatim — it is a stock interview question.

Common pitfalls

• Appending to a dynamic array in a loop via new[](old) — quadratic; that workload is a queue.

• Dense 0..N-1 indexing into an associative array — pure hash overhead over a dynamic array.

• Linear find_first-by-ID over a queue per response — an associative array makes it constant time.

• Using any runtime-sized family in code destined for synthesis — only fixed arrays synthesize.