Collections Overview

24 min read

Predictable-allocation collection types that fill the BCL gaps when your game code needs priority queues, ring buffers, tries, disjoint sets, and thread-safe containers without surprise GC churn.

Summary

The Scylla collection types under Scylla.Core.Structures are predictable-allocation, builder-constructed, optionally synchronized data structures with optional Burst-compatible DOTS variants. Reach for them when System.Collections.Generic is not enough: when allocation patterns matter (game loops, hot paths, deterministic frame budgets), when thread-safety is a runtime concern (a worker pool feeding a main-thread consumer), when DOTS/Burst compatibility is required (a Burst job operating on a queue or a map), or when a specialized structure (bit array, disjoint set, trie) is the right shape for the problem. Every collection in the namespace shares a common interface, a common builder pattern, and a consistent thread-safety model.

The common shape comes from two interfaces. IScyllaCollection is the non-generic base: Count, IsEmpty, Capabilities, ThreadSafety, SyncRoot, Clear(). IScyllaCollection<T> extends that with TryAdd(T), TryRemove(out T), TryPeek(out T), and CopyTo(Span<T>). The ScyllaCollectionCapabilities flags enum reports what optional operations the concrete instance supports (HasCapacity, SupportsPeek, SupportsContains, SupportsCopyTo, SupportsKeyLookup, SupportsRandomAccess); use the flags for feature detection in place of type-casting. The ScyllaCollectionThreadSafety enum (Unsynchronized, Synchronized, LockFree) tells you whether to hold an external lock when accessing the collection concurrently.

Every collection has a fluent builder via the static CreateBuilder() method. The common builder steps are .WithCapacity(n) (initial size), .FixedCapacity() (never grow, so TryAdd returns false when full), .Synchronized() (wrap the result in a thread-safe shell that locks on a shared SyncRoot), and .Build() (finalize). The synchronized wrapper is exposed as a public nested class (ScyllaQueue<T>.SynchronizedScyllaQueue, etc.) with the same API surface; you can also call AsSynchronized() on a built instance to wrap it after the fact. The synchronized variant is the right shape for cross-thread use; the unsynchronized variant is the right shape for single-thread hot paths where every operation pays no lock cost.

The DOTS variants (suffixed with DOTS: ScyllaQueueDOTS<T>, ScyllaMapDOTS<TKey, TValue>, etc.) are Burst-compatible blittable structs that use NativeArray<T>-style memory and Unity’s allocator convention (Temp, TempJob, Persistent). They are disposable and must be explicitly released. The DOTS variants are not interchangeable with the managed variants; the APIs differ (TryEnqueue instead of TryAdd, no boxing for value types, no LINQ extensions). Use the DOTS variant inside a Burst-compiled job; use the managed variant everywhere else.

Use the Scylla collection types for:

  • Predictable memory behaviour in a hot path (FixedCapacity() plus pre-sizing to the max expected size produces zero growth allocations).
  • Cross-thread access via the synchronized wrapper without externally managing locks (.Synchronized() on the builder, or .AsSynchronized() after construction).
  • Burst-compiled job code that needs a queue, map, or other typed container (the DOTS variants).
  • Specialized algorithms that the standard library does not cover: bit-set operations (ScyllaBitArray), Union-Find / connected components (ScyllaDisjointSet), prefix-keyed lookup or autocomplete (ScyllaTrie).
  • Type-keyed registries where each type maps to a small collection of instances (ScyllaTypeMap).
  • Unity-serializable dictionaries that round-trip through Unity’s serializer (SerializableDictionary).
  • Capability-detection patterns where code branches on which optional operations the collection supports (ScyllaCollectionCapabilities flags).

