Re: [Caml-list] Stack_overflow

Re: [Caml-list] Stack_overflow

[Jon Harrop]

On Friday 31 March 2006 21:44, mulhern wrote:
> Unfortunately, I get a Stack_overflow exception. If I roughly half the
> number of elements in the list the Stack_overflow exception goes away.

Try increasing the stack size using:

  export CAMLRUNPARAM='...'

where you get "..." from the manual. Something like 'l=100M', IIRC.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Stack_overflow

[mulhern]

Hi!

I'm trying to compile an automatically generated list definition with
approximately 12,000 elements. The list has type (record_type *
record_type list) list where record_type is a simple record with 4
fields.

I'm doing this because I'm trying to achieve a poor man's version of
staged compilation.

Unfortunately, I get a Stack_overflow exception. If I roughly half the
number of elements in the list the Stack_overflow exception goes away.

Does anybody have an suggestions for me to get around the stack
overflow problem? What if I want to make my data an order of magnitude
larger?

Thanks!

-mulhern

Re: [Caml-list] Stack_overflow

[Eric Cooper]

On Fri, Mar 31, 2006 at 02:44:26PM -0600, mulhern wrote:
> I'm trying to compile an automatically generated list definition with
> approximately 12,000 elements.
> [...]
> Unfortunately, I get a Stack_overflow exception.

Try using the natively-compiled compilers, ocamlc.opt or ocamlopt.opt.

-- 
Eric Cooper             e c c @ c m u . e d u

Re: Stack_overflow

[Stefan Monnier]

> Does anybody have an suggestions for me to get around the stack
> overflow problem?

Chunkify your list: turn it into a bunch of lists (each limited to size
predefined maximum length) and then concat them all at the end?


        Stefan

Re: Stack_overflow

[mulhern]

Thanks to everybody who responded.

To clarify things:
I'm trying to _compile_ a list definition.
So, my .ml file looks like this:

---
let myList = [("first", ["some"; more]);
                   ("second", ["more"; "still"])]
---
except that there are 12,000 elements in the list instead of two as in
the example.
_ocamlc_ throws a Stack_overflow error while compiling this list. So,
I want to know how to influence _ocamlc_ to be able to compile this or
larger lists.

The suggestion of chunkifying the list into smaller lists is a
practical one; I may be forced to try it.

ocamlc.opt compiles the list fine but that reduces portability.

-mulhern

On 3/31/06, mulhern <mulhern@gmail.com> wrote:
> Hi!
>
> I'm trying to compile an automatically generated list definition with
> approximately 12,000 elements. The list has type (record_type *
> record_type list) list where record_type is a simple record with 4
> fields.
>
> I'm doing this because I'm trying to achieve a poor man's version of
> staged compilation.
>
> Unfortunately, I get a Stack_overflow exception. If I roughly half the
> number of elements in the list the Stack_overflow exception goes away.
>
> Does anybody have an suggestions for me to get around the stack
> overflow problem? What if I want to make my data an order of magnitude
> larger?
>
> Thanks!
>
> -mulhern
>

Re: [Caml-list] Re: Stack_overflow

[Ingo Bormuth]

Hi, 

I recently had a very similar problem, trying to build a simple 
in-binary database holding 80.000 records (12 MB).

In my case even ocamlc.opt couldn't cope. Maybe there are non tail 
recursive calls in the compiler. Eventually recompiling ocaml
itself with greater stack size could do the job.

Cutting the list into pieces and merging at runtime worked fine.

What I did, was using a CSV file to auto generate ocaml code similar to:

  let table = Hashtbl.create 80000 ;;

  Hashtbl.add table "Key" [ Value1 , Value2, Value3 ] ;; (* 80.000 times *)

  Iterate over table and build some index hash tables ValueX -> Key
 
Compilation takes a while and uses plenty of RAM, but building the table
and looking up 80000 values takes just a second on my old laptop.


Ingo



On 2006-03-31 18:23, mulhern wrote:
> To clarify things:
> I'm trying to _compile_ a list definition.
> So, my .ml file looks like this:
> 
> ---
> let myList = [("first", ["some"; more]);
>                    ("second", ["more"; "still"])]
> ---
> except that there are 12,000 elements in the list instead of two as in
> the example.
> _ocamlc_ throws a Stack_overflow error while compiling this list. So,
> I want to know how to influence _ocamlc_ to be able to compile this or
> larger lists.
> The suggestion of chunkifying the list into smaller lists is a
> practical one; I may be forced to try it.
> 
> ocamlc.opt compiles the list fine but that reduces portability.
> 
> Odn 3/31/06, mulhern <mulhern@gmail.com> wrote:
> >
> > I'm trying to compile an automatically generated list definition with
> > approximately 12,000 elements. The list has type (record_type *
> > record_type list) list where record_type is a simple record with 4
> > fields.
> > I'm doing this because I'm trying to achieve a poor man's version of
> > staged compilation.
> > Unfortunately, I get a Stack_overflow exception. If I roughly half the
> > number of elements in the list the Stack_overflow exception goes away.
> > Does anybody have an suggestions for me to get around the stack
> > overflow problem? What if I want to make my data an order of magnitude
> > larger?

