Hello everyone,
in this post I'm not asking for something specific, but rather I'd like
to spark a discussion regarding the issue of performance within the
functional paradigm...most of the things i will mention will probably
not be news for most of you...Hopefully, however the issues I plan to
raise will eventualy help someone else faced with the same dilemmas as me...
First of all, let me clarify upfront that I strongly believe that
'functional' and 'immutable' should be the default (as Rich often says).
This thread is certainly not about praising the 'imperative' style. It
is about having all the facts before you start coding (probably before
even designing)...Most of you presumably already do...
Ok so, it is evident from my other posts that I'm building a library for
writing board games. In a nutshell, when it's finished, I'd like someone
else to be able to write up his own board game, show it up on screen and
genetically train a neural-net for an opponent, in literally less than
5-6 hours (~ 100 LOC).
Now, for those of you that have done any board games you can immediately
identify the hot-spots of such a program. These are 2: actually
exploring the game-tree and training the neural-net. Notice how both
these tasks can be run in parallel...(exploring the game tree is not
immediately apparent how to do in parallel but we have reducers)...
Generally there are 3 major ways going about writing a program -
functionally all the way, imperatively all the way, a mixture. I sort of
implemented all 3 categories for my chess game and I've got some
interesting results:
1. Firstly and more importantly (I mean that), the purely functional
and immutable road is simply such a pleasure to travel...There are
no words to describe the beauty, clarity and elegance of the
functional version. Mutation is non-existent or only through
reference types and operations like 'update-position' and 'move'
return brand new piece and board respectively. Also, it is the only
one that is extremely stable and always brings back the correct
answer. It is *gorgeous*... On the flip-side, it performs horrible!
It is very very slow for realistic depths like 4 or 6 even
regardless of utilising reducers to the maximum and countless
optimisations. The best time I can report is 9 min for level 4.
2. after watching Daniel Solano Gomez's presentation on infoq ("11 tips
to boost performance"), I realised that If I wanted raw speed (as he
puts it), I 'd have to resort to arrays. Well, I made my heart a
stone and went to implement an array-based version that favours
mutation. Having such modular code in the first place, that did not
take too long...I just wrote up different version of 'move' and
'collides?' (amove, acollides?) that know how to deal with arrays
and created a ChessPiece2 record which holds a java.awt.Point object
which is mutated by update-position (instead of returning a brand
new piece). Basically, (I thought) i was done in 30 min... However
it turned out I was being sooo ignorant!!! Making such a u-turn in
programming paradigms while working on the same project is never
that simple. The functional style protected me from so many bad
things...of course, I already knew that but I was surprised to see
how many these are! For instance, making a move in the functional
version caused absolutely no damage...there is an 'execute!' fn that
does damage if we want it to (via atom only) but this is to be used
only when we decide what move we want. Now, trying out a move messes
up everything!!! Now, I need means of undoing and not only that...My
entire searching algorithm can no longer function properly...Off the
top of my head, I need some sort of serial loop/recur that tries
moves when recursion rolls in and takes them back (by undoing) when
recursion rolls out . In other words I need to keep track of the
changes carefully! On the filp-side, even though this version has
bugs and does not return the correct answer, it seems it can reach
level 4 in roughly 2 min. This is 4x faster! Again, I'm being
cautious cos there are bugs so I can't be sure of the time but there
seems to be a dramatic performance increase...The code however is a
lot buggier and uglier...
3. Finally I tried doing a functional version that uses mutable arrays
but doesn't mutate them...Instead critical fns like 'move' build new
arrays (btw 'aclone' does not deep copy) to return and updating a
piece's position does return a new piece... This version, is not
very stable but does return the correct answer in just over 7 min
for level 4...again the importance of immutability shines! the
timing shows that i got 22% better performance. I have not profiled
this but I expect most of the time being spent copying arrays.
In essence what am I telling you here? 2 things basically... Firstly,
think about performance before you actually design your solution...it
may be that some tasks are not well suited for immutable data-structures
and it can be a show stopper. Don't think for a second that you can
convert your gorgeous, purely immutable approach to a purely mutable
(better performing one) without any cost. These are 2 fundamentally
different choices that lead to completely different algorithmic designs...
so where does this leave me? well, I am going to stick with the elegant,
all-clojure solution and perhaps find a 8/12-core machine to do my
training on... however, in a different setting I might choose
otherwise...at the moment I don't have time to spend hundreds of hours
to fix all the bugs of the mutable version so i can get it to preform
better... I hate the process as well...if someone was paying me though,
my ego would be far less!
Of course, there are going to be people that will say: "You're using the
wrong algorithm!", "You can prune the tree!" etc etc...that is not the
point though...even of I do pruning does anybody think I can get to
level 4 in less than 5 min? That would require pruning half the tree!
anyway, what I'm trying to say is that in algorithms like these
performance matters a lot... most machine learning algorithms involve
matrix multiplication...why do you think all the machine-learners use
matlab? you think they enjoy writing matlab code? No - it just goes
super fast ! If performance matters to you , then perhaps your time is
best spent thinking a mutable approach from day 1... I cannot believe I
said that but there you go - I said it!
No hard feelings eh? I still love Clojure... :-)
Jim
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
