+1
i stay functional if possible and fall back to mutable on isolated,
performance critical spots if i can't get it done fast enough in a
purely functional way.
i solved the move-mess-up-everything problem by forcing a move to
implement both apply and unapply on a game board. (it was a java
project). this way, i could still safely try a move and undo it in
secret - and i could still use multithreading by making one copy of a
board per thread.
however, depending on the game, the single thread version was up to 10x
faster because of being able to cut off large portions of the tree while
the multithread version had less information per branch and could not
simply share it while travering the tree of possibilities.
Am 25.08.2012 22:01, schrieb Jim - FooBar();:
> 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
--
--
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
