← All posts

Comprehensively redesign IsPrimeServer - sdball/protohackers

Commit a72e300 from github.com/sdball/protohackers

The first major issue was that the protohackers challenges threw a literal zero at my prime number module I stole from the Internet. That prime number module assumed integers >= 1 and a literal zero meant a literal divide by zero.

Did the server keep running? Yes it did. But did the client get an answer to that request? No it did not.

The second major issue is that I thought I needed to redesign how I was parsing sent bytes to check for the ASCII character ‘\n’ vs the binary character “\n”. But that turns out to be a mistake on my part. The literal ‘\n’ (ASCII 10, line feed, new line, etc) is not equal to “\n” but that’s because no bitstring is equal to the “same” binary.

> "a" == 'a' # => false

The effect of that mistake is that the line handling code in IsPrimeServer is more complex and guarded than it probably needs to be.

The third major issue is that the original prime number module I stole from the Internet is AMAZINGLY SLOW. My poor server was spending minutes trying to serve thousands of requests that expected to be completed in seconds.

I found another module to steal from the Internet and its performance is much faster. Like, MUCH, faster. Over 600,000 times faster.

Benchmarking PrimeFactors ...
Benchmarking PrimeNumbers ...

Name                   ips        average  deviation         median         99th %
PrimeNumbers        4.92 M     0.00020 ms ±14638.15%     0.00017 ms     0.00025 ms
PrimeFactors     0.00001 M      129.39 ms     ±0.19%      129.31 ms      130.18 ms

Comparison:
PrimeNumbers        4.92 M
PrimeFactors     0.00001 M - 636398.34x slower +129.39 ms

So really I overcomplicated the fixes from my original attempt. I really only needed to

I’m leaving the complexity of my current code for now and all the logging output. When I revisit I’ll see if I can organize the module a bit better and make it all more readable and less overly complicated.

Happily along the way I also dug into fly.toml and figured out how to connect multiple external ports to multiple internal ports. Yay!

a72e3000e7225b0acaaf6db5bd6ba38efbd83d89 on sdball/protohackers

added files

benchmark/primes.exs

Benchee.run(%{
  "PrimeFactors" => fn -> PrimeFactors.is_prime?(86358305) end,
  "PrimeNumbers" => fn -> PrimeNumbers.is_prime?(86358305) end
}, time: 3)

lib/prime_numbers.ex

defmodule PrimeNumbers do
  def is_prime?(2), do: true
  def is_prime?(3), do: true

  def is_prime?(x) when is_integer(x) and x > 3 do
    from = 2
    to = trunc(:math.sqrt(x))
    n_total = to - from + 1

    n_tried =
      Enum.take_while(from..to, fn i -> rem(x, i) != 0 end)
      |> Enum.count()

    n_total == n_tried
  end

  def is_prime?(x) when is_integer(x), do: false

  def is_prime?(x) when is_float(x), do: false

  def is_prime?(_anything), do: false
end

test/prime_numbers_test.exs

defmodule PrimeNumbersTest do
  use ExUnit.Case, async: true

  test "zero is not prime" do
    assert PrimeNumbers.is_prime?(0) == false
  end

  test "negatives are not prime" do
    assert PrimeNumbers.is_prime?(-3) == false
  end

  test "identifies prime numbers and composite numbers" do
    assert PrimeNumbers.is_prime?(1) == false
    assert PrimeNumbers.is_prime?(2) == true
    assert PrimeNumbers.is_prime?(3) == true
    assert PrimeNumbers.is_prime?(4) == false
    assert PrimeNumbers.is_prime?(5) == true
    assert PrimeNumbers.is_prime?(16) == false
    assert PrimeNumbers.is_prime?(17) == true
    assert PrimeNumbers.is_prime?(59) == true
    assert PrimeNumbers.is_prime?(60) == false
    assert PrimeNumbers.is_prime?(61) == true
    assert PrimeNumbers.is_prime?(210) == false
    assert PrimeNumbers.is_prime?(211) == true
  end

  test "floats are not prime" do
    assert PrimeNumbers.is_prime?(1.123) == false
    assert PrimeNumbers.is_prime?(2.000) == false
  end

  test "words are not prime" do
    assert PrimeNumbers.is_prime?("two") == false
  end
end

modified files

fly.toml

