Ring probabilities with Elixir
I’ve been hearing more about Elixir lately so I thought I’d take it for a spin.
“Elixir is a functional, meta-programming aware language built on top of the Erlang VM. It is a dynamic language that focuses on tooling to leverage Erlang’s abilities to build concurrent, distributed and fault-tolerant applications with hot code upgrades.”
I’ve never really spent any time with Erlang but always been curious about it and the fact that it’s one of the best kept ‘secrets’ in many startups these days. I’ve heard for years how easy it is to ‘scale out’ compared with many other languages and platforms.
Joe Armstrong, the creator of Erlang, wrote a post about Elixir in which he seemed to really like it except for some minor things. This got me even more curious so I decided to write some code that seemed like it could benefit from the features provided by Elixir for easily making suitable algorithms parallelizable.
Let’s talk about Ring probabilities. Let’s say we had a cluster of N nodes in a ring topology. We then might have some code that requires S steps to be run and each subsequent step is run on a node to the right of the previous node with some probability P.
In the initial state (S=0) the probability of some piece of code running on node A is P=1.
At the next step (S=1) the probability of the step running on a node to the right in the ring is P and the probability of the step running on a node to the left is 1-P.
Here is an example with some crude ascii diagrams to visually represent this :
Initial node probablity for 5 node ring at S=0 is P=1 for starting node.
N = 5 (nodes)
For S = 0 (initial state)
1 - P = 0.5 P = 0.5
Counter-clockwise Clockwise
+-----+
| P = |
+----------+ 1.0 +----------+
| +-----+ |
+--+--+ +--+--+
| 0.0 | | 0.0 |
+--+--+ +--+--+
| |
| |
| +-----+ +-----+ |
+--+ 0.0 +---------+ 0.0 +--+
+-----+ +-----+
Node probablities for the same 5 node ring after 2 state transitions
N = 5 (nodes)
S = 2
1 - P = 0.5 P = 0.5
Counter-clockwise Clockwise
+-----+
| P = |
+----------+ 0.5 +-------------+
| +-----+ |
+--+--+ +--+--+
| 0.0 | | 0.0 |
+--+--+ +--+--+
| |
| |
| +------+ +-------+ |
+--+ 0.25 +---------+ 0.25 +--+
+------+ +-------+
Let’s first write the sequential version of the algorithm to calculate the ring probabilities. The parallel version will be handled in the next post. Data types in Elixir are pretty basic at this point with Elixir still having not reached 1.0. I decided to use an array to represent the ring in anticipation of later parallelizing the algorithm. A list seemed unsuitable for this due to access times being linear and that a parallel map across the structure would most likely be required. For a sequential version it’s interesting that a list is the fastest data structure to use in combination with recursion and pattern matching but I’ll get into that in the next post.
For now let’s get back to implementing a sequential version with an array and the map function …
Elixir doesn’t have an array or vector type (yet ?). I’m not going to comment on this. Instead we will use Erlang’s array type. Dipping into Erlang libraries from Elixir is pretty trivial so it’s no big deal other than Elixir’s parameter conventions for function calls is the reverse of Erlang’s and this can be a little annoying.
Let’s look at the function for calculating the node probabilities given a direction change probability, number of nodes and state count :
def calc_ring_probs(p, n, s)
when is_float(p) and p >= 0 and p <= 1 and
is_integer(n) and n > 0 and
is_integer(s) and s >= 0 do
# Probs at S = 0.
# Certain that we are positioned at only start location.
# e.g. P(Start Node) = 1
initial_probs = :array.new [size: n, fixed: true, default: 0.0]
initial_probs = :array.set 0, 1.0, initial_probs
final_probs = initial_probs
IO.puts "Calculating ring node probabilities where P=#{p} N=#{n} S=#{s} ...\n"
# If we are moving beyond the initial state then do the calculation ...
if s > 0 do
# ... through all the states ...
final_probs =
reduce 1..s,
initial_probs,
fn (_, new_probs) -> calc_state_probs(p, new_probs) end
end
final_probs
end
The first thing you might notice at the beginning of calc_ring_probs are the guard clauses (when …) after the function parameter definition. This is a nice way of ensuring some pre-conditions are met for the function to return meaningful results.
We check that the probability parameter is a float within the range 0.0 -> 1.0, we also make sure that there are more than zero nodes and this must be an integer and that the state is either zero or more and also an integer.
Next the initial probabilities are created using an Erlang array. If the state required is not the initial state (S=0) then we reduce for the number of states and calculate the probabilities of the ring at each state(calc_state_probs) until we reach the final state.
Now let’s look at the implementation of calc_state_probs.
def calc_state_probs(p, prev_probs)
when is_float(p) and p >= 0 and p <= 1 do
sz = :array.size(prev_probs)
:array.map fn(i, _) ->
prev_i = if i == 0 do sz - 1 else i - 1 end
prev_prob = :array.get(prev_i, prev_probs)
next_i = if i == sz - 1 do 0 else i + 1 end
next_prob = :array.get(next_i, prev_probs)
p * prev_prob + (1 - p) * next_prob
end, prev_probs
end
The function takes the probability P and an array of the previous probabilities. We determine the previous and next node probability indexes based on the current index. If the current index is the first or last index in the array then the previous index is the last and the next index is the first, respectively. We calculate the current index using the respective probability P or 1-P and the previous and next node probabilities.
That’s really all there is to the sequential version.
On a macbook air a 1,000,000 node ring over 10 state changes takes ~7.4 seconds.
bash-3.2$ mix run lib/ring_probs.ex 0.5 1000000 10
Calculating ring node probabilities where P=0.5 N=1000000 S=10 ...
{:array, 50, 0, 0.0,
{{0.24609375, 0.0, 0.205078125, 0.0, 0.1171875, 0.0, 0.0439453125, 0.0,
0.009765625, 0.0},
{9.765625e-4, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0}, 10, 10, 10, 10, 10, 10}}
... 999950 node probabilities ...
{:array, 999950, 0, 0.0,
{{{{{{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0},
{9.765625e-4, 0.0, 0.009765625, 0.0, 0.0439453125, 0.0, 0.1171875, 0.0,
0.205078125, 0.0}, 10, 10, 10, 10, 10, 10}, 100, 100, 100, 100, 100, 100,
100, 100, 100, 100}, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000,
1000}, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000,
10000}, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000,
100000, 100000}}
calc time: 7370.12 msecs
The complete code can be found here.
My reluctance with Elixir is that it’s a strong dynamically typed language. This is much the same issue I’ve had with Erlang. There are ways to work around this. One way is using a static analysis tool. Read this for more info. Apparently success types are a way to correctly infer types in Erlang. I can’t say that I’m convinced, my own experience has shown that any production system that needs to scale at least requires something like type-hinting. I might be wrong and in fact I hope I am because I like what I’ve seen regarding Elixir and heard about the Erlang VM for building distributed systems.
In the next post we’ll re-write the code to make it run concurrently and also look at how a sequential version of the algorithm using recursion, pattern matching and lists is an order of magnitude faster than the sequential version using arrays in this post.
The sequential recursive version may even be faster than a concurrent version depending on how many cores your machine has 😉