[Caml-list] Map module

[Caml-list] Map module

[Alessandro Baretta]

Hello folks. I've been away for a while. I hope everyone is 
well. Long live the Caml!

Now to the question?

How well is the Map module supposed to scale into the tens 
of thousands of entries? I'm getting a stack overflow when 
trying to insert some 80k key-value pairs in a Map. My 
function is tail recursive, so I should not be responsibile 
for this.

Alex

-------------------
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] Map module

[Dominique Quatravaux]

> How well is the Map module supposed to scale into the tens 
> of thousands of entries?

  Funny, this very same topic was discussed yesterday... Have a look
at the archives.

-- 
Dominique QUATRAVAUX                           Ingénieur senior
01 44 42 00 08                                 IDEALX


-------------------
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] Map module

[james woodyatt]

On Thursday, Jun 5, 2003, at 08:42 US/Pacific, Alessandro Baretta wrote:
>
> How well is the Map module supposed to scale into the tens of 
> thousands of entries? I'm getting a stack overflow when trying to 
> insert some 80k key-value pairs in a Map. My function is tail 
> recursive, so I should not be responsibile for this.

The Map.add function is not tail recursive.  It consumes stack at O(log 
N).  Many of the other functions are not tail recursive either.


-- 
j h woodyatt <jhw@wetware.com>

-------------------
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] Map module

[Brian Hurt]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1126 bytes --]

On Thu, 5 Jun 2003, Alessandro Baretta wrote:

> Hello folks. I've been away for a while. I hope everyone is 
> well. Long live the Caml!
> 
> Now to the question?
> 
> How well is the Map module supposed to scale into the tens 
> of thousands of entries? I'm getting a stack overflow when 
> trying to insert some 80k key-value pairs in a Map. My 
> function is tail recursive, so I should not be responsibile 
> for this.
> 

Glancing at the code, it appears to be a height-balanced tree.  So 
operations should use only O(log N) stack frames- call it something less 
than 32 stack frames for 80K elements.  Which means either there is a bug 
in that code, or your insert routine is not tail-recursive.

Attached is a little test program I whipped up to test the map module.  I 
insert 800K elements into a map in the two worst ways I can think of- 
increasing key order and decreasing key order.  I'm actually rather 
impressed with the performance- running this code only takes a couple of 
seconds.  Which makes me more suspicious that your insert routine isn't 
tail recursive.

Got a code sample you can share?

Brian


[-- Attachment #2: Type: TEXT/PLAIN, Size: 722 bytes --]


module Int =
    struct
       type t = int
       let compare (a: t) (b: t) = if a < b then -1 else if a > b then 1 else 0
    end

module IntMap = Map.Make(Int)

let max = 800000

let _ =
    let rec loop map a b i =
        if i < max then
            loop (IntMap.add i a map) (a+b) a (i+1)
        else
            map
    in
    loop (IntMap.empty) 1 1 0

let _ =
    let rec fib a b i =
        if i < max then
            fib (a+b) a (i+1)
        else
            a, b
    in
    let rec loop map a b i =
        if i > 0 then
            loop (IntMap.add i a map) b (a-b) (i-1)
        else
            map
    in
    let a, b = fib 1 1 0 in
    loop (IntMap.empty) a b max

Re: [Caml-list] Map module

[Alessandro Baretta]

Brian Hurt wrote:
> On Thu, 5 Jun 2003, Alessandro Baretta wrote:
> 
> 
> Glancing at the code, it appears to be a height-balanced tree.  So 
> operations should use only O(log N) stack frames- call it something less 
> than 32 stack frames for 80K elements.  Which means either there is a bug 
> in that code, or your insert routine is not tail-recursive.
> 

The insert routine is actually tail recursive, but somewhere 
else there is something which is not tail recursive. I have 
now tried converting my code to simple read-parse-print tail 
recursive functional cycle and still I get a Stack overflow.

Here's the code:

let read_cap s = Scanf.sscanf s "%2s %5[0-9]%[^\r\n]%[\r\n]"
let rec output_table input_ch =
   try
     let line = input_line input_ch in
     let prov, cap = read_cap line (fun p c _ _ -> p, c) in
      Printf.printf "%s\t%s\n" cap prov;
       output_table input_ch
   with
     | End_of_file -> print_string ""
     | Scanf.Scan_failure (_) -> output_table input_ch


***

Ok, now I'm using a "while true" cycle with exceptions. This 
simply cannot overflow.

let output_table2 input_ch =
   try
     while true do
       try
	let line = input_line input_ch in
	let prov, cap = read_cap line (fun p c _ _ -> p, c)
           in Printf.printf "%s\t%s\n" cap prov
       with Scanf.Scan_failure (_) -> ()
     done
   with End_of_file -> ()

And, yes, this does work. So what is wrong with the 
recursive version?

Alex

-------------------
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] Map module

[jeanfrancois.monin]

This is a Very FAQ (a bold warning should be inserted in the on-line
manuel, if not already done).

> let rec output_table input_ch =
>    try
>      let ...
>             output_table input_ch
>    with ...

is NOT tail-recursive. Put the try... with... construct 
outside the definition of the recursive functions.

  Jean-Francois Monin


-------------------
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] Map module

[Fred Smith]

The question is: Why isn't this function tail-recursive?
>
> let read_cap s = Scanf.sscanf s "%2s %5[0-9]%[^\r\n]%[\r\n]"
> let rec output_table input_ch =
>    try
>      let line = input_line input_ch in
>      let prov, cap = read_cap line (fun p c _ _ -> p, c) in
>       Printf.printf "%s\t%s\n" cap prov;
>        output_table input_ch
>    with
>      | End_of_file -> print_string ""
>      | Scanf.Scan_failure (_) -> output_table input_ch
>
>

I believe the answer is the try ... with.  The pointer to the exception
handler is part of each recursive call and cannot be popped off the stack
until its recursive child returns.  Hence the function is not
tail-recursive.  Putting the recursive definition inside the try ... with
should solve your problem.

Good luck.

-Fred

-------------------
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] Map module

[Alessandro Baretta]

Fred Smith wrote:
> The question is: Why isn't this function tail-recursive?
> 
>>let read_cap s = Scanf.sscanf s "%2s %5[0-9]%[^\r\n]%[\r\n]"
>>let rec output_table input_ch =
>>   try
>>     let line = input_line input_ch in
>>     let prov, cap = read_cap line (fun p c _ _ -> p, c) in
>>      Printf.printf "%s\t%s\n" cap prov;
>>       output_table input_ch
>>   with
>>     | End_of_file -> print_string ""
>>     | Scanf.Scan_failure (_) -> output_table input_ch
>>
>>

I have received several answers to my tail-recursion puzzle. 
I wish to thank all who helped.


Alex

-------------------
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