diff --git a/fly.toml b/fly.toml
index 47fa649..69d463a 100644
--- a/fly.toml
+++ b/fly.toml
@@ -9,16 +9,13 @@ processes = []
 builder = "heroku/buildpacks:20"
 buildpacks = ["https://cnb-shim.herokuapp.com/v1/hashnuke/elixir"]

-[env]
-PORT = "8080"
-
 [experimental]
 allowed_public_ports = []
 auto_rollback = true

 [[services]]
 http_checks = []
-internal_port = 8080
+internal_port = 11235
 processes = ["app"]
 protocol = "tcp"
 script_checks = []
@@ -26,11 +23,28 @@ script_checks = []
 hard_limit = 25
 soft_limit = 20
 type = "connections"
-
 [[services.ports]]
 handlers = []
-port = "8080"
+port = "11235"
+[[services.tcp_checks]]
+grace_period = "1s"
+interval = "15s"
+restart_limit = 0
+timeout = "2s"

+[[services]]
+http_checks = []
+internal_port = 11236
+processes = ["app"]
+protocol = "tcp"
+script_checks = []
+[services.concurrency]
+hard_limit = 25
+soft_limit = 20
+type = "connections"
+[[services.ports]]
+handlers = []
+port = "11236"
 [[services.tcp_checks]]
 grace_period = "1s"
 interval = "15s"

lib/prime_factors.ex

diff --git a/lib/prime_factors.ex b/lib/prime_factors.ex
index 61dafe8..7fcfe5e 100644
--- a/lib/prime_factors.ex
+++ b/lib/prime_factors.ex
@@ -3,12 +3,16 @@ defmodule PrimeFactors do
     factors(n, div(n, 2)) |> Enum.filter(&is_prime?/1) |> Enum.reverse()
   end

+  def is_prime?(0), do: false
   def is_prime?(1), do: false
+  def is_prime?(n) when is_integer(n) and n < 1, do: false

-  def is_prime?(n) do
+  def is_prime?(n) when is_integer(n) do
     factors(n, div(n, 2)) == [1]
   end

+  def is_prime?(_other), do: false
+
   defp factors(1, _), do: [1]
   defp factors(_, 1), do: [1]

lib/protohackers/application.ex

diff --git a/lib/protohackers/application.ex b/lib/protohackers/application.ex
index 0721b1d..cb3fd45 100644
--- a/lib/protohackers/application.ex
+++ b/lib/protohackers/application.ex
@@ -10,8 +10,10 @@ defmodule Protohackers.Application do
   end

   defp children(:prod) do
-    # right now I only now how to have one port open from fly.io
-    [{Protohackers.IsPrimeServer, 8080}]
+    [
+      {Protohackers.EchoServer, 11235},
+      {Protohackers.IsPrimeServer, 11236}
+    ]
   end

   defp children(_other) do

lib/protohackers/is_prime_server.ex

diff --git a/lib/protohackers/is_prime_server.ex b/lib/protohackers/is_prime_server.ex
index 790bea8..72e6eb0 100644
--- a/lib/protohackers/is_prime_server.ex
+++ b/lib/protohackers/is_prime_server.ex
@@ -7,7 +7,7 @@ defmodule Protohackers.IsPrimeServer do
     GenServer.start_link(__MODULE__, port)
   end

-  defstruct [:listen_socket, :supervisor]
+  defstruct [:listen_socket, :supervisor, task_id: 1]

   @impl true
   def init(port) do
@@ -22,7 +22,7 @@ defmodule Protohackers.IsPrimeServer do
       reuseaddr: true,
       # keep the peer socket open after the client closes its writes
       exit_on_close: false,
-      # receive data line by line
+      # automatically split inputs by newline
       packet: :line
     ]

@@ -41,11 +41,13 @@ defmodule Protohackers.IsPrimeServer do
   def handle_continue(:accept, %__MODULE__{} = state) do
     case :gen_tcp.accept(state.listen_socket) do
       {:ok, socket} ->
+        Logger.info("Starting Task.Supervisor child to handle connection #{state.task_id}")
+
         Task.Supervisor.start_child(state.supervisor, fn ->
-          handle_connection(socket)
+          handle_connection(socket, state.task_id)
         end)