Features

  • Twelve collection types. ScyllaQueue<T>, ScyllaDeque<T>, ScyllaStack<T>, ScyllaPriorityQueue<T>, ScyllaMap<TKey,TValue>, ScyllaTypeMap, ScyllaRingBuffer<T>, ScyllaBitArray, ScyllaDisjointSet, ScyllaTrie, ScyllaTrie<TValue>, SerializableDictionary<TKey,TValue>. Each solves a specific shape the standard library does not.
  • Uniform IScyllaCollection interface. Non-generic base (Count, IsEmpty, Capabilities, ThreadSafety, SyncRoot, Clear) plus typed extension IScyllaCollection<T> (TryAdd, TryRemove, TryPeek, CopyTo). Code typed against the interface swaps concrete types in one line.
  • Capability flags for feature detection. ScyllaCollectionCapabilities (HasCapacity, SupportsPeek, SupportsContains, SupportsCopyTo, SupportsKeyLookup, SupportsRandomAccess) lets callers branch on optional operations at runtime instead of type-casting.
  • Fluent builder on every collection. .CreateBuilder() plus .WithCapacity(n), .FixedCapacity(), .Synchronized(), and type-specific steps (.WithComparer(...) on ScyllaMap). .Build() returns the configured instance.
  • Fixed-capacity mode for predictable allocation. .FixedCapacity() makes the collection refuse new items once full (TryAdd returns false) instead of growing. The right primitive for hot paths and frame-budget code that requires zero growth allocations.
  • Synchronized wrappers per type. Every collection exposes a nested Synchronized* class with the same surface. Obtain via .Synchronized() on the builder or AsSynchronized(syncRoot) after construction. Locks every operation on a shared SyncRoot.
  • Three thread-safety modes. ScyllaCollectionThreadSafety enum (Unsynchronized, Synchronized, LockFree) reports the per-instance guarantee so calling code knows whether external locking is required.
  • Try* no-throw contract. TryAdd, TryRemove, TryPeek, TryGetValue return bool and never throw on capacity or missing-key failures. Calling code branches on the return value; exceptions are reserved for programming errors (null buffer, disposed instance).
  • Burst-compatible DOTS variants. *DOTS blittable structs for nine of the twelve types (ScyllaQueueDOTS, ScyllaMapDOTS, …) use NativeArray<T>-style memory and Unity’s allocator convention. Use inside Burst-compiled jobs; the managed variant everywhere else.
  • Specialized algorithms. ScyllaBitArray for bit-set operations and popcount; ScyllaDisjointSet for Union-Find / connected components with path compression and union-by-rank; ScyllaTrie for prefix-keyed lookup and autocomplete.
  • Type-keyed registry. ScyllaTypeMap maps each Type to a sub-bucket of typed instances keyed by uint id. TryAdd<T>(id, value), TryGet<T>(id, out value), ClearType<T>(). The right primitive for module-style registries.
  • Unity-serializable dictionary. SerializableDictionary<TKey, TValue> round-trips through Unity’s JsonUtility and Inspectors. Same surface as System.Collections.Generic.Dictionary plus serialization support.

The collection catalogue

Twelve collection types ship in Scylla.Core.Structures. Each one solves a specific problem; pick the type that matches the actual access pattern rather than reaching for the most familiar shape.

A few terms appear repeatedly. FIFO (first-in, first-out) is the queue order: oldest item out first. LIFO (last-in, first-out) is the stack order: newest item out first. Open addressing is the dictionary implementation strategy ScyllaMap uses: collisions are resolved by linear probing through the same backing array, not by chaining into separate buckets. Path compression and union-by-rank are the two optimizations ScyllaDisjointSet applies to Union-Find, producing amortized near-constant-time Find and Union.

