Python 2.6 and 3.0 are upon us.
I helped a friend set up the new Python environment for research and development, and we thought about constructing a PythonPack: a compilation of packages every home should have lying around.
[Read more…] about Must Have Python Packages
Python
Small Python Interactive Interface Trick
Not too long ago, I helped someone with some research work, and one of the research tools was also used from the Python interactive prompt.
The interface used was handy enough for development: intuitive, readable, short, and useful. Still, for interactive research it wasn’t handy enough.
To improve the script, I decided to use a trick I heard about a long time ago – using __repr__:
class NoParens(object): def __init__(self, obj): self.obj = obj def __call__(self, *args, **kwargs): return self.obj(*args, **kwargs) def __repr__(self): result = self.obj() return str(result) |
And using it looks like this:
In [2]: import noparens In [3]: def test(): ...: return 4**4 ...: In [4]: t = noparens.NoParens(test) In [5]: t Out[5]: 256 In [6]: t,t,t Out[6]: (256, 256, 256) |
For research consoles that interact with other programs or devices, such as debuggers and sniffers I found this useful, and made work a bit less annoying.
Fractal Memory Usage and a Big Number
In a previous post I said I’d talk about 4**(4**(4**4)).
First, about the number. I first saw it mentioned in a math lesson back in high-school, when the teacher wanted to demonstrate estimation abilities.
He wrote it on the board, like so:
4444
and then asked students to estimate how big that number is. Turns out this number is much bigger than most students thought. (For comparison, the number of atoms in the observable universe is 1080.)
Given that this number is so big, it should come as no surprise that computing it will consume all available memory.
What is interesting is the way the memory is consumed:
(It died with a MemoryError just before the next “jump”.)
When I first saw this I was fascinated. To those interested it is generated by the long pow function in Python, implemented in longobject.c. According to the comment there, the algorithm is a left to right 5-ary exponentiation, taken from “Handbook of Applied Cryptography”.
In short, the simpler algorithm “left-to-right binary exponentiation” (used for smaller exponents) repeatedly squares the accumulator, and according to the binary digits of the exponents, multiplies it by the base. 5-ary exponentiation basically does the same thing, but in each iteration it ‘eats’ five digits of the exponent instead of just one.
It might be very interesting to study algorithms and code according to their memory usage. Once at work I used a similar memory usage graph to optimize the memory usage of some algorithm that was eating too much memory. I don’t remember the details as it happened a few years ago, but I do remember that I recognized the “type of the memory eating”, which helped me to narrow the problem down to a specific area of code, where indeed the problem was located. (I consider this a case of programming-fu :)
Notes:
1) The reason I’m talking about Python is because it has arbitrarily sized longs built-in.
2) This graph was generated using Windows’ task manager. On my Ubuntu machine it looks quite different, almost a straight line. Any guesses why?
My Bad Memory, High Load, and Python
About a month ago the new Ubuntu 8.04 was released and I wanted a clean install. I downloaded an image and burned it to a CD. Just before installing, I tried “check CD for defects” and found a few. Turns out (*) this was because of bad memory – and memtest confirmed it.
So I went to the shop, replaced the bad memory, and also bought two new sticks. I went home to install the new Ubuntu, and after the installation, Firefox crashed. After rebooting back to memtest, I saw this:
Back at the computer shop, they asked me to reproduce the errors. Just firing up the computer and booting directly into memtest didn’t seem to do the trick, so I suspected that I had to overwork my computer a bit to reproduce this.
Since I was at the lab, I didn’t want to muck around too much.
So I thought, “what’s the quickest way to give your CPU a run around the block?”
That’s right – a tight loop:
while True: pass |
However, this snippet doesn’t really play with the memory.
The next simplest thing to do, that also jiggles some ram is the following (and one of my favorites):
In [1]: x = 4**(4**4) In [2]: y = 4**x |
I will talk about this peculiar piece of code at a later post.
In any case, this snippet also didn’t reproduce the error. It is also quite unwieldy, as it raises a MemoryError after some time. Later at home I tried two more scripts.
The first is a variation on the one above:
x = 4**(4**4) while True: try: y = 4**x except MemoryError: pass |
I ran a few of those in parallel. However, my Ubuntu machine actually killed the processes running this one by one.
The second is smarter. It allocates some memory and then just copies it around:
import sys import copy megabytes = int(sys.argv[1]) x1 = [["a"*1000 + str(i) for i in range(1000)] for j in range(megabytes)] while True: x2 = copy.deepcopy(x1) |
After both of these scripts didn’t reproduce the problem and it still persisted arbitrarily, I returned the computer to the lab. Turns out that the two replacement sticks and the two new sticks weren’t exactly identical, and that was the cause of the problem. So now my memory is well again.
As for the scripts above, I once wrote a similar script at work. I was asked to help with testing some software in some stress testing. The goal was to simulate a heavily used computer. A few lines of Python later and the testing environment was ready.
Footnotes:
(*) – Finding out that it was a memory issue wasn’t as easy as it sounds. I didn’t think of running memtest. I checked the image on my HD with md5, and the hash didn’t match. I downloaded a second image, and again the hash didn’t match. I checked twice.
At this point I was really surprised: not only the second check didn’t match the published md5, it also didn’t match the first check. Some hours and plenty of voodoo later, a friend suggested running memtest, and the culprit was found.
PyKoan – The Logic Game
As you can probably tell, I’m back from my undeclared hiatus. I’ve got lots of stuff to talk about, and I’ll be starting with PyKoan, one small project I’ve been working on lately in my spare time.
A few weeks ago I stumbled upon an article in wikipedia, regarding a logic game. This game fascinated me, especially because of the “Godel Escher Bach” connection. Quoting from Wikipedia:
Zendo is a game of inductive logic designed by Kory Heath in which one player (the “Master”) creates a rule for structures (“koans”) to follow, and the other players (the “Students”) try to discover it by building and studying various koans which follow or break the rule. The first student to correctly state the rule wins.
As it happens I’m also taking a mathematical logic course this semester. Having read about the game, I wanted to write a similar computer game. Hence – PyKoan.
PyKoan is a game where the goal is to discover some logical rule, for example, “For each x holds x%2 == 0”. This rule is applied to a koan – a list of integers. An example koan that “has Buddha nature” (follows the rule) is [0,2,8]. One which doesn’t is [1].
To implement this idea, I wrote an implementation of an expression tree very similar to the one used in vial, but with a different implemented language. I also did some experimentation with the design. Since I’ve been talking a lot about expression trees without giving a full explanation, in a future post I’ll write about the implementation used in PyKoan.
So far I didn’t code a lot of the game, just the expression tree framework, and a simple rule builder. When using Python’s interactive prompt, one can get a taste of how the game might feel:
In [19]: r = rulegen.create_rule(rulegen.easy_grammer, rulegen.easy_grammer_start) In [20]: r.eval([]) Out[20]: False In [21]: r.eval([0]) Out[21]: False In [22]: r.eval([1]) Out[22]: False In [23]: r.eval([2]) Out[23]: True In [24]: r.eval([2,2]) Out[24]: True In [25]: r.eval([2,2,3]) Out[25]: True In [26]: r.eval([3]) Out[26]: False In [27]: r.eval([4]) Out[27]: False In [28]: print r x exists such that x == 2 |
Here is how I would generate such an expression manually:
In [3]: from exptree import exps In [4]: exps.Exists('x',exps.Eq('x',2)) Out[4]: exps.Exists(exps.Var(x), exps.Eq(exps.Var(x), exps.Imm(2))) In [5]: print _ x exists such that x == 2 |
The game has many interesting possibilities for research, for example, computer players. Other possibilities include “just” guessing koans (not the rule itself), creating interesting and playable rules, and so on. There’s a lot to do.
This time, instead of just publishing the (unfinished) code, I decided to do something different. I’ve opened a space in assembla, with public read access. I’m opening this project for participation: if you want to join then leave a comment, or send me an email.
(Since Assembla seems to be going through some connectivity issues right now, here’s a link to a copy).
Singleton: my use-case for class decorators
It seems that class decorators will finally be making an appearance in Python 3 and Python 2.6. I’ve thought about using them from time to time, but the use-cases weren’t that common. However, I did find myself writing a lot of singletons.
This time I wanted to write a bunch of boiler-plate objects, that should all be singletons. So I thought of class decorators, to avoid repetition. Here is my singleton implementation, and it seems to work under Python2.6:
>>> def eq_is(self, other): ... return self is other ... >>> def singleton(cls): ... cls.__eq__ = eq_is ... return cls() ... >>> @singleton ... class a(object): ... def __repr__(self): ... return 'foobar' ... >>> a foobar >>> a == a True |
I just can’t wait for the new Pythons to come out of alpha!
Python + Curses + Numpy -> Ascii Art Rotating Cube
Well, the title says it all, or at least most of it.
If you are still not convinced, a picture’s worth 500 dwords:
/ |\
/ | \
/ | \
// | \\
/ | \
/ \ \
| / \ |
|\ / \ /|
| \ / \\ / |
| \ / // |
| /\ / \ |
| / \\ / \|
|/ \ / |
/ \/ /
\ | /
\ | /
\\ | //
\ | /
\ | /
\ /
I’ve been toying with the idea of writing a roguelike, and I thought that it would be really fun if it had an ‘Eye-Of-The-Beholder’ kind of view as well, just in ascii-art. There are plenty of things I wanted to do with ascii-art, since it’s such a nice toy. So I started writing some code, and this is a small test on the way.
Nowadays, when I discuss 3d ascii-art, people usually think about a picture transformed with aalib or something similar. Although it is a (very) nice idea, I think it would be more fun to play with ascii-art directly.
Other playing possibilities include a ray-tracer. You could write some fps with ray-tracing ascii-art graphics, because there are so few pixels.
Maybe I’ll write one, when I get to it.
Oh! The code, what about the code?
Here it is.
A few notes:
1. The code ain’t too pretty, as it is a work in progress that doesn’t get much time invested in it. However, I’d still rather publish it.
2. It uses curses. Under windows you’ll have to get some replacement module.
3. It uses numpy. If you don’t have it already, be sure to get it.
4. Run ‘test_cube.py’. Use the direction keys to rotate the cube, ‘q’ to exit.
Python Tidbits
Memory Leaks
With the advent of the Python’s garbage collector, it would seem that Python programs should not leak memory. However, this is not always the case. With just a bit of circular references, you can find yourself leaking quite a bit of memory.
A simple example is a bidirectional data structure, like a 2-way linked list, or a tree where the nodes have a reference to their parents. To really free those, you have to break the cycle manually. Another option is to use a weakref for some of the references. (Usually, I like to use weakref.proxy for the parent links.)
An easy way to test code for memory leaks is to run it in a loop (allocate, do job, deallocate, repeat), and call gc.collect() before and after. If the value that gc.collect() returns after the loop grows with the size of the loop, you might have a memory leak.
I found out about a special case of a potential memory leak just the other day.
Let’s say you want to implement some switch code. A common idiom is to write it like this:
def a(x): print 'a', x def b(x): print 'b', x ... func = {0: a, 1: b}[x] func() |
This works well enough. However, if you do the same thing in a class instance, things start to get messy:
class A(object): def __init__(self): self.lookup = {0: self.a, 1: self.b} def a(self, x): print 'a', x def b(self, x): print 'b', x def do_something(self): ... func = self.lookup[x] func(x) |
In this simple example, __init__ creates a reference cycle. This is because self.a creates a method object on the spot, with a reference to self.
So, if z is an instance of A, our cycle is: z->lookup->z.a->z.
Take heed.
(Note: Some cycles are collectible with gc.collect(). The simple cycle described here is such a case. It may get ugly though.)
Undefined
While writing the VM for vial, we needed some way to avoid testing assembly code for undefined values.
For example, after executing a div instruction, CF is undefined. We handle this in the templates by writing CF=UNKNOWN(), and we allow to VM to decide on a value. If you need the VM to just execute code, returning 0 for undefined values is fine. If, however, you are testing code, your actual CPU might return a non-zero value, and your test will fail with no real reason.
To solve this problem, our VM may be told to return a special singleton object for undefined values:
class _UndefinedNumber(object): def __eq__(self, other): if other is self: return True return False def __ne__(self, other): return not self == other def binary_action(self, other): return self def unary_action(self): return self def __str__(self): return "Undefined" __repr__ = __str__ (__add__, __sub__, __mul__, __div__, __floordiv__, __mod__, __pow__, __and__, __xor__, __or__, __lshift__, __rshift__, __rlshift__, __rrshift__, __radd__, __rsub__, __rmul__, __rdiv__, __rfloordiv__, __rmod__, __rpow__, __rand__, __rxor__, __ror__) = 24*[binary_action] (__neg__, __pos__, __abs__, __invert__) = 4*[unary_action] Undefined = _UndefinedNumber() |
Now, we test only the flags that are not Undefined. Note that any operation on an Undefined returns an Undefined. This is done to allow registers to be Undefined as well. This way, if AX gets Undefined, so will AH and EAX.
Here is an example:
In [2]: Undefined + 1 Out[2]: Undefined In [3]: Undefined * 2 Out[3]: Undefined In [4]: Undefined / Undefined Out[4]: Undefined |
Note that this constant might behave a bit strangely. For example, Undefined * 0 is Undefined, and Undefined – Undefined is also Undefined. Because of that, I’m not sure using this object in production circumstances is a good idea, so in the meantime, this is just a testing utility.
Issues in writing a VM – Part 3 – State and Memory
When implementing the VM, I had to keep track of state. The state of the VM includes the registers, virtual variables and memory. Fortunately, keeping track of state information is pretty easy. Basically, it amounts to having a dict, where the keys are registers or variables, and the values are, well, their values.
Holding the state of registers is a bit involved by the fact that registers may overlap, as I mentioned in a previous article. To handle this, the class keeping track of the state information, upon seeing a request to change the value of a register, propagates this change to its parent and child registers.
Holding memory might be different though. At a first glance, it would seem that memory should be kept in some buffer. However, it is much easier to keep the memory in a python dict as well, and treat that dict as if it was a sparse array. This implementation allows programs to write at address 10, and at address 10000, without requiring the VM to keep track of all the addresses in between. (Of course, we are not going to implement paging just now :)
I really liked this idea of treating dicts as sparse lists. In fact, it could work even better with some tree data structure instead of a hash table. With a tree data structure your keys would be sorted, and you could do slices.
I went ahead and tried using tree data structures for this, but it seems to be more trouble than it’s worth, so I think that unless it becomes a real timing issue, I’ll let it go.
I did have some fun wrapping the memory in some class to abstract away the data structure, and to give it a few more capabilities:
In [2]: import vm In [3]: m = vm.VMMemory() In [4]: m.set(0, "hello world!\r\n") In [5]: m.set(51, "foobar, foobar\x00") In [6]: m.set(77, "a"*30) In [7]: print m 0000: 68656c6c6f20776f726c64210d0a???? hello world!..?? 0033: 666f6f6261722c20666f6f62617200?? foobar, foobar.? 004d: 61616161616161616161616161616161 aaaaaaaaaaaaaaaa 005d: 6161616161616161616161616161???? aaaaaaaaaaaaaa?? |
Issues in Writing a VM – Part 2
Writing a VM capable of executing expression trees is different from writing a VM for executing assembly instructions. Here I’ll cover several issues stemming from this difference.
The first group of issues involve generality. Supporting a specific instruction set is a straightforward job, even if a hard one. Vial has to support multiple platforms and that’s a little tricky. These are just a few of the problems:
- Different registers for each instruction set. This one is easy enough to solve. Just have a node in the expression tree with some value to indicate the register.
- Register overlaps. A change to one register implies a change to its parents and its children. Consider RAX->EAX->AX->AH,AL. Changing EAX will affect all of the registers in the hierarchy.
To handle this, we wrote a CPU class to keep all the info about the platform, including register overlaps. - Delayed branches. Some platforms have branch delay slots. This means that after any branch instruction, right before the branch is taken, instructions in the delayed slots are executed anyway. For instance, SPARC has three delay slots, while MIPS has just one. This isn’t an easy issue to solve, and for now we didn’t tackle it. We’ve got a few ideas though.
To make sure that our implementation is generic enough, we decided to write a skeleton disassembler implementation for MIPS as well.
The second group of issues involve the nature of expression trees versus instructions:
- Stepping over statements or instructions? Each expression tree for an instruction usually holds more than one statement. For example, dec eax changes eax as well as the zero flag. Since some instructions like rep stosd may contain a long loop, being able to step over statements instead of expressions is preferable.
The problem is, executing expression trees is done with a DFS-like walk. If implemented with recursion it makes pausing the walk for each step a bit complicated. However, recursion is the clearest way to write the execution code, and I’d rather not give it up.
My solution was to use Python generators. Each time a statement was executed, the function would yield, thus returning control to the calling function, while keeping its state intact.
- Instruction Pointer changes. The lower-level disassembler returns expression trees for each instruction. However, it does not return the jump to the next instruction as well. While this is the required behavior, it means that the VM should change the instruction pointer after executing each instruction.
This is easier said than done: What should we do after jumps? Several possible solutions emerged.
The first was to append an IP change to each instruction’s expression. Those changes will have to be appended only where needed.
A second solution was to check if the IP was changed, and if it was not, change it. This solution however will not support instructions that jump to themselves.
The last and our preferred solution was to check if the IP was touched. This solution is simple and very straightforward.
There are many more issues I didn’t write about, for example, self modifying code. I’ll leave those issues for future articles.