Back to Questions
1.1k
views6
comments
Stack overflow on Seq.hd
f#

I have a function a part of a template parser:

1
2
3
4
5
6
7
8
9
10

 

        let rec parse_internal parser (nodes:Node list) (tokens : Lexer.Token seq) parse_until =
            let token = Seq.hd tokens
            let tokens = (LazyList.of_seq <| Seq.skip 1 tokens) :> Lexer.Token seq
            if token = Lexer.Nothing then  
                (nodes, seq [Lexer.Nothing])
            else 
                let tagNodes, tokens = parse_token parser tokens token
                parse_internal parser (nodes @ tagNodes) tokens parse_until

This code does what I need it do, except one strange thing - on one computer I am getting a stack overflow exeption. The call stack does not contain any reference to my code. By placing Debug.WriteLine statements I localized the statement causing the stack overflow - it is the 

1

let token = Seq.hd tokens

statement. It is only happening on my Vista/ x64 box and does not happen on a half a dozen other computers (all 32 bit). The stack overflow is only happening on a template of a considerable size (400+ tokens). But the same template is processed just fine on all other computers.

Any idea what can cause a stack overflow in the Seq.hd?

Just in case if it can tell you anything here is 2 frames of the call stack I am getting:

FSharp.PowerPack.dll!Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token>.Force.get() + 0x22d bytes

FSharp.PowerPack.dll!<StartupCode$FSharp.PowerPack>.$Lazylist.clo@30_1<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token> ll = {Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token>}) + 0x4f bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.IEnumerator.clo@151<NDjango.Lexer.Token,Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token>>.System-Collections-IEnumerator-MoveNext() + 0x9c bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.clo@1087_1<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Core.Unit dummy = null) + 0x5b bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.SequenceExpressionHelpers.clo@786<NDjango.Lexer.Token>.System-Collections-IEnumerator-MoveNext() + 0x86 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.takeOuter@665@665<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>(Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>> x@665 = {Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>}, Microsoft.FSharp.Core.Unit _unit = null) + 0x81 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.takeInner@658@658<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>(Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>> x@658 = {Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>}, Microsoft.FSharp.Core.Unit _unit = null) + 0x1cc bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>.System-Collections-IEnumerator-MoveNext() + 0xee bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Generator.clo@464<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Core.Unit _unit = null) + 0x66 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Generator.appG<NDjango.Lexer.Token>(Microsoft.FSharp.Collections.Generator.Generator<NDjango.Lexer.Token> g = {Microsoft.FSharp.Collections.Generator.LazyGeneratorWrappingEnumerator<NDjango.Lexer.Token>}) + 0xd6 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Generator.EnumeratorWrappingLazyGenerator<NDjango.Lexer.Token>.System-Collections-IEnumerator-MoveNext() + 0xf1 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.IEnumerator.clo@289<NDjango.Lexer.Token>.System-Collections-IEnumerator-MoveNext() + 0x56 bytes

FSharp.PowerPack.dll!Microsoft.FSharp.Collections.LazyListModule.f@207<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Core.Unit _unit = null) + 0x62 bytes

FSharp.PowerPack.dll!Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token>.Force.get() + 0x314 bytes
FSharp.PowerPack.dll!<StartupCode$FSharp.PowerPack>.$Lazylist.clo@30_1<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token> ll = {Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token>}) + 0x4f bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.IEnumerator.clo@151<NDjango.Lexer.Token,Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token>>.System-Collections-IEnumerator-MoveNext() + 0x9c bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.clo@1087_1<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Core.Unit dummy = null) + 0x5b bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.SequenceExpressionHelpers.clo@786<NDjango.Lexer.Token>.System-Collections-IEnumerator-MoveNext() + 0x86 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.takeOuter@665@665<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>(Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>> x@665 = {Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>}, Microsoft.FSharp.Core.Unit _unit = null) + 0x81 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.takeInner@658@658<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>(Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>> x@658 = {Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>}, Microsoft.FSharp.Core.Unit _unit = null) + 0x1cc bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Seq.ConcatEnumerator<NDjango.Lexer.Token,System.Collections.Generic.IEnumerable<NDjango.Lexer.Token>>.System-Collections-IEnumerator-MoveNext() + 0xee bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Generator.clo@464<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Core.Unit _unit = null) + 0x66 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Generator.appG<NDjango.Lexer.Token>(Microsoft.FSharp.Collections.Generator.Generator<NDjango.Lexer.Token> g = {Microsoft.FSharp.Collections.Generator.LazyGeneratorWrappingEnumerator<NDjango.Lexer.Token>}) + 0xd6 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.Generator.EnumeratorWrappingLazyGenerator<NDjango.Lexer.Token>.System-Collections-IEnumerator-MoveNext() + 0xf1 bytes

