Re: [Caml-list] Map module

[Brian Hurt <brian.hurt@qlogic.com>]

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