Some weeks ago, I started writing a simple webserver in Elixir. One of the challenges was building a JSON deserializer. To keep things organized, I separated the logic into two steps:

tokenize → parse

Elixir is a functional language with immutable variables and no traditional loops. To iterate, you rely on recursion and creating new values. This becomes important when dealing with performance.

The Problem: Parsing Lists in Elixir

Take this simplified version of my parse_list function:

1
defp parse_list([{token_type, value} | rest], list) do
2
  case token_type do
3
    type when type in [:string, :number] ->
4
      parse_list(rest, [value | list])  # append at the head (O(1))
5

6
    # other cases...
7
  end
8
end

In Elixir, lists are linked lists. Appending to the end (list ++ [value]) is O(n), so we prepend instead ([value | list]) which is O(1).

But this introduces a problem:

• Input: [1, 2, 3]
• Parsed result: [3, 2, 1] (it’s reversed)

To fix this, I reversed the list again once parsing was finished:

1
defp parse_list([{token_type, value} | rest], list) do
2
  case token_type do
3
    :closed_list ->
4
      {rest, Enum.reverse(list)}
5

6
    type when type in [:string, :number] ->
7
      parse_list(rest, [value | list])
8

9
    # ...
10
  end
11
end

This got me thinking:

If I have a huge JSON list, I traverse it once… and then reverse it again. That’s two full passes. Is this slow? Should I optimize further (e.g., use a stack)?

Time to benchmark.

Talking Is Easy, Show me the data.

Let’s process 10 million JSON items.

1
test "kaboom" do
2
  list =
3
    0..9_999_999
4
    |> Enum.map(fn _ -> "\"a\"" end)
5
    |> Enum.join(",")
6

7
  input = ~s({
8
    "foo": [#{list}]
9
  })
10

11
  tokens = JsonParser.tokenize(input)
12

13
  {microseconds, json} =
14
    :timer.tc(fn ->
15
      JsonParser.parse(tokens)
16
    end)
17

18
  milliseconds = microseconds / 1_000
19
  IO.puts("Parse time: #{milliseconds} ms")
20

21
  assert Map.has_key?(json, :foo)
22
  assert length(json.foo) == 10_000_000
23
end

The output:

466.635 ms

Not bad for parsing 10 million items. But what if I remove the final Enum.reverse(list) step?

The performance improved by… only ~30 ms.

fuck.

⡴⠒⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠉⠳⡆⠀
⣇⠰⠉⢙⡄⠀⠀⣴⠖⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣆⠁⠙⡆
⠘⡇⢠⠞⠉⠙⣾⠃⢀⡼⠀⠀⠀⠀⠀⠀⠀⢀⣼⡀⠄⢷⣄⣀⠀⠀⠀⠀⠀⠀⠀⠰⠒⠲⡄⠀⣏⣆⣀⡍
⠀⢠⡏⠀⡤⠒⠃⠀⡜⠀⠀⠀⠀⠀⢀⣴⠾⠛⡁⠀⠀⢀⣈⡉⠙⠳⣤⡀⠀⠀⠀⠘⣆⠀⣇⡼⢋⠀⠀⢱
⠀⠘⣇⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡴⢋⡣⠊⡩⠋⠀⠀⠀⠣⡉⠲⣄⠀⠙⢆⠀⠀⠀⣸⠀⢉⠀⢀⠿⠀⢸
⠀⠀⠸⡄⠀⠈⢳⣄⡇⠀⠀⢀⡞⠀⠈⠀⢀⣴⣾⣿⣿⣿⣿⣦⡀⠀⠀⠀⠈⢧⠀⠀⢳⣰⠁⠀⠀⠀⣠⠃
⠀⠀⠀⠘⢄⣀⣸⠃⠀⠀⠀⡸⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠈⣇⠀⠀⠙⢄⣀⠤⠚⠁⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡀⠀⠀⢘⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⢰⣿⣿⣿⡿⠛⠁⠀⠉⠛⢿⣿⣿⣿⣧⠀⠀⣼⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡀⣸⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣿⡀⢀⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡇⠹⠿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⡿⠁⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣤⣞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢢⣀⣠⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠲⢤⣀⣀⠀⢀⣀⣀⠤⠒⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

30 ms across 10 million elements is… almost nothing. You can’t see it. You can’t feel it. Your program will not suddenly become a rocket ship.

Yes, reversing a list makes the algorithm technically slower. But the difference is not meaningful for most workloads.

So, the lesson here is:

Benchmark your code before optimizing what doesn’t matter.