-- 
Ingo Bormuth, voicebox & telefax: +49-12125-10226517       '(~o-o~)'
public key 86326EC9, http://ibormuth.efil.de/contact   --ooO--(.)--Ooo--

Re: [Caml-list] Re: Stack_overflow

[Christophe TROESTLER]

On Fri, 31 Mar 2006, mulhern <mulhern@gmail.com> wrote:
> 
> The suggestion of chunkifying the list into smaller lists is a
> practical one; I may be forced to try it.

Maybe you want to do this in an auxiliary program that saves the
compiled list in a file (output_value) and the main program just reads
it (input_value)?

My 0.02€,
ChriS

Re: [Caml-list] Re: Stack_overflow

[Till Varoquaux]

[-- Attachment #1: Type: text/plain, Size: 1312 bytes --]

On 4/1/06, mulhern <mulhern@gmail.com> wrote:
>
> Thanks to everybody who responded.
>
> To clarify things:
> I'm trying to _compile_ a list definition.
> So, my .ml file looks like this:
>
> ---
> let myList = [("first", ["some"; more]);
>                    ("second", ["more"; "still"])]
> ---
> except that there are 12,000 elements in the list instead of two as in
> the example.
> _ocamlc_ throws a Stack_overflow error while compiling this list. So,
> I want to know how to influence _ocamlc_ to be able to compile this or
> larger lists.
>
> The suggestion of chunkifying the list into smaller lists is a
> practical one; I may be forced to try it.
>
> ocamlc.opt compiles the list fine but that reduces portability.
>
> -mulhern


Note that ocamlc.opt should produce exactly the same code than ocamlc....
The difference is that the compiler is natively compiled instead of
byte-compiled. Therefor your program will run in as many places it just
won't compile on plateforms without ocamlc.opt. You could put your list in a
separate module, byte compile it and "include" it in the reste of your
source. This *should* solve the problem (I might be wrong) and you could
still bundle the rest of your sources in a way that would allow to compile
them with ocamlc.


Till

[-- Attachment #2: Type: text/html, Size: 1743 bytes --]

Re: [Caml-list] stack overflow

[John Max Skaller]

Yang Shouxun wrote:

> Dear OCaml users,
> 
> I've written a modified version of C4.5 program in OCaml. However, when the 
> input is big, say over 50000, the program (native code on Debian) died for 
> stack overflow. Otherwise, it runs as expected.
> 
> Can anybody explain possible reasons causing stack overflow in OCaml?


Which version of Ocaml?

For Linux, there is no way a tiny dataset like 50,000 elements
could cause a stack overflow .. unless you're running an accounting
package which limits the stack/memory of a process you get ALL
of virtual memory for your stack.

Yet I had this problem, and it turned out to be
a code generation bug in Ocaml 3.03/4. That problem
has been fixed in 3.05.

The diagnostic I got, by the way, was not 'stack overflow'
but 'out of memory' when the stack really did overflow:
in my case non-tail recursive lexing was easy to make
blow the stack with a 7 Meg file: it took minutes to
dump, and the disk thrashed a lot .. the mouse froze ..
and i couldn't kill the process :(

If you are not getting these symptoms, it isn't a stack
overflow. [I am, of course, talking about the i86 native
code compiler]

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[Markus Mottl]

On Wed, 09 Apr 2003, Yang Shouxun wrote:
> My training data contain statistical values for word combinations (or
> collocations) extracted from a corpus. The number is indeed very large.

Funny, I am currently also applying my tool to NLP (natural language
processing): because of the isomorphism between context-free grammars and
algebraic datatyes, it is possible to learn propositions about derivation
trees (or even more general: learn non-recursive functions). The problem
there is rather the size of CFG extracted from a large, annotated
corpus for German (many, many thousands of productions), which really
looks messy.

> I've learned this style in Scheme. Yet I feel paralyzed when trying to write 
> in it to build trees. The type declaration may make my point clearer.
> --8<--
> type  dtree = Dnode of dnode | Dtree of (dnode * int * dtree list)
> --8<--
> The problems are that unless the next call returns, the tree is not complete 
> yet and it may have several calls on itself.

But that's what the closure is for: it abstracts away the subtree that
still needs to be computed.

> I'm running Debian unstale. I checked just now on my laptop and "ulimit -s" 
> reurned "unlimited". I suppose the desktop that actually ran the program was 
> similarly configured.

Given that you already run into problems for comparatively small sizes,
I suppose that you are using the byte-code interpreter? Its builtin
stack space is 256KB, i.e. 64K-words.

> I also downloaded your AIFAD and had a cursive look at it. I found it
> does not handle continuous attributes yet and your design goal is quite
> different from mine. So I wrote mine from scratch and called it DTLR
> (Decision Tree Learner for Retrieval).

Yes, I haven't yet implemented handling of continuous attributes, because
I am aiming at an even more general system, where you can specify abstract
algebras (signatures) that describe how to handle values of some abstract
types, i.e. not only continuous (numeric) values. I have already done
so separately in another project, but wasn't very satisfied with the
design. Furthermore, I'd like to integrate it into AIFAD.

> If you are interested, I can send a copy to you tomorrow. It does not 
> implement all the features I planned, without documentation except some 
> comments, but it is enough for my own needs right now.

That would be great! - Thanks!

Regards,
Markus

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[Yang Shouxun]

On Wednesday 09 April 2003 16:14, Markus Mottl wrote:
> On Wed, 09 Apr 2003, Yang Shouxun wrote:
> > Yes, the decision tree building function is not tail recursive. I heared
> > people saying C4.5 (in C) also has stack overflow problem when the
> > training dataset becomes very large.
>
> I can't imagine that this is the problem: either the data is
> well-distributed, in which case the stack size will grow roughly
> logarithmically with the size of the data due to partitioning. And if not,
> the maximum depth of the tree is limited by the number of available input
> variables anyway. You'd need many, many thousands of those before this
> becomes a problem, which even large, industrial datasets that I know do
> not exceed.

My training data contain statistical values for word combinations (or 
collocations) extracted from a corpus. The number is indeed very large.

> > I don't know how to write a tail recursive version to build trees.
> > If there are not that many continuous attributes and the dataset is
> > not so large, the tree stops growing before stack overflow.
>
> The trick is to use continuation passing style (CPS): you pass a function
> closure (continuation) containing everything that's needed in subsequent
> computations.  Instead of returning a result, the sub-function calls the
> continuation with the result, which makes the functions tail-recursive.

I've learned this style in Scheme. Yet I feel paralyzed when trying to write 
in it to build trees. The type declaration may make my point clearer.
--8<--
type  dtree = Dnode of dnode | Dtree of (dnode * int * dtree list)
--8<--
The problems are that unless the next call returns, the tree is not complete 
yet and it may have several calls on itself.

> But anyway, I think there must be some fishy operation going on. Why not
> use the debugger to find out? Or even better: send a link to the code :-)

I suppose the program is not buggy so far as it works as expected.  It's buggy 
in the design itself: it must recurse (so far as I can implement) and it 
cannot afford recurse too deeply. Sorry, I don't have a homepage.

> > Can one know the maximal number of calls before it overflow the stack?
>
> It depends: byte-code uses its own stack, which you can query using the
> Gc-module. Otherwise, for native-code, call the ulimit-program (Unix),
> which displays resource limits including stack usage or interface to
> the system call "getrlimit".

I'm running Debian unstale. I checked just now on my laptop and "ulimit -s" 
reurned "unlimited". I suppose the desktop that actually ran the program was 
similarly configured.

> In any case, it would be interesting to see your code. Are you going to
> release it under some free license?

Yes, I'm going to release it under GPL. As you can see, I basically use free 
software and am willing to pay it back. I intend to register a project for it 
on savannah soon. Be warned that my code may look rather ugly.

I also downloaded your AIFAD and had a cursive look at it. I found it does not 
handle continuous attributes yet and your design goal is quite different from 
mine. So I wrote mine from scratch and called it DTLR (Decision Tree Learner 
for Retrieval).

If you are interested, I can send a copy to you tomorrow. It does not 
implement all the features I planned, without documentation except some 
comments, but it is enough for my own needs right now.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[Markus Mottl]

On Wed, 09 Apr 2003, Yang Shouxun wrote:
> Yes, the decision tree building function is not tail recursive. I heared 
> people saying C4.5 (in C) also has stack overflow problem when the training 
> dataset becomes very large.

I can't imagine that this is the problem: either the data is
well-distributed, in which case the stack size will grow roughly
logarithmically with the size of the data due to partitioning. And if not,
the maximum depth of the tree is limited by the number of available input
variables anyway. You'd need many, many thousands of those before this
becomes a problem, which even large, industrial datasets that I know do
not exceed.

> I don't know how to write a tail recursive version to build trees.
> If there are not that many continuous attributes and the dataset is
> not so large, the tree stops growing before stack overflow.

The trick is to use continuation passing style (CPS): you pass a function
closure (continuation) containing everything that's needed in subsequent
computations.  Instead of returning a result, the sub-function calls the
continuation with the result, which makes the functions tail-recursive.

But anyway, I think there must be some fishy operation going on. Why not
use the debugger to find out? Or even better: send a link to the code :-)

