resolve variables by index

[MatheusRich]

Our resolver calculates which environment the variable is found in, but it’s still looked up by name in that map. A more efficient environment representation would store local variables in an array and look them up by index.

Extend the resolver to associate a unique index for each local variable declared in a scope. When resolving a variable access, look up both the scope the variable is in and its index and store that. In the interpreter, use that to quickly access a variable by its index instead of using a map.

[MatheusRich]

https://github.com/munificent/craftinginterpreters/tree/master/note/answers/chapter11_resolving/4/com/craftinginterpreters

[MatheusRich]

This simple benchmark suggests I'll see 1.5-3x improvement with the change. It will be fun to compare with real results.

alias LangValue = Int32 | Hash(String, LangValue)
alias AnyEnv = Env | IndexedEnv

abstract class Expr
  abstract def eval(env : AnyEnv) : LangValue
end

class Literal < Expr
  def initialize(@value : LangValue)
  end

  def eval(env : AnyEnv) : LangValue
    @value
  end
end

class Var < Expr
  def initialize(@name : String, @index : Int32? = nil)
  end

  def eval(env : AnyEnv) : LangValue
    env.get(@name, @index)
  end
end

class Assign < Expr
  def initialize(@name : String, @value : Expr, @index : Int32? = nil)
  end

  def eval(env : AnyEnv) : LangValue
    val = @value.eval(env)
    env.set(@name, val, @index)
    val
  end
end

class Binary < Expr
  enum Op
    Add
    Less
  end

  def initialize(@op : Op, @left : Expr, @right : Expr)
  end

  def eval(env : AnyEnv) : LangValue
    l = @left.eval(env)
    r = @right.eval(env)
    case @op
    when .add?  then l.as(Int32) + r.as(Int32)
    when .less? then (l.as(Int32) < r.as(Int32) ? 1 : 0)
    else
      raise "Unknown operator"
    end
  end
end

class While < Expr
  def initialize(@cond : Expr, @body : Array(Expr))
  end

  def eval(env : AnyEnv) : LangValue
    while @cond.eval(env) != 0
      @body.each(&.eval(env))
    end
    0
  end
end

class Block < Expr
  def initialize(@exprs : Array(Expr))
  end

  def eval(env : AnyEnv) : LangValue
    result = 0
    @exprs.each { |e| result = e.eval(env) }
    result
  end
end

class Record < Expr
  def initialize(@fields : Hash(String, Expr))
  end

  def eval(env : AnyEnv) : LangValue
    obj = {} of String => LangValue
    @fields.each { |name, expr| obj[name] = expr.eval(env) }
    obj
  end
end

class FieldGet < Expr
  def initialize(@target : Expr, @field : String)
  end

  def eval(env : AnyEnv) : LangValue
    obj = @target.eval(env).as(Hash(String, LangValue))
    obj[@field]
  end
end

class FieldSet < Expr
  def initialize(@target : Expr, @field : String, @value : Expr)
  end

  def eval(env : AnyEnv) : LangValue
    obj = @target.eval(env).as(Hash(String, LangValue))
    val = @value.eval(env)
    obj[@field] = val
    val
  end
end

class Env
  property vars = {} of String => LangValue

  def get(name : String, index : Int32? = nil) : LangValue
    vars[name]? || 0
  end

  def set(name : String, value : LangValue, index : Int32? = nil)
    vars[name] = value
  end
end

class IndexedEnv
  property vars : Array(LangValue)
  property name_to_index : Hash(String, Int32)

  def initialize(names : Array(String))
    @vars = Array(LangValue).new(names.size, 0)
    @name_to_index = {} of String => Int32
    names.each_with_index do |name, i|
      @name_to_index[name] = i
    end
  end

  def get(name : String, index : Int32? = nil) : LangValue
    idx = index || name_to_index[name]
    vars[idx]
  end

  def set(name : String, value : LangValue, index : Int32? = nil)
    idx = index || name_to_index[name]
    vars[idx] = value
  end
end

ast = Block.new([
  Assign.new("x", Literal.new(0), 0),
  Assign.new("i", Literal.new(0), 1),

  While.new(
    Binary.new(Binary::Op::Less, Var.new("i", 1), Literal.new(10_000)),
    [
      Assign.new("x", Binary.new(Binary::Op::Add, Var.new("x", 0), Var.new("i", 1)), 0),
      Assign.new("i", Binary.new(Binary::Op::Add, Var.new("i", 1), Literal.new(1)), 1),
    ] of Expr
  ),

  Var.new("x", 0),
])

