Property test with 6+ uses of a generator locks up

[atacratic]

The following locks up indefinitely during evaluation, spinning the CPU (but not eating memory).

eg =
  go _ =
    t =
      !int
        * +25
        + !int
        * +4
        + !int
        * +12
        + !int
        * +30
        + !int
        * +24
        + !int
--        * +60
--        + !int
--        * +60
--        + !int
    expect true
  .base.test.runs 1 go

Six uses of !int seems to be the minimal number to generate the lockup. With five uses evaluation takes about 7 seconds for me.

Related to #45 maybe?

[edit] ah, not 'indefinitely': it's about a minute for 6 uses, and grows as you add more

[aryairani]

Thanks for reporting this!

[pchiusano]

Yeah this is a great minimal performance bug. Wild guess is perhaps the flatMap for Weighted (which backs Gen) has some quadratic behavior for left nesting (which this would be I think). If so we could apply some standard tricks to it to fix.

/cc @runarorama

[runarorama]

I'll try hitting it with Codensity :)

[pchiusano]

Observation on this:

> sample 1 '(List.replicate 30 nat)

Is very snappy, but replacing nat with int takes forever for any value of n > 5. Taking a look at these:

  base.Weighted.ints : Weighted Int
  base.Weighted.ints =
    go n = yield n <|> weight 1 '(go (if n > +0 then negate n else Int.increment (negate n)))
    List.foldLeft (a n -> a <|> yield n) Weighted.Fail [+0, +1, -1, maxInt, minInt] <|> go +2

  base.Weighted.nats : Weighted Nat
  base.Weighted.nats =
    go n =
      use Nat +
      yield n <|> weight 1 '(go (n + 1))
    go 0

The only difference I see between these is that the thing being flatMap'ed is a somewhat shallow left nested (a <|> b) expression.

I'm not certain there's actually different asymptotics between these two, or just different constant factors, but if it's just constant factors there's a huge difference between the two.

I wonder if just adding a <|> constructor to Weighted would help.