Thursday, 24 April 2008

Parallel Quicksort in Erlang

Jaksa is doing some posts on parallel graph algorithm in Java using fork/join, and he mentions quicksort:

"The equivalent of the hello world for parallel languages is the quicksort algorithm"

Now I'm tempted to say something like "Oh yea? You know how many lines of code quicksort is in Erlang? 3!" Yes really:


qsort([]) -> [];
qsort([Pivot|Rest]) ->
qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).


But this would be wrong, as the terseness of the quicksort implementation says more about the power of list comprehensions than about Erlang's concurrency-supporting language features.

So then let's see how you could implement a concurrent quicksort in Erlang, which will say something about the way in which we can implement concurrency in Erlang. We'll start with the original Wikipedia quicksort from above, and alter it a little bit to make it more obvious what I'm going to do next:


qsort([]) -> [];
qsort([Pivot|Rest]) ->
Left = [X || X <- Rest, X < Pivot],
Right = [Y || Y <- Rest, Y >= Pivot],
qsort(Left) ++ [Pivot] ++ qsort(Right).


Note the two calls to qsort at the end. Since there is no shared state between these two functions, they can be executed in parallel, and the results can be concatenated to yield the sorted result. Depending on the distribution of the input, each of these calls could be split up into 2 more qsort calls etc. etc. Note that you could do a hybrid recursive-tail-recursive solution which sorts the smallest partition using normal recursion and the largest using tail-recusrion, but that is not the aim here.

Let's assume that we already have a function that executes any input function in a separate Erlang process called "peval". (Note Erlang processes are extremely light-weight and take very little time to construct. They're are not modelled as operating system processes). peval takes two arguments, a function to execute, and the arguments to the function. When called, it looks like a normal function call:


(emacs@21ccw.blogspot.com)38> pqsort:peval(fun(X) -> X*X end, 13).
169


But, in the background, it spawns a process and the function is evaluated on this new process. The result is then returned to the calling process. Using peval, we now have a parallel quicksort:


pqsort([]) -> [];
pqsort([Pivot|Rest]) ->
Left = [X || X <- Rest, X < Pivot],
Right = [Y || Y <- Rest, Y >= Pivot],
peval(fun pqsort/1, Left) ++ [Pivot] ++ peval(fun pqsort/1, Right).


Now there is a significant observation to make. The concurrent and non-concurrent versions look remarkably similar, we only had to substitute the original function evaluations with parallel versions. This is one of the reasons why I think functional languages are better suited to concurrency that OO ones.

Let's look at peval. peval creates a new process using spawn_link. spawn_link() is used instead of spawn(), so that the creator process receives exception when the new child process throws an exception.


peval(Fun, Args) ->
Pid = spawn_link(fun() -> wait() end),
Pid ! {self(), Fun, Args},
receive
{Pid, R} -> R
end.

wait() ->
receive
{From,Fun,Args} ->
From ! {self(), Fun(Args)}
end.


That's it! Parallel quicksort in about 15 lines of Erlang code. If I add a "+" output to console on every entry to peval, and "-" on every exit from peval, you get the following output:


(emacs@21ccw.blogspot.com)18> L1 = lists:map(fun(X) -> trunc(random:uniform()*100) end, lists:seq(1,100)).
[57,33,2,85,59,65,61,71,83,75,94,94,19,5,79,53,31,54,39,61,
61,79,55,6,37,35,86,31,88|...]