require "benchmark"

Benchmark.ips do |x|
  x.report("hash env: while loop") do
    env1 = Env.new
    ast.eval(env1)
  end
  x.report("array env: while loop") do
    env2 = IndexedEnv.new(["x", "i"])
    ast.eval(env2)
  end
end

fib_ast = Block.new([
  Assign.new("a", Literal.new(0), 0),
  Assign.new("b", Literal.new(1), 1),
  Assign.new("i", Literal.new(0), 2),

  While.new(
    Binary.new(Binary::Op::Less, Var.new("i", 2), Literal.new(2)),
    [
      Assign.new("tmp", Var.new("b", 1), 3),
      Assign.new("b", Binary.new(Binary::Op::Add, Var.new("a", 0), Var.new("b", 1)), 1),
      Assign.new("a", Var.new("tmp", 3), 0),
      Assign.new("i", Binary.new(Binary::Op::Add, Var.new("i", 2), Literal.new(1)), 2),
    ] of Expr
  ),

  Var.new("a", 0), # return a
])
Benchmark.ips do |x|
  x.report("hash env: fib") do
    env1 = Env.new
    fib_ast.eval(env1)
  end
  x.report("array env: fib") do
    env2 = IndexedEnv.new(["a", "b", "i", "tmp"])
    fib_ast.eval(env2)
  end
end

richards_ast = Block.new([
  # task_map = {}
  Assign.new("task_map", Record.new({} of String => Expr), 0),

  # scheduler = []
  Assign.new("scheduler", Record.new({} of String => Expr), 1),

  # Create Task1
  Assign.new("task", Record.new({
    "id"        => Literal.new(1),
    "state"     => Literal.new(1),
    "msg_queue" => Record.new({} of String => Expr),
  }), 2),
  FieldSet.new(Var.new("task_map", 0), "1", Var.new("task", 2)),
  FieldSet.new(Var.new("scheduler", 1), "1", Var.new("task", 2)),

  # Create Task2
  Assign.new("task", Record.new({
    "id"        => Literal.new(2),
    "state"     => Literal.new(1),
    "msg_queue" => Record.new({} of String => Expr),
  }), 2),
  FieldSet.new(Var.new("task_map", 0), "2", Var.new("task", 2)),
  FieldSet.new(Var.new("scheduler", 1), "2", Var.new("task", 2)),

  # loop_counter = 0
  Assign.new("loop_counter", Literal.new(0), 6),

  # while loop_counter < 10000
  While.new(
    Binary.new(Binary::Op::Less, Var.new("loop_counter", 6), Literal.new(10000)),
    [
      # for each task in scheduler
      Assign.new("task", FieldGet.new(Var.new("scheduler", 1), "1"), 2),

      # msg = { sender: 0, data: loop_counter }
      Assign.new("msg", Record.new({
        "sender" => Literal.new(0),
        "data"   => Var.new("loop_counter", 6),
      }), 3),

      # enqueue msg to task's msg_queue
      FieldSet.new(FieldGet.new(Var.new("task", 2), "msg_queue"), "msg", Var.new("msg", 3)),

      # simulate message processing: task.state = task.state + 1
      Assign.new("state", FieldGet.new(Var.new("task", 2), "state"), 5),
      FieldSet.new(Var.new("task", 2), "state",a
        Binary.new(Binary::Op::Add, Var.new("state", 5), Literal.new(1))
      ),

      # reschedule task
      FieldSet.new(Var.new("scheduler", 1), "1", Var.new("task", 2)),

      # loop_counter += 1
      Assign.new("loop_counter",
        Binary.new(Binary::Op::Add, Var.new("loop_counter", 6), Literal.new(1)), 6
      ),
    ]
  ),

  # return final state value of task 1
  FieldGet.new(
    FieldGet.new(Var.new("task_map", 0), "1"),
    "state"
  ),
])

Benchmark.ips do |x|
  x.report("hash env: richards") do
    env1 = Env.new
    richards_ast.eval(env1)
  end
  x.report("array env: richards") do
    env2 = IndexedEnv.new(["task_map", "scheduler", "task", "msg", "new_msg", "state", "loop_counter"])
    richards_ast.eval(env2)
  end
end