Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

core dump #2661

Closed
vicuna opened this issue Jun 10, 2004 · 2 comments
Closed

core dump #2661

vicuna opened this issue Jun 10, 2004 · 2 comments
Labels

Comments

@vicuna
Copy link

vicuna commented Jun 10, 2004

Original bug ID: 2661
Reporter: administrator
Status: closed
Resolution: not a bug
Priority: normal
Severity: minor
Category: ~DO NOT USE (was: OCaml general)

Bug description

Full_Name: Javier Casas
Version: OCaml 3.07+2
OS: W2K
Submission from: cable230a022.usuarios.retecal.es (212.183.230.22)

Well, it seems like in the next program you read a big file (the problem is
really not in the size of the file, but in the number of lines) it crashes
dumping a core.

let rec add x stack =
try
let head=Stack.top stack in
let size=List.length head in
let newsize=List.length x in
if size>newsize then
Stack.push x stack
else
let head=Stack.pop stack in
let z=head @ x in
add z stack
with
Stack.Empty -> Stack.push x stack;;

let rec readinternal file mystack=
try
let mystring=input_line file in
let ()=add [mystring] mystack in
readinternal file mystack
with
End_of_file -> ();;

let read file=
let mystack=Stack.create () in
let ()=readinternal file mystack in
let result=ref [] in
let join s=result:= s @ !result in
let ()=Stack.iter join mystack in
!result;;

let myfile=open_in "file" in
let lines=read myfile in
List.iter (print_string) lines;;

The program reads a file and transforms it to a list of lines, then prints the
lines. It uses a stack to reduce the number of list appends and its size, so its
opperative is near O(n + log2 n), wich is much better than the "standard" while
not EOF read_line;append to list. It runs well unless you try to read a file
with a lot of lines. (I managed to read a file of 98303 lines, but if i try one
line more, it breaks).

Of course, this tests have been run using ocamlopt, working inside an athlon XP
1600.
W2k says it is a stack overflow.

@vicuna
Copy link
Author

vicuna commented Jun 11, 2004

Comment author: administrator

Full_Name: Javier Casas
Version: OCaml 3.07+2

W2k says it is a stack overflow.

W2k is right. Your program overflows the stack because your "add" function
recurses too deeply. Note that it is not tail-recursive, since its recursive
call is within a try ... with block.

The program reads a file and transforms it to a list of lines, then prints
the
lines. It uses a stack to reduce the number of list appends and its size, so
its
opperative is near O(n + log2 n), wich is much better than the "standard"
while
not EOF read_line;append to list.

That's a really complicated way of doing it. The best way is O(n):

let read file =
let accu = ref [] in
try while true do (accu := (input_line file) :: !accu) done; assert false;
with End_of_file -> List.rev !accu
;;

-- Damien

@vicuna
Copy link
Author

vicuna commented Jun 11, 2004

Comment author: administrator

non-tail recursion DD 2004-06-11

@vicuna vicuna closed this as completed Jun 11, 2004
@vicuna vicuna added the bug label Mar 19, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant