Skip to content

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

Open
@msaxena2

Description

@msaxena2

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.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions