Stack space overflow when using -N2 and not with -N1

[mitar]

I get a stack space overflow error when using -N2 (or -N4), but the program works with -N1. The program is my test and benchmarking program for  Etage-Graph package.

So this works normally: ./etage-graph-test -s 10 +RTS -N1

Generating a random graph of size 10.
Graph contains 10 nodes.
Dijkstra search time for shortest paths: 0.000875s
Etage search time for shortest paths: 0.010341s (0.5s timeout)
Found 100.00 % shortest paths.
etage-graph-test: DissolvingException "()"

But this does not: ./etage-graph-test -s 10 +RTS -N2

Generating a random graph of size 10.
Graph contains 10 nodes.
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

The most interesting thing is that this happens only for graph sizes (-s parameter) between (including) 1-19. For larger sizes it works without problems. What means that the problem is this line:

map spFromSource (nodes graph) `using` parListChunk (noNodes graph `div` (numCapabilities * 10)) rdeepseq

Yes. So also /etage-graph-test -s 5 +RTS -N1 fails. OK, so parListChunk with 0 as an argument is not well defined, or it is defined to diverge. Is this a wanted feature or it is a bug?

[daniel.is.fischer]

Definitely a bug.

parListChunk :: Int -> Strategy a -> Strategy [a]
parListChunk n strat xs =
  concat `fmap` parList (evalList strat) (chunk n xs)

chunk :: Int -> [a] -> [[a]]
chunk _ [] = []
chunk n xs = as : chunk n bs where (as,bs) = splitAt n xs

means that parListChunk 0 strat xs evaluates an infinity of empty lists in parallel. Either parListChunk or chunk should ensure that the chunks are non-empty. Since chunk is not exported and used only by parListChunk, having the latter call chunk (max 1 n) xs would avoid re-checking the chunksize in each recursive step.

[daniel.is.fischer]

bugfix and whitespace

[daniel.is.fischer]

bugfix only

[daniel.is.fischer]

I sent the patches to libraries@ on Monday, didn't think of putting them here for convenience.

[simonmar]

Done, thanks. I did it slightly differently:

--- a/Control/Parallel/Strategies.hs
+++ b/Control/Parallel/Strategies.hs
@@ -428,9 +428,13 @@ parListNth n strat = evalListNth n (rpar `dot` strat)
 -- It is expected that this function will be replaced by a more
 -- generic clustering infrastructure in the future.
 --
+-- If the chunk size is 1 or less, 'parListChunk' is equivalent to
+-- 'parList'
+--
 parListChunk :: Int -> Strategy a -> Strategy [a]
-parListChunk n strat xs =
-  concat `fmap` parList (evalList strat) (chunk n xs)
+parListChunk n strat xs
+  | n <= 1    = parList strat xs
+  | otherwise = concat `fmap` parList (evalList strat) (chunk n xs)
 
 chunk :: Int -> [a] -> [[a]]
 chunk _ [] = []