Skip to content

readme.md

Latest commit

 

History

History
89 lines (64 loc) · 3.09 KB

readme.md

File metadata and controls

89 lines (64 loc) · 3.09 KB

MemoryQueue

A persistent First In First Out queue.

Design

The Memory Queue is designed to be scalable, simple and efficient. It's implemented as a single linked list with a count variable and two extra pointers to store the addresses for the head and tail. New elements are added at the tail and old elements are removed from the head. This design allows for O(1) time complexity in the worst case for all operations. New elements are immediately serialized and added to stable memory, ensuring that the queue is persistent across canister upgrades. Removed elements have their memory blocks marked as deallocated and are reused when new elements are added.

Each node in the linked list stores a value, the size of that value and the next node's pointer. The size requires 4 bytes and the pointer requires 8 bytes, resulting in 12 bytes memory overhead for each element.

Memory Layout

The Memory Queue uses a single region to store all its data. The region has a header, followed by the nodes data in the queue.

64 bytes is reserved for the header.

  • Header Section
Field Offset Size (In bytes) Type Description
MAGIC 0 3 Blob Magic number
LAYOUT VERSION 3 1 Nat8 Layout version
COUNT 4 8 Nat64 Number of elements in the queue
HEAD 12 8 Nat64 First node in the linked list
TAIL 20 8 Nat64 Last node in the linked list
RESERVED 28 47 - Extra space for future use
  • Node Section

After the reserved header space, a sequence of nodes with the data of the queue is stored. This is the memory layout of each node:

Field Offset Size (In bytes) Type Description
NEXT 0 8 Nat64 Pointer to the next node
SIZE 8 4 Nat32 Size of the value
VALUE 12 |SIZE| Blob The serialized value

Usage Example

    import MemoryQueue "mo:memory-collection/MemoryQueue";
    import TypeUtils "mo:memory-collection/TypeUtils";

    stable var sstore = MemoryQueue.newStableStore<Nat>();
    sstore := MemoryQueue.upgrade(sstore);

    let queue = MemoryQueue.new<Nat>(sstore, TypeUtils.Nat);

    for (i in Iter.range(1, 10)) {
        queue.add(i);
    };

    assert queue.size() == 10;

    var i = 1;
    while (queue.size() > 0) {
        let ?n = queue.pop();
        assert n == i;
        i += 1;
    };

Benchmarks

Benchmarking the performance with 10k calls

Instructions

MemoryQueue
add() 54_112_857
vals() 37_068_706
pop() 74_438_819

Heap

MemoryQueue
add() 762_280
vals() 1_608_792
pop() 2_168_580