Array.ST is not being nice to me

[Robert van Herk]

Hi all,

I have a problem with regards to the speed of ST arrays.

In short: a Data.Map.Map outperforms Data.Array.ST in my application,
whereas as far as I understand it, the ST array should be quicker.

My application is a compiler. It compiles some source code into a (huge)
number of boolean equations. These equations are finally printed to stdout;
they form my "byte-code".

Also the equations are defined in terms of the other equations again. So,
for instance, compiled byte code may look like:

1 == 5
5 == True /\ 3
3 == False

To optimize the compiled code, I do some tricks like constant propagation.
So, for instance, if I know that one equation always results in some
constant, I substitute that constant for that equation. So above set of
equations will be rewritten as:

1 == False
5 == False
3 == False

------

All in all, my compiler does the following:
- It generates a set of equations for some statement in the source code
- It rewrites these equations
- It remembers for each equation which other equations it depends upon,
such that if these are rewritten to something simple, this equation may be
rewritten too.


So there are a lot of lookups of the equations, especially for all the
rewritings.

All in all, I store quite some data for each equation, amongst which are:

data EquationState = EQS {cDefinition::Equation, usedBy::Map.Map Int (),
...}

First, I stored all the equations in a Data.Map.Map. Int EquationState.
But then I thought it'd be more clever to put it into an ST array, seen the
large number of lookups. So now i put it into an ST array.
However, the code runs much, much slower now (about 4 times).

The ST array does use slightly less memory though.

I did some profiling. It seems that it is not the GC that is making
over-hours.

So my theory now is:
I do a large number of lookups.
Only a small number of these lookups trigger a change in the array.
One EquationState is pretty big.

Is it so that when you look something up from an ST array, the whole
element gets deeply copied in memory, just in case you would change it in
the array?

Seen the size of my elements, I could imagine that that would cause a whole
bunch of needless copying.

Or is there some other reason for this slower behaviour of ST array?
Robert
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20080208/f2212257/attachment-0001.htm