[Haskell-cafe] Quadratic complexity though use of STArrays

[Bertram Felgenhauer]

Dan Rosén wrote:
> What complexity does these functions have?
> 
> I argue that the shuffleArr function should be O(n), since it only contains
> one loop of n, where each loop does actions that are O(1): generating a random
> number and swapping two elements in an array.
> 
> However, they both have the same runnig time (roughly), and through looking
> at the plot it _very_ much looks quadratic.

Right. In the case of shuffleArr, it's the garbage collection time that
explodes. I think that the reason is that the garbage collector has to
scan the whole array (which lives in the old generation) on each garbage
collection, while the young generation is kept very small, making GCs
very frequent.

Indeed the program behaves much better with just one GC generation:

  > ./a.out +RTS -G1
  (1000000, 1988698, 1760732, 1.98870,1.76073)
  (1500000, 2991546, 2683592, 1.99436,1.78906)
  (2000000, 4018388, 3611451, 2.00919,1.80573)

Output format:
  (n, time for your original shuffleArray (t1),
      time for Daniel's stricter version (t2),
      t1/n, t2/n)

While with the default settings, it looks much worse:
  > ./a.out
  (1000000, 7575850, 7958790, 7.57585, 7.95879)
  (1500000,17119397,19449044,11.41293,12.96602)
  (2000000,30687335,35125661,15.34367,17.56283)

You can also increase the initial heap size,
  > ./a.out +RTS -H250M
  (1000000, 1131828,  901863, 1.13183, 0.90186)
  (1500000, 1726737, 1427783, 1.15116, 0.95186)
  (2000000, 2324647, 1935705, 1.16232, 0.96785)

Bertram