Collection copies and cost

Assignment copies the elements

For fixed arrays, dynamic arrays, queues and associative arrays alike, b = a; copies every element of a into b. Afterwards the two collections are separate, so a change to one never shows in the other.

A copy is also a snapshot. Taking snapshot = pending_q; when reset starts keeps a record of what was outstanding, which stays intact while the original is cleared.

The copy takes time in proportion to the number of elements. Copying a 10,000-entry queue once is cheap, but copying it once per response adds up to as many as 100 million element copies over the test.

Arguments copy too, unless you pass by reference

A collection passed as an ordinary input argument is copied into the routine. The routine works on its own copy, so popping from it has no effect on the caller, and the copy costs the same as an assignment.

Declaring the argument ref passes the caller's collection itself, with no copy. Changes made inside the routine are then visible to the caller, which is exactly what a helper that drains or fills a queue needs. A ref argument requires an automatic routine.

When the routine should only read the collection, declare it const ref. You avoid the copy, and the compiler rejects any accidental change.

function automatic void drain(int q[$]);
  q.delete();          // empties the copy
endfunction

function automatic void drain(ref int q[$]);
  q.delete();          // empties the caller's queue
endfunction

Handles are the exception

Copying an array of int or of packed structs copies the values themselves. Copying a queue of class handles copies only the handles, so both queues then point at the same objects. Module 4 explains handles and how to copy the objects behind them.

Structs are values, so a queue of structs copies every field. That makes a queue of packed structs a safe way to keep a private snapshot of expected responses.

Removing items while you walk a queue

Deleting from a queue inside a loop that walks it forward skips elements. After q.delete(i), every later element moves down one place, so the element that was at i + 1 is now at i, and the loop steps past it.

Start with {2, 4, 6, 1} and delete the even values going forward. The 2 goes, the 4 slides into its place and is skipped, and the 6 goes, leaving {4, 1} instead of {1}. The same trap exists for every collection: never change its shape while a foreach loop is walking it.

Walk backward from the last index instead, or build the result in one step: q = q.find with (item % 2 != 0); leaves {1}.

Counting the work

Searching a pending queue from the front for each response costs up to n compares when n reads are pending. Over n responses that adds up to about n²/2 compares in the worst case.

In the opening story, the copy made things worse. Copying the queue before each search added up to n element copies per response, another quadratic term on top of the search.

The 2-minute run in the opening story made about half a million compares, and the 3-hour run made about 50 million.

An associative array keyed by ID turns each search into a single lookup. The standard does not fix how long a lookup takes, but simulators use tree or hash structures whose cost grows far more slowly than a scan.

Choosing a collection

Pick the collection from the operations you need, not from habit. Use a fixed array when the spec fixes the count, and a dynamic array when the length is known as the transaction starts. Use a queue when items arrive one by one and leave in order.

Use an associative array when you look items up by a key from a large or sparse space, such as IDs or addresses. Use an associative array of queues when items are looked up by key and must keep their order within each key.

Try it

The assignment and the input argument both worked on copies, so pending_q kept its first element and all 1,000 entries. Only the ref argument changed the caller's queue.

The search cost 500,500 compares, exactly 1000 × 1001 / 2, while the map needed one lookup per response. Change n to 2000 and predict both counts before you run it.

Check yourself

module tb;
  int a [$];
  int b [$];
  initial begin
    a = '{1, 2, 3};
    b = a;
    b.push_back(4);
    a[0] = 9;
    $display("%0d %0d %0d", a.size(), b.size(), b[0]);
  end
endmodule

function automatic void drain(ref int q[$]);
  q.delete();
endfunction

function automatic void drain(int q[$]);
  q.delete();
endfunction

function automatic void drain(inout int q[$]);
  q.delete();
endfunction

function automatic void drain(ref int q[$]);
  while (q.size() > 0) void'(q.pop_front());
endfunction

Practice

• Value snapshot Implement · Easy
• Aliased collection repair Fix · Medium