On Friday 09 July 2010 16:15:30, Patrick LeBoutillier wrote:
Hi all,
I recently started writing a simulator for Knuth's MIX computer in Haskell. My first attempt had the basic data types for the machine defined like this:
type Byte = Word8 type Address = Word16 type Word = Word32 type FieldSpec = (Int,Int) data Register = A Word | X Word | I Address | J Address type Memory = M.Map Address Word
After hitting some kind of dead end with this setup (basically getting frustrated/lost with all the bit-twiddling), I tried again with these more abstract types:
data Byte = Byte Word8
This could be type Byte = Word8, I don't think that would complicate anything. If it would, newtype Byte = Byte Word8 would eliminate the run- time cost of the data constructor.
data Sign = Plus | Minus
data Address = Address Byte Byte data SignedAddress = SignedAddress Sign Address data Word = Word Sign Byte Byte Byte Byte Byte data FieldSpec = FieldSpec Int Int
As Felipe said, make the fields strict and {-# UNPACK #-} them for better performance, {-# UNPACK #-}-ing Sign too should be better, then all the data is in one place and you needn't visit the heap multiple times. If you don't need to access individual bytes, using Word16/Word32 instead of multiple Byte fields would be faster, too.
data Memory = Memory (M.Map Address Word)
Now I find my code is much clearer (it almost writes itself...) and practically absent of low-level bit operations (except, for example, converting a Word into an actual Haskell Int32 to perform the actual arithmetic). However, I'm wondering about the cost of all the "packing/unpacking" via pattern-matching and/or accessors. Perhaps I should not worry about this and optimize later if required?
Probably. For example, it is likely that the lookups in the Map take far longer than the pattern matching/field accesses. So before you go into low-level optimisations, you should investigate different memory representations (since the memory will probably be mutated a lot, you might look at STArrays, if that doesn't cut it, STUArrays [that would mean Word should become a native type again]).
Is this type of premature optimization (assuming the previous version was faster...) really the root of all evil?
No. But it's the cause of a lot of unnecessary headaches. If you know that performance matters much and you know that low-level code is faster for your task and you are familiar enough with the needed low- level stuff, then start out writing the low-level code. If you're not at home with e.g the bit-twiddling stuff, it will be easier to write the code high-level first and then translate it to low-level-bit- twiddling. If you don't know that the low-level stuff will be faster (the optimiser is pretty good), write the high-level code and measure. Translate to low-level if necessary. (Translating from high-level to low-level tends to be much easier than writing low-level from scratch, since in the translation, you can focus on small details while the big picture is already there).
Note: I'm not far enough into the simulator to be able to actually test it out and get metrics.
Patrick
Thanks,
Patrick