Fractals in Elixir (Rebooted)

When I first started learning Elixir, I tried building an Elixir program that would generate fractals concurrently. I have a repo with several attempts in different languages, and I wrote a blog article about my single-threaded Elixir solution last year.

After that article, I did get some concurrency into my Elixir program, but the performance of the program was awful. And every inuition that I had to speed it up was wrong. It kind of killed my interest in the project.

That was more than a year ago, and I’m ready to tackle it again. Three things brought me back: first, I’ve just simply picked up a lot of Elixir knowledge since then; second, I read the most excellent Elixir in Action by Saša Jurić; last, I gave myself permission to throw away the old code¹ and start from scratch.²

In this article, I’m going to explain what I think went wrong with my first attempt and what I plan to do to fix those problems in this new attempt.

The goal

My program generates several different types of fractals: the Mandelbrot set, Julia sets, the Burning Ship fractal, and the Newton fractal.

All of these fractals are computed with an escape-time algorithm The algorithm iterates over a grid of points from the complex-number plane. For each of those grid points, you iterate a function related to the fractal, feeding output of one iteration in as input for the next. If the input gets too large, the original point out of the set; otherwise, it’s in the set. If you’ve iterated enough times, you assume the point is in the set.

My program also provides different color schemes for the points that escape the set based on how quickly (i.e., how many iterations) it takes to get too big.

These options are all specified in a JSON file.³ You can also specify the image size, the corners of the complex number plane, and parameters for the different types of fractal sets.

Using the language wrong, maybe

What I did right

I used a case expression to pick a function for coloring the fractal based on the color option provided by the user:

case options.color do
  :black_on_white -> &Simple.black_on_white/1
  :white_on_black -> &Simple.white_on_black/1
  :gray           -> &Simple.gray/1
  :blue           -> &WarpPov.blue/1
  :green          -> &WarpPov.green/1
  :red            -> &WarpPov.red/1
  :random         -> Random.build_random
end

The function returned by this case expression was passed in as a parameter to the escape-time algorithm. When it came to coloring a pixel, the algorithm would call the color function. A function as a first-class citizen: Functional Programming!

If I coded this up in Ruby, I probably would have something similar. Instead of returning functions, I would return Simple::BlackOnWhite.new and WarpPov::Blue.new. The Ruby objects would implement convert_to_color for my escape-time algorithm to use. A polymorphic method: Object-Oriented Programming!

The case expression in Elixir bothers me a bit. I suppose it would bother me in Ruby, too. In Ruby I’d be tempted to use some metaprogramming: options.color.camelcase.constantize.new. But that only hides the case expression with a hash-table look up inside the Ruby runtime.

I suspect it bothers me because this case expression became my only hammer.

What I did wrong

I also used a case expression for the iterating function for the escape-time algorithm:

case options.fractal do
  :burningship -> BurningShip.iterator(grid_point)
  :mandelbrot  -> Mandelbrot.iterator(grid_point)
  :julia       -> Julia.iterator(options.c)
  :newton      -> Newton.iterator
end

I also used it to pick a concurrency strategy:

case options[:concurrency] do
  "none"     -> &Fractals.Generator.Taskless.generate/2
  "chunked"  -> &Fractals.Generator.TasklessChunked.generate/2
  "original" -> &Fractals.Generator.OriginalTasked.generate/2
  "crunchy"  -> &Fractals.Generator.LongerTasked.generate/2
  "smooth"   -> &Fractals.Generator.PooledProcesses.generate/2
end

No, I don’t know why I used options[:concurrency] instead of options.concurrency. And, yes, each strategy is named after a type of peanut butter.

Now in the case (ha!) of picking a concurrency strategy, I should have just done new projects. I had written my algorithms with a single-threaded mentality; it didn’t generalize well for the concurrent strategies.

As for picking the function for the fractal, let’s look at the larger context:

def build(options) do
  fn grid_point ->
    case options.fractal do
      :burningship -> BurningShip.iterator(grid_point)
      :mandelbrot  -> Mandelbrot.iterator(grid_point)
      :julia       -> Julia.iterator(options.c)
      :newton      -> Newton.iterator
    end
  end
end

So the case expression returns a function which is going to be the return value from another function built by this build function. Yeah, what could be confusing about that?

The “problem” as I saw it was that some of the fractal functions needed to know the current grid point from the complex number plane. Grid points change, so I had to delay the building of the fractal function until I knew the grid point, and I had to build a new one each time. And building functions returning functions returning functions was a good idea.

I wish I had tried to rely more on pattern matching in function parameters. Write all module-level functions and pattern match on options.fractal. Maybe I’ll try this later.

However, at the heart of it, while Elixir is an FP language, I don’t think passing functions around is really the Elixir way. First-class functions are great for Enum functions like map and reduce, but not for polymorphic decisions like which color function to apply.

What I’ll do better

Elixir provides several polymorphic solutions (including passing functions around like I did). I’m not committed to any solution yet, but I’m leaning heavily towards using processes to solve the problem. The color and fractal-function case expressions will probably still exist, but as a way to determine which type of worker to start up.

Wrong Processes

Originally I wrote the app as a single-threaded process. Then I tried to make it concurrent from the bottom up. Each of the grid points can be iterated on independently of each other, so why not do them all in separate Tasks?

Because it doesn’t work. Most of the images are 1024x768, so the system (i.e., my MacBook Pro) is flooded with hundreds of thousands of processes (786,432 to be exact, more or less).

I found that if I sent a couple of rows instead of single grid point to be processed by each Task, then I got better performance, but it was still only fractionally better than the single-threaded performance. Some times is was worse.

One thing I discovered in the past year is that standard output is handled by a separate process in Elixir. When you call IO.puts, it sends a message to the output process, and that process actually writes it to the standard output. This got me to thinking that maybe I should have a separate process for outputting the image file.

I also read many blog articles and tutorials on Elixir, and most importantly I read Elixir in Action by Saša Jurić⁴.

All of these things got me thinking that maybe I should break up the processes differently. I decided on four processes:

• build the grid,
• iterate the grid points,
• determine pixel colors, and
• output the file.

These will probably be supervisors, and they will dispatch work to worker processes. The worker processes will be pooled so that they don’t overwhelm the system. The one concern I have is the amount of data that has to flow between these processes; I fear this could overwhelm any benefits of concurrent processing. But we’ll see.

Chunks

I believe that chunking the data will still be useful. I’m going to design the system to use chunks, and if I feel like my unit of work should be single grid points, I can always just use a chunk size of 1.

So a “chunk” will be a tuple:

@type chunk :: {number, Fractals.Options.t, list(any)}

The first element is the chunk number. The first process will send chunks in order, but the other processes probably won’t. Some chunks will take longer to process. But the output process needs to know the order so that it can write the pixels in the right order.

The second element is the options from the JSON file as described above and from command-line arguments.

The last element is the chunk of data: a list of grid points, a list of escape-time results, and a list of colors depending which process is sending or receiving them.

Everything will change

This is my perspective on this project for now. It may change. It probably will change. It must change. And it probably will fail. I’m learning this stuff.

I’ve decided to start with the output process since it intrigues me the most and should be pretty straightforward.⁵ We’ll look at what I come up with next time.

Footnotes

elixir fractals