<html><body>
<p>Hi all,<br>
<br>
I have a problem with regards to the speed of ST arrays.<br>
<br>
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.<br>
<br>
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".<br>
<br>
Also the equations are defined in terms of the other equations again. So, for instance, compiled byte code may look like:<br>
<br>
1 == 5<br>
5 == True /\ 3<br>
3 == False<br>
<br>
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:<br>
<br>
1 == False<br>
5 == False<br>
3 == False<br>
<br>
------<br>
<br>
All in all, my compiler does the following:<br>
- It generates a set of equations for some statement in the source code<br>
- It rewrites these equations<br>
- 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.<br>
<br>
<br>
So there are a lot of lookups of the equations, especially for all the rewritings.<br>
<br>
All in all, I store quite some data for each equation, amongst which are:<br>
<br>
data EquationState = EQS {cDefinition::Equation, usedBy::Map.Map Int (), ...}<br>
<br>
First, I stored all the equations in a Data.Map.Map. Int EquationState.<br>
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.<br>
However, the code runs much, much slower now (about 4 times).<br>
<br>
The ST array does use slightly less memory though.<br>
<br>
I did some profiling. It seems that it is not the GC that is making over-hours.<br>
<br>
So my theory now is: <br>
I do a large number of lookups.<br>
Only a small number of these lookups trigger a change in the array.<br>
One EquationState is pretty big.<br>
<br>
<b>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?</b><br>
<br>
Seen the size of my elements, I could imagine that that would cause a whole bunch of needless copying.<br>
<br>
Or is there some other reason for this slower behaviour of ST array?<br>
Robert</body></html>