-        {:noreply, state, {:continue, :accept}}
+        {:noreply, %{state | task_id: state.task_id + 1}, {:continue, :accept}}

       {:error, reason} ->
         Logger.error("Unable to accept connection #{inspect(reason)}")
@@ -53,52 +55,129 @@ defmodule Protohackers.IsPrimeServer do
     end
   end

-  defp handle_connection(socket) do
-    with {:ok, json} <- receive_line(socket),
-         {:ok, submitted_data} <-
-           Jason.decode(json),
-         {:ok, number} <-
-           validate_request(submitted_data) do
-      send_response(socket, number |> is_prime?)
-      handle_connection(socket)
+  def is_prime?(0), do: false
+
+  def is_prime?(number) when is_integer(number) and number > 0 do
+    PrimeNumbers.is_prime?(number)
+  end
+
+  def is_prime?(number) when is_integer(number) and number < 0 do
+    false
+  end
+
+  def is_prime?(number) when is_float(number), do: false
+
+  defp handle_connection(socket, task_id) do
+    with {:ok, received} <- receive_lines(socket, _buffer = "") do
+      case process_lines(socket, task_id, received) do
+        {:ok} ->
+          handle_connection(socket, task_id)
+
+        {:halt, :malformed} ->
+          Logger.error("task_id=#{task_id} : halting malformed")
+      end
     else
       {:error, :closed} ->
+        Logger.info("task_id=#{task_id} : socket closed")
         :gen_tcp.close(socket)

       {:error, :timeout} ->
+        Logger.info("task_id=#{task_id} : socket timeout")
         :gen_tcp.close(socket)

+      {:error, :exceeded_write_limit} ->
+        Logger.error("task_id=#{task_id} : exceeded write limit")
+        :gen_tcp.send(socket, "ERR_EXCEEDED_WRITE_LIMIT")
+        :gen_tcp.close(socket)
+
+      {:error, :enotconn} ->
+        Logger.error("task_id=#{task_id} : socket not connected")
+        :gen_tcp.close(socket)
+
+      _error ->
+        Logger.error("task_id=#{task_id} : unknown error")
+        :gen_tcp.close(socket)
+    end
+  end
+
+  defp process_lines(socket, task_id, received) do
+    data = IO.iodata_to_binary(received)
+    requests = String.split(data, "\n", trim: true)
+    parsed = Enum.map(requests, &parse_request(&1, task_id))
+
+    numbers =
+      Enum.take_while(parsed, fn
+        number when is_number(number) -> true
+        _ -> false
+      end)
+
+    numbers
+    |> Enum.each(fn number ->
+      prime? = is_prime?(number)
+      Logger.info("task_id=#{task_id} : response : #{number} prime? #{prime?}")
+      send_response(socket, prime?)
+    end)
+
+    # we've encountered a bad request: stop the works
+    if Enum.count(numbers) < Enum.count(requests) do
+      Logger.error("task_id=#{task_id} : invalid request detected")
+      :gen_tcp.send(socket, "malformed")
+      :gen_tcp.close(socket)
+      {:halt, :malformed}
+    else
+      {:ok}
+    end
+  end
+
+  @buffer_size_limit _100_kb = 1024 * 100
+
+  defp receive_lines(socket, buffer) do
+    buffered_size = IO.iodata_length(buffer)
+
+    case :gen_tcp.recv(socket, _bytes_to_read = 0, _timeout_millis = 30_000) do
+      {:ok, data} when buffered_size + byte_size(data) > @buffer_size_limit ->
+        {:error, :exceeded_write_limit}
+
+      {:ok, data} ->
+        dbg(data)
+
+        if String.ends_with?(data, "\n") do
+          {:ok, [buffer, data]}
+        else
+          receive_lines(socket, [buffer, data])
+        end
+
+      {:error, :closed} ->
+        {:ok, buffer}
+
+      {:error, reason} ->
+        {:error, reason}
+    end
+  end
+
+  defp parse_request(request, task_id) do
+    case Jason.decode(request) do
+      {:ok, decoded} ->
+        parse_decoded(decoded, task_id)
+
       {:error, %Jason.DecodeError{}} ->
-        :gen_tcp.send(socket, "malformed\n")
-        :gen_tcp.close(socket)
-
-      {:error, :invalid_request} ->
-        :gen_tcp.send(socket, "malformed\n")
-        :gen_tcp.close(socket)
+        Logger.error("task_id=#{task_id} : invalid request : #{inspect(request)}")
+        false
     end
   end