FSharp.Core.dll!Microsoft.FSharp.Collections.IEnumerator.clo@289<NDjango.Lexer.Token>.System-Collections-IEnumerator-MoveNext() + 0x56 bytes

FSharp.PowerPack.dll!Microsoft.FSharp.Collections.LazyListModule.f@207<NDjango.Lexer.Token>.Invoke(Microsoft.FSharp.Core.Unit _unit = null) + 0x62 bytes

FSharp.PowerPack.dll!Microsoft.FSharp.Collections.LazyList<NDjango.Lexer.Token>.Force.get() + 0x314 bytes

.

First off, I agree with everything Tomas said, and think it's likely to solve your problem.

That said, the disparity between 32-bit and 64-bit is perhaps not unexpected; for the .Net 2.0 CLR, the 64-bit JITter does not honor .tail calls as often as the 32-bit one, so there are cases where valid F# code will run fine on 32-bit but fail with StackOverflow on 64-bit. (I believe the CLR team is making improvements here in .Net 4.0.)

I think the reason you're seeing Seq.hd as the 'cause' is simply that it's the first thing that 'forces' evaluation of the Seq. Back to point one, if you rewrite this to use a LazyList throughout, I think you'll quit using any stack space and it will all just work, regardless of the bit-ness of the platform.

By on 5/26/2009 8:41 PM ()

Hi,
I'm not fully sure what exactly is going on here, but I think your usage of LazyList and sequences is a bit suspicious and it could be causing the issue. I mean these two lines:

1
2
3

 
let token = Seq.hd tokens
let tokens = (LazyList.of_seq <| Seq.skip 1 tokens) :> Lexer.Token seq

This gets the first token and then creates a new lazy list, initialized from a lazy sequence, so I guess that when you access next element of the lazy list in the next iteration, it still remembers the way it was created (which is a sequence of nested references where lazylist references sequence, which references lazylist and so on..). But I'm not fully sure about this....

Anyway, the best way to write the code would be to create LazyList once, before running the function and then use pattern matching inside the processing function to test the two possible cases.

I believe that would look roughly like this:

1
2
3
4
5
6
7
8
9
10

 
let rec parse_internal parser (nodes:Node list) (tokens : LazyList<Lexer.Token>) parse_until =
  match tokens with
  | LazyList.Nil | LazyList.Cons(Lexer.Nothing, _) -> 
      (nodes, seq [Lexer.Nothing]) // end of sequence or 'nothing'
  | LazyList.Cons(token, tokens) -> 
      let tagNodes, tokens = parse_token parser tokens token
      parse_internal parser (nodes @ tagNodes) tokens parse_until

parse_internal (tokens |> LazyList.of_seq)

BTW: is the 'parse_until' parameter used anywhere in the code?

As a side note, it would be also nice to get rid of '@' in the last call, because that's not particularly fast operation. That would probably require passing the current list of 'nodes' to the 'parser_token' function, so that it can prepend new tokens one-by-one, but that's probably just a detail.

Hope this helps!
T.

By on 5/26/2009 6:47 PM ()

Thank you guys for quick response. Unfortunately it did not help much. I followed your suggestion and ended up with the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        let rec parse_internal parser (nodes:Node list) (tokens : LazyList<Lexer.Token>) parse_until =
           match tokens with
           | LazyList.Nil | LazyList.Cons(Lexer.Nothing, _) -> 
                if not <| List.is_empty parse_until then
                    fail_unclosed_tags parse_until
                (nodes, LazyList.of_list <| [Lexer.Nothing])
           | LazyList.Cons(token, tokens) -> 
                if is_term_token token parse_until then
                    (nodes @ [new Node(token)], tokens)
                else
                    if (not <| List.is_empty parse_until) && Seq.hd tokens = Lexer.Nothing && not <| is_term_token token parse_until then 
                        fail_unclosed_tags parse_until
                    else
                        let tagNodes, tokens = parse_token parser tokens token
                        parse_internal parser (nodes @ tagNodes) tokens parse_until

