Associative Arrays

Sparse storage keyed by anything

An associative array — byte mem [longint] — is a hash map: storage is allocated only for indices you actually write , and the index can be any type with an ordering — integral types, string, classes, even the wildcard [*] (which you should avoid because it disallows ordered iteration). This is the only practical way to model a 64-bit address space: a fixed array of 2^64 bytes is impossible, a dynamic array of the used range wastes memory, but an associative array costs only as much as the touched locations.

Reading an index that was never written does not allocate it — it returns the default value for the element type (0 for 2-state, X for 4-state) and most simulators warn. That is why disciplined code always guards reads with exists(). Writes allocate. num() (or size()) reports how many entries exist, and delete(idx) removes one entry while delete() clears everything.

module sparse_mem_demo;
  byte mem [longint];   // 64-bit address space, sparse

  initial begin
    mem[64'h0000_0000_0000_1000] = 8'hA5;
    mem[64'hFFFF_FFFF_0000_0000] = 8'h3C;   // 16 EB apart, 2 entries

    $display("entries used = %0d", mem.num());   // 2

    if (mem.exists(64'h1000))
      $display("addr 0x1000 = %0h", mem[64'h1000]);

    if (!mem.exists(64'h2000))
      $display("addr 0x2000 never written - skip, don't read");

    mem.delete(64'h1000);   // remove one entry
    mem.delete();           // remove all entries
  end
endmodule

Iteration with first/next/prev

Because the index space is sparse you cannot iterate with a counting for-loop. The traversal methods first(), next(), last(), and prev() each take the index variable by reference , update it to the neighboring existing key in sorted index order, and return 1 on success or 0 when the traversal is exhausted — which makes them natural loop conditions. foreach also works on associative arrays and visits keys in the same sorted order; use the explicit methods when you need to start mid-range or walk backwards.

byte mem [longint];
longint addr;

initial begin
  mem[100] = 8'h11; mem[5] = 8'h22; mem[7000] = 8'h33;

  // Forward walk in ascending index order: 5, 100, 7000
  if (mem.first(addr))
    do
      $display("mem[%0d] = %0h", addr, mem[addr]);
    while (mem.next(addr));

  // foreach visits the same sorted key order
  foreach (mem[a])
    $display("foreach mem[%0d] = %0h", a, mem[a]);
end

ASSOCIATIVE ARRAY — SPARSE LAYOUT AND TRAVERSAL

  index space (64-bit, mostly empty)
  ┌──────────────────────────────────────────────────────┐
  │ ........ 5 ........ 100 .................. 7000 .... │
  └──────────┬───────────┬──────────────────────┬────────┘
             ▼           ▼                      ▼
        ┌─────────┐ ┌─────────┐           ┌─────────┐
        │ key:5   │ │ key:100 │           │ key:7000│   only 3
        │ val:22  │ │ val:11  │           │ val:33  │   entries
        └─────────┘ └─────────┘           └─────────┘   allocated
             ▲           ▲                      ▲
   first(a)──┘  next(a)──┘            next(a)──┘ next(a) returns 0
   (a=5)        (a=100)               (a=7000)   → loop ends

  exists(k) : 1 if entry allocated      num() : entry count
  read of missing key : default value + warning, NO allocation

ID-indexed scoreboards for out-of-order traffic

When a DUT can reorder responses (out-of-order AXI, tagged NoC packets, multi-threaded caches), a FIFO queue scoreboard breaks — order is no longer the contract. The fix is an associative array keyed by transaction ID : predictions are stored under their tag, and each response looks up, compares, and deletes its own entry. Leftover entries at end of test are dropped transactions. This queue-vs-associative scoreboard choice is a classic interview discriminator between junior and mid-level verification engineers.

class ooo_scoreboard;
  packet expected [int];     // keyed by transaction ID

  function void predict(packet p);
    if (expected.exists(p.id))
      $error("Duplicate outstanding ID %0d", p.id);
    expected[p.id] = p;
  endfunction

  function void check_response(packet p);
    if (!expected.exists(p.id)) begin
      $error("Response with unknown ID %0d", p.id);
      return;
    end
    if (!expected[p.id].compare(p))
      $error("Data mismatch on ID %0d", p.id);
    expected.delete(p.id);   // retire the entry
  endfunction

  function void check_drained();
    if (expected.num() != 0)
      $error("%0d IDs never got a response", expected.num());
  endfunction
endclass

Key takeaways

• Associative arrays allocate per written key — the only sane model for huge sparse address spaces.

• Guard reads with exists(); reading a missing key returns a default value and never allocates.

• first/next/prev take the key by ref and return 0 at the end — sorted-order traversal without dense indices.

• Out-of-order DUTs need ID-keyed associative scoreboards; in-order DUTs use queues.

Common pitfalls

• Reading mem[addr] without exists() — silently consumes the default value as if it were real data.

• Wildcard index [*] — convenient to declare, but bans foreach and ordered first/next traversal.

• Forgetting delete(id) after checking a response — the scoreboard leaks and the drain check false-fails.

• Assuming insertion order during iteration — traversal is sorted by index value, not arrival order.