[Haskell-Performance] Performance Drop Using Cell-Map despite deterministic map accesses

Please Prepare Test Data

Program Execution in a definition where the <k> cell resides under a cell with multiplicity * and type Map results in a rise in time per rewrite step as the configuration grows dynamically.

Consider the following definition:

module MULTICELL
  imports INT
  syntax Stmt ::= "addCell" "(" Int ")"  | "wait"

  configuration <cells>
                  <cell multiplicity="*" type="Map">
                    <id> 0 </id>
                    <k> $PGM:Stmt </k>
                  </cell>
                </cells>
                <counter> 1 </counter>


  rule <k> addCell(N) => addCell(N -Int 1) ... </k>
       (.Bag =>  <cell> <id> C </id> <k> wait </k> </cell> )
       <counter> C => C +Int 1 </counter>
    requires N >Int 0

  rule addCell(0) => .

endmodule

A program in the above definition has the form addCell(N), where N is the number of <cell>(s) to be added during execution. Note that none of the added cells can be further rewritten; only the initial cell is rewritten. Thus, the access to the map is deterministic.

Attached are bug reports for programs addCell(70) and addCell(80). On my machine, the former takes 31 s, and the latter 54 s, indicating rewrites take much longer as the size of the cell map increases.

P.S. I also tried added <id> 0 </id> to the rules for addCell, in the hope that it would speed up identifying the map-item where the rule can apply, but it didn't seem to make any difference.

Start with the MULTICELL definition in the issue and reproduce the behavior using the attached addCell(70) and addCell(80) bug reports. Compare rewrite time as the Map cell collection grows; done means the performance regression is characterized and the reported scaling behavior is addressed.