> Can one know the maximal number of calls before it overflow the stack?

It depends: byte-code uses its own stack, which you can query using the
Gc-module. Otherwise, for native-code, call the ulimit-program (Unix),
which displays resource limits including stack usage or interface to
the system call "getrlimit".

In any case, it would be interesting to see your code. Are you going to
release it under some free license?

Regards,
Markus Mottl

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[David Monniaux]

On Wed, 9 Apr 2003, Yang Shouxun wrote:

> I've written a modified version of C4.5 program in OCaml. However, when the 
> input is big, say over 50000, the program (native code on Debian) died for 
> stack overflow. Otherwise, it runs as expected.

In the case of native code, OCaml uses the ordinary system-provided stack.
Please make sure the system stack size limit is not too low (ulimit -a on
certain shells to see it, ulimit -s to set it, in kilobytes).

David Monniaux            http://www.di.ens.fr/~monniaux
Laboratoire d'informatique de l'École Normale Supérieure,
Paris, France

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[Yang Shouxun]

On Wednesday 09 April 2003 10:33, John Gerard Malecki wrote:
> Yang Shouxun wrote (2003-04-09T10:34:45+0800):
>  > On Wednesday 09 April 2003 10:17, John Gerard Malecki wrote:
>  > > What is C4.5?
>  >
>  > It's a decision tree learner.
>
> Interesting.  Do you have a web site where I can learn more?