TypePurposeKey access patternDOTS variant
ScyllaQueue<T>FIFO queue, array-backed with a circular bufferTryAdd (enqueue), TryRemove (dequeue front), TryPeek (peek front). Optional TryEnqueue / TryDequeue aliases. O(1) amortized.ScyllaQueueDOTS<T>
ScyllaDeque<T>Double-ended queue, push and pop at both endsTryPushBack, TryPushFront, TryPopBack, TryPopFront, plus the shared TryAdd / TryRemove. O(1) at both ends.ScyllaDequeDOTS<T>
ScyllaStack<T>LIFO stack, array-backedTryAdd (push), TryRemove (pop), TryPeek (top). O(1) push / pop.ScyllaStackDOTS<T>
ScyllaPriorityQueue<T>Binary-heap priority queue, ordered by an IComparer<T> (or via IScyllaPriorityQueueItem)TryEnqueue (insert), TryDequeue (remove min), TryPeek (look at min). O(log n) insert / remove, O(1) peek.ScyllaPriorityQueueDOTS<T>
ScyllaMap<TKey, TValue>Open-addressing hash map with linear probing; no boxing for value typesTryAdd, TryRemove, TryGetValue, TrySet, ContainsKey, EnsureCapacity. O(1) amortized.ScyllaMapDOTS<TKey, TValue>
ScyllaTypeMapType-keyed dictionary: each Type maps to a sub-bucket of typed instances keyed by uint idTryAdd<T>(id, value), TryGet<T>(id, out value), TrySet, TryRemove<T>(id, out), ClearType<T>(), ContainsType<T>, CountOf<T>.none
ScyllaRingBuffer<T>Fixed-capacity circular buffer; optional overwrite-on-full modeTryAdd (with overwrite), TryRemove (oldest), TryPeek. Optional random access via [index].ScyllaRingBufferDOTS<T>
ScyllaBitArrayFixed-size bit array backed by ulong[]; popcount, set / get / toggle, bitwise opsSet(index), Unset(index), Get(index), Toggle(index), SetAll, Clear, PopCount, And, Or, Xor, Not. O(1) per bit; O(n / 64) for bulk ops.ScyllaBitArrayDOTS
ScyllaDisjointSetUnion-Find with path compression and union-by-rankFind(x), Union(x, y), Connected(x, y), ComponentCount. Amortized near-constant-time on both operations.ScyllaDisjointSetDOTS
ScyllaTriePrefix tree (set) for string keys; insertion, prefix-existence, removalTryAdd(string), Contains(string), ContainsPrefix(string), TryRemove(string), CopyTo. Used by Console autocomplete.none
ScyllaTrie<TValue>Prefix tree (map) for string keys; same as ScyllaTrie but with associated valuesTryAdd(string, TValue), TryGet, TrySet, TryRemove(string, out TValue), ContainsPrefix. Returns IScyllaTrie<TValue> from the builder.none
SerializableDictionary<TKey, TValue>Unity-serializable dictionary that round-trips through Unity’s JsonUtility and inspectorsSame as System.Collections.Generic.Dictionary<TKey, TValue>. Annotated for inspector display via [SerializeField].none

Common surface elements across the managed variants:

  • Builder: .CreateBuilder() returns a fluent builder. Common steps: .WithCapacity(n), .FixedCapacity(true / false), .Synchronized(syncRoot), optional type-specific steps (.WithComparer(IEqualityComparer<T>) on ScyllaMap), .Build().
  • Synchronized wrapper: every collection exposes a nested Synchronized* class implementing the same interface. Obtain via AsSynchronized(syncRoot) on the unsynchronized instance, or via .Synchronized() on the builder. The wrapper locks every operation on the shared SyncRoot.
  • Capabilities reporting: every collection sets the appropriate ScyllaCollectionCapabilities flags; check the flags before calling capability-specific methods through the interface.
  • Fixed vs growable: the optional fixedCapacity constructor argument (and .FixedCapacity() builder step) toggles between growing on overflow and refusing new items when full.

Each family also has its own dedicated page with per-type recipes, builder-reference tables, and pitfalls: Queues, Stacks, and Buffers for the five sequential containers, Maps and Dictionaries for the three key-value types, and Specialized Structures for the bit array, disjoint set, and trie. This page covers the shared contract and the catalogue; the family pages go deep on each type. State machines, a behavioral structure rather than a container, live on their own State Machines page.

Recipes

These recipes cover the mechanisms every collection shares: the common interface, the builder and capacity settings, the synchronized wrappers, and Burst jobs. Each one is a self-contained answer to a single problem, so jump to the one that matches what you are building. For recipes specific to one collection, see the per-family pages linked at the end of this section.

Work through the common interface

Problem. Sometimes the right abstraction for a collection is the slot it occupies in the rest of the codebase, not the specific operations it supports. You want to write a system manager that can drain any kind of queue – an event queue, a spawn queue, a command queue – without knowing the concrete type, and you want it to detect at runtime whether the collection supports peeking, contains queries, or random access, rather than type-casting every time.

Solution. Every collection in the namespace implements IScyllaCollection (the non-generic base) and most also implement IScyllaCollection<T> (the typed extension). The interfaces give you a uniform way to read counts, check capabilities, and use synchronized lock objects without knowing the concrete type.

using Scylla.Core.Structures;

/* Non-generic base. Every collection in the namespace implements this. */
IScyllaCollection any = someCollection;

int  count   = any.Count;       /* element count */
bool empty   = any.IsEmpty;     /* shorthand for Count == 0 */
ScyllaCollectionCapabilities caps = any.Capabilities; /* bitfield */
ScyllaCollectionThreadSafety ts   = any.ThreadSafety;
object syncRoot = any.SyncRoot; /* non-null on synchronized wrappers */

