What are possible causes of "C stack overflow" in Hugs?
I'm getting a "C stack overflow" error from Hugs when processing a moderately large dataset, but not doing anything that looks unreasonably complex or involved. As far as I can tell, the code causing the problem is about here: [[ -- Return list of distinct labels used in a graph graphLabels :: (Label lb) => [Arc lb] -> [lb] graphLabels gs = graphLabels1 gs [] graphLabels1 (t:gs) ls = graphLabels1 gs $ foldl (flip addSetElem) ls (arcLabels t) graphLabels1 [] ls = ls ]] I think the function graphLabels1 is set to call itself recursively to a depth of a little over 1000. Can this kind of recursion blow the Hugs stack? This code has been working quite happily for some time. The called function arcLabels is quite trivial, and addSetElem is pretty simple too: [[ addSetElem :: (Eq a) => a -> [a] -> [a] addSetElem e es = if e `elem` es then es else e:es ]] ... I changed the function 'graphLabels' thus: [[ graphLabels :: (Label lb) => [Arc lb] -> [lb] graphLabels gs = nub $ concat $ map arcLabels gs ]] and the C stack overflow goes away. But I've been burned in the past with serious performance problems using nub, so I'm wary of this. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
On Wed, 04 Feb 2004 23:00:50 +0000 Graham Klyne <gk@ninebynine.org> wrote:
I'm getting a "C stack overflow" error from Hugs when processing a moderately large dataset, but not doing anything that looks unreasonably complex or involved. <snip>
I think the function graphLabels1 is set to call itself recursively to a depth of a little over 1000. Can this kind of recursion blow the Hugs stack?
"foldl f x xs" generally requires #xs (the number of elements of xs) stacks to be evaluated. Note that ls(the second argument of graphLabels1) is not evaluated until
graphLabels1 [] ls = ls .
foldl (flip addSetElem) ls (arcLabels t)
ls is also defined by a foldl and its ls is also ... So, let gs = [g_1, g_2, ..., g_N], you need at least \sum_{n = 1}^N #g_n stacks. Is'n it large? The simplest and safest solution is to change foldl to foldl', but it produces the unnecessary evaluation of `elem`s in addSetElem's. I think that
import DeepSeq {- or f $!! x = force x `seq` f x where force [] = () force (x:xs) = x `seq` force xs -} ... graphLabels1 (t:gs) ls = graphLabels1 gs $!! foldl (flip addSetElem) ls (arcLabels t is better in your case.
Sorry for my poor English and hope it helps, Koji Nakahara
The simplest and safest solution is to change foldl to foldl', but it produces the unnecessary evaluation of `elem`s in addSetElem's.
Wrong. Please ignore it. $!! is better in a sense that it reduces the stack usage further than foldl' (foldl''s second argument needs stacks to be evaluated). -- Koji Nakahara
participants (2)
-
Graham Klyne -
Koji Nakahara