Array.ST is not being nice to me

Robert van Herk robert.van.herk at
Fri Feb 8 06:11:03 EST 2008

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

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

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?
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the Glasgow-haskell-users mailing list