any.Clear();

/* Generic extension. Adds TryAdd / TryRemove / TryPeek / CopyTo. */
IScyllaCollection<int> typed = someTypedCollection;

bool added   = typed.TryAdd(item: 42);
bool removed = typed.TryRemove(out int next);
bool peeked  = typed.TryPeek(out int top);
int   copied = typed.CopyTo(destination: stackalloc int[16]);

/* Capability-based dispatch. Use the flags rather than type-casting.
 * The right pattern for a generic system that handles multiple queue types. */
if ((typed.Capabilities & ScyllaCollectionCapabilities.SupportsPeek) != 0)
{
    typed.TryPeek(out int peeked2);
}

if ((typed.Capabilities & ScyllaCollectionCapabilities.HasCapacity) != 0)
{
    /* The collection has a Capacity property; either cast or use the
     * concrete type if Capacity matters for back-pressure decisions. */
}

/* Thread-safe iteration. Hold the lock during multi-step operations so
 * a worker thread can't enqueue between your IsEmpty check and TryRemove. */
if (typed.ThreadSafety == ScyllaCollectionThreadSafety.Synchronized)
{
    lock (typed.SyncRoot)
    {
        if (!typed.IsEmpty)
        {
            typed.TryRemove(out int item);
        }
    }
}

Build a collection with explicit capacity and synchronization

Problem. You’re setting up a collection at startup and you know its maximum size, whether it should grow, which comparer it needs, and whether it will be shared across threads. You want all of those decisions in one readable block, not scattered across multiple statements and conditionals.

Solution. Every managed collection exposes a static CreateBuilder() returning a fluent Builder nested class. The builder collects construction parameters and produces the final collection via .Build(). The same parameters are available on the direct constructor for simple cases; the builder is preferable when multiple options are set together.

/* Direct construction. Use for simple cases with default capacity. */
var spawnQueue = new ScyllaQueue<int>(capacity: 256, fixedCapacity: false);

/* Builder pattern. Use when multiple options are set at once.
 * Pre-sized and fixed: a frame-budget spawn queue that never allocates at runtime. */
ScyllaQueue<int> frameQueue = ScyllaQueue<int>.CreateBuilder()
    .WithCapacity(256)
    .FixedCapacity()         /* never grow; TryAdd returns false when full */
    .Build();

/* Synchronized via the builder - for a queue shared between a pathfinding
 * thread and the main thread. Returns the IScyllaCollection-typed wrapper. */
IScyllaCollection<int> pathQueue = ScyllaQueue<int>.CreateBuilder()
    .WithCapacity(256)
    .Synchronized()           /* wrap in SynchronizedScyllaQueue */
    .Build() as IScyllaCollection<int>;

/* Map-specific builder steps: comparer for custom equality semantics.
 * Case-insensitive key lookup for a command registry or item database. */
var commandMap = ScyllaMap<string, int>.CreateBuilder()
    .WithCapacity(64)
    .WithComparer(StringComparer.OrdinalIgnoreCase)
    .Build();

/* DisjointSet (Union-Find) for dungeon region tracking. */
var regionSet = ScyllaDisjointSet.CreateBuilder()
    .WithCapacity(100)
    .Build();

/* Trie map for autocomplete with pre-allocated node capacity. */
var commandTrie = ScyllaTrie<int>.CreateBuilder()
    .WithNodeCapacity(256)
    .Build();

Feed a pathfinding queue from a background thread

Problem. Your pathfinding system runs on a worker thread and pushes finished paths into a queue; the main thread drains that queue every frame and moves units. You need the hand-off to be safe without writing your own lock wrapper around the queue every time you touch it.

Solution. Each collection has a nested Synchronized* class that wraps an unsynchronized instance and locks every operation on a shared SyncRoot. Obtain the wrapper through the builder’s .Synchronized() step or via AsSynchronized() on a built instance. The wrapper handles the locking for you; for multi-step atomic sequences (check count, then remove) you lock the SyncRoot once externally so no other thread can intervene between the two operations.

/* Build the unsynchronized queue. The pathfinding worker owns the write side. */
var innerQueue = new ScyllaQueue<PathResult>(capacity: 256);

/* Wrap it so both threads can safely call TryAdd / TryRemove without a
 * separate lock. The optional syncRoot lets external code use the same lock. */
