Vector data structure for Motoko

December 26, 2025 · View on GitHub

mops documentation

Vector data structure for Motoko

Important notice: Vector has been integrated into the core package under the name List. This package will not be updated anymore. The use of List is encouraged over Vector for the following reasons:

  • List has a more modern API design. Lists are static records that can be declared stable and support dot notation without being classes.
  • List is a more comprehensive package. It has more convenience functions than Vector.
  • List has been optimized for instructions to a higher degree than Vector.

Overview

The Vector data structure is meant to be a replacement for Array when a growable and/or shrinkable data structure is needed. It provides random access like Array and Buffer and can grow and shrink at the end like Buffer can. Unlike Buffer, the memory overhead for allocated but no yet used space is O(n)O(\sqrt{n}) instead of O(n)O(n).

The package is published on MOPS and GitHub. Please refer to the README on GitHub where it renders properly with formulas and tables.

The API documentation can be found here on Mops.

For updates, help, questions, feedback and other requests related to this package join us on:

Characteristics

The data structure is based on the paper Resizable Arrays in Optimal Time and Space by Brodnik, Carlsson, Demaine, Munro and Sedgewick (1999) which has the following characteristics:

  • based on a 2-dimensional array
  • persistent memory overhead: O(n)O(\sqrt{n})
  • worst-case instruction overhead: O(n)O(\sqrt{n})
  • no re-allocation or copying of data blocks

The implementation is furthermore cycle optimized.

Motivation

When developing smart contract canisters, to be sure that the canister does not ever run into cycle limits, one has to reason about the code's worst-case complexity. This is even more important as publicly accessible smart contract canisters don't control their input and operate in a potentially adversarial environment. Understanding worst-case behavior is often critical.

The go-to data structure for a resizable array is Buffer from motoko-base. Buffer is a fixed-size array with some reserve capacity that is "grown" when it fills up. Growing means that the old array is copied into a newly allocated larger array and the old array becomes garbage. The growing factor is 1.5x. Therefore, Buffer has linear persistent memory overhead (1.5x) and linear worst-case behavior (copying the entire array in the growth event).

The present data structure improves both metrics from linear to O(n)O(\sqrt{n}) in exchange for less performant random access. Since the underlying data structure is a 2-dimensional array, put and get operation become approximately twice as expensive. However, the implementation is highly optimized so that in practice it is less than 2x in practice. Several convenience functions operate even faster for Vector than they do for Buffer. For details see the Benchmarking section below.

Interface

Vector is a static type and can therefore be declared stable. This is unlike Buffer which is a class and can not be directly declared stable.

Vector provides 40+ convenience functions that are modeled and named after the convenience functions of Buffer. This is done to make it as easy as possible to replace Buffer with Vector.

If a stable declaration is not required then the package also provides a class version of Vector. This can be used as a drop-in replacement for Buffer as it provides exactly the same interface. As with Buffer, the user can benefit from the convenient dot-notation for the class methods.

Usage

Install with mops

You need mops installed. In your project directory run:

mops add vector

In the Motoko source file import the package as one of:

import Vec "mo:vector";
import Vec "mo:vector/Class";

for the static version or the class version, respectively.

Example

import Vector "mo:vector";

let v = Vector.new<Nat>();
Vector.add(v, 1);
Vector.add(v, 2);
Vector.add(v, 3);
assert(Vector.get(v, 0) == 1);
assert(Vector.get(v, 1) == 2);
assert(Vector.get(v, 2) == 3);
Vector.size(v);

Executable version of above example

import Vector "mo:vector/Class";

let v = Vector.Vector<Nat>();
v.add(1);
v.add(2);
v.add(3);
assert(v.get(0) == 1);
assert(v.get(1) == 2);
assert(v.get(2) == 3);
v.size();

Executable version of above example

Build & test

For tests run:

git clone git@github.com:research-ag/vector.git
mops install
mops test

Benchmarks

We extensively benchmarked Vector against Buffer and the Motoko-native Array, where applicable. Each line in the follwing tables below is one benchmark and corresponds to the given function name.

The benchmarking code can be found here: canister-profiling

The benchmarks were run with dfx 0.20.1 and moc 0.11.2.

Time

This table shows the number of wasm instruction for the given function execution.

For some functions the number of instructions is expected to be independent of the size of the vector, e.g. init, get, getOpt, put, size, clear, isEmpty. However, even in those case we run the function N times and take the average because there may be marginal differences in cost based on the concrete integer value of the index being used.

For some functions the function is run only once for a vector of size N because a single call iterates through the whole vector, e.g. addMany, clone, indexOf, firstIndexWith, lastIndexOf, lastIndexWith, forAll, forSome, forNone, iterate, iterateRev, vals, valsRev, items, itemsRev, keys, iterateItems, iterateItemsRev, addFromIter, toArray, fromArray, toVarArray, fromVarArray, contains, max, min, equal, compare, toText, foldLeft, foldRight, reverse, reversed.

The functions add and removeLast have sporadic worst-case behavior when the data structure has to grow. They are therefore run N times and the result is averaged to obtain an amortized cost per call.

