Compile time Table[A, B] lookup performance

[zevv]

Trying to pinpoint performance issues in my code I found that table lookups at compile are suffering from some strange behaviour: the snippet below places 1000 objects in a table and looks them up again. Filling the table is fast, but the 1000 lookups take about 12 seconds on my machine. The interesting part is that lookup time does not seem related to the key, but only to the object size: doubling the size of array a in the object Flop will result in roughly double the compile time.

import tables

type Flop = object 
  a: array[128, int]  # <-- compile time is proportional to array size

proc hop(): bool =
  var v: Table[int, Flop]

  echo "create"
  for i in 1..1000:
    v.add i, Flop()

  echo "search"
  for i in 1..1000:
    discard contains(v, i)

  echo "done"

const r = hop()

[krux02]

I did some investigations, and it seems that the compiler uses most of the time copying values around. This seems to be related to value types in Nim and the VM. You can work around this problem my not using value types (TableRef).

import tables

type Flop = object
  a: array[128, int]

proc hop(): bool =
  var v = newTable[int, Flop]()

  echo "create"
  for i in 1..1000:
    v.add i, Flop()

  echo "search"
  for i in 1..1000:
    discard hasKey(v, i)

  echo "done"

const r = hop()

This program is now instant again.