var sharedQueue = innerQueue.AsSynchronized();
ScyllaQueue<PathResult>.SynchronizedScyllaQueue withCustomLock =
    innerQueue.AsSynchronized(syncRoot: myLockObject);

/* Worker thread: enqueue finished paths. The wrapper locks internally. */
sharedQueue.TryAdd(finishedPath);
sharedQueue.TryRemove(out PathResult consumed);

/* Main thread: drain in a multi-step atomic sequence. Lock once externally
 * so no path can sneak in between the IsEmpty check and the TryRemove. */
lock (sharedQueue.SyncRoot)
{
    if (!sharedQueue.IsEmpty)
    {
        sharedQueue.TryRemove(out PathResult nextPath);
        ApplyPathToUnit(nextPath);
    }
}

/* Builder variant: produces a SynchronizedScyllaQueue directly. */
ScyllaQueue<PathResult>.SynchronizedScyllaQueue fromBuilder =
    ScyllaQueue<PathResult>.CreateBuilder()
    .WithCapacity(256)
    .Synchronized()
    .Build() as ScyllaQueue<PathResult>.SynchronizedScyllaQueue;

Run collection operations inside a Burst-compiled job

Problem. You have a Burst-compiled job that fans out entity processing across worker threads – collision bucketing, pathfinding candidates, crowd simulation – and you need a queue or map that the job can write into without boxing value types or touching the managed heap.

Solution. Anyone who has shipped a Burst-compiled job knows the managed collections do not survive the trip into burstable code, and reaching for a DOTS-friendly variant is the standard workaround. Each collection (except ScyllaTypeMap, the tries, and SerializableDictionary) has a DOTS variant suffixed with DOTS. The DOTS variants are blittable structs that use NativeArray<T>-style memory and Unity’s allocator convention. They are disposable; you must explicitly release the memory. The API is similar but not identical to the managed variants (TryEnqueue instead of TryAdd, specific per-type shape).

using Unity.Collections;

/* Construct a DOTS queue for a job that gathers collision candidates.
 * Specify capacity and allocator; TempJob lasts up to four frames. */
var candidateQueue = new ScyllaQueueDOTS<int>(capacity: 1024, Allocator.TempJob);

/* DOTS API: TryEnqueue, TryDequeue. Blittable struct semantics; no
 * boxing for value types - safe for structs inside a Burst job. */
candidateQueue.TryEnqueue(entityID: 42);
candidateQueue.TryDequeue(out int nextCandidate);

/* Dispose to release the unmanaged memory. The framework does not auto-
 * release; forgetting Dispose leaks memory until the application exits. */
candidateQueue.Dispose();

/* DOTS map: entity ID -> contact count, accumulated per job batch. */
var contactMap = new ScyllaMapDOTS<int, int>(capacity: 64, Allocator.Persistent);
contactMap.TryAdd(key: entityID, value: 0);
contactMap.TryGetValue(entityID, out int contacts);
contactMap.Dispose();

/* DOTS bit array: per-entity dirty flags for a transform update job. */
var dirtyFlags = new ScyllaBitArrayDOTS(capacity: 1024, Allocator.TempJob);
dirtyFlags.Set(7);
dirtyFlags.Dispose();

/* Use inside a Burst-compiled job. The DOTS variants are designed to be
 * passed into a job struct as job-owned NativeArray-like data. */
[BurstCompile]
public struct CollisionBucketJob : IJob
{
    public ScyllaQueueDOTS<int> CandidateQueue;

    public void Execute()
    {
        /* Runs on a worker thread. No managed memory touched. */
        CandidateQueue.TryEnqueue(42);
    }
}

Per-family recipes

The recipes above cover the shared contract, builders, synchronization, and Burst jobs common to every collection. Per-type recipes now live on the dedicated family pages:

  • Queues, Stacks, and Buffers: event and command queues, rewind deques, priority dispatch, undo stacks, and rolling ring-buffer windows.
  • Maps and Dictionaries: keyed lookups with custom comparers, type-and-ID registries, and Inspector-serializable dictionaries.
  • Specialized Structures: fog-of-war bit sets, connected-region union-find, and prefix-tree autocomplete.

API Sketch

The shared interfaces, the capability and thread-safety enums, and the per-collection entry points. Each collection has its own builder, synchronized wrapper, and (optionally) DOTS variant; this sketch lists the entry points.