(emacs@21ccw.blogspot.com> pqsort:pqsort(L1).
+++-++++-+--++-+++++-+--+--+--+++-+--++-+------+++
+-++-+---+++-+--+---++-+-----+++++-+--++-+---+++++
-+--+--+++-+--+---++-+----++-++-++-+------++++-+--
++++-+--++-+---++++-+--++-+---++++-+--+++-++-+---+
++-+--+----+-----+++-+++-+--+++-++-+---+----++-+--
--
[2,4,5,6,7,9,11,13,14,17,18,19,20,21,22,24,27,31,32,33,35,
37,38,39,40,42,44,47,48|...]

(emacs@21ccw.blogspot.com)5> pqsort:integrate_output("+++-++++-+--++-+++++-+--+--+--+++-+--++-+------+++").
0123234565654565678910910989878767898987898987654345...


You can see that for the first few pevals, by integrating over the output, that number of parallel processes goes up to around 8-10. This will depend on the distribution, and the relative times it takes to initialise processes to doing the actual computation etc.

Now that we've got pqsort going, I'm looking forward to doing the parallel graph algorithms of Jaksa's fork/join graph algorithms. There will be an obstacle to ensure that no nodes are visited more than once, but this could (possibly) be solved by partitioning the graph into subgraphs first where no children have multiple parents. We'll see...

Update (7 May 2008): This implementation is wrong! (see comments). There's a follow-up post here: Parallel Quicksort in Erlang - Part II

Friday, 18 April 2008

IE7 Page Zoom Broken

We use XPlanner at work for some projects, and we noticed that there seems to be a problem with the hyperlinks in Internet Explorer (version 7.0.5730.11) when the pages are zoomed in (you can zoom pages in IE with Ctrl +). The horizontal areas for the links were not aligned to the actual text, which means that some links seem can't be clicked correctly, but you can click white space (look carefully at the first image, you can see the normal I-beam cursor):





I shouldn't be surprised, since it does so badly in the Acid3 test. I couldn't find any other reports of this issue, and will be happy to link to them if you post a comment.

P.S. Firefox, Opera and Safari don't have this problem.

Thursday, 10 April 2008

Getting started with distributed Erlang - Mnesia table relocation

Mnesia is a distributed database that forms part of the Erlang release. One of the features that I think is potentially powerful, is transparent table relocation across machines. With Mnesia, you can replicate tables to any nodes you wish in your network, and Mnesiatakes care of all the back end bits for you. With "transparent", I mean that you don't need to do anything in your clients to make them "aware" of the new tables. Reads that were taking place from a table on one machine, will now be distributed across multiple nodes (where the nodes reside on single or multiple machines).

I wanted to see how difficult it is to achieve this. For the setup, I installed two virtual Ubuntu 7.10 machines using VMware Player. You can get images for most Ubuntu distros at http://isv-image.ubuntu.com/vmware/. FYI, the username and password for these images is ubuntu:ubuntu. I named the two nodes

node1.21ccw.blogspot.com and
node2.21ccw.blogspot.com

You'll need to edit the network configurations with the IP addresses if you want to reproduce this experiment. If you need some help, post a question as comment :)

I now had two machines that could ping each other using the full names, and a warm and fuzzy feeling inside:


The next step was to start up an Erlang node on each machine. There's a catch here though. I got some problems using erl -sname, probably because of the way I set up the hostnames of the machines. So, I had to specify the fully qualified names manually:


ubuntu@node1:~/node1$ erl -name 'node1@node1.21ccw.blogspot.com'
Erlang (BEAM) emulator version 5.5.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.5.5 (abort with ^G)


ubuntu@node2:~/node2$ erl -name 'node2@node2.21ccw.blogspot.com'
Erlang (BEAM) emulator version 5.5.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.5.5 (abort with ^G)
(node1@node1.21ccw.blogspot.com)1> nodes().
[]


Notice the output of the nodes() command. This will return a list of other Erlang nodes that this node is aware of. Initially there's no awareness. To let a node know of another node, you can use net_adm:ping/1 to ping the other node. Both nodes will then become be aware of each other:


(node1@node1.21ccw.blogspot.com)4> net_adm:ping('node2@node2.21ccw.blogspot.com').
pong

(node1@node1.21ccw.blogspot.com)5> nodes().
['node1@node1.21ccw.blogspot.com']


(node2@node2.21ccw.blogspot.com)1> nodes().
['node1@node1.21ccw.blogspot.com']


Cool. Now the nodes know of each other. To get Mnesia started, you have to create a schema on each node. A schema is located on the file system, in the same location where the actual disc-copies of tables will reside. [node()|nodes()] creates a list of the current node and all the other connected nodes. ls() shows the directory that Mnesia has created for the database.


(node1@node1.21ccw.blogspot.com)5> mnesia:create_schema([node()|nodes()]).
ok

(node1@node1.21ccw.blogspot.com)6> ls().
Mnesia.node1@node1.21ccw.blogspot.com
ok



(node2@node2.21ccw.blogspot.com)2> ls().
Mnesia.node2@node2.21ccw.blogspot.com
ok


Now we have to start Mnesia on both nodes. You will notice that when we do an mnesia:info on node2 at this point, that it shows both nodes as being running database nodes.



(node1@node1.21ccw.blogspot.com)8> mnesia:start().
ok



(node2@node2.21ccw.blogspot.com)3> mnesia:start().
ok

(node2@node2.21ccw.blogspot.com)4> mnesia:info().
...
running db nodes = ['node1@node1.21ccw.blogspot.com','node2@node2.21ccw.blogspot.com']
...

Next we'll create an actual database table, and populate it with some data. We define a record using rd(), then create a table on node1 (by default, this table will reside in RAM and have a disc copy), write a record to it and then read the record again. The primary key of the table is the first field of the record, i.e. the name.


(node1@node1.21ccw.blogspot.com)9> rd(person, {name, email_address}).
person

(node1@node1.21ccw.blogspot.com)10> mnesia:create_table(person, [{attributes, record_info(fields, person)}, {disc_copies, [node()]}]).
{atomic,ok}

(node1@node1.21ccw.blogspot.com)11> mnesia:transaction(fun() -> mnesia:write(#person{name = "John", email_address = "john@21ccw.blogspot.com"}) end).
{atomic,ok}

(node1@node1.21ccw.blogspot.com)14> mnesia:transaction(fun() -> mnesia:read({person, "John"}) end).
{atomic,[#person{name = "John",email_address = "john@21ccw.blogspot.com"}]}

(node1@node1.21ccw.blogspot.com)15> mnesia:info(). ...
...
[{'node1@node1.21ccw.blogspot.com',disc_copies}] = [person]
...


What happens when we do the same read on node2? Remember that node has access to the person table only via the network, since it resides in RAM and on disc on node1.

node2@node2.21ccw.blogspot.com)5> mnesia:transaction(fun() -> mnesia:read({person, "John"}) end).
{atomic,[{person,"John","john@21ccw.blogspot.com"}]}
Nice. Mnesia has transparently read the record from a table that's on another machine :)

Now we decide to copy the table to node2. This requires a single command. Mnesia does the copying of the actual data for you to the other machine, and when you look at the file system on node2, there will now be "person.DCD" file, which is the disc copy of the table.


(node1@node1.21ccw.blogspot.com)15> mnesia:add_table_copy(person, 'node2@node2.21ccw.blogspot.com', disc_copies).
{atomic,ok}



(node2@node2.21ccw.blogspot.com)9> ls("Mnesia.node2@node2.21ccw.blogspot.com").
DECISION_TAB.LOG LATEST.LOG person.DCD
schema.DAT
ok


At this point, when you do a query on the person table, the actual data can come from either node. I'm not sure how Mnesia decides how to distribute the data, that's something to investigate further.

Since the table is resident on both nodes, we can actually delete it from node1, and doing a read on node1 will now read the table over the network from node2:


(node1@node1.21ccw.blogspot.com)23> mnesia:del_table_copy(person, node()).
{atomic,ok}

(node1@node1.21ccw.blogspot.com)19> mnesia:info().
...
[{'node2@node2.21ccw.blogspot.com',disc_copies}] = [person]
...

(node1@node1.21ccw.blogspot.com)18> mnesia:transaction(fun() -> mnesia:read({person, "John"}) end).
{atomic,[#person{name = "John",email_address = "john@21ccw.blogspot.com"}]}

Cool.

What I've show is how to start up an Erlang/Mnesia node on two machines that are networked together, create tables on either node, and move the tables to other nodes by copying and then deleting them. Mnesia has the ability to configure tables to be RAM only, RAM and disc and disc only, which gives you lots of power for optimisation. Couple this with the fact that you can change your configuration dynamically and you have powerful, dynamically configurable distributed database!

Wednesday, 2 April 2008

Using Rake for Erlang Unit Testing

My previous Erlang/Yaws project, dayfindr.com, is ticking along nicely:
$ yaws --status --id dayfindr
Uptime: 33 Days, 13 Hours, 38 Minutes
The feedback has been mostly positive, although I've had a "That's a very irritating site." comment. Well, you can't please everyone!

Following on the experience gained with dayfindr, I'm starting a new Lyme project which will be using some of the OTP design principles (Think of OTP as Erlang application design patterns). Using OTP will give me hot upgrades, which dayfindr lacks at the moment. The first step that I encountered towards this goal was getting my directory structure to conform to the OTP application structure:


/project [The project root]
/ebin [The compiled .beam files]
/src [The source .erl files]
/include [Include files like record definitions]

I've been using the Makefile that's provided in the Erlang book, which is quite simple and compiles the beam files to the same directory as the source folder, which doesn't comply to the required directory structure. Now, I could just update the Makefile, but Makefiles have a cryptic syntax that I don't really want to spend time learning. Plus, they're difficult to debug in my experience. So I Googled around a bit for erlang Makefiles with little to disappointing success. Then I saw an interesting link:

Building Erlang with Rake

When they make a movie of my life and this moment, you will hear an orchestra and a choir of baritones singing "Eureka" when I click on the link.

Rake is an Ruby equivalent of Make, and more. It took some effort to get it working, since I had rake 0.7.1 on my machine, but trying to find the problem taught me a bit of Ruby in the process. Upgrading to 0.7.3 solved the problem. Sean's Rakefile compiles your src files into the ebin directory very nicely! After tinkering around with Rake, I realised that it's a really nice tool:
  • It has a nice mix of declarative and imperative code. You can define rules (e.g. always compile .erl to .beam), or tasks (which can be imperative, e.g. running unit tests).
  • You can use the full power of Ruby, and don't need to learn Make.
  • It has syntax that is very close to the domain (i.e. it's a good DSL)
  • It's easy to debug, since you can use the normal Ruby puts functions etc.
  • How you set up you dependencies is completely up to you, e.g. you can have different rules for files that conform to different regular expressions.
After I got this working, inspired with confidence, I decided to integrate my unit testing into the Rakefile. I think it's important to note at this point that I have less than a day's Ruby experience, and it was easy to get this working. Hacking a Makefile would probably have taken me hours and hours. The idea is that the test task is dependent on the compile task, so that if you do a "rake test", it will compile anything that's new and run the unit tests. You can just compile with "rake compile".

In order to get this going I created two Erlang files, foo.erl and bar.erl. Here's bar.erl, which contains two functions, and a test (EUnit)for each function. One of the tests will fail:


-module(bar).
-export([bar1/0, bar2/0]).

-ifdef(EUNIT).
-include_lib("eunit/include/eunit.hrl").
-endif.


bar1() ->
ok.

bar2() ->
okk.

-ifdef(EUNIT).
bar1_test_() ->
[
?_assert(ok == bar1())
].
-endif.

-ifdef(EUNIT).
bar2_test_() ->
[
?_assert(ok == bar2())
].
-endif.

Notice that the unit test code is only compiled into the beam file when the EUNIT flag is set. You can set this in the Rakefile. The unit tests are in the same source file, so we can also test non-exported functions.

Now let's look at the Rakefile:


require 'rake/clean'

INCLUDE = "include"

ERLC_FLAGS = "-I#{INCLUDE} +warn_unused_vars +warn_unused_import"

SRC = FileList['src/*.erl']
OBJ = SRC.pathmap("%{src,ebin}X.beam")

CLEAN.include("ebin/*.beam")

directory 'ebin'

rule ".beam" => ["%{ebin,src}X.erl"] do |t|
sh "erlc -D EUNIT -pa ebin -W #{ERLC_FLAGS} -o ebin #{t.source}"
end

task :compile => ['ebin'] + OBJ

task :default => :compile

task :run_tests => [:compile] do
puts "Modules under test:"
OBJ.each do |obj|
obj[%r{.*/(.*).beam}]
mod = $1
test_output = `erl -pa ebin -run #{mod} test -run init stop`

if /\*failed\*/ =~ test_output
test_output[/(Failed.*Aborted.*Skipped.*Succeeded.*$)/]
else
test_output[/1>\s*(.*)\n/]
end

puts "#{mod}: #{$1}"
end
end

The juicy bits are the rule and the "run_tests" task. The rule states "for each file ending in .erl, compile the beam file using erlc and put the beam file in ebin". The run_tests task starts up an erlang runtime for each module, and calls test() for that module. The test output is captured and parsed using regular expressions. I know the Ruby code can be improved, so comments are most welcome.

Here's what happens when I compile and run the tests:


$ rake clean
(in /home/bjnortier/development/project1)

$ rake
(in /home/bjnortier/development/project1)
erlc -D EUNIT -pa ebin -W -Iinclude +warn_unused_vars +warn_unused_import -o ebin src/foo.erl
erlc -D EUNIT -pa ebin -W -Iinclude +warn_unused_vars +warn_unused_import -o ebin src/bar.erl

$rake run_tests
(in /home/bjnortier/development/project1)
Modules under test:
foo: All 2 tests successful.
bar: Failed: 1. Aborted: 0. Skipped: 0. Succeeded: 1.


At this points I have cleaning, compiling and running the tests for each module. Nice. I'm quite pleased with how it works at the moment, but there's still quite a bit of work to be done:
  • Concatenating the running of the unit tests into one no-shell erlang execution. Actually running the tests are very fast, but the shell termination takes about a second or so. Thus, for each module, there is a approximately a second of extra time. Running all the tests in the same erlang session will require some more text parsing, but it's do-able.
  • Displaying the failed tests. Seeing "Failed: 1" is not very useful for determining what went wrong, so I'll update the parsing to include the failures and errors.
  • Probably change the "run_tests" task to just "test"
  • Continuous integration that hooks into version control.

If there is significant progress I'll post the results. I hope you can use some of it :)

Tuesday, 1 April 2008

The MacbookPro Index

I'm looking into prices for a Macbook Pro, so that I can bolster my own prediction. I'm aware of the fact that for some reason, they are a bit more expensive in the UK than in the US (even without sales tax/VAT). I'm from South Africa, so I can organise for someone to bring me one, but I would never have guessed that it would be cheaper to buy it there than in the UK, and even cheaper than the states if you ignore sales tax/VAT.

Here's a summary of the prices for the 3 models in Us Dollars (USD), Canadian Dollars (CAD), Punds Sterling (GBP), South African Rand (ZAR) and Hong Kong Dollars (HKD). Prices were taken from the official apple websites, except in South African where the ZA Store is one of the official retailers.









15" 2.4GHz15"2.5 GHz17" 2.5GHz
US199924992799
CAD209925992899
GBP129915991799
ZAR184992299925999
HKD154001920021500


Using the following VAT and exchange rates (as on 31/3/2008 and 1/4/2008. A quick investigation revealed Hong Kong at 0%. I could be wrong):







CountryVAT
Exchange Rate
USD0
1
CAD0
1.02
GBP18
0.50
ZAR14
8.12
HKD0
7.79


we get the pre-tax cost in US Dollars:








15" 2.4GHz15"2.5 GHz17" 2.5GHz
US199924992799
CAD2049.82538.092813.05
GBP2197.882705.473043.86
ZAR1997.932483.942807.95
HKD1977.642465.632760.99


At a glance, the UK price is consistently higher than any others, and remember this is without VAT. UK VAT is at 17.5%, the highest of the 5, which will make the post-tax prices even higher.

And if you prefer a pretty picture (using Google Charts API):


And now onto the MacbookPro index. If you haven't heard about the Big Mac index, it is an informal way of measuring purchasing power parity between countries. It can be used to estimate if a currency is over or undervalued, since a Big Mac is pretty much the same in every country. It is calculated by dividing the price of a Big Mac in one country, by that it another country, and comparing this value to the actual exchange rate.

For the MacbookPro index, I've used an average price (non-weighted for simplicity), and here are the results:







CurrencyUnder valuation [%]
CAD0.02
GBP8.91
ZAR-0.1
HKD-1.27


and the graph:


You could conclude that the pound is undervalued by about 9%. I wouldn't. I would conclude that Macs are overpriced in the UK. I think I'll get mine elsewhere...