Reached Elixir's compiler implementation limit

Background

In my fictitious car company I have a module that tells me if I can sell a car with some specifications in a given country. This module Cars.Jurisdiction reads a CSV file at compile time and it exposes a function that given a triple, compares that with the compiled CSV and returns true or false depending if I can sell or not the car in that country.

defmodule Cars.Jurisdiction do

#########################
# Compile time madness! #
#########################

  csv_data =
    :cars
    |> :code.priv_dir()
    |> Path.join("cars_to_sell.csv")
    |> File.stream!
    |> CSV.decode!(headers: false, separator: ?;)
    |> Stream.map(&List.to_tuple/1)
    |> Stream.uniq
    |> Enum.map(fn {car, country, engine_type} ->
      {String.trim(car), String.trim(country), String.trim(engine_type)}
    end)

  cars_with_electric_engine =
    csv_data
    |>  # Filter and mapping operations

  car_country_combo_with_diesel_engine =
    csv_data
    |>  # Filter and mapping operations

  allowed_cars =
    csv_data
    |>  # Filter and mapping operations

  allowed_countries =
    Enum.map(csv_data, fn {_car, country, _engine} -> country end)

  allowed_engines =
    Enum.map(csv_data, fn {_car, _country, engine} -> engine end)

  @allowed_cars_countries_engines csv_data
  @cars_with_electric_engine cars_with_electric_engine
  @car_country_combo_with_diesel_engine car_country_combo_with_diesel_engine
  @allowed_cars allowed_cars
  @allowed_countries allowed_countries
  @allowed_engines allowed_engines

################################
# End of compile time madness! #
################################

  @spec is_blocked?(String.t, String.t, String.t, [{String.t, String.t, String.t}]) :: boolean
  def is_blocked?(car, country, engine, csv_input \\ @allowed_cars_countries_engines) do
  # never trust a Human made CSV! Humans are carbon based! How flimsy!  
  csv_data =
      Enum.map(csv_input, &trim_csv/1) 

    cond do
      car not in @allowed_cars -> true
      car in @cars_with_electric_engine -> false
      {car, country} in @car_country_combo_with_diesel_engine -> false
      country not in @allowed_countries -> true
      engine not in @allowed_engines -> true
      true -> {car, country, engine} not in csv_data
    end
  end

  defp trim_csv({car, country, engine}), do:
    {String.trim(sport), String.trim(country), String.trim(league)}

end

Problem

Now, because I have a lot of stuff happening at compile time, I expected the compile time to go up a little, specially since this is running in Elixir 1.5, which is missing a ton of improvements to compile time that newer versions have.

However,I didn’t expect this to take over 20 minutes to compile. I also didn’t expect to see compilation failing with the following error:

== Compilation error in file lib/cars/jurisdiction.ex ==
** (CompileError) Elixir.Cars.Jurisdiction: function 'is_blocked?'/2+1029:
  An implementation limit was reached.
  Try reducing the complexity of this function.
  Instruction: {bif,'=:=',{f,0},[{x,2},{literal,<<"handball">>}],{x,1023}}
    (stdlib) lists.erl:1338: :lists.foreach/2
    (stdlib) erl_eval.erl:670: :erl_eval.do_apply/6
make[1]: *** [compile] Error 1

I am not sure I understand what is going on here. It is complaining about my cond statement.
I am aware that this code would be cleaner with functions using pattern matching (in fact if I do so, I avoid this error, but the code still takes half an hour to compile) but this cond statement only has 6 cases.

Questions

  1. Why am I getting this error?
  2. Why don’t I get the error if I use functions with pattern matching?
  3. Why does it take over half an hour to compile?

And most importantly:

  1. How can I git rid of the error and the long compilation time ?

Looks like the var in list operation does not support over 1024 list elements.

You should compile lookup functions based on your data, it would be more practical to use.

You are getting the error because the function is too complex which means it has too many expressions.

You can try avoiding the in expansion by using Enum.member?/2 instead or by moving the literals to other functions:

def is_blocked?(...) do
  cond do
    car not in allowed_cars() -> true
    ...
  end
end

defp allowed_cars(), do: @allowed_cars
3 Likes

@ericmj This raises quite a few questions for me:

  1. which one is more efficient at runtime? The in expansion or Enum.member? ?
  2. I assume Enum.member? will compile faster than the in expansion. Is this correct?

Where can I read about the in expansion to learn more about it?

In this case I don’t think you should focus on which is more efficient since one of them doesn’t work. In the general case in should be more efficient when given a literal on the right hand side.

Enum.member? is a normal function call, while in is a macro that will do more work at compile time and can therefor be slower, but it’s unclear if it’s in by itself that is slow or the code it produces that is slow to compile. It can also be something else that causes the slowdown, we don’t have enough information to reproduce your issue. My suggestion was more about fixing the compilation error and less about fixing the slowness issue.

You can find ins documentation here: Kernel — Elixir v1.11.4.

2 Likes

You probably want to use a MapSet, which provides better performance for element lookups compared to lists, which are linear.

6 Likes

I have changed the cond to look like the followoing:

cond do
      not Enum.member?(@allowed_sports, sport) ->
        true

      Enum.member?(@sports_with_wildcard_countries, sport) ->
        false

      Enum.member?(@sport_country_with_wildcard_leagues, {sport, country}) ->
        false

      not Enum.member?(@allowed_countries, country) ->
        true

      not Enum.member?(@allowed_leagues, league) ->
        true

      true ->
        not Enum.member?(csv_data, {sport, country, league})
    end

With this change the error no longer happens. The compile time also went down from 25 minutes to just 3!

Going back to my list of questions:

Answers (based on my current understanding):

  1. I am getting this error because the in operator is a macro, which expands code behind. This expanded code generates a list with more than 1024 expressions to evaluate, which over the limit.
  2. I am not sure about this one. The code still takes an obscene amount of time to compile (over 20 minutes), however I am guessing that because of the nature of the macro code running behind the scenes, even though it expands close to the limit, it does not quite reach it.
  3. Because the macro needs to create a list of expressions to evaluate, which takes time.
  1. in should be faster at runtime, however it is slower at compile time.
  2. I believe my assumption to be correct.

Good point! Will take this into consideration!!

We ran into this with Absinthe a bit. If the body of a module expanded into overly complex code the compile times eventually became non linear. We never did figure out why, and instead refocused our efforts on just minimizing the amount of code we dumped in the module body. I’m not 100% sure that your scenario is the same though because your expansion is happening principally inside function bodies.

3 Likes

just for the record Elixir v1.11 solves this limiation

3 Likes