namespace Scylla.Core.Structures
{
    /* Shared interfaces and enums. */
    public interface IScyllaCollection
    {
        int    Count        { get; }
        bool   IsEmpty      { get; }
        ScyllaCollectionCapabilities Capabilities { get; }
        ScyllaCollectionThreadSafety ThreadSafety { get; }
        object SyncRoot     { get; }
        void   Clear();
    }

    public interface IScyllaCollection<T> : IScyllaCollection
    {
        bool TryAdd   (T item);
        bool TryRemove(out T item);
        bool TryPeek  (out T item);
        int  CopyTo   (Span<T> destination);
        int  CopyTo   (T[] destination, int destinationIndex);
    }

    [Flags]
    public enum ScyllaCollectionCapabilities
    {
        None              = 0,
        HasCapacity       = 1 << 0,
        SupportsPeek      = 1 << 1,
        SupportsContains  = 1 << 2,
        SupportsCopyTo    = 1 << 3,
        SupportsKeyLookup = 1 << 4,
        SupportsRandomAccess = 1 << 5
    }

    public enum ScyllaCollectionThreadSafety { Unsynchronized, Synchronized, LockFree }

    /* Queue family. */
    public sealed class ScyllaQueue<T> : IScyllaCollection<T>
    {
        public ScyllaQueue(int capacity = 16, bool fixedCapacity = false);
        public int  Capacity         { get; }
        public bool IsFixedCapacity  { get; }
        public bool IsFull           { get; }
        public bool TryEnqueue       (T item);
        public bool TryDequeue       (out T item);
        public bool TryPeekFront     (out T item);
        public bool Contains         (T item, IEqualityComparer<T> comparer = null);
        public SynchronizedScyllaQueue AsSynchronized(object syncRoot = null);
        public static Builder         CreateBuilder();
        public sealed class Builder
        {
            public Builder WithCapacity(int capacity);
            public Builder FixedCapacity(bool value = true);
            public Builder Synchronized(object syncRoot = null);
            public IScyllaCollection<T> Build();
        }
        public sealed class SynchronizedScyllaQueue : IScyllaCollection<T> { /* same shape */ }
    }

    public sealed class ScyllaDeque<T> : IScyllaCollection<T>
    {
        public bool TryPushBack (T item); public bool TryPushFront(T item);
        public bool TryPopBack  (out T item); public bool TryPopFront(out T item);
        public bool TryPeekBack (out T item); public bool TryPeekFront(out T item);
        /* + Builder, SynchronizedScyllaDeque, etc. */
    }

    public sealed class ScyllaStack<T> : IScyllaCollection<T>
    {
        public ScyllaStack(int capacity = 16, bool fixedCapacity = false);
        /* TryAdd = push, TryRemove = pop, TryPeek = top. Plus Builder + SynchronizedScyllaStack. */
    }

    public sealed class ScyllaPriorityQueue<T> : IScyllaCollection<T>
    {
        public ScyllaPriorityQueue(int capacity = 4, bool fixedCapacity = false,
            ScyllaPriorityQueueOrder order = ScyllaPriorityQueueOrder.Min, IComparer<T> comparer = null);
        public bool TryEnqueue(T item);
        public bool TryDequeue(out T item);
        public bool TryPeek   (out T item);
        /* Ordered by the comparer. Pass ScyllaPriorityQueueItemComparer<T>.Default
         * to order by IScyllaPriorityQueueItem.QueuePriority (get-only).
         * + Builder (MinHeap/MaxHeap/WithComparer), SynchronizedScyllaPriorityQueue. */
    }

    public interface IScyllaPriorityQueueItem
    {
        int Priority { get; set; }
    }

    /* Map family. */
    public interface IScyllaMap<TKey, TValue> : IScyllaCollection
    {
        bool TryAdd      (TKey key, TValue value);
        bool TryRemove   (TKey key);
        bool TryRemove   (TKey key, out TValue value);
        bool TryGetValue (TKey key, out TValue value);
        bool TrySet      (TKey key, TValue value);
        bool ContainsKey (TKey key);
        void EnsureCapacity(int minCapacity);
    }

    public sealed class ScyllaMap<TKey, TValue> : IScyllaMap<TKey, TValue>
    {
        public ScyllaMap(int capacity = 16, bool fixedCapacity = false,
            IEqualityComparer<TKey> comparer = null);
        public int  Capacity        { get; }
        public bool IsFixedCapacity { get; }
        /* + Builder (.WithCapacity / .FixedCapacity / .WithComparer / .Synchronized / .Build),
         *   SynchronizedScyllaMap, AsSynchronized. */
    }

