A List<T> holds every item in one array, so a sequence of a hundred million items needs all of its memory at once. Many workloads touch only a small region at a time, such as a buffer being filled, a log being appended or a range being scanned, and could run in a fraction of that memory if the rest stayed on disk.

Sphere10 Framework's paged lists do that behind the ordinary list contract. This article covers MemoryPagedList<T>, which keeps a bounded number of pages in memory and swaps the others to temporary files, and StreamPagedList<T>, which maps a list of constant-size items directly onto a stream so that it can be reopened later.

1. A first look

MemoryPagedList<T> takes the capacity of one page in bytes, the total number of bytes that loaded pages may occupy, and the size of an item. The sample uses 4,096-byte pages and allows four of them in memory.

using var list = new MemoryPagedList<int>(pageSize: PageBytes, maxMemory: 4 * PageBytes, fixedItemSize: sizeof(int));
var saved = 0;
var loaded = 0;
list.PageSaved += (_, _) => saved++;
list.PageLoaded += (_, _) => loaded++;

list.AddRange(Enumerable.Range(0, ItemCount));

Adding 100,000 integers creates 98 pages, of which at most four are resident at any moment. When a fifth page is needed, the list picks a resident page to evict, saves it to its own temporary file if it has changed, and releases its items.

2. How a paged list is organised

A paged list implements IExtendedList<T>, the Framework's list contract with 64-bit counts and batch members such as AddRange, ReadRange and UpdateRange. Internally it divides its items into pages. Each operation finds the pages that cover the requested range, opens them and reads or writes through them. Code that uses the list sees only indexes.

Both lists in this article grow and shrink at the end only. Add, AddRange and a RemoveRange that reaches the last item are supported, as are reads and updates anywhere. Inserting into the middle or removing from the middle throws NotSupportedException.

3. Bound memory with MemoryPagedList

stateDiagram-v2
    direction TB
    [*] --> Unloaded: page created
    Unloaded --> Loading: index accessed
    Loading --> Loaded: items in memory
    Loaded --> Unloading: evicted or Flush
    Unloading --> Unloaded: items released
    Loaded --> Deleting: removed from end
    Deleting --> Deleted
    Deleted --> [*]

var middle = list.ReadRange(50000, 3).ToArray();
Require(middle.SequenceEqual(new[] { 50000, 50001, 50002 }), "Swapped page returned different items.");
list.Update(10, -1);
list.Flush();
Require(list.CurrentOpenPages == 0, "Flush left pages resident.");
Require(list.Read(10) == -1, "Update was lost when its page was swapped out.");

The members that expose the paging are few.

• Pages lists every page, loaded or not, and CurrentOpenPages counts the resident ones.
• Flush() saves every changed page and unloads all of them.
• PageLoading, PageLoaded, PageSaving, PageSaved, PageUnloading and PageUnloaded report each step, which is useful for diagnostics and tests.
• EnterOpenPageScope(page) pins one page in memory until the returned scope is disposed.

For items of varying size, a second constructor takes a Func<TItem, long> that returns the size of each item, and a page then closes when its byte capacity is reached. The swap files are temporary. They are deleted when the list is disposed, so a MemoryPagedList<T> cannot be reopened in a later run.

4. Persist constant-size items with StreamPagedList

---
config:
  packet:
    bitsPerRow: 16
    bitWidth: 22
    showBits: false
---
packet-beta
0-15: "List header, 256 bytes"
16-19: "Item 0"
20-23: "Item 1"
24-27: "Item 2"
28-31: "Item 3 ..."

using (var file = File.Open(path, FileMode.CreateNew, FileAccess.ReadWrite)) {
	var list = new StreamPagedList<int>(PrimitiveSerializer<int>.Instance, file);
	list.AddRange(Enumerable.Range(0, ItemCount));
	list.Update(10, -1);
	list.RemoveRange(ItemCount - 10, 10);
}

Removing from the end truncates the stream. To reopen the file, construct the list over it again with autoLoad: true, or call Load() when RequiresLoad is true.

using (var file = File.Open(path, FileMode.Open, FileAccess.ReadWrite)) {
	var reopened = new StreamPagedList<int>(PrimitiveSerializer<int>.Instance, file, autoLoad: true);
	Require(reopened.Count == ItemCount - 10, "Reopened count differs.");
	Require(reopened.Read(10) == -1 && reopened.Read(reopened.Count - 1) == ItemCount - 11, "Reopened items differ.");
	Require(file.Length == StreamPagedList<int>.ListHeaderSize + reopened.Count * sizeof(int), "File length differs from header plus items.");
}

The serializer, the byte order and the includeListHeader setting are not recorded in a way that lets the list adapt, so pass the same values when reopening. Setting includeListHeader: false omits the header, which suits a list that lives inside another container's stream.

5. Choose between them

The stream-mapped collections are a different family, built on clustered streams, and support items of any size with insertion and removal at any position.

6. Get the package and run the sample

The paged lists ship in the core Sphere10.Framework package. The sample targets .NET 10.

dotnet new console --framework net10.0 --name ArticleSample
cd ArticleSample
dotnet add package Sphere10.Framework --version 3.1.3

The complete MIT-licensed sample contains the program shown above. Extract the download over the generated project and run it against a new directory.

dotnet run -c Release -- ./fresh-data

Memory-paged: 100000 items in 98 pages, 4 resident
Pages saved: True; pages reloaded: True; resident after flush and one read: 1
Stream-paged: 99990 items reopened from a 400216-byte file

The Collections guide lists every paged, file-mapped and stream-mapped type.

The Sphere10 Framework overview describes the rest of the toolkit.

Author: Herman Schoenfeld