A couple of nights ago, after reading like the 10th consecutive network analysis paper, I absolutely needed to do something different. Consequently I grabbed my copy of land of lisp and decided to port chapter 10 game to Python.
The game is easy to understand. It starts with a single animal moving in the world. The animal is able to reproduce (alone, no sex, it's family friendly! -- well don't know) introducing mutations. At each stage each animal chooses a direction, moves there, if there are plants then it eats them (gaining energy) and if has enough energy spawns a child. New plants are grown at each stage: one in a random spot of the central "jungle" area and one in a random spot in the whole board (possibly in the jungle). When the animal finishes energy, dies.
The original lisp code is very loop oriented, with massive use of global mutated variables. As a consequence I thought that a Python translation would be very easy, and in fact, it was. The "sensible" spots are where I expected them to be. For example here:
For those who are not fluent in Lisp, in the "labels" form the recursive function angle is defined and that is used afterwards. In the first version of the code, I did a rather faithful translation (and the resulting code was very unpythonic).
Here we notice that calls to random & co. take a huge amount of time. But that was to be expected. Here the point is that turn and in turn (pun intended) angle take a huge amount of time. The code could be rewritten in a much simpler way, without the inner recursive function. Here turn is responsible for 2/3 of the time: if we could just reduce the time of an order of magnitude (that is, place the function in the same order of the other methods of Animal) we could achieve acceptable performance.
However, even without the profiler Python proves quite slow. For example lets time 10000 evolutionary iterations:
The game is easy to understand. It starts with a single animal moving in the world. The animal is able to reproduce (alone, no sex, it's family friendly! -- well don't know) introducing mutations. At each stage each animal chooses a direction, moves there, if there are plants then it eats them (gaining energy) and if has enough energy spawns a child. New plants are grown at each stage: one in a random spot of the central "jungle" area and one in a random spot in the whole board (possibly in the jungle). When the animal finishes energy, dies.
The original lisp code is very loop oriented, with massive use of global mutated variables. As a consequence I thought that a Python translation would be very easy, and in fact, it was. The "sensible" spots are where I expected them to be. For example here:
(defun turn (animal) (let ((x (random (apply #'+ (animal-genes animal))))) (labels ((angle (genes x) (let ((xnu (- x (car genes)))) (if (< xnu 0) 0 (1+ (angle (cdr genes) xnu)))))) (setf (animal-dir animal) (mod (+ (animal-dir animal) (angle (animal-genes animal) x)) 8)))))
For those who are not fluent in Lisp, in the "labels" form the recursive function angle is defined and that is used afterwards. In the first version of the code, I did a rather faithful translation (and the resulting code was very unpythonic).
def turn(self):
# inefficient and unpythonic, rewrite!
x = random.randint(0, sum(self.genes)-1)
def angle(index, x):
xnu = x - self.genes[index]
if xnu < 0:
return 0
else:
return 1 + angle(index+1, xnu)
self.dir += angle(0, x)
self.dir %= 8
Now, the code is horrible, in my opinion. And it was late night... I convinced myself that the gratuitous use of recursion should not impact too much on the execution times: after all it can't blow the stack as it is on exactly 8 elements. I was quite wrong.
I run the profiler on the file (-mprofile) and let it run just 5000 iterative evolutions. The total time is 75.698 seconds. Please, consider that the profiler slows things a lot. I am going to give performance impressions later. Here I report some snippets of the full profile output.
| 781884 | 2.911 | 0.000 | 2.911 | 0.000 | :0(random) |
| 755960 | 2.791 | 0.000 | 2.791 | 0.000 | :0(sum) |
| 65076/2958 | 1.482 | 0.000 | 4.095 | 0.001 | copy.py:145(deepcopy) |
| 755960 | 3.482 | 0.000 | 3.482 | 0.000 | isle.py:31(move) |
| 755960 | 10.859 | 0.000 | 51.522 | 0.000 | isle.py:44(turn) |
| 3528217/755960 | 21.310 | 0.000 | 21.310 | 0.000 | isle.py:47(angle) |
| 755960 | 2.488 | 0.000 | 2.517 | 0.000 | isle.py:56(eat) |
| 755960 | 2.555 | 0.000 | 6.802 | 0.000 | isle.py:61(reproduce) |
| 5000 | 10.540 | 0.002 | 75.516 | 0.015 | isle.py:73(update_world) |
| 1 | 0.000 | 0.000 | 75.698 | 75.698 | profile:0(execfile('isle.py')) |
| 781884 | 7.859 | 0.000 | 10.770 | 0.000 | random.py:160(randrange) |
| 781884 | 6.353 | 0.000 | 17.123 | 0.000 | random.py:224(randint) |
% time python isle.py << EOF 10000 quit EOF 13.04s user 0.02s system 99% cpu 13.070 totalNotice the trick with << EOF to let us automate user input (I love Unix). Let us compare it with the original lisp implementation. With clisp the performance are less than spectacular to say the least:
% time clisp << EOF<br />(load "evolution.lisp")<br />(evolution)<br />10000<br />quit<br />EOF<br />clisp <<< '(load "evolution.lisp") (evolution) 10000 quit' <br />57.54s user 4.96s system 98% cpu 1:03.31 total<br /><br />Probably I could pre-compile the stuff and improve performance. No time right now, moreover I was more interested in SBCL anyway. However, with SBCL it is impressive:
% time sbcl --noinform --load evolution.lisp --eval '(evolution)' << EOF 10000 quit EOF 0.90s user 0.10s system 99% cpu 1.011 totalThat is like 13 times faster than the Python version. I'm sure I can optimize the Python program. For sure, I expect to cut down the execution time of a factor of at least 2 fixing the bloody recursive function. And about what to optimize afterwards, bets are open. On the other hand, the careful reader has surely noticed that turn is a method: in fact I decided to transform Animal in a class. I believe that it is a mistake (that is to say, either transform the full program in an object oriented way or let the whole thing without objects). For example the "reproduce" method *sucks* to a very large extent:
def turn(self):
# inefficient and unpythonic, rewrite!
x = random.randint(0, sum(self.genes)-1)
def angle(index, x):
xnu = x - self.genes[index]
if xnu < 0:
return 0
else:
return 1 + angle(index+1, xnu)
self.dir += angle(0, x)
self.dir %= 8
It is clear that the method should return the copy instead of adding to the global ANIMALS list. Anyway... I will deal with object orientation of that code in a later post.
My opinion is that the lisp code which I translated is not very lispish, but I like a lot the idea of writing the program quickly. This is the classical example where one risks to over-engineer the simple program, which does its job and is really funny. I loved looking at the black and white terminal with all my animals running around trying to survive! Still, I believe that writing the thing in Python in the first place would have yielded very different code, as it would have done doing it in Haskell or even Scheme. I believe that the example was more on the procedural/imperative aspects of lisp than on writing functional (or OO) code...
Full code here.
No comments:
Post a Comment