[Haskell-beginners] Pattern matching vs bit twiddling?

[Daniel Fischer]

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