-  defp receive_line(socket) do
-    :gen_tcp.recv(socket, _bytes_to_read = 0, _timeout_millis = 10_000)
+  defp parse_decoded(%{"method" => "isPrime", "number" => number}, _task_id)
+       when is_number(number) do
+    number
   end

-  defp validate_request(%{"method" => "isPrime", "number" => number}) when is_number(number) do
-    {:ok, number}
-  end
-
-  defp validate_request(_malformed) do
-    {:error, :invalid_request}
+  defp parse_decoded(invalid_json, task_id) do
+    Logger.error("task_id=#{task_id} : invalid json: #{inspect(invalid_json)}")
+    nil
   end

   defp send_response(socket, is_prime) do
     response = %{method: "isPrime", prime: is_prime} |> Jason.encode!()
     :gen_tcp.send(socket, "#{response}\n")
   end
-
-  defp is_prime?(number) when is_integer(number) do
-    Code.ensure_loaded!(PrimeFactors)
-    PrimeFactors.is_prime?(number)
-  end
-
-  defp is_prime?(number) when is_float(number), do: false
 end

mix.exs

diff --git a/mix.exs b/mix.exs
index f57206a..dc8bed3 100644
--- a/mix.exs
+++ b/mix.exs
@@ -22,7 +22,8 @@ defmodule Protohackers.MixProject do
   # Run "mix help deps" to learn about dependencies.
   defp deps do
     [
-      {:jason, "~> 1.4.0"}
+      {:jason, "~> 1.4.0"},
+      {:benchee, "~> 1.1.0", only: :dev}
     ]
   end
 end

mix.lock

diff --git a/mix.lock b/mix.lock
index 8ab831f..e8f9f63 100644
--- a/mix.lock
+++ b/mix.lock
@@ -1,3 +1,6 @@
 %{
+  "benchee": {:hex, :benchee, "1.1.0", "f3a43817209a92a1fade36ef36b86e1052627fd8934a8b937ac9ab3a76c43062", [:mix], [{:deep_merge, "~> 1.0", [hex: :deep_merge, repo: "hexpm", optional: false]}, {:statistex, "~> 1.0", [hex: :statistex, repo: "hexpm", optional: false]}], "hexpm", "7da57d545003165a012b587077f6ba90b89210fd88074ce3c60ce239eb5e6d93"},
+  "deep_merge": {:hex, :deep_merge, "1.0.0", "b4aa1a0d1acac393bdf38b2291af38cb1d4a52806cf7a4906f718e1feb5ee961", [:mix], [], "hexpm", "ce708e5f094b9cd4e8f2be4f00d2f4250c4095be93f8cd6d018c753894885430"},
   "jason": {:hex, :jason, "1.4.0", "e855647bc964a44e2f67df589ccf49105ae039d4179db7f6271dfd3843dc27e6", [:mix], [{:decimal, "~> 1.0 or ~> 2.0", [hex: :decimal, repo: "hexpm", optional: true]}], "hexpm", "79a3791085b2a0f743ca04cec0f7be26443738779d09302e01318f97bdb82121"},
+  "statistex": {:hex, :statistex, "1.0.0", "f3dc93f3c0c6c92e5f291704cf62b99b553253d7969e9a5fa713e5481cd858a5", [:mix], [], "hexpm", "ff9d8bee7035028ab4742ff52fc80a2aa35cece833cf5319009b52f1b5a86c27"},
 }

test/prime_factors_test.exs

diff --git a/test/prime_factors_test.exs b/test/prime_factors_test.exs
index 8cf70fa..574c57e 100644
--- a/test/prime_factors_test.exs
+++ b/test/prime_factors_test.exs
@@ -1,7 +1,15 @@
 defmodule PrimeFactorsTest do
   use ExUnit.Case, async: true

-  test "identifies prime numbers" do
+  test "zero is not prime" do
+    assert PrimeFactors.is_prime?(0) == false
+  end
+
+  test "negatives are not prime" do
+    assert PrimeFactors.is_prime?(-3) == false
+  end
+
+  test "identifies prime numbers and composite numbers" do
     assert PrimeFactors.is_prime?(1) == false
     assert PrimeFactors.is_prime?(2) == true
     assert PrimeFactors.is_prime?(3) == true
