java-topology/docs/tickets/lua-0001-searchupvalue-linear-scan-per-reference.md

lua-0001: searchupvalue() O(n) linear scan per variable reference during compilation

Target: lua/lua Severity: LOW-MEDIUM CWE: CWE-407 (Inefficient Algorithmic Complexity) File: lparser.c — searchupvalue() (~line 360), called from singlevaraux() Status: PATCHED

Description

During Lua compilation, every reference to a variable name goes through singlevaraux() → searchupvalue(). searchupvalue() performs a linear scan of the FuncState.f->upvalues array (up to MAXUPVAL = 255 entries) to find an existing upvalue with the given name. A function with many upvalues that references them frequently (e.g. in a tight inner loop body) pays O(n) per reference at compile time. With M references and N upvalues: O(M × N).

Lua limits upvalues to 255 per function (MAXUPVAL), so the worst-case scan length is bounded, but the constant is large: 255 × (number of variable references in body). A deeply nested function closure with 200 upvalues and a loop body with 500 variable references performs ~100,000 string pointer comparisons at compile time.

Root cause

/* lparser.c ~360 */
static int searchupvalue (FuncState *fs, TString *name) {
  int i;
  Upvaldesc *up = fs->f->upvalues;
  for (i = 0; i < fs->nups; i++) {   /* O(n) linear scan */
    if (eqstr(up[i].name, name)) return i;
  }
  return -1;
}

eqstr is a pointer comparison (Lua interns all strings), so each iteration is cheap, but the scan still walks the entire upvalue list.

Fix

Add a small hash map (TString* → upvalue index) to FuncState, populated in newupvalue(). searchupvalue() becomes a single hash lookup.

Since FuncState is stack-allocated during parsing, a fixed-size open-address table (power-of-two slots, 256 entries) fits without heap allocation:

/* In FuncState (lparser.h): */
int upval_map[256];   /* slot → upvalue index; -1 = empty */

/* newupvalue(): after allocating */
int slot = luaO_str2num(name) & 255;   /* or name->hash & 255 */
/* linear probe on collision */
upval_map[slot] = fs->nups - 1;

/* searchupvalue(): */
static int searchupvalue (FuncState *fs, TString *name) {
  int slot = name->hash & 255;
  /* probe up to 8 slots */
  for (int probe = 0; probe < 8; probe++, slot = (slot+1)&255) {
      int idx = fs->upval_map[slot];
      if (idx < 0) return -1;
      if (eqstr(fs->f->upvalues[idx].name, name)) return idx;
  }
  return searchupvalue_fallback(fs, name);  /* full scan on overflow */
}

Ops numbers (Java benchmark)

See defects/lua/unit/LuaTest.java (bench label "searchupvalue"). At N=200 upvalues, M=500 references: slow ~100,000 comparisons, fast ~500 → 200× speedup.