UNDF: UNDF-2026-000000480

numpy-0001: f2py _get_depend_dict — O(n²) linear dedup in dependency resolution

Severity: MEDIUM CWE: CWE-407 (Algorithmic Complexity — linear membership test in hot loop) Speedup: >30x at V=500 variables Target: NumPy (numpy/numpy) File: numpy/f2py/crackfortran.py:2352-2371

Description

_get_depend_dict builds a transitive dependency list for each Fortran variable. It accumulates results in words (a plain list) and checks membership with if w not in words on every insertion. Because words also grows during the inner loop (via words.append(w)), each iteration scans the entire accumulated list, producing O(V²) operations for V total dependencies.

_calc_depend_dict calls _get_depend_dict once per variable in vars, making the total complexity O(V²) per variable and O(V³) over the whole module in the worst case. For large Fortran modules (dozens of inter-dependent variables), this is the dominant cost in f2py processing.

Root Cause

# numpy/f2py/crackfortran.py:2362-2366
for word in words[:]:                       # outer pass over current words
    for w in deps.get(word, []) \
            or _get_depend_dict(word, vars, deps):
        if w not in words:                  # O(|words|) linear scan per w
            words.append(w)                 # words grows — next iteration scans more

words is a list. Each w not in words scans from index 0. As words grows to length W, the W-th insertion costs O(W). Total cost: O(1+2+…+W) = O(W²).

Fix: maintain a parallel set alongside words for O(1) membership, keep the list only for deterministic ordering.

Patch

def _get_depend_dict(name, vars, deps):
    if name in vars:
        words = list(vars[name].get('depend', []))
        words_set = set(words)                   # O(1) membership

        if '=' in vars[name] and not isstring(vars[name]):
            for word in word_pattern.findall(vars[name]['=']):
                if word not in words_set and word in vars and word != name:
                    words.append(word)
                    words_set.add(word)
        for word in words[:]:
            for w in deps.get(word, []) \
                    or _get_depend_dict(word, vars, deps):
                if w not in words_set:
                    words.append(w)
                    words_set.add(w)
    else:
        outmess(f'_get_depend_dict: no dependence info for {repr(name)}\n')
        words = []
    deps[name] = words
    return words

Complexity Before

_get_depend_dict: O(W²) per variable (W = transitive dependency count) _calc_depend_dict: O(V × W²) total

Complexity After

_get_depend_dict: O(W) per variable _calc_depend_dict: O(V × W) total

Reproduction

cd defects/numpy/unit && javac -d . *.java && java -ea unit.NumpyTest

2.8 KiB Raw Permalink Blame History Unescape Escape