@@ -16,6 +24,15 @@ defmodule PrimeFactorsTest do
     assert PrimeFactors.is_prime?(211) == true
   end

+  test "floats are not prime" do
+    assert PrimeFactors.is_prime?(1.123) == false
+    assert PrimeFactors.is_prime?(2.000) == false
+  end
+
+  test "words are not prime" do
+    assert PrimeFactors.is_prime?("two") == false
+  end
+
   test "determines prime factors of a given number" do
     assert PrimeFactors.of(3) == []
     assert PrimeFactors.of(9) == [3]

test/protohackers/is_prime_server_test.exs

diff --git a/test/protohackers/is_prime_server_test.exs b/test/protohackers/is_prime_server_test.exs
index 7571ad9..88813d6 100644
--- a/test/protohackers/is_prime_server_test.exs
+++ b/test/protohackers/is_prime_server_test.exs
@@ -1,6 +1,137 @@
 defmodule Protohackers.IsPrimeServerTest do
+  alias Protohackers.IsPrimeServer
   use ExUnit.Case

+  test "server prime number calculation requirements" do
+    assert IsPrimeServer.is_prime?(-4) == false
+    assert IsPrimeServer.is_prime?(-3) == false
+    assert IsPrimeServer.is_prime?(-2) == false
+    assert IsPrimeServer.is_prime?(-1) == false
+    assert IsPrimeServer.is_prime?(0) == false
+    assert IsPrimeServer.is_prime?(1) == false
+    assert IsPrimeServer.is_prime?(2) == true
+    assert IsPrimeServer.is_prime?(3) == true
+    assert IsPrimeServer.is_prime?(4) == false
+  end
+
+  test "rejects malformed request" do
+    socket = tcp_connect()
+    assert tcp_roundtrip(socket, "not a valid request") == "malformed"
+    tcp_close(socket)
+  end
+
+  test "rejects invalid request" do
+    socket = tcp_connect()
+    request = %{method: "notValid", number: 123}
+    assert tcp_roundtrip(socket, request |> Jason.encode!()) == "malformed"
+    tcp_close(socket)
+  end
+
+  test "accepts and answers proper requests" do
+    socket = tcp_connect()
+
+    response = tcp_roundtrip(socket, request_prime(2))
+    assert response.method == "isPrime"
+    assert response.prime == true
+
+    response = tcp_roundtrip(socket, request_prime(5))
+    assert response.method == "isPrime"
+    assert response.prime == true
+
+    response = tcp_roundtrip(socket, request_prime(6))
+    assert response.method == "isPrime"
+    assert response.prime == false
+
+    tcp_close(socket)
+  end
+
+  test "a valid request can be multiple sends" do
+    socket = tcp_connect()
+    :gen_tcp.send(socket, "{\"method\":\"isPrime\"")
+    :gen_tcp.send(socket, ",\"number\":123}")
+    :gen_tcp.send(socket, [10])
+    response = tcp_response(socket)
+    assert response.method == "isPrime"
+    assert response.prime == false
+  end
+
+  test "multiple requests are answered in order" do
+    socket = tcp_connect()
+
+    request1 = %{method: "isPrime", number: 2} |> Jason.encode!()
+    tcp_send(socket, request1)
+
+    request2 = %{method: "isPrime", number: 6} |> Jason.encode!()
+    tcp_send(socket, request2)
+
+    [response1, response2] =
+      tcp_response(socket)
+      |> String.split("\n", trim: true)
+      |> Enum.map(&handle_response/1)
+
+    assert response1.method == "isPrime"
+    assert response1.prime == true
+
+    assert response2.method == "isPrime"
+    assert response2.prime == false
+
+    tcp_close(socket)
+  end
+
+  test "multiple requests are answered in order and stop at the first malformed request" do
+    socket = tcp_connect()
+
+    request1 = %{method: "isPrime", number: 2} |> Jason.encode!()
+    tcp_send(socket, request1)
+
+    request2 = %{method: "isPrime", number: 6} |> Jason.encode!()
+    tcp_send(socket, request2)
+
+    request3 = %{method: "isNotValid", number: 6} |> Jason.encode!()
+    tcp_send(socket, request3)
+
+    request4 = %{method: "isPrime", number: 7} |> Jason.encode!()
+    tcp_send(socket, request4)
+
+    responses = tcp_response(socket) |> String.split("\n", trim: true)
+    assert Enum.count(responses) == 3
+
+    [response1, response2, response3] =
+      responses
+      |> Enum.map(&handle_response/1)
+
+    assert response1.method == "isPrime"
+    assert response1.prime == true
+
+    assert response2.method == "isPrime"
+    assert response2.prime == false
+
+    assert response3 == "malformed"
+
+    tcp_close(socket)
+  end
+
+  test "concurrent connections are concurrent" do
+    socket1 = tcp_connect()
+    socket2 = tcp_connect()
+
+    request = %{method: "isPrime", number: 47} |> Jason.encode!()
+
+    socket1_response = tcp_roundtrip(socket1, request)
+    assert socket1_response.prime == true
+
+    socket2_response = tcp_roundtrip(socket2, request)
+    assert socket2_response.prime == true
+
+    socket1_response = tcp_roundtrip(socket1, request)
+    assert socket1_response.prime == true
+
+    tcp_close(socket1)
+    tcp_close(socket2)
+  end
+
+  ## helpers
+
   def tcp_connect() do
     {:ok, socket} = :gen_tcp.connect('localhost', 11236, [:binary, active: false])
     socket