While the code certainly looks cleaner, I am still getting the same exception. I even tried to remove the remaining Seq.hd tokens call from the if statement to no avail. The stack overflow is still happening.

As a side note when I change the data type from Token seq to LazyList<Token> i got a warning 'this construct has been deprecated consider using seq...?' - so, has it? Been deprecated that is?

And another one - does the list implementation holds a pointer to both the first and the last element? That would make splicing of 2 lists an operation which does not depend on the size of the lists

As to tomasp question about parse_until - in my initial posting I removed some of the code which I thought was not related to the problem. Now I posted the complete code of the function. If you guys are curious this code is a part of NDjango - an open source implementation of django template engine in F#: www.ndjango.com The source code can be downloaded here svn://svn.hill30.com/ndjango/ The function in question is on line 140 of the NDjangoParser/Parser.fs file.

Any input will be greatly appreciated

By on 5/27/2009 5:18 AM ()

As a side note when I change the data type from Token seq to LazyList<Token> i got a warning 'this construct has been deprecated consider using seq...?' - so, has it? Been deprecated that is?

No; you're using F# 1.9.6.2 I take it? That deprecation message was a mistake, and you won't see it in the latest release.

While the code certainly looks cleaner, I am still getting the same exception. I even tried to remove the remaining Seq.hd tokens call from the if statement to no avail. The stack overflow is still happening.

Are you compiling in 'Debug' mode or 'Release' mode (without or with -O)? (Actually the compiler options changed a bit from 1.9.6.2 to 1.9.6.16 so I'm not even sure.) I wonder if you're in Debug/no-opt/no-tail-call mode. Also, don't use Seq.hd on a LazyList - use LazyList.hd instead.

It could also be that the code that is originally producing the tokens (not shown here) has the StackOverflow - does the stack trace repeat over and over again through this method, or through the producer code? If I have time I may look at the link to your code you sent.

And another one - does the list implementation holds a pointer to both the first and the last element? That would make splicing of 2 lists an operation which does not depend on the size of the lists

F# Lists are immutable (and concrete), and they're singly-linked (you have only a pointer to the head); either of these constraints means you must traverse the whole first list to 'append'. This is pretty fundamental - you need to know this to reason about the complexity of various operations and to choose suitable data structures.

By on 5/27/2009 8:38 AM ()

I figured it out. You were right - your fix did fix the stack overflow. I just had similar code in the rendering routines as well. Once I fixed it the stack overflow is gone.

Having said that I am still confused - what does it mean the lazy list 'remembers how it was created'? I undestand that the way I originally used the LazyList was causing creation of unnecessary objects which could have impacted performance. I also understand how using regular sequence and advancing it with Seq.skip 1 can cause stack overflow. But with LazyList - I am still missing something

By on 5/27/2009 7:52 PM ()

Hi, great to hear that it resolved the problem!
I'm not fully sure how to explain what was the problem. However, when you convert sequence to lazylist, it keeps a reference to the original sequence. When the underlying sequence is created using Seq.skip, it is the inefficient sequence that can cause stack overflow. When you convert lazy list back to sequence, it returns a sequence that keeps reference to the original lazy list and so it also references the original sequence.

I'm not sure whether this explains stack overflow exception or not, but it could explain some inefficiencies. Anyway, here is a very simple implementation of lazy list that could demonstrate how the conversion between the two representations works:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 
type LazyList<'T> = 
  | LazyCell of 'T * Lazy<LazyList<'T>>

let rec listToSeq(LazyCell(h, t)) =
  seq { yield h
        yield! listToSeq(t.Force()) }
    
let listOfSeq(s:seq<_>) =
  let en = s.GetEnumerator()
  let rec next() =
    en.MoveNext() |> ignore
    LazyCell(en.Current, lazy next())
  next()

let rec test s =
  let next = listOfSeq (Seq.skip 1 s)
  test (listToSeq(next))
By on 5/28/2009 6:47 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper