UNDF: UNDF-2026-000000639

nim-0001: sequtils.deduplicate — O(N²) result.contains in for loop

Severity: HIGH

Location

lib/pure/collections/sequtils.nim:236-237
Public stdlib API: import std/sequtils; deduplicate(seq)

Description

deduplicate[T](s: openArray[T], isSorted: bool = false): seq[T] deduplicates a sequence by building the result array one element at a time. For each input element itm, it calls result.contains(itm) — which is an O(N) linear scan of the result array — before deciding to append. This makes the unsorted path O(N²).

The function is public stdlib API used throughout the Nim ecosystem. The isSorted fast path exists (O(N) via adjacent comparison) but the default isSorted = false path is always O(N²). Users who don't pass isSorted = true or who have unsortable types get quadratic behavior silently.

The Nim compiler itself calls deduplicate (via nimsets.nim:713) during enum set deduplication in type-checking.

Root Cause

# sequtils.nim:226-237
result = @[]
if s.len > 0:
  if isSorted:
    var prev = s[0]
    result.add(prev)
    for i in 1..s.high:
      if s[i] != prev:
        prev = s[i]
        result.add(prev)
  else:
    for itm in items(s):
      if not result.contains(itm): result.add(itm)  # O(N) scan, O(N) outer = O(N²)

result.contains(itm) on a seq[T] is O(len(result)) linear scan. Called for every element in the input → O(N²) total.

Fix

For hashable types, use a HashSet as a seen-tracker alongside the result:

else:
  var seen = initHashSet[T]()
  for itm in items(s):
    if itm notin seen:
      seen.incl(itm)
      result.add(itm)

For non-hashable types (no hash proc), sorting then deduplicating is O(N log N). A two-overload approach can dispatch at compile time using when compiles(hash(s[0])).

Complexity

	Before	After
deduplicate (unsorted, hashable)	O(N²)	O(N)
deduplicate (unsorted, non-hashable)	O(N²)	O(N log N)
deduplicate (isSorted = true)	O(N)	O(N) unchanged

Impact

Any Nim code that calls deduplicate on a sequence of N elements without passing isSorted = true incurs O(N²) cost. At N=10,000 that is 100 million comparisons versus 10,000 hash lookups. Affected: all code using import std/sequtils and calling deduplicate on unsorted data.

2.3 KiB Raw Permalink Blame History