UNDF: UNDF-2026-000000690

UNDF: (pending)

numpy-0002: join_by — names list rebuilt inside loop + .index() O(F²)

CWE-407 — Algorithmic Complexity: O(F²) list rebuild + linear search in join_by

Field	Value
ID	numpy-0002
Severity	MEDIUM
Ecosystem	numpy
Package	`numpy`
File	`numpy/lib/recfunctions.py`
Lines	1602–1628, 1636–1648
Complexity	O(F²) on F total fields across the two joined arrays
Hot path	`join_by()` — join two structured arrays on a key field

Background

join_by(key, r1, r2) joins two NumPy structured arrays on one or more key fields, analogous to a SQL join. It constructs the output dtype by iterating over fields in r2 and checking for collisions with fields already in ndtype.

Defect — site 1: names list rebuild inside loop

# numpy/lib/recfunctions.py  lines 1606–1628
# Add the fields from r2
for fname, fdtype in _get_fieldspec(r2.dtype):
    # we need to rebuild this list every time         ← comment in source
    names = [name for name, dtype in ndtype]          # DEFECT: O(F) rebuild per iteration
    try:
        nameidx = names.index(fname)                  # DEFECT: O(F) linear search
    except ValueError:
        ndtype.append((fname, fdtype))
    else:
        # collision handling ...
        ndtype[nameidx:nameidx + 1] = [...]

For F2 fields in r2 and F1 fields already in ndtype, the rebuild + .index() costs O(F1 + F2) per iteration, totalling O(F2 × (F1 + F2)) = O(F²).

The comment "we need to rebuild this list every time" was added because collision handling mutates ndtype (splice at nameidx), but this does not require a full list reconstruction — an O(1) dict/index update suffices.

Defect — site 2: tuple `not in` scan in output assembly

# numpy/lib/recfunctions.py  lines 1636–1648
names = output.dtype.names      # tuple of all output field names
for f in r1names:
    selected = s1[f]
    if f not in names or ...:   # O(|names|) tuple scan
        f += r1postfix
    ...
for f in r2names:
    selected = s2[f]
    if f not in names or ...:   # O(|names|) tuple scan
        f += r2postfix
    ...

output.dtype.names is a tuple; f not in names scans it linearly. Called for every field in both arrays: O((F1+F2)×F_total).

Complexity table

F (total fields)	list ops	dict ops	Speedup
50	~2,500	50	50×
200	~40,000	200	200×
500	~250,000	500	500×
1,000	~1,000,000	1,000	1,000×

Fix

Build a name-to-index dict alongside ndtype and keep it updated:

# Fixed
ndtype = _get_fieldspec(r1k.dtype)

# Add r1 fields
for fname, fdtype in _get_fieldspec(r1.dtype):
    if fname not in key:
        ndtype.append((fname, fdtype))

# Build index dict once — O(F) total
name_to_idx = {name: i for i, (name, _) in enumerate(ndtype)}

# Add r2 fields using O(1) dict lookup
for fname, fdtype in _get_fieldspec(r2.dtype):
    if fname not in name_to_idx:                 # O(1)
        name_to_idx[fname] = len(ndtype)
        ndtype.append((fname, fdtype))
    else:
        nameidx = name_to_idx[fname]
        _, cdtype = ndtype[nameidx]
        if fname in key:
            ndtype[nameidx] = (fname, max(fdtype, cdtype))
            name_to_idx[fname] = nameidx          # unchanged
        else:
            ndtype[nameidx:nameidx + 1] = [
                (fname + r1postfix, cdtype),
                (fname + r2postfix, fdtype)
            ]
            # Rebuild index for names shifted by the splice — O(F) once
            name_to_idx = {n: i for i, (n, _) in enumerate(ndtype)}

# Site 2: convert output dtype names tuple to set once
names_set = set(output.dtype.names)              # O(F) once
for f in r1names:
    if f not in names_set or ...:                # O(1)
        f += r1postfix
    ...
for f in r2names:
    if f not in names_set or ...:                # O(1)
        f += r2postfix
    ...

4 KiB Raw Permalink Blame History Unescape Escape