readme.md

MemoryBuffer

A buffer that stores its elements in stable memory.

Design

The MemoryBuffer is built using two MemoryRegions. A blob region for storing the serialized values and a pointer region for storing the memory address and the size of the serialized values. The pointer region acts as a index to value map, connecting the index of the value to the memory address where it is located. Each entry has an overhead of 12 bytes. The memory address takes up 8 bytes, while the stored size takes up 4 bytes.

When the MemoryBuffer is filled, it doesn't need to be resized and have all its elements shifted to a new MemoryRegion. Instead it allocated more bytes in its current MemoryRegion and adds the new elements to the end of the MemoryRegion.

Usage Example

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

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

    let mbuffer = MemoryBuffer.MemoryBuffer<Nat>(sstore, TypeUtils.Nat);

    mbuffer.add(1);
    mbuffer.add(3);
    mbuffer.insert(1, 2);
    assert mbuffer.toArray() == [1, 2, 3];

    for (i in Iter.range(0, mbuffer.size() - 1)) {
        let n = mbuffer.get(i);
        mbuffer.put(i, n ** 2);
    };

    assert mbuffer.toArray() == [1, 4, 9];
    assert mbuffer.remove(1) == ?4;
    assert mbuffer.removeLast() == ?9;

Create Custom TypeUtils

To store more complex data types, you can create your own utilities to serialize and deserialize your data. The MemoryBuffer only requires that the data type implements the Blobify interface. This interface has two functions:

  public type Blobify<T> = {
    to_blob: (T) -> Blob;
    from_blob: (Blob) -> T;
  }

Here is an example for a custom User data type:

  type User = {
    id: Nat;
    name: Text;
  }

• Using candid

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

  let blobify_user : TypeUtils.Blobify<User> = {
    to_blob = func(user: User) : Blob = to_candid(user);
    from_blob = func(blob: Blob) : User {
      let ?user : ?User = from_candid(blob) else Debug.trap("Blobify error: Failed to decode User");
      return user;
    }
  };

  // we create a super type of TypeUtils that contains
  // only the utilities we need
  let user_type_utils = { blobify = blobify_user };

  stable var sstore = MemoryBuffer.newStableStore<User>();
  sstore := MemoryBuffer.upgrade(sstore);

  let mbuffer = MemoryBuffer.MemoryBuffer<User>(sstore, user_type_utils);

• custom serialization

If we want to avoid the extra bytes required in candid for storing the type information we can decide to implement our own serialization function. We will choose a simple serialization format where we serialize both fields to their Blob representation. Retrieve the size of resulting blobs and serialize them as well. We'll assume that the blob sizes of both fields are less that a 256 and concatenat them as a single byte to the resulting blob. Then we concatenate the size blobs with the blobs of the fields. And finally we concatenate the resulting blobs.

  import MemoryBuffer "mo:memory-collection/MemoryBuffer";
  import TypeUtils "mo:memory-collection/TypeUtils";
  import Blobify "mo:memory-collection/TypeUtils/Blobify";

  let blobify_user : TypeUtils.Blobify<User> = {
    to_blob = func(user: User) : Blob {
      let id_blob = Blobify.Nat.to_blob(user.id)
      let id_size = Blob.fromArray([Nat8.fromNat(id_blob.size())]);

      let name_blob = Blobify.Text.to_blob(user.name);
      let name_size = Blob.fromArray([Nat8.fromNat(name_blob.size())]);

      return TypeUtils.concat_blobs(
        [id_size, id_blob, name_size, name_blob]
      );
    };
    from_blob = func(blob: Blob) : User {
      let bytes = Blob.toArray(blob);
      let id_size = Nat8.toNat(bytes[0]);

      let id_bytes = Array.slice(bytes, 1, 1 + id_size);
      let id_blob = Blob.fromArray(id_bytes);
      let id = Blobify.Nat.from_blob(id_blob);

      let name_size = Nat8.toNat(bytes[1 + id_size]);
      let name_bytes = Array.slice(bytes, 2 + id_size, 2 + id_size + name_size);
      let name_blob = Blob.fromArray(name_bytes);
      let name = Blobify.Text.from_blob(name_blob);

      return { id; name; };
    };
  };

  let user_type_utils = { blobify = blobify_user };

  stable var sstore = MemoryBuffer.newStableStore<User>();
  sstore := MemoryBuffer.upgrade(sstore);

  let mbuffer = MemoryBuffer.MemoryBuffer<User>(sstore, user_type_utils);