@@ -14,7 +145,7 @@ defmodule Protohackers.IsPrimeServerTest do
         data <> "\n"
       end

-    :ok = :gen_tcp.send(socket, data)
+    :ok = :gen_tcp.send(socket, data |> String.to_charlist())
     socket
   end

@@ -49,76 +180,7 @@ defmodule Protohackers.IsPrimeServerTest do
     :gen_tcp.close(socket)
   end

-  test "rejects malformed request" do
-    socket = tcp_connect()
-    assert tcp_roundtrip(socket, "not a valid request") == "malformed\n"
-    tcp_close(socket)
-  end
-
-  test "rejects invalid request" do
-    socket = tcp_connect()
-    request = %{method: "notValid", number: 123}
-    assert tcp_roundtrip(socket, request |> Jason.encode!()) == "malformed\n"
-    tcp_close(socket)
-  end
-
-  test "accepts and answers proper requests" do
-    socket = tcp_connect()
-
-    request = %{method: "isPrime", number: 2} |> Jason.encode!()
-    response = tcp_roundtrip(socket, request)
-    assert response.method == "isPrime"
-    assert response.prime == true
-
-    request = %{method: "isPrime", number: 5} |> Jason.encode!()
-    response = tcp_roundtrip(socket, request)
-    assert response.method == "isPrime"
-    assert response.prime == true
-
-    request = %{method: "isPrime", number: 6} |> Jason.encode!()
-    response = tcp_roundtrip(socket, request)
-    assert response.method == "isPrime"
-    assert response.prime == false
-
-    tcp_close(socket)
-  end
-
-  test "multiple requests are answered in order" do
-    socket = tcp_connect()
-
-    request1 = %{method: "isPrime", number: 2} |> Jason.encode!()
-    tcp_send(socket, request1)
-
-    request2 = %{method: "isPrime", number: 6} |> Jason.encode!()
-    tcp_send(socket, request2)
-
-    [response1, response2] =
-      tcp_response(socket)
-      |> String.split("\n", trim: true)
-      |> Enum.map(&handle_response/1)
-
-    assert response1.method == "isPrime"
-    assert response1.prime == true
-
-    assert response2.method == "isPrime"
-    assert response2.prime == false
-
-    tcp_close(socket)
-  end
-
-  test "concurrent connections are concurrent" do
-    socket1 = tcp_connect()
-    socket2 = tcp_connect()
-
-    request = %{method: "isPrime", number: 47} |> Jason.encode!()
-
-    socket1_response = tcp_roundtrip(socket1, request)
-    assert socket1_response.prime == true
-
-    socket2_response = tcp_roundtrip(socket2, request)
-    assert socket2_response.prime == true
-
-    tcp_close(socket1)
-    tcp_close(socket2)
+  def request_prime(number) do
+    %{method: "isPrime", number: number} |> Jason.encode!()
   end
 end

Commit a72e300 from github.com/sdball/protohackers