Use a Set to dedupe included resources (19× faster at n=4000)

[Xaelp]

Use a Set to dedupe included resources (19× faster at n=4000)

Version: 1.12.5 (current latest)
Files: src/utils/serializer.utils.ts, src/classes/serializer.ts

Summary

When building a compound document, ts-japi deduplicates included resources using an array with keys.includes(key). That membership check is a linear scan, and it runs once per candidate resource — so serializing n included resources costs ~n²/2 string comparisons.

Switching keys from Array to Set makes it O(n). The array is only ever used for membership testing and appending, so the change is semantically identical.

Where

recurseRelatorsDepth:

const key = resource.getKey();
if (!keys.includes(key)) {   // O(n) scan, inside a loop over n resources
  keys.push(key);
  included.push(resource);
}

recurseRelators has the same pattern. keys originates in Serializer.serialize as const keys = [].

Benchmark

Isolated npm install ts-japi@1.12.5, two copies differing only by the Set change. One serializer, one relator, include depth 1, each of n primary resources related to a distinct resource (so included grows to n). Median of 3 runs, warmup discarded, process.hrtime.bigint(), Node v24.4.1.

n	array (ms)	Set (ms)	speedup	included
100	0.40	0.39	1.04×	100
250	0.83	0.53	1.57×	250
500	1.41	1.07	1.32×	500
1000	4.64	1.92	2.41×	1000
2000	24.58	4.00	6.14×	2000
4000	142.72	7.55	18.90×	4000

Growth per doubling of n:

n	array	Set
250→500	1.69×	2.01×
500→1000	3.30×	1.80×
1000→2000	5.29×	2.08×
2000→4000	5.81×	1.89×

Below n≈500 both are dominated by fixed overhead and the difference is noise — at n=100 the two are indistinguishable. From n=1000 the quadratic signature is unambiguous: the array approaches ~5.8× per doubling while the Set holds ~1.9–2.1×, i.e. linear.

One caveat stated plainly: ~5.8× per doubling is steeper than the 4× a pure O(n²) predicts. The extra is most likely allocation/GC and cache-miss effects as the key array grows. The asymptotic direction is not in doubt, but treat the constants as indicative rather than exact.

Correctness: outputs are byte-identical (JSON.stringify equality) between the two variants, with matching included counts at every n.

Proposed fix

--- a/src/classes/serializer.ts
+++ b/src/classes/serializer.ts
-    const keys: string[] = [];
+    const keys = new Set<string>();
...
-        keys.push(resource.getKey());
+        keys.add(resource.getKey());

--- a/src/utils/serializer.utils.ts
+++ b/src/utils/serializer.utils.ts
-        if (!keys.includes(key)) {
-          keys.push(key);
+        if (!keys.has(key)) {
+          keys.add(key);
           included.push(resource);
         }

Two call sites in serializer.ts, two in serializer.utils.ts. The keys parameter type changes from string[] to Set<string> — internal only, not part of the public API.

Happy to open a PR with the fix and a regression benchmark if that's useful.

[jrandolf]

n = 4000? That's a lot of objects! You should only include maybe 100 objects at a time 😂. Anyway, accepted.

[Xaelp]

Great! I actually use it on endpoints that can return up to 10K included resources 😅. In our case, batching that much data into a single response is more efficien. It avoids thousands of additional network round trips and reduces the overhead of many smaller requests. The underlying infrastructure is designed to handle responses of that size, so keeping the serialization path efficient matters quite a bit.