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??
This entry was posted in Design, Programming, Python and tagged , , , , . Bookmark the permalink.