Fixed-size queue data structure

[mmagician]

There is currently no built-in mechanism to maintain a fixed-size queue (circular buffer) of most-recent elements in an account's storage.
It is needed for storing the last Global Exit Roots (GER) for AggLayer bridge as described here.

Approach A: Queue Account Component

Implement a fixed-size circular queue as an account component with a map slot to store the queue data and a value slot to store the queue metadata, as originally proposed by @mmagician in the issue body.

Storage Layout

• QUEUE_METADATA_SLOT: [head_index, capacity, 0, 0]
• QUEUE_DATA_SLOT: { [index, 0, 0, 0] => VALUE }

MASM Interface

# QUEUE COMPONENT
# =================================================================================================
# A fixed-size circular queue that stores the most recent N elements.
#
# Storage Layout:
#   METADATA_SLOT: [head_index, capacity, 0, 0]
#   DATA_SLOT (map): { [i, 0, 0, 0] => VALUE } for i in 0..capacity
#
# The queue maintains a circular buffer where:
#   - head_index: points to the oldest element (next to be overwritten)
#   - capacity: maximum number of elements the queue can hold
#
# To push: write at (head_index + 1) % capacity, increment head_index

# CONSTANTS
# =================================================================================================

# Storage slot names (to be customized per component)
const QUEUE_METADATA_SLOT = word("miden::queue::metadata")
const QUEUE_DATA_SLOT = word("miden::queue::data")

# PROCEDURES
# =================================================================================================

#! Pushes a new element to the back of the queue.
#! If the queue is full, the oldest element is overwritten.
#!
#! Inputs:  [VALUE]
#! Outputs: [OLD_VALUE]
#!
#! Where:
#! - VALUE is the value to push onto the queue.
#! - OLD_VALUE is the overwritten value (or EMPTY_WORD if queue wasn't full).
#!
#! Invocation: exec
pub proc queue_push
    # TODO: Implement
end

#! Checks if a value exists in the queue.
#!
#! Inputs:  [VALUE]
#! Outputs: [exists]
#!
#! Where:
#! - VALUE is the value to search for.
#! - exists is 1 if found, 0 otherwise.
#!
#! Note: This iterates through all elements, O(n) complexity.
#!
#! Invocation: exec
pub proc queue_contains
    # TODO: Implement
end

Approach B: Static Slot Names

For a queue that doesn't require runtime configuration, use statically-defined slot names. To map an index to the slot name, insert these slot names into memory, and then map the index to the slot name via a memory lookup. This is the approach proposed by @PhilippGackstatter here.

MASM Interface

# Static Queue with 4 slots
const QUEUE_METADATA = word("miden::example::queue::metadata")
const QUEUE_SLOT_0 = word("miden::example::queue::0")
const QUEUE_SLOT_1 = word("miden::example::queue::1")
const QUEUE_SLOT_2 = word("miden::example::queue::2")
const QUEUE_SLOT_3 = word("miden::example::queue::3")

const QUEUE_CAPACITY = 4
const SLOT_TABLE_PTR = 100  # Memory location for slot ID lookup table

#! Initializes the slot lookup table in memory.
#! Must be called once before using the queue.
proc init_slot_table
    # Store slot IDs at SLOT_TABLE_PTR + i*2 for each slot
    push.QUEUE_SLOT_0[0..2] push.SLOT_TABLE_PTR mem_storew
    push.QUEUE_SLOT_1[0..2] push.SLOT_TABLE_PTR add.2 mem_storew
    # ... etc for all slots
end

#! Gets the slot ID for a given queue index.
#! 
#! Inputs:  [index]
#! Outputs: [slot_prefix, slot_suffix]
proc get_slot_for_index
    # => [index]
    
    # Calculate memory address: SLOT_TABLE_PTR + index * 2
    mul.2 push.SLOT_TABLE_PTR add
    # => [addr]
    
    # Load slot ID (2 felts)
    mem_loadw drop drop
    # => [slot_prefix, slot_suffix]
end

pub proc queue_push
    # TODO: Implement
end

pub proc queue_contains
    # TODO: Implement
end

Trade-offs

Approach	Pros	Cons
Map-based	Flexible capacity, two data slots	Less efficient
Static slots	Direct access, efficient access	Lots of boilerplate code, many data slots

Supporting double-word values

Both approaches support double-word values rather easily (actually multi-word values if we want to):

Map-based

When reading, we can read the two consecutive slots.
When writing, we can write the two consecutive slots and increment the head index by 2.

Static slots

Analogous.

[bobbinth]

Thank you for writing this up! I'd probably go for something that is easier to implement even if it is less efficient (I think that's the map-based approach).

In the longer term, I think we can migrate queues to be based on multi-value slots - though, the interface would probably change a bit. For queues with capacity around 64, this should be quite a bit more efficient than the storage map-based approach even for single reads/writes (and even more efficient if multiple reads/writes would be needed).

[mmagician]

Actually, since we now store GERs in a map, we no longer need queues, so I'm going to close this issue (queues might still be useful for other applications but we don't need them for anything atm)

Double-word arrays are still needed for storing the MMR frontier, but we already have double-word arrays as of #2299.