Dict comparison slower on JS target

[richard-viney]

While doing some benchmarking I found that comparing two identical Dicts can be 10-12x slower than Erlang.

Profiling showed the time is 60-70% in the iteration over the dict's contents. Does anyone know what the expected tradeoffs are of the Dict implementation on JS (it seems to be a custom HashMap implementation, in dict.mjs), or are performance differences between the two targets unavoidable here?

I also tested a native Map<number, number> in JS but it was still 4x slower than Erlang. Perhaps Erlang's maps are just faster, or it may be due to the value equality check needing to be implemented manually in JS, whereas on Erlang it's provided by the VM.

Here's some code which Erlang runs in 0.45 seconds, and JavaScript in 5.2 seconds. It compares two identical 10,000 entry dicts:

import birl
import gleam/dict.{type Dict}
import gleam/int
import gleam/io
import gleam/list

pub fn main() {
  let dict_keys = list.range(0, 10_000)
  let d1 = make_simple_dict(dict_keys)
  let d2 = make_simple_dict(dict_keys)

  let started_at = birl.monotonic_now()
  compare_dicts(d1, d2, 10_000)
  let elapsed_time = int.to_string({ birl.monotonic_now() - started_at } / 1000)

  io.println("Time: " <> elapsed_time <> " ms")
}

fn make_simple_dict(keys: List(Int)) {
  list.fold(keys, dict.new(), fn(d, i) { dict.insert(d, i, i) })
}

fn compare_dicts(d1: Dict(Int, Int), d2: Dict(Int, Int), n: Int) -> Int {
  case d1 == d2 {
    True ->
      case n {
        0 -> 0
        _ -> compare_dicts(d1, d2, n - 1)
      }
    False -> panic as "Dicts are expected to be equal"
  }
}

[lpil]

I'm surprised the gap isn't bigger! One is implemented in C and the other in JavaScript.

Did you have some idea for improving performance of the JavaScript one?

[richard-viney]

I haven't yet looked into the Dict implementation to comment on performance improvements, it looks conceptually similar to Immutable.js' map implementation, so I might see if the two have similar performance characteristics, and if Immutable.js is faster then try to figure out why.

Re. the equality check, there's a win to be had by returning as soon as any entry fails the equality check, which is implemented in gleam-lang/stdlib#738. Doesn't help in the test case above which compares identical dicts though, performance only improves when comparing dicts of the same size that aren't equal.