for ai in a has quadratic complexity in VM when a is const

[timotheecour]

this is the root cause for #16703 compilation 5x slower (33s => 171s for nim_temp c testament), which had occurred when the mimetypes.mimes constant (1800 elements) was used in a (single) for loop in VM.

Example

when true:
  import macros
  proc identity[T](a: T): T = a
  macro genData(n: static int): untyped =
    result = newNimNode(nnkBracket)
    for i in 0..<n: result.add newLit $i
  const n = 8000 # every time this doubles, compilation time quadruples (ie quadratic complexity)
  const arr = genData(n)

  proc fn() =
    # let arr = arr # would be fast with this
    for i in 0..<3:
      echo i
      for ai in arr: discard # slow! ditto with `items(arr)`
      # for ai in identity(arr): discard # would be fast!
  static: fn()

Current Output

n = 4000: 5s
n = 8000: 18s
n = 16000: 70s

Expected Output

linear instead of quadratic complexity

workaround

transform the const used in VM into a var/let either via let arr = arr or using identity(arr) instead of arr

Additional Information

1.5.1 2b5841c

adding medium priority because this bug is easy to go un-noticed and can drastically affect compile times; in other words fixing this can significantly improve compile times in case your code uses a const in VM with for ai in a

what probably happens is that the const value is copy/pasted in each iteration, which exactly would explain the quadratic complexity

[juancarlospaco]

If it is const then is known at compile time,
if it is known at compile time then it can be unrolled,
this needs loop unrolling, like C/C++/Pascal had for decades.

[timotheecour]

this needs loop unrolling, like C/C++/Pascal had for decades.

that's a separate and broader issue; this issue concerns only for ai in a running in VM with a const a, whereas loop unrolling would concern for ai in a running in RT (and perhaps also VM but less critical) where a is const (or more generally when a.len is known at CT such as an array, not necessarily const)

[shirleyquirk]

Same issue https://forum.nim-lang.org/t/8003, the quadratic code here:

Nim/compiler/vmgen.nim

Lines 475 to 479 in df429fa

	proc genLiteral(c: PCtx; n: PNode): int =
	# types do not matter here:
	for i in 0..<c.constants.len:
	if sameConstant(c.constants[i], n): return i
	result = rawGenLiteral(c, n)

[juancarlospaco]

Maybe start marking those places with something like # TODO: PERFORMANCE quadratic complexity.
People often pass by focused on fixing bugs, but maybe for 2.0 a more aggressive refactoring can happen...

[Araq]

So ... Instead of fixing the bug, we will tell you exactly the source location where it hides? Maybe ideas are better when they have a connection to reality, I dunno.

[juancarlospaco]

I agree, I am talking when it means a break on the public API of the module.