UNDF: UNDF-2026-000000689

UNDF: (pending)

numpy-0001: stack_arrays — seen=[] list dedup O(A×F²) field-name tracking

CWE-407 — Algorithmic Complexity: O(A×F²) list-contains in structured-array stacking

Field	Value
ID	numpy-0001
Severity	MEDIUM
Ecosystem	numpy
Package	`numpy`
File	`numpy/lib/recfunctions.py`
Lines	1396–1405
Complexity	O(A×F²) on A arrays with F fields each
Hot path	`stack_arrays()` — stacking structured/record arrays

Background

stack_arrays(arrays) superposes structured arrays field by field, building a merged output array. It tracks which field names have already been seen in order to handle anonymous arrays (arrays without named fields) by generating synthetic names like f0, f1, …

Defect

# numpy/lib/recfunctions.py  lines 1394–1405
output = ma.masked_all((np.sum(nrecords),), newdescr)
offset = np.cumsum(np.r_[0, nrecords])
seen = []                                   # DEFECT: list, not set
for (a, n, i, j) in zip(seqarrays, fldnames, offset[:-1], offset[1:]):
    names = a.dtype.names
    if names is None:
        output[f'f{len(seen)}'][i:j] = a
    else:
        for name in n:
            output[name][i:j] = a[name]
            if name not in seen:            # O(F) list scan each time
                seen.append(name)

The outer loop runs A times (once per input array). The inner loop runs F times per array. if name not in seen is an O(|seen|) linear scan, so the total work for field-name dedup is O(A×F²). The same seen list grows across all arrays, making later checks progressively more expensive.

Note that stack_arrays also calls a sibling loop at lines 1377–1383 (the newdescr / names list build) with the same O(F²) pattern — see numpy-0002 for the join_by variant.

When does this matter?

Scientific pipelines that stack many structured arrays (e.g. HDF5 record batches, FITS tables, structured CSV readers) can pass hundreds of arrays each with dozens of fields, reaching millions of unnecessary comparisons.

Complexity table

Arrays (A)	Fields (F)	list ops	set ops	Speedup
10	50	~12,500	500	25×
50	100	~250,000	5,000	50×
100	200	~2,000,000	20,000	100×
500	500	~62,500,000	250,000	250×

Fix

Replace seen = [] with seen = set() and use in/.add():

# Fixed
seen = set()                                # FIX: O(1) membership
for (a, n, i, j) in zip(seqarrays, fldnames, offset[:-1], offset[1:]):
    names = a.dtype.names
    if names is None:
        output[f'f{len(seen)}'][i:j] = a
    else:
        for name in n:
            output[name][i:j] = a[name]
            if name not in seen:            # O(1) set probe
                seen.add(name)

set.add() and name not in seen are both O(1) amortised. The only change is the data structure; the ordering semantics of len(seen) for synthetic name generation (f0, f1, …) are preserved because set cardinality is tracked identically.

3.1 KiB Raw Permalink Blame History Unescape Escape