Arven.SegmentedDictionary 0.1.0

SegmentedDictionary<TKey, TValue>

Alternativa thread-safe y de alto rendimiento a Dictionary<TKey,TValue> y ConcurrentDictionary<TKey,TValue> para .NET 8, diseñada para millones de elementos, cargas incrementales en batches de ~10.000 elementos y workloads con lecturas y escrituras concurrentes.

Reglas fundamentales de diseño

1. El costo de modificar un shard depende del tamaño de ese shard, nunca del tamaño total del diccionario.
2. Nunca se realiza un resize/rehash global como consecuencia del crecimiento normal de la colección.

Problem

Un Dictionary<TKey,TValue> monolítico sufre spikes de latencia cuando crece: cada resize realoca los arrays de buckets/entries y rehashea todos los elementos existentes. Con millones de elementos, cada resize cuesta decenas/cientos de milisegundos, y empeora a medida que la colección crece (exactamente el patrón "batch 1 rápido … batch N cada vez más lento").

ConcurrentDictionary mitiga pero no elimina el problema: sus resizes son globales y toman todos sus locks internos (en la práctica: spikes de ~200ms medidos a 5M elementos, ver resultados abajo).

SegmentedDictionary elimina el resize global por construcción.

Architecture

                     key
                      │
                      ▼  comparer.GetHashCode(key)  (1 sola vez por operación)
                      ▼  Fibonacci mixing (h ^= h>>16; h *= 2654435761u; h ^= h>>15)
                      ▼
        shard = hash >> (32 - log2(shardCount))      ← bits ALTOS, O(1)
                      │
        ┌─────────────┼─────────────┬─────────────┐
        ▼             ▼             ▼             ▼
     Shard 0       Shard 1       Shard 2   …   Shard N-1
        │                                        │
        ▼                                        ▼
   hash table propio                      hash table propio
   (open addressing,                      (open addressing,
    linear probing,                        linear probing,
    índice = hash & (cap-1))    ← bits BAJOS, O(1)
   lock propio                             lock propio

• Routing estable de por vida: el shard de una key se determina por los bits altos del hash mezclado y el shardCount es fijo desde la construcción. Ningún crecimiento redistribuye entradas.
• Cada shard es una hash table independiente (open addressing + linear probing, capacidad potencia de 2, load máximo 0.72). Sus resizes son locales: agrandar el shard 17 no toca ni bloquea a ningún otro.
• Los shards se crean lazy al primer write de su slot (Interlocked.CompareExchange, el perdedor de la carrera descarta su candidato). Un diccionario vacío solo aloja el array de referencias.

⚠️ Detalle que los benchmarks hicieron evidente: enrutar y hacer probing con los mismos bits del hash correlaciona shard con posición inicial de probe y produce clustering catastrófico dentro del shard (medido: lookup 10× más lento, 627µs/10K lookups a 5M). Por eso routing usa bits altos y probing bits bajos.

Tamaño de shard vs tamaño de batch

Los ~10.000 elementos son el tamaño del batch de entrada, no del shard. Un shard puede contener 50K–1M+ elementos; los batches se particionan por shard antes de insertar.

Thread safety

Caveat conocido (idéntico a ConcurrentDictionary): actualizar el valor de una key existente muta la entrada in-place; un reader concurrente podría observar un valor "torn" solo si TValue es un struct mayor que un word de máquina. La presencia/ausencia de keys es consistente para todo tipo.

Performance

Medido en esta máquina (Intel Core Ultra 9 275HX, .NET 8.0, BenchmarkDotNet ShortRun; el suite completo se habilita con --full).

Latencia por batch de 10K hasta 5M (§25 — el dato que importa)

Probe custom que mide cada uno de los 500 batches:

Probe a 10M entradas (1000 batches de 10K), menos = mejor en todo:

El max de ConcurrentDictionary (570 ms a 10M) evidencia los resizes globales, que crecen con el tamaño total. En SegmentedDictionary el spike máximo lo produce el resize de un solo shard, así que baja con más shards y se elimina casi por completo con WithExpectedCapacity (que pre-dimensiona cada shard: 0 resizes medidos al cargar 1M; ver GrowthTests).

Insert secuencial de 1M (throughput total)

Lookup (10K keys aleatorias, µs)

Lookup O(1) confirmado (plano entre 5M y 10M) e invariante al shardCount (64→1024 shards a 1M: 66µs → 79µs, +18% para 16x de shards). Por tipo de key a 1M (SegmentedDictionary vs ConcurrentDictionary): long 81µs vs 35µs, string 455µs vs 290µs, Guid 124µs vs 53µs — CD gana ~1.6-2.3x en reads single-thread con keys pesadas; el costo extra es el hashing/mixing + indirección por shard.

Concurrencia — sweep completo 1–64 threads (2M ops, menor = mejor)

90% reads / 10% writes:

50% reads / 50% writes:

Veredicto: en read-heavy gana SegmentedDictionary en todo el rango de threads (~1.2–1.4x sobre CD); en 50/50 CD gana ~10–20%. Dictionary+lock queda 10–25x atrás en cuanto hay contención real.

Remove y churn (1M, tombstones)

El remove de SegmentedDictionary es mejor que CD, pero el churn sostenido de add/remove es el punto débil relativo (los tombstones se purgan en los resizes locales; cuesta ~1.7x comparado con CD).

Batch paralelo — evaluado y descartado como default (§11)

Insert paralelo por shard vs secuencial: a 10K items empata (374µs vs 405µs vacío; 474 vs 313 con 5M precargado); a 100K items el paralelo gana 3x (4.6ms → 1.5ms). Conclusión: solo paga con batches ≫10K. Queda como API interna experimental (AddRangeParallel), no expuesta.

Decisiones tomadas por benchmark

1. Dictionary interno + lock por shard → rechazado: los reads pagaban el Monitor (~15ns/op) y quedaban 5x detrás. Reemplazado por open addressing propio con reads lock-free.
2. Routing/probing por bits bajos compartidos → rechazado (clustering, 627µs). Reemplazado por bits altos / bits bajos.
3. shardCount default 512 (medidos 64/128/256/512/1024).
4. Load factor 0.72 probado contra 0.50: aplana el P99 pero duplica la memoria (1GB vs 512MB a 10M) → descartado como default.
5. Pre-sizing vía WithExpectedCapacity: 2 Gen0, mejor P99/mean del probe.
6. Count: contadores striped por shard (una cache line cada uno) para las escrituras; Count suma con reads volátiles. Benchmarked contra un contador global Interlocked a 32/64 threads con 50% writes: paridad — ni la contención ni el fix se miden. Se mantiene la versión striped porque elimina la única cache line compartida por todos los writers (techo de escalabilidad en CPUs con coherencia más débil).
7. Enumeración sin LOH: los snapshots por shard van en chunks de ~32KB, no en un array del tamaño del shard (un shard de 100K serían 1.6MB en LOH por cada enumeración).
8. ReaderWriterLockSlim/lock-free-completo/custom allocators: no introducidos — los benchmarks no justifican su costo/complejidad (§33).

Memory

• Overhead por entry: Entry{int State; uint Hash; TKey Key; TValue Value} — para int,int: 16 bytes, ~22B/entry amortizado al load 0.72 (vs ~24B/entry de Dictionary, ~45B+/entry de ConcurrentDictionary por sus nodos).
• Sin objetos por entry: un array de structs por shard.
• 5M de int,int: ~129 MB live medidos (vs 237 MB de ConcurrentDictionary).
• Sin arrays LOH por encima de 85K por shard hasta escalas enormes; los buffers de batch se alquilan de ArrayPool (allocaciones por batch de 10K: ~24KB, vs 400KB de ConcurrentDictionary).

Usage

using Arven.Collections.Generic;

// Default: 512 shards. shardCount debe ser potencia de 2.
var dict = new SegmentedDictionary<long, MyObject>(shardCount: 128);

// RECOMENDADO si conocés la escala: elige shardCount Y pre-dimensiona cada
// shard, de modo que cargar hasta la capacidad esperada no produce NI UN resize
// local (medido: 0 resizes y 2 Gen0 al cargar 1M).
var big = SegmentedDictionary<long, MyObject>.WithExpectedCapacity(10_000_000);

dict.TryAdd(id, value);

if (dict.TryGetValue(id, out MyObject? result))
{
    ...
}

dict[id] = value;                    // upsert
dict.TryUpdate(id, newValue);        // solo si existe
dict.GetOrAdd(id, k => Create(k));   // o sin closure:
dict.GetOrAdd(id, myState, static (k, s) => Create(k, s));
dict.TryRemove(id, out var removed);

Es IDictionary<TKey,TValue> (y IReadOnlyDictionary<TKey,TValue>): cambiar Dictionary<int, Item> por SegmentedDictionary<int, Item> es directo.

Custom comparer

var dict = new SegmentedDictionary<string, int>(StringComparer.OrdinalIgnoreCase);

El comparer se usa para routing y almacenamiento, y se calcula GetHashCode() una sola vez por operación (el hash mezclado se almacena en cada entry, así que los resizes locales no recalculan hashes).

Batch

// IEnumerable, Span, o async; devuelven cuántos se agregaron (duplicados salteados)
dict.AddRange(batch);                  // IEnumerable<KeyValuePair<K,V>>
dict.AddRange(batch.AsSpan());         // span
int added = await dict.AddRangeAsync(StreamItems(), cancellationToken);

El batch particiona por shard (counting sort sobre buffers de ArrayPool), calcula cada hash una vez, y toma el lock de cada shard una sola vez por chunk con un único chequeo de capacidad.

Semántica de AddRange*:

• Devuelven cuántos items se agregaron; los duplicados (contra el diccionario existente o dentro del mismo batch) se saltean.
• Si AddRangeAsync se cancela a la mitad, los chunks ya completados permanecen insertados (la cancelación corta entre chunks; no hay rollback). Si necesitás atomicidad, cargá a un diccionario nuevo y swappeá la referencia.

Las operaciones de lectura/escritura puntuales son síncronas a propósito: son memory-bound y crear TryAddAsync/TryGetValueAsync sería asincronía artificial. La única API async es AddRangeAsync(IAsyncEnumerable<…>).

Known limitations

• shardCount no cambia tras construir (es lo que hace imposible el rehash global). Para estimaciones erradas, WithExpectedCapacity o un shardCount más grande solo cuestan memoria de punteros (shards vacíos no se alocan).
• TValue estructural grande + updates concurrentes: ver caveat de torn values.
• Count es exacto pero se actualiza fuera del lock del shard: en medio de una ráfaga puede quedar momentáneamente atrás de las operaciones en flight.
• Clear() concurrente con escrituras in-flight puede descartar dichas escrituras (documentado arriba).
• Values.Contains(value) es O(n) (búsqueda lineal); no hay índice inverso.
• Lookups single-thread con keys pesadas (string/Guid) quedan ~1.6–2.3x detrás de ConcurrentDictionary; churn sostenido de add/remove ~1.7x detrás de CD (ver tablas de benchmarks).
• CopyTo bajo escrituras concurrentes: si el diccionario crece más allá del destino a mitad de copia, el excedente se omite silenciosamente (consistente con la enumeración weakly-consistent).
• Gaps residuales de la spec, aceptados conscientemente: las implementaciones internas "chaining" y "buckets/entries custom" (§8 B/D) nunca se compararon — el open addressing actual ganó a Dictionary-por-shard y a CD en el workload objetivo; el factor de crecimiento 1.5x vs 2x (§7) no se A/B-testeó (en tablas power-of-two el crecimiento efectivo es ~2x salvo ruido); el suite BDN --full con percentiles nativos queda disponible pero no se corrió en esta sesión.

Build, test, benchmarks

dotnet build                                  # librería + tests + benchmarks
dotnet test                                   # 51 tests (correctness + concurrencia + stress corto)
dotnet test --filter "Name=MixedWorkload_LongRun"   # stress largo (5 seeds × 1 min)

dotnet run -c Release --project SegmentedDictionary.Benchmarks                 # suite BDN reducido
dotnet run -c Release --project SegmentedDictionary.Benchmarks -- --full       # suite completo (default job, percentiles)
dotnet run -c Release --project SegmentedDictionary.Benchmarks -- --latency-probe 5000000