    public sealed class ScyllaTypeMap : IScyllaCollection
    {
        public ScyllaTypeMap(int typeCapacity = 16, int bucketCapacity = 16,
            bool fixedCapacity = false, IEqualityComparer<Type> typeComparer = null);
        public int  TypeCount             { get; }
        public int  TypeCapacity          { get; }
        public bool ContainsType<T>      ();
        public int  CountOf<T>           ();
        public bool Contains<T>          (uint id);
        public bool TryGet<T>            (uint id, out T value);
        public bool TryAdd<T>            (uint id, T value);
        public bool TrySet<T>            (uint id, T value);
        public bool TryRemove<T>         (uint id, out T value);
        public int  ClearType<T>         ();
        /* + AsSynchronized, SynchronizedScyllaTypeMap. */
    }

    /* Specialized structures. */
    public sealed class ScyllaRingBuffer<T> : IScyllaCollection<T>
    {
        public ScyllaRingBuffer(int capacity, bool overwriteOnFull = false);
        /* TryAdd / TryRemove / TryPeek + Builder + SynchronizedScyllaRingBuffer. */
    }

    public sealed class ScyllaBitArray : IScyllaCollection
    {
        public ScyllaBitArray(int capacity = 64);
        public int  Capacity { get; }
        public int  Count    { get; } /* popcount, maintained in O(1) */
        public bool IsEmpty  { get; }
        public void Set      (int index);
        public void Unset    (int index);
        public void Set      (int index, bool value);
        public bool Get      (int index);
        public void Toggle   (int index);
        public void SetAll   ();
        public void Clear    ();
        public int  PopCount ();
        public void And      (ScyllaBitArray other);
        public void Or       (ScyllaBitArray other);
        public void Xor      (ScyllaBitArray other);
        public void Not      ();
        public Enumerator GetEnumerator();
        public static Builder CreateBuilder();
        public SynchronizedScyllaBitArray AsSynchronized(object syncRoot = null);
    }

    public sealed class ScyllaDisjointSet : IScyllaCollection
    {
        public ScyllaDisjointSet(int capacity = 16);
        public int  Capacity        { get; }
        public int  Count           { get; }
        public int  ComponentCount  { get; }
        public int  Find            (int x);
        public bool Union           (int x, int y);
        public bool Connected       (int x, int y);
        public void Clear           ();
        public static Builder       CreateBuilder();
        public SynchronizedScyllaDisjointSet AsSynchronized(object syncRoot = null);
    }

    public interface IScyllaTrie : IScyllaCollection
    {
        bool TryAdd       (string key);
        bool Contains     (string key);
        bool ContainsPrefix(string prefix);
        bool TryRemove    (string key);
    }

    public sealed class ScyllaTrie : IScyllaTrie
    {
        public ScyllaTrie(int nodeCapacity = 16, bool fixedCapacity = false, bool ignoreCase = false);
        public bool IgnoreCase { get; }
        public int  NodeCapacity { get; }
        /* + Builder, SynchronizedScyllaTrie. */
    }

    public interface IScyllaTrie<TValue> : IScyllaCollection
    {
        bool TryAdd       (string key, TValue value);
        bool TryGet       (string key, out TValue value);
        bool TrySet       (string key, TValue value);
        bool TryRemove    (string key, out TValue value);
        bool Contains     (string key);
        bool ContainsPrefix(string prefix);
    }

    public sealed class ScyllaTrie<TValue> : IScyllaTrie<TValue>
    {
        public ScyllaTrie(int nodeCapacity = 16, bool fixedCapacity = false, bool ignoreCase = false);
        /* + Builder, SynchronizedScyllaTrie<TValue>. */
    }

    /* Unity-serializable dictionary. */
    [Serializable]
    public sealed class SerializableDictionary<TKey, TValue> : IDictionary<TKey, TValue> { }