You can download the source code for C4.5 from 
http://www.cse.unsw.edu.au/~quinlan/ and some papers about it. Markus wrote 
AIFAD (http://www.oefai.at/~markus/aifad).

> I notice that Brian Rogoff just published some info which is very
> handy.  Use the byte-code compiler and run with the environment
> variable OCAMLRUNPARAM='b=1' and you will get a stack trace.  It could
> be that the problem is not your code but the library routines which
> you are using.
>
> Good luck.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[Yang Shouxun]

On Wednesday 09 April 2003 10:19, brogoff@speakeasy.net wrote:
> The most likely explanation is that you created a very large list, say of
> length over 50_000, and tried to apply some non-tail-recursive operation to
> it, perhaps even implicitly. There was a very recent thread on this topic.
>
> The second explanation is that you wrote some (non-tail) recursive function
> and it blew the stack.

Yes, the decision tree building function is not tail recursive. I heared 
people saying C4.5 (in C) also has stack overflow problem when the training 
dataset becomes very large.

I don't know how to write a tail recursive version to build trees.  If there 
are not that many continuous attributes and the dataset is not so large, the 
tree stops growing before stack overflow.

Can one know the maximal number of calls before it overflow the stack?

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[David Brown]

On Wed, Apr 09, 2003 at 10:10:37AM +0800, Yang Shouxun wrote:

> I've written a modified version of C4.5 program in OCaml. However, when the 
> input is big, say over 50000, the program (native code on Debian) died for 
> stack overflow. Otherwise, it runs as expected.
> 
> Can anybody explain possible reasons causing stack overflow in OCaml?

Where do you catch the End_of_file exception.  A common mistake is to
add a try clause inside of a tail recursive call.  The call is no longer
tail-recursive, and makes a chain of exception handlers for each
invocation.  e.g.

   let rec loop () =
     try let line = input_line () in
     ...;
     loop ()
     with End_of_file -> ...

instead of

   let rec loop () =
     let line = input_line () in
     ...;
     loop ()
   in
   try loop ()
   with End_of_file -> ...

Dave

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] stack overflow

[brogoff]

The most likely explanation is that you created a very large list, say of 
length over 50_000, and tried to apply some non-tail-recursive operation to it, 
perhaps even implicitly. There was a very recent thread on this topic. 

The second explanation is that you wrote some (non-tail) recursive function 
and it blew the stack. 

If you switch to the bytecode compiler and run with stack trace, you'll find out 
pretty quickly. 

-- Brian


On Wed, 9 Apr 2003, Yang Shouxun wrote:

> Dear OCaml users,
> 
> I've written a modified version of C4.5 program in OCaml. However, when the 
> input is big, say over 50000, the program (native code on Debian) died for 
> stack overflow. Otherwise, it runs as expected.
> 
> Can anybody explain possible reasons causing stack overflow in OCaml?
> 
> Thanks for your time!
> shouxun
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] stack overflow

[Yang Shouxun]

Dear OCaml users,

I've written a modified version of C4.5 program in OCaml. However, when the 
input is big, say over 50000, the program (native code on Debian) died for 
stack overflow. Otherwise, it runs as expected.

Can anybody explain possible reasons causing stack overflow in OCaml?

Thanks for your time!
shouxun

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners