In addition to what @michallepicki noted, when parallelizing, you should avoid sending huge data structures as messages between processes, as that would involve a lot of copying. Often it is a good idea to implement the algorithm without parallelization, using it as a benchmark, and adding parallelization as an optimization.

One big change from other languages is that lists are immutable linked lists, so some operations become very expensive and take time (and sometimes space!) proportional to the length of the list.

Some examples:

a = [1]
b = [2 | a]

Prepending to the beginning of a list is fast - it allocates a single new cons cell. Takes constant time.

a = [1]
b = [1] ++ [2]

Concatenating two lists is more expensive - all the cells in the left-hand argument to ++ need to be reallocated, taking time and space proportional to the size of that list.

a = [1,2,3]
b = hd(a)

This is efficient, since the head is the first cons cell. Takes constant time. Note that tl(a) is also efficient, since those are the SAME cons cells as in a.

a = [1,2,3]
b = List.at(a, -1)

in order to access “the end” of a list, all the cons cells need to to be walked. List.at will take time proportional to the size of the list.

You’ll need to modify your algorithm to avoid doing the inefficient kind of operations; for instance, popping from the end might instead be represented with a constant-time functional queue like Erlang’s :queue (docs)

Also note (at least according to Wikipedia) the time complexity of this algorithm is exponential in the number of unique values in the input…

Re: the usage of spawn_link - consider using Task instead, it’s specifically tuned to the “take input, process, send message and then shut down” pattern you’ve implemented. Task.async_stream may prove useful as well.

It’s actually easy to make things slower by trying to parallelize things. Modern processors are usually really fast but are bottlenecked by memory access and bad data layouts. In Elixir most of this is abstracted away but in general you want to make sure that the overhead of parallelizing is lower than what you gain from running on multiple cores/machines at the same time (I hope that makes sense). So you need to find the balance of how much work you parallelize and how many workers to create. The gains may be bigger on bigger data sets.

I didn’t read too deeply so you may already know these but some general tips:

Recursion is often the best tool for writing complicated loops but to allow the compiler to do some optimizations, make sure your functions are tail-recursive (I think yours are but good to double check).

When you use a Stream, you lose the laziness of it (it gets ran) immediately when you pipe it into an Enum function like Enum.reduce. So make sure you don’t mix them by mistake.

Look through what data structures and tools are provided with OTP. Some may have better performance or memory footprint characteristics for the particular job you want to do. Look at :ets for example.

Spawning processes with Flow is not cheap. Make sure doing that actually improves performance on a case-by-case basis and check that you pass only the data that is needed for this chunk of work. Sending big measages to many processes is slow and could result in big memory usage.

Some micro optimizations can definitely be applied to reduce Elixir protocol overhead, e.g. use erlang’s :lists module instead of going through Enum… But it may be not worth much, it depends.

Benchmark what is faster with the Benchee library. Small chunks of code.

Have fun, this is cool stuff!

Also, one tip: I see that your items in the itemsets are strings like "POLKADOT". It might make sense to convert them to numeric IDs or atoms (especially if your program is short-lived, so you won’t have issues with “leaking atoms”). That’s in order to make sure that multiple copies of the same item won’t be stored multiple times in memory, and instead stored only once and referenced.