Module with too many functions exausts erlang atoms

This line here clouds what you’re trying to prove. This first generates a list of 10 million atoms. This will blow out the atom table long before you try to actually make any functions.

iex(1)> defmodule PocManyClauses do
...(1)>   @list (1..10000000) |> Enum.map(fn n -> :"fn_#{n}" end)
...(1)> end
no more index entries in atom_tab (max=1048576)

Crash dump is being written to: erl_crash.dump...done

Regardless, it still probably isn’t possible to generate a function with 10 million clauses even if you could get past the atom thing. In Absinthe we generate a LOT of functions and compile time starts becoming an issue orders of magnitude below 10 million.

Ahh, this is crucial. How long does it take to compile? 2 hours? 3 hours? maybe a day?

If all goes well we will only need to compile this file once and then use it as is forever. What is your longest compile time and how many functions do you think you have? (a estimation would be great, nothing precise is needed).

The default limit for atoms is 1,048,576 (see here). You could increase it by providing the +t n option, e.g. iex --erl "+t 20000000".

However, 10 million functions seem quite extreme, so not sure if you’ll bump into some other problems. Perhaps considering other options, such as multiclauses, or statically generated maps, or some such would work better. In any case, I’m curious to read more about your experiences with it.

Absinthe experienced non linear compilation time that made having a huge number of functions impossible. However, that version of Absinthe also had a lot more going on in the module body than just defining functions, and this seemed to have a large effect on compilation time.

Doing:

:observer.start()

defmodule PocManyClauses do
  @list 1..10_000_000 |> Enum.map(fn n -> :"fn_#{n}" end)

  Enum.map(@list, fn n ->
    def unquote(n)(), do: unquote(n)
  end)
end

and then compiling via elixir --erl "+t 20000000" huge.ex indicates you also will run into a memory problem:

image1688×1124 167 KB

Notably, compilation does not seem to be generating atoms, as the atom count remains steady.

In any case, generating hard coded modules as a lookup table has its uses, but for your situation (Complexity of a search withing a range in a ets? - #9 by benwilson512) it feels like a proper data structure or data storage engine (ets) will be better.

Very accurate!

We are already running into memory problems - to “fix” this we are now compiling the code in a machine with over 30GB of RAM. So far it has stabilized around 25GB so we are waiting.

The problem is that using an interval tree will give a complexity of O(log n + m ). With an ETS table we will have (best case scenario) O(log n).
But with a module with multiclause functions, we will have O(1).

We are talking about tens of thousands of requests per second, going up to hundreds of thousands during Christmas and similar events. For us, speed really does matter.

If we power through the problem of atoms and compilation time, what disadvantages would this approach have compared to a slower alternative? (such as ETS or interval trees).

Is this true? The O() behaviour of pattern matching depends on the complexity and kind of pattern. For integer literals and atom literals (which boil down to integers) it’s my understanding that the beam can produce O(1) lookup tables. You’re trying to generate range check clauses though and I’m pretty sure that the theoretical best for that is O(log(n)).

More to the point, the O here doesn’t really matter cause you have a fixed size lookup space. What you need to determine is how fast a given lookup is, and how many lookups the system can handle concurrently. If that meets your needs then the O doesn’t really matter. If it’s too slow then yeah, looking for something with a better O can be a good guide, but I’d make sure your problem space actually permits O(1).

Are your intervals regular? (Such that you could “round down”, then use a hash lookup?)

The intervals are not regular afaik, but that would be a cool idea, I admit!

Do you really mean 10 million functions or one function with 10 million clauses?

I think it would be useful if you could provide an example more similar to how your real code would look like.

If you’re mapping a value to another value, you can consider building a compile-time map. Here’s a sketch:

defmodule Test do
  @squares 1..10_000_000
           |> Enum.map(&{&1, &1 * &1})
           |> Map.new()

  def square(x), do: Map.fetch!(@squares, x)
end

Testing on my machine, it takes about 2 minutes to compile this thing. Peak memory usage during compilation is about 10 gb, and the generated beam is about 200 mb, which is also roughly the memory overhead when the module is loaded at runtime. Invoking Test.square/1 takes around 5 microseconds (after the module has been loaded). This huge map should reside in a constant pool, so you should be able to safely access it from multiple processes without creating extra copies of it.