Profiling help (Warning: Euler spoilers)
James, Which version of Control.Monad.State are you importing? If you're just importing vanilla Control.Monad.State, that's actually sending you to Control.Monad.State.Lazy. Using Control.Monad.State.Strict might solve your problems, srsly. Laziness can result in epically failing memory leaks. Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
Am Donnerstag 04 März 2010 04:20:05 schrieb Louis Wasserman:
James,
Which version of Control.Monad.State are you importing?
If you're just importing vanilla Control.Monad.State, that's actually sending you to Control.Monad.State.Lazy.
Using Control.Monad.State.Strict might solve your problems, srsly. Laziness can result in epically failing memory leaks.
That was my first thought too, but for this code, Control.Monad.State.Lazy is the better choice. Control.Monad.State.Strict doesn't play too well with sequence (and hence mapM). Since James consumes the list of chain lengths as it is produced (key = maximum keys), no large thunks can build up. With the strict State, he can't start to look for the maximum until all chain lengths have been computed, building a big fat thunk for the list.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
Actually, looking back, I'm not sure mapM is even the right choice. I think
foldM would suffice. All we're doing is finding the association pair with
the minimum key, no? In this case, foldM would do everything we need
to...and State.Strict would be pretty good at that.
Louis Wasserman
wasserman.louis@gmail.com
http://profiles.google.com/wasserman.louis
On Thu, Mar 4, 2010 at 8:32 AM, Daniel Fischer
Am Donnerstag 04 März 2010 04:20:05 schrieb Louis Wasserman:
James,
Which version of Control.Monad.State are you importing?
If you're just importing vanilla Control.Monad.State, that's actually sending you to Control.Monad.State.Lazy.
Using Control.Monad.State.Strict might solve your problems, srsly. Laziness can result in epically failing memory leaks.
That was my first thought too, but for this code, Control.Monad.State.Lazy is the better choice. Control.Monad.State.Strict doesn't play too well with sequence (and hence mapM). Since James consumes the list of chain lengths as it is produced (key = maximum keys), no large thunks can build up. With the strict State, he can't start to look for the maximum until all chain lengths have been computed, building a big fat thunk for the list.
Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
Am Donnerstag 04 März 2010 16:07:51 schrieb Louis Wasserman:
Actually, looking back, I'm not sure mapM is even the right choice. I think foldM would suffice. All we're doing is finding the association pair with the minimum key, no? In this case, foldM would do everything we need to...and State.Strict would be pretty good at that.
Yes, it would (much much better than C.M.S.Lazy). And it would be an improvement over the original, but not much. The real problem is that Data.Map isn't well suited for this task. Inserting n key -> value associations into an initially empty Map takes O(n*log n) time. Since here the keys have a tendency to come in increasing order, there are a lot of rebalancings necessary, giving extra bad constants on top. What one wants here is a data structure with O(1) access and update for the cache. Enter STUArray. Of course, now comes the difficulty that you don't know how large your numbers will become (56991483520, you probably don't have enough RAM for such a large array), so you have to choose a cutoff and decide what to do when you exceed that. That makes the code more convoluted, but a lot faster.
participants (2)
-
Daniel Fischer -
Louis Wasserman