    /* DOTS variants exist for every collection except ScyllaTypeMap, the tries,
     * and SerializableDictionary. Each accepts a Unity Allocator and is
     * IDisposable; the API uses TryEnqueue / TryDequeue / etc. shape. */
    public struct ScyllaQueueDOTS<T>          : IDisposable where T : unmanaged { }
    public struct ScyllaDequeDOTS<T>          : IDisposable where T : unmanaged { }
    public struct ScyllaStackDOTS<T>          : IDisposable where T : unmanaged { }
    public struct ScyllaPriorityQueueDOTS<T>  : IDisposable where T : unmanaged, IScyllaPriorityQueueItem { }
    public struct ScyllaMapDOTS<TKey, TValue> : IDisposable where TKey : unmanaged, IEquatable<TKey>
                                                            where TValue : unmanaged { }
    public struct ScyllaRingBufferDOTS<T>     : IDisposable where T : unmanaged { }
    public struct ScyllaBitArrayDOTS          : IDisposable { }
    public struct ScyllaDisjointSetDOTS       : IDisposable { }
}

See the API reference for full signatures, remarks, and exception contracts on every member. Each concrete collection has its own per-type page or section in the API docs; this overview lists the entry points.

Capabilities reference

The ScyllaCollectionCapabilities flags tell callers what optional operations the concrete collection supports. Use them for feature detection in place of type-casting.

FlagBitMeaning
None0Only the base contract (Count, IsEmpty, Clear) is available.
HasCapacity1The collection exposes a Capacity property and may grow or be fixed-size.
SupportsPeek2TryPeek(out T) returns the “next” item without removing.
SupportsContains4Contains(item) (or ContainsKey(key) on maps) returns whether the collection holds the value.
SupportsCopyTo8CopyTo(Span<T>) and CopyTo(T[], int) are available.
SupportsKeyLookup16Maps and tries: TryGetValue(key, out value) or equivalent is available.
SupportsRandomAccess32The collection exposes indexed access ([i] getter or equivalent).

The ScyllaCollectionThreadSafety enum reports the synchronization guarantee. Unsynchronized is the default for direct construction; Synchronized is the wrapper variant; LockFree is reserved for specialized lock-free implementations (currently none ship).

Best Practices

  • Pre-size every collection. Pass capacity to the constructor or .WithCapacity(n) on the builder. The default capacity is small; growth allocates and is wasted work when the size is known.
  • Pick the right collection for the access pattern. A queue used as a stack wastes the FIFO tracking; a priority queue used as a queue wastes the heap maintenance. Read the table at the top of the page and pick the type whose access pattern matches the call site.
  • Use FixedCapacity() when overflow should refuse new items. The fixed-capacity collections never grow and never allocate at runtime. Combined with a pre-sized capacity, the result is a zero-allocation hot path.
  • Reach for the synchronized wrapper only when genuinely shared across threads. Synchronized collections pay a lock cost on every operation. For single-thread hot paths, use the unsynchronized variant; for cross-thread, use the wrapper or external locking. Mixing the two on the same instance produces undefined behaviour.
  • Use ScyllaMap<TKey, TValue> over Dictionary<TKey, TValue> when the keys or values are structs. The open-addressing implementation avoids the per-operation boxing that the standard library’s chained-bucket implementation incurs.
  • Use ScyllaBitArray for any large boolean array. 64 bits per ulong vs 1 byte per bool (for a 1 KB bool[1024]); the memory saving is 8x and the cache locality improves further. The Count property is O(1) (maintained incrementally), unlike a manual loop over a bool[].
  • Use ScyllaDisjointSet for connected-component tracking. Procedural map generation, social-graph clustering, and any “are these things in the same group?” question fit the disjoint-set pattern. The amortized near-constant Find and Union beat the alternatives.
  • Use ScyllaTrie for prefix-keyed lookup. Autocomplete, command suggestions, file-path matching. The ContainsPrefix operation is what makes the trie better than a hash map for these uses.
  • Use the DOTS variants only inside Burst-compiled jobs. The blittable structs are designed for that context; using them in regular managed code costs the disposable overhead with none of the Burst benefit.
  • Dispose every DOTS instance. The Unity allocator levels have specific lifetimes; failing to call Dispose() leaks unmanaged memory. Use using statements where possible.
  • Use SerializableDictionary only for Unity serialization needs. It is heavier than Dictionary<,> and ScyllaMap<,>; use it only when the dictionary must round-trip through Unity’s serializer or appear in the Inspector.
  • Check Capabilities flags for feature detection. When working through the interface, the flags tell you what optional operations the concrete type supports without type-casting. The pattern is if ((collection.Capabilities & ScyllaCollectionCapabilities.SupportsPeek) != 0) { ... }.

Pitfalls

Updated on July 9, 2026