Memory Layout

Pointer Region

• Header

Field	Offset	Size	Type	Default Value	Description
MAGIC	0	3	Blob	"BTR"	Magic number
LAYOUT VERSION	3	1	Nat8	0	Layout version
Blob Region Id	4	4	Nat32	-	Id of the Blob Region
COUNT	8	4	Nat32	-	Number of elements in the buffer
RESERVED	12	52	Nat32	-	Reserved for future use

• Pointers

A series of 12 byte entries that point to the memory blocks of the elements in the Blob Region. These pointers are stored contiguously in the pointer region immedialy after the header with an offset of 64 bytes.

Field	Offset	Size	Type	Default Value	Description
Address	0	8	Nat64	-	Address of the memory block
Size	8	4	Nat32	-	Size of the memory block

Blob Region

• Header

Field	Offset	Size	Type	Default Value	Description
MAGIC	0	3	Blob	"BLB"	Magic number
LAYOUT VERSION	3	1	Nat8	0	Layout version
POINTER REGION ID	4	4	Nat32	-	Id of the Pointer Region
RESERVED	8	56	Nat32	-	Reserved for future use

• Memory Blocks Data

A series of randomly sized elements stored as blobs at the address and size specified by the pointers in the Pointer Region. These blobs are stored immediately after the header with an offset of 64 bytes.

Benchmarks

Buffer vs MemoryBuffer

Benchmarking the performance with 10k Nat entries

• put() (new == prev) - updating elements in the buffer where number of bytes of the new element is equal to the number of bytes of the previous element
• put() (new > prev) - updating elements in the buffer where number of bytes of the new element is greater than the number of bytes of the previous element
• sortUnstable() - sorting elements in their serialized form. Requires that the elements can be orderable in their serialized form.

Instructions

Benchmarking the performance with 10k Nat entries

	Buffer	MemoryBuffer (with Blobify)	MemoryBuffer (encode to candid)
add()	4_691_772	55_509_319	38_539_297
get()	2_502_553	31_863_052	29_825_339
put() (new == prev)	3_893_443	63_154_140	35_279_406
put() (new > prev)	4_557_041	413_035_339	207_344_314
put() (new < prev)	4_235_072	161_521_983	158_895_293
add() reallocation	8_868_309	434_357_563	162_142_959
removeLast()	4_688_550	126_960_035	74_724_171
reverse()	3_120_910	13_794_169	13_788_413
remove()	3_682_590_903	383_682_557	380_509_119
insert()	3_264_760_420	642_877_048	357_788_879
shuffle()	-----	219_269_838	219_265_425
sortUnstable()	-----	988_375_542	------

Heap

	Buffer	MemoryBuffer (with Blobify)	MemoryBuffer (encode to candid)
add()	8_960	1_204_548	609_692
get()	8_960	993_528	369_032
put() (new == prev)	8_960	1_367_672	646_308
put() (new > prev)	8_964	11_260_020	2_728_356
put() (new < prev)	8_964	2_332_688	1_772_776
add() reallocation	158_984	-23_327_632	3_142_896
removeLast()	8_960	1_960_312	719_052
reverse()	8_904	248_960	248_960
remove()	99_136	3_502_272	3_017_012
insert()	154_852	-11_315_348	10_800_952
shuffle()	-----	7_887_376	7_887_376
sortUnstable()	-----	14_785_428	-----

Generate benchmarks by running mops bench in the project directory.

Notes and Observations

• This should come as a surprise but the MemoryBuffer requires significantly more instructions than the Buffer for most operations when performing the same operations. The reason is the Buffer does not need to serialize and deserialize its elements and most importantly, it does not need to access stable memory which is slower than heap memory.
• remove() and insert() perform better in the MemoryBuffer than the Buffer because the MemoryBuffer does not need to shift elements, it just shifts the fixed sized pointers in the pointer region.
• Encoding to candid is more efficient than using a custom encoding in most cases because to_candid() and from_candid() are system functions provided with motoko and are more efficient than most functions that can be implemented in motoko after the fact. However, candid encoding includes extra bytes for the type information which can add up to a significant amount. So, it is important to consider the trade-offs when choosing between candid and custom encoding.
• Finally, candid encoding cannot be compared in its blob form because they are not in an orderable form. This is why the sortUnstable() #BlobCmp benchmark is not available for candid encoding.