I’m no expert, please correct me if I’m wrong.

I think it’s mostly because ets not really a data structure like map or list. With map everytime you overwrite a value, you have to GC old term (when it hits the threshold). Also likely we cross initial process heap size inbetween. On the other hand Ets is mutable and lives outside process memory, gc is no longer relevant and updates are truly updates in-memory, unlike maps, where update creates a new map (even though it’s optimized and doesn’t actually copy whole thing, there is still non zero overhead)

Anyway, today realised that, without measuring and proving it’s hard to make predictions/guesses about performance (like the one i made above:)). I tired multiple things today for part two to improve from 30s (using map), guessing what might be the bottleneck. And none of them improved performance much (max improvement i got was 5-6s)

Mainly I tried:

• Since accessing keys from “spoken map” is not equally distributed (some keys are accessed often than rest, such as 0,1,2,3), I tried creating a cache for these keys, to reduce lookups and updates to map
• map.get_and_update so we can lookup and update on one pass. (I know it’s constant, but wanted to still reduce potential overhead)
• tried erlang array

I dislike using ets for solving these sort of questions, because it’s an escape hatch. I prefer solving with proper functional data structure (part of the appeal)

That felt pretty weird after the last couple of days to get to part 2 and just have to update the end turn. At least I feel pretty happy about the implementation (not for speed though, looking forward to see if someone posts something clever for a fast solution).

Recursively run iterate until end turn. Took around 30s on Macbook Pro Intel and 15s on a new Macbook Air M1 (running from iex):

defmodule AdventOfCode.Day15 do
  @end_turn 30_000_000 - 1

  def run(input) do
    input
    |> String.split(",", trim: true)
    |> Enum.map(&String.to_integer/1)
    |> iterate(0, %{})
  end

  def iterate([speak], @end_turn, _history), do: speak

  def iterate([speak], turn, history) do
    next = turn - Map.get(history, speak, turn)
    iterate([next], turn + 1, Map.put(history, speak, turn))
  end

  def iterate([speak | rest], turn, history) do
    iterate(rest, turn + 1, Map.put(history, speak, turn))
  end
end

My original brute force solution for part two took about 41 seconds to run (using a map to keep the necessary history). I couldn’t come up with a clever solution, so I did the thing we are not supposed to do and I used the process dictionary for my data structure and got an impressive speed boost using the same algorithm!

MAP :
Name           ips        average  deviation         median         99th %
1           2.03 K      0.00049 s    ±23.90%      0.00047 s      0.00093 s
2        0.00002 K        41.78 s     ±0.00%        41.78 s        41.78 s

PROCESS DICTIONARY :
Name           ips        average  deviation         median         99th %
1           6.28 K      0.00016 s    ±27.22%      0.00014 s      0.00029 s
2        0.00007 K        14.87 s     ±0.00%        14.87 s        14.87 s

Solution using atomics is under 3s on my comp.

I did that at first too, just in case, but after seeing part 2 I confirmed that you don’t need to save the entire history for each number. But removing that didn’t make it any faster…