When you're building financial reconciliation software, correctness is the
first requirement. Performance is the second. At small scale the two rarely
conflict. At a million transactions per run, they start to fight each other —
and the data structures you chose at the beginning of the project start to
look like liabilities.
This is the story of how we took CedarRecon's exception classification engine
from a dictionary-based implementation running at 1,368ms per million
transactions to a columnar engine running at 646ms — a 2.1x improvement —
and what we learned along the way, including four approaches that made things
worse, not better.
What Exception Classification Does
Reconciliation engines do two things: match transactions and classify the ones
that couldn't be matched. Matching is interesting in its own right (see our
earlier post on the hash-based matching engine), but classification is what
produces the output that compliance teams actually act on.
The classifier takes three inputs:
- Unmatched source transactions (what we sent)
- Unmatched target transactions (what we received)
- Matched pairs (transactions already resolved by the matching engine)
And assigns every unmatched transaction one of eight discrepancy types:
DuplicateInSource — multiple source rows share the same reference
DuplicateInTarget — multiple target rows share the same reference
SplitPayment — one source, multiple targets for the same reference
ConsolidatedPayment — multiple sources, one target for the same reference
AmountMismatch — closest target has a different amount
DateMismatch — closest target has the same amount, different date
MissingInTarget — no target exists for this source
MissingInSource — no source claimed this target
These eight types are assigned in a strict cascade — earlier phases take
priority and a row classified in phase 1 is never reclassified in phase 6.
The classification is a pure function: same inputs, same outputs, every time.
That constraint turns out to be important for how we structured the
optimization work.
The Starting Point: Dictionary-Based Classification
The original implementation built four dictionaries from the input data:
var sourceByRef = unmatchedSource
.GroupBy(tx => tx.NormalizedReference.Value)
.ToDictionary(g => g.Key, g => g.ToList());
var targetByRef = unmatchedTarget
.GroupBy(tx => tx.NormalizedReference.Value)
.ToDictionary(g => g.Key, g => g.ToList());
var matchedSourceLegCounts = matchedPairs
.GroupBy(p => p.Source.NormalizedReference.Value)
.ToDictionary(g => g.Key, g => g.Count());
var matchedTargetLegCounts = matchedPairs
.GroupBy(p => p.Target.NormalizedReference.Value)
.ToDictionary(g => g.Key, g => g.Count());
Then the 8-phase cascade ran lookups against those dictionaries. Every
lookup hashed a NormalizedReference.Value string — O(string length) per
lookup, called millions of times across the cascade at N=1M.
The benchmark numbers were not good:
| N | Mean | ms/1K rows | Growth |
|---|---|---|---|
| 10K | 42ms | 4.2ms/1K | — |
| 100K | 632ms | 6.3ms/1K | 1.5x |
| 1M | 8,400ms | 8.4ms/1K | 2.0x |
Super-linear scaling at 2.0x from N=10K to N=1M. At N=1M, 8.4 seconds per
classification run. For a batch reconciliation system running overnight,
that's acceptable. For anything approaching real-time, it isn't.
We set a benchmark discipline before touching anything: every optimization
claim must be backed by BenchmarkDotNet evidence, hypotheses that turn out
wrong get documented as negative results, and we never batch multiple changes
into one unbenchmarked commit. That last rule saved us several times.
First Wins: DictionaryBuilder and Parallel Batching
DictionaryBuilder
The first obvious improvement was the dictionary construction itself.
GroupBy().ToDictionary() makes two passes and allocates intermediate
IGrouping objects. A single-pass approach using
CollectionsMarshal.GetValueRefOrAddDefault builds the same structure in
one pass with roughly half the allocations:
public static Dictionary<string, List<Transaction>> Build(
IReadOnlyList<Transaction> transactions)
{
var dict = new Dictionary<string, List<Transaction>>(
transactions.Count, StringComparer.Ordinal);
foreach (var tx in transactions)
{
ref var list = ref CollectionsMarshal.GetValueRefOrAddDefault(
dict, tx.NormalizedReference.Value, out _);
list ??= new List<Transaction>();
list.Add(tx);
}
return dict;
}
Result: 2.4–3.7x faster dictionary construction, ~50% less allocation,
and the super-linear curve for this specific phase flattened to roughly
linear. This was the clearest win of the entire investigation, and it cost
about 20 lines of code.
Parallel Batching
The cascade's more expensive phases (Split/Consolidated, Mismatch) could
run in parallel across reference groups. We added Parallel.ForEach with
ConcurrentBag collection and a merge step, with a configurable
ParallelThreshold (default 10,000) below which parallel overhead isn't
worth it.
Combined effect of both fixes: 2.02x faster at N=1M.
But the whole-method scaling curve still climbed — 0.816ms/1K at N=10K
rising to 1.196ms/1K at N=1M, a 1.46x growth ratio. The dictionary
structure itself was still the problem.
Dead End #1: FrozenDictionary
The steepest-growing phase was SplitConsolidatedPhases — 3.06x growth
from N=10K to N=1M. The obvious hypothesis: FrozenDictionary<TKey, TValue>,
introduced in .NET 8, offers faster lookups than Dictionary<TKey, TValue>
for read-only scenarios. We'd build the dictionaries once and freeze them
before the cascade.
The benchmark:
| N | Dictionary | FrozenDictionary | Δ |
|---|---|---|---|
| 10K | 1.21 µs/1K | 0.95 µs/1K | −22% |
| 100K | 1.87 µs/1K | 2.23 µs/1K | +19% |
| 1M | 3.09 µs/1K | 4.35 µs/1K | +41% |
FrozenDictionary won at N=10K and lost badly at N=100K and N=1M — the
opposite of what we needed.
The lesson: the problem wasn't lookup speed. It was scan pattern. At large
N, the dictionary's bucket array and the heap-allocated List<Transaction>
objects it pointed to were scattered across memory with no spatial locality.
Every "lookup" was really a cache miss chain: hash → bucket → list pointer
→ list contents, none of it co-located. A faster hash function doesn't fix
a cache miss problem.
This distinction — lookup speed vs access pattern — shaped everything that
came after.
The Indexed Engine: Sorting Instead of Hashing
If hashing was the wrong model, what was the right one? For sequential
access over a known key set, sorted arrays.
A sorted array of transactions, sorted by normalized reference, has all
transactions for the same reference in a contiguous block. Iterating over
them is a sequential memory access — exactly the pattern CPU prefetchers
are built for. A dictionary's entries, by contrast, are accessed in hash
order, which for large tables approximates random access.
ReferenceInterner
The first building block: map reference strings to dense sequential integers
(0, 1, 2, ...) once, upfront, so every subsequent operation works on ints
instead of strings.
public sealed class ReferenceInterner
{
private readonly Dictionary<string, int> _ids = new(StringComparer.Ordinal);
public int GetOrAdd(string reference)
{
if (_ids.TryGetValue(reference, out var id))
return id;
id = _ids.Count;
_ids.Add(reference, id);
return id;
}
public int Count => _ids.Count;
}
After interning, every lookup in the cascade is an array index operation
on a dense integer — O(1), no hashing, no string comparison. The string
dictionary pays its cost once at build time and never appears on the hot
path again.
RefGroup
Instead of Dictionary<string, List<Transaction>>, we built a RefGroup
struct that points into sorted arrays:
public struct RefGroup
{
public int ReferenceId;
public int SourceStart; // first position in sorted source array
public int SourceCount; // number of source rows for this reference
public int TargetStart;
public int TargetCount;
public int MatchedSourceCount; // legs already matched
public int MatchedTargetCount;
public int TotalSourceLegs => SourceCount + MatchedSourceCount;
public int TotalTargetLegs => TargetCount + MatchedTargetCount;
}
One flat RefGroup[] array, one flat source IndexedTransaction[] array,
one flat target IndexedTransaction[] array. All sorted by ReferenceId.
All contiguous in memory. All accessible via array index, never via hash
lookup.
The cascade phases became sequential scans over RefGroup[], with inner
loops over the contiguous row ranges each group described. No dictionaries,
no hash lookups, no pointer chasing.
First indexed-engine results
Phase benchmark, SplitConsolidatedScan (the worst-scaling phase):
| N | Dictionary µs/1K | Indexed µs/1K | Δ |
|---|---|---|---|
| 10K | 1.27 | 0.82 | −35% |
| 100K | 1.87 | 0.64 | −66% |
| 1M | 3.09 | 0.91 | −71% |
Growth ratio: 2.43x → 1.11x. Nearly flat. The cache-locality hypothesis
was confirmed.
Whole-method at N=1M: 0.52x vs dictionary (1.92x faster).
But a new problem had appeared. MismatchScan — which had previously been
cheap — was now the most expensive scan phase and was showing 1.6x growth:
| N | MismatchScan µs/1K |
|---|---|
| 10K | 7.76 |
| 100K | 10.79 |
| 1M | 12.57 |
We had fixed the scan pattern problem and exposed a different problem: the
arithmetic inside the inner loop.
Item 1: decimal → long (The Instruction-Count Insight)
MismatchScan's inner loop found the closest unmatched target by amount:
var diff = Math.Abs(targetRows[ti].Amount - sourceRow.Amount);
Amount was decimal. On .NET, decimal arithmetic is software-emulated —
there is no native CPU instruction for it. Math.Abs on a decimal is a
method call that executes multiple instructions. At N=1M with the mismatch
phase touching every source row that reached it, this added up.
The fix: store amounts as long AmountMinor (scaled by 10^4) at index-build
time. Math.Abs on a long is a single CPU instruction.
Scale factor choice: 10^4, not 10^2. Most currencies use 2 decimal places,
but ISO 4217 includes currencies with 3 (KWD, BHD, OMR). Scaling by 10^2
would silently truncate those — a data loss bug that would only surface on
specific currency combinations. 10^4 is a strict superset of every realistic
precision in this domain.
var diff = Math.Abs(targetBatch.AmountMinor[ti] - sourceAmountMinor);
Result:
| N | Before µs/1K | After µs/1K | Δ |
|---|---|---|---|
| 10K | 7.76 | 5.20 | −33% |
| 100K | 10.79 | 6.86 | −36% |
| 1M | 12.57 | 6.34 | −50% |
Growth ratio: 1.6x → 1.22x. Half the cost at N=1M, nearly flat scaling.
Same fact class as the FrozenDictionary lesson — understanding what kind
of work is expensive (software-emulated arithmetic vs native instructions)
matters more than optimizing at the wrong level.
Dead Ends #2, #3, #4: Three More Negative Results
Before reaching the columnar design, we tested three more approaches that
didn't work. Documenting them is as important as documenting what did.
Dead End #2: BuildGroups allocation
Hypothesis: List<RefGroup> + [.. groups] spread in BuildGroups
allocated two arrays — the list's backing array and a second array from
the spread. Replacing with a pre-sized RefGroup[] + count cursor would
eliminate the second allocation.
Result: Allocated column unchanged at every N. The realistic dataset
always has some matched-only references (contributing to internedCount
but not to count), so count < internedCount on every run, meaning
Array.Resize fired just as often as the old spread. The "double
allocation" only exists when count == internedCount exactly — a case
the realistic dataset never produces.
Mean time improved slightly (~17% at N=100K) but inconsistently. The change
was kept (not worse) but the hypothesis was wrong.
Dead End #3: ReferenceInterner reverse list
Hypothesis: ReferenceInterner built a List<string> for reverse
lookup (GetValue). Since GetValue is diagnostics-only and never called
during classification, making it optional should reduce allocation at no
time cost.
Result: Allocation down 10–16%. Time consistently +5–34% worse at
all N.
This is also where we learned that 3 benchmark iterations is not enough for
effect sizes in the 5–35% range. The first run (3 iterations, noisy) showed
an apparent win on both allocation and time. A rerun with 15 iterations
(tighter error bars) revealed the time regression clearly. We reverted the
change and adopted warmupCount: 3, iterationCount: 15 as the standing
benchmark convention from that point forward.
Dead End #4: Index-sort (sort int[] instead of structs)
Hypothesis: Array.Sort on an IndexedTransaction[] moves whole
~20-byte structs on every swap. Sorting a parallel int[] rowOrder by
ReferenceId would move only 4-byte ints — smaller element, cheaper sort.
Result: The sort did get cheaper. But every scan phase then needed one
extra array dereference to read a row: rows[rowOrder[i]] instead of
rows[i]. At N=1M, that extra dereference for every row read in every
phase cost more than the sort savings.
| Phase (N=1M) | Struct-sort µs/1K | Index-sort µs/1K | Δ |
|---|---|---|---|
| SplitConsolidatedScan | 2.81 | 4.53 | +61% |
| DuplicateScan | 5.55 | 7.34 | +32% |
The pattern from FrozenDictionary reappeared: indirection costs more than
it saves at production scale. Cache misses from pointer chasing dominate
any algorithmic savings from working with smaller elements.
The Columnar Leap: Struct-of-Arrays
The index-sort investigation clarified the real problem. Even after
compacting IndexedTransaction to ~20 bytes, array-of-structs still had
a structural inefficiency: every cache line loaded for any phase contained
all fields, even ones that phase never read.
DuplicateScan only checks whether multiple rows share the same reference.
It never looks at amounts or dates. But in an array-of-structs layout, the
cache line containing a row's ReferenceId also contains AmountMinor and
DayNumber. That's wasted bandwidth at every cache line boundary.
Struct-of-arrays separates the columns:
public sealed class ColumnarTransactionBatch
{
public int Count { get; init; }
public required int[] OriginalIndex { get; init; }
public required int[] MatchKeyId { get; init; }
public required long[] AmountMinor { get; init; }
public required int[] DayNumber { get; init; }
public required byte[] ProcessingState { get; init; }
}
DuplicateScan touches only ProcessingState. MismatchScan touches only
AmountMinor, DayNumber, and ProcessingState. MatchKeyId is read
only during index build. When a phase iterates over AmountMinor, every
byte in every cache line is an amount value — 100% useful data.
ProcessingState: the generic execution buffer
One design decision worth explaining: ProcessingState is a byte[], not
a ClassificationState[]. The enum exists and works fine for external
APIs, but on the hot path we use byte constants:
internal static class ClassificationStateBytes
{
public const byte None = 0;
public const byte DuplicateInSource = 1;
// ...
public const byte MissingInSource = 8;
}
The reason: ProcessingState is an execution buffer, not a typed domain
field. The same array can be reused by a future matching operator with
completely different byte semantics — no reallocation, just a different
interpretation. This is how database execution engines handle per-row status:
one generic buffer, operator-local meaning. Translate to stable domain types
(DiscrepancyType) before exposing results; the buffer stays internal.
Columnar scan phase results (N=1M)
| Phase | Array-of-structs µs/1K | Columnar µs/1K | Δ |
|---|---|---|---|
| MismatchScan | 6.34 | 4.54 | −28% |
| MissingSweep | 2.96 | 1.45 | −51% |
| SplitConsolidatedScan | 2.81 | 3.45 | +23% |
| DuplicateScan | 5.55 | 5.12 | −8% |
Most phases improved. SplitConsolidatedScan regressed — unexpected, but
it's a phase that barely touches column data and is dominated by RefGroup
iteration, so the columnar layout didn't help it as much.
The IndexBuild regression
There was a catch. The initial columnar builder used sort-then-scatter:
// Sort a parallel int[] by MatchKeyId
Array.Sort(sortOrder, (a, b) => tmpMatchKeyId[a].CompareTo(tmpMatchKeyId[b]));
// Scatter each column
for (var i = 0; i < n; i++)
originalIndex[i] = tmpOriginalIndex[sortOrder[i]]; // random read
At N=1M, tmpOriginalIndex[sortOrder[i]] is a random read — sortOrder[i]
is an arbitrary position in a large array that doesn't fit in cache. Same
problem as the index-sort approach in dead end #4, just in the build phase
instead of the scan phases.
IndexBuild at N=1M: +18% worse than array-of-structs.
The whole-method benchmark was still positive (0.50x vs dictionary, 2x
faster) because scan-phase wins outweighed the build regression. But we
had a known problem.
Histogram Sort: The Final Piece
MatchKeyId is a dense integer — it's an interned reference ID assigned
sequentially from 0. Dense integer keys are the ideal case for counting
sort (also called histogram sort).
Instead of a comparison sort (O(n log n)) and a random-read scatter, we do:
Pass 1: Count rows per key in one sequential scan:
for (var i = 0; i < n; i++)
counts[tmpMatchKeyId[i]]++;
Pass 2: Prefix sum to get start offsets:
var running = 0;
for (var k = 0; k < keyCount; k++)
{
starts[k] = running;
running += counts[k];
}
Pass 3: Place rows using a cursor per key:
var cursor = starts.ToArray(); // copy of starts
for (var i = 0; i < n; i++)
{
var key = tmpMatchKeyId[i];
var pos = cursor[key]++; // cursor advances sequentially within each key
finalAmountMinor[pos] = tmpAmountMinor[i];
// ... other columns
}
The reads from tmp* arrays are sequential (we iterate input order).
The writes to final* arrays are contiguous within each key bucket
(cursor[key]++ means consecutive rows for the same key go to consecutive
positions). No random reads anywhere.
Total: O(n + k) instead of O(n log n). For typical reconciliation data
with high reference reuse, k ≪ n and this is effectively O(n).
The merge-join disappears
There's a bonus: RefGroup[] construction used to require a merge-join
walk over both sorted arrays to discover group boundaries. With histogram
sort, starts[k] and counts[k] are already exactly SourceStart and
SourceCount for every reference k. RefGroup[] is built in a single
O(k) pass over the key space, with no traversal of row arrays at all:
for (var k = 0; k < internedCount; k++)
{
var sourceCount = source.Counts[k];
var targetCount = target.Counts[k];
if (sourceCount == 0 && targetCount == 0) continue;
groups[count++] = new RefGroup
{
ReferenceId = k,
SourceStart = source.Starts[k],
SourceCount = sourceCount,
TargetStart = target.Starts[k],
TargetCount = targetCount,
// ...
};
}
Histogram sort results
IndexBuild benchmark (µs/1K rows):
| N | Array-of-structs | Scatter sort | Histogram | vs AoS |
|---|---|---|---|---|
| 10K | 241 | 212 | 139 | −42% |
| 100K | 448 | 322 | 206 | −54% |
| 1M | 395 | 464 | 296 | −25% |
The N=1M regression (+18% with scatter) became a −25% improvement with
histogram. No trade-offs, no reversals at any N.
Final Results
Whole-method benchmark, DictionaryClassifier vs ColumnarClassifier:
| N | Dictionary | Columnar+Histogram | Ratio |
|---|---|---|---|
| 10K | 8.06 ms | 2.52 ms | 0.31x |
| 100K | 108.6 ms | 51.8 ms | 0.48x |
| 1M | 1,368 ms | 646 ms | 0.47x |
The columnar engine with histogram sort is 2.1x faster than the
dictionary engine at N=1M.
The full journey for MismatchScan specifically — from the original
dictionary baseline through every optimization:
| Stage | N=1M µs/1K | vs original |
|---|---|---|
| Dictionary engine | 12.57 | baseline |
| Indexed engine (item 1, decimal→long) | 6.34 | −50% |
| Columnar engine (item 6, AoS→SoA) | 4.54 | −64% |
What We Learned
1. Know which kind of slowness you have. FrozenDictionary failed because
the problem was cache miss patterns, not lookup speed. Index-sort failed
because the problem was read indirection cost, not sort element size. Every
time we correctly identified the bottleneck type, the fix worked. Every time
we guessed, it didn't.
2. Benchmark discipline is non-negotiable. Three of our negative results
(FrozenDictionary, index-sort, scatter sort) would have been hard to
predict analytically. The fourth (reverse list removal) showed an apparent
win with 3 iterations that reversed with 15 iterations. Intuition about
what should be faster is unreliable enough that "benchmark it" isn't just
good practice — it's the only reliable epistemology for performance
engineering at this level.
3. Document the dead ends. Every negative result in this investigation
tells you something about the system that a positive result doesn't.
FrozenDictionary's failure taught us the problem was scan pattern, not
lookup speed — which directly led to the sorted-array design. Index-sort's
failure taught us that indirection costs more than element size saves at
scale — which directly influenced the histogram sort design. If we'd
hidden those results, we'd have lost the reasoning.
4. Dense integer keys change the game. Once ReferenceInterner existed
— once every string key was a dense sequential integer — a whole class of
algorithms became available. Counting sort. Direct array indexing. RefGroup
construction from prefix sums. The interning step was inexpensive (one
dictionary lookup per distinct reference, upfront) and unlocked everything
that came after.
5. The database execution model scales. ProcessingState as a generic
byte buffer with operator-local semantics, ColumnarTransactionBatch as a
shared execution context, refgroup-based range access rather than
per-row object navigation — these patterns exist in database engines for
the same reasons they work here. Financial reconciliation data at scale
has more in common with a database's internal representation than with a
collection of domain objects.
What's Next
The engine still has known costs worth addressing. The temporary arrays in
ColumnarIndexBuilder (~20 bytes/row) are the remaining source of
super-linear growth at N=1M — eliminating them would require a two-pass
encode (first pass counts, second pass places directly into final arrays).
The ProcessingState design also sets up a future build strategy selector:
when the matching engine and quality gates share the same
ColumnarTransactionBatch, those operators may have different key
characteristics. Dense keys get histogram sort. Sparse integer keys get
radix sort. Arbitrary comparison keys fall back to struct-sort. The
selector doesn't exist yet — it will when the second operator needs it.
CedarRecon is open source. The full benchmark suite, all negative results,
and the complete investigation history are in the repository.
Top comments (0)