N = 100,000
value data type: Nat
methodvectorvector classbufferarray
init15151414
addMany1717--
clone188188298-
add336378552-
get20524713672
getOpt261303149-
put26630915282
size18322410169
removeLast315356395-
indexOf18218217256
firstIndexWith163163--
lastIndexOf222222179-
lastIndexWith203203--
forAll175175157-
forSome163163162-
forNone163163162-
iterate106106140-
iterateRev133133--
vals15615612720
valsRev163163--
items266266--
itemsRev293293--
keys105105--
iterateItems142142--
iterateItemsRev177177--
addFromIter406406354-
toArray158158117-
fromArray163163190-
toVarArray226226170114
fromVarArray16316319064
clear139180329-
contains18218216356
max17417419157
min17417419757
equal356356243133
compare397397284133
toText4554553980
foldLeft16316317669
foldRight190190192135
reverse426426243145
reversed412412243145
isEmpty11615612088

Note:

  • add is the function that can grow the data structure. It performs better in amortized terms than for Buffer because the growth events are cheaper. Vector only allocates new data blocks, it does not re-allocate and copy old data blocks.
  • get, put and getOpt are the random access functions. Vector is a 2-dimensional array where (only) the second dimension has option-values, Buffer is a 1-dimensional array with option-values and Array is a 1-dimensional array with non-option-values. Hence, the expected access time for Vector is expected to be roughly the sum of access times for Buffer and Array. This is correctly reflected in the numbers.
  • All functions that iterate through the data structure are optimized in a way that they don't use random access. This is the reason that they are generally only slighly (0-35%) more costly than Buffer. In some case the function can be cheaper than for Buffer (iterate, max, min).

Memory

This table shows the heap allocation (persistent and garbage) for the given function execution. The results are for a data structure of size N.

The memory size is generally shown in bytes for a single function execution.

In some cases, the value depends on the size N of the Vector, e.g. init, addMany, clone, etc.

In cases when there is an amortized cost such as add, removeLast then the function is executed N times so that one can get an idea of the average.

N = 100,000
value data type: Nat
methodvectorvector classbufferarray
init408688409076400504400008
addMany408640408640--
clone425032425420553568-
add4160604160601659216-
get0000
getOpt000-
put0000
size0000
removeLast74047404553112-
indexOf282800
firstIndexWith88--
lastIndexOf20200-
lastIndexWith00--
forAll242448-
forSome8848-
forNone8848-
iterate8848-
iterateRev00--
vals172172480
valsRev6868--
items16001041600104--
itemsRev16000801600080--
keys4444--
iterateItems88--
iterateItemsRev00--
addFromIter4160604160601200008-
toArray400180400180400024-
fromArray408716409104600504-
toVarArray400180400180400008400008
fromVarArray408716409104600504400024
clear202040-
contains2828480
max3636480
min3636480
equal34434400
compare34434400
toText320016432001643199992296
foldLeft3636480
foldRight282800
reverse000400028
reversed4161444165320400028
isEmpty0000

Note:

  • init and addMany create a data structure of size N. Here we see the persistent N\sqrt{N} memory overhead for Vector relative to Array.
  • add shows the garbage creation of Buffer due to copying of the entire data block during growth events. Vector copies only its index block which is in the order of N\sqrt{N}.
  • removeLast shows the same effects as add but for shrink events.
  • items produces a large amount of garbage because the iterator produces tupels (unlike vals which produces single Nat values in this example). If that is a problem than the iterateItems function may provide a better alternative for the use case.

Design

The data structure is based on the paper Resizable Arrays in Optimal Time and Space by Brodnik, Carlsson, Demaine, Munro and Sedgewick (1999).

The vector elements are stored in so-called data blocks and the whole data structure consists of a sequence of data blocks of increasing size. Hence it is in fact a two-dimensional array (but not a "square" one).

The trick lies in the selection of the sizes of the data blocks. They are chosen such that the conversion of the externally used single index to the internally used index pair can be cheaply done by bit shifts.

The data block sizes can be better understood when thinking of the data blocks being arranged in "super blocks". Super blocks are merely a virtual concept and have no manifestation in the implementation. The capacity of a super block is always a $2−power.The-power. The i-th super block has capacity \2^i and consists of \2^{\lfloor i / 2\rfloor} data blocks of size \2^{\lceil i / 2 \rceil}. This is followed by the next super block of capacity \2^{i+1}$ and so on.

Hence, the sequence of data block sizes look like this:

\1,\ \ 2,\ \ 2,2,\ \ 4,4,\ \ 4,4,4,4,\ \ 8,8,8,8,\ \ ...$$

where the additional white space indicates super block boundaries.

Implementation notes

Each data block is a mutable array of type [var ?X] where X is the element type. The data blocks themselves are stored in the mutable array called data_blocks. Hence data_blocks has type [var [var ?X]].

The present implementation differs from the article in that the data block indices are shifted by $2 and we introduce two data blocks of size \0 and \1atthebeginningofthesequence.Thismakestheaccessfasterbecauseiteliminatesthefrequentcomputationofat the beginning of the sequence. This makes the access faster because it eliminates the frequent computation ofi+2$ in the internal formulas needed for index conversion.

Besides the data_blocks array, the Vector type constains the index pair i_block, i_element which means the next position that should be written by an add operation: data_blocks[i_block][i_element]. We do not store any more information to reduce memory. But we also do not store less any information (such as only the total size in a single variable) as to not slow down access.

When growing we resize data_blocks (the outer array) so that it can store exactly one next super block. But unused data blocks in the last super block are not allocated, i.e. set to the empty array.

When shrinking we keep space in data_blocks for two additional super blocks. But unused data blocks in the last two super blocks are deallocated, i.e. set to the empty array.

MR Research AG, 2023-2024

Authors

Andrii Stepanov with contributions from Timo Hanke, Andy Gura and react0r-com.

License

Apache-2.0