Cats: StateT Performance Regression

[fosskers]

Between 1.0.0 and 1.1.0 (and previously between 0.9 and 1.0.0), StateT has suffered a performance regression. I discovered this when updating versions for scalaz-and-cats.

For:

  type EitherStr[T] = EitherT[Eval, String, T]
  type StEtr[T] = StateT[EitherStr, Int, T]

  def countdownT: StEtr[Unit] = StateT.get[EitherStr, Int].flatMap({ n =>
    if (n <= 0) MonadError[StEtr, String].raiseError("crap")
    else StateT.set[EitherStr, Int](n - 1) *> countdownT
  })

  def runCountDownT: Either[String, (Int, Unit)] = countdownT.run(10000).value.value

we see this runtime drop from 8,920,953 ns to 9,744,808 ns. This is after a 2x slowdown between 0.9 and 1.0.0 which @iravid said had something to do with IndexedStateT. This 9.7 million ns number is around twice as slow as the equivalent ScalaZ, and 5 orders of magnitude slower than Haskell.

[kailuowang]

Thanks for reporting this. It's probably introduced in this PR https://github.com/typelevel/cats/pull/2187 which improves the stack safety of StateT.
A very interesting alternative solution might be @iravid 's FreeState, which seems to be 1 order of magnitude faster.

[fosskers]

Can't really get mad about a regression if it's for safety/correctness eh? Cool, hopefully FreeState turns out.

[johnynek]

We did actually know it was slightly slower, but we made the trade off. It would be very interesting to see if we could recover some of that.