AoC issue: Poor DFA performance

[fridis]

The Fuzion Advent-of-Code solution from 12 Dec

dec12_part2 is

  input := (io.stdin.with ()->io.buffered.read_lines).val.filter !=""

  binomial(n, k i64) =>
    for res := i64 1, res * (n+1-i) / i
        i in i64 1 .. k
    else
      res

  record(s String) =>
    (record (s.split[0]
             .as_codepoints)
            (s.split[1]
              .split ","
              .map_sequence (.parse_i32.val)))

  record(springs Sequence codepoint, groups Sequence i32) is

    times5 => (record ((springs ++ ["?".as_codepoints.first]).cycle.take springs.count*5+4).as_array
                      (groups.cycle.take groups.count*5).as_array)

    count(s, g, sr) i64 =>
      if sr > 0
        if      s >= springs.count || springs[s] = "."  then 0
                                                        else count s+1 g   sr-1
      else if sr = 0
        if      s >= springs.count || springs[s] = "."  then count s   g   -1
        else if                       springs[s] = "#"  then 0
        else                                                 count s+1 g   -1
      else
        if      s >= springs.count && g >= groups.count then 1
        else if s >= springs.count                      then 0
        else if g >= groups.count  && springs[s] = "."  then count s+1 g   sr
        else if g >= groups.count  && springs[s] = "#"  then 0
        else if g >= groups.count  && springs[s] = "?"  then count s+1 g   sr
        else if                       springs[s] = "."  then count s+1 g   sr
        else if                       springs[s] = "#"  then count s+1 g+1 groups[g]-1
        else
          for q := 0, q+1 while s+q<springs.count && springs[s+q] = "?" else
            next_is_dot := if s+q >= springs.count || springs[s+q] = "." then 1 else 0
            for ng := 0, ng + 1
                csum := i64 0, csum + cng + cls
            while g+ng <= groups.count && ((0..ng-1).map gi->groups[g+gi] |> sum) + ng - next_is_dot <= q do
              # collapse groups to size 1 including gap:
              q_collapsed := q - ((0..ng-1).map gi->groups[g+gi] |> sum) + next_is_dot

              # we fit ng groups into q question marks
              factor := binomial q_collapsed.as_i64 ng.as_i64
              cng := if factor = 0 then i64 0 else factor * count s+q g+ng sr

              # now try to connect the following one
              cls i64 := if next_is_dot = 0 && g+ng < groups.count
                  lsz := groups[g+ng]
                  for cl := i64 0, cl + cd
                      nl := 1, nl + 1
                  while nl < lsz && q_collapsed-nl >= ng
                    factor2 := binomial (q_collapsed-nl).as_i64 ng.as_i64
                    cd := if factor2 = 0 then i64 0 else ca := count s+q g+ng+1 lsz-nl; factor2 * ca
                  else
                    cl
                else
                  0
            else
              csum

  data := input.map_sequence record

  part1 => data.map_sequence (.count 0 0 -1) |> sum
  part2 => data.map_sequence (.times5)
               .map_sequence (.count 0 0 -1) |> sum

  say "part1 $part1 part2 $part2"

requires almost 10sec to run on an empty input:

> echo "" | time ~/fuzion/clean/fuzion/build/bin/fz -XjavaProf part2.fz
part1 0 part2 0
 + pid33883-fuzion-XjavaProf-flamegraph.svg
27.45user 1.26system 0:09.16elapsed 313%CPU (0avgtext+0avgdata 1765460maxresident)k
 > 

The problem is that this test apparently stresses the DFA (4.6s) and findAllClasses (1.7s) phases:

[michaellilltokiwa]

duplicate of #3391

[fridis]

The reason for this is probably different than that of #3391, so I re-open this.