Opened 9 years ago

Closed 9 years ago

#5100 closed bug (fixed)

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

Reported by: mitar Owned by: simonmar
Priority: high Milestone: 7.2.1
Component: libraries (other) Version: 7.1
Keywords: Cc: mmitar@…
Operating System: Linux Architecture: x86_64 (amd64)
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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?

Attachments (3)

fix-5100.dpatch (9.8 KB) - added by daniel.is.fischer 9 years ago.
bugfix and whitespace
nonempty-chunks.dpatch (1.4 KB) - added by daniel.is.fischer 9 years ago.
bugfix only
whitespace.dpatch (8.7 KB) - added by daniel.is.fischer 9 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 9 years ago by 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.

comment:2 Changed 9 years ago by daniel.is.fischer

Component: Compilerlibraries (other)

comment:3 Changed 9 years ago by simonmar

Milestone: 7.2.1
Owner: set to simonmar
Priority: normalhigh

Changed 9 years ago by daniel.is.fischer

Attachment: fix-5100.dpatch added

bugfix and whitespace

Changed 9 years ago by daniel.is.fischer

Attachment: nonempty-chunks.dpatch added

bugfix only

Changed 9 years ago by daniel.is.fischer

Attachment: whitespace.dpatch added

comment:4 Changed 9 years ago by daniel.is.fischer

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

comment:5 Changed 9 years ago by simonmar

Resolution: fixed
Status: newclosed

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 _ [] = []
Note: See TracTickets for help on using tickets.