[Caml-list] "Nasty" functions and memory usage

[Caml-list] "Nasty" functions and memory usage

[Alex Baretta]

I have been waiting some ten minutes or so, now, for my Pentium
200 to calculate the type of nasty function number 5...

let f0 = function x,y -> x,y;;
let f1 = function x,y -> f1(f0 x, f0 y);;
let ...
let f5 = function x,y -> f5(f4 x, f4 y);;

... and I have reason to believe I will still have to wait a long
long time if I want to see the result.

The question is the following: the problem of calculating the type
of fN is DSPACE(2**(2**N))-hard, as far as I understand ...(I have
evidence, too! The type of f4 was so long it took the machine
several minutes only to print it to the screen once it had it
calculated.)

So how can the memory usage of the ocaml interpreter be constant
at 2200Kb? Here's my top screen...

  2:31am  up 15:37,  5 users,  load average: 1.08, 1.05, 0.71
57 processes: 54 sleeping, 3 running, 0 zombie, 0 stopped
CPU states: 95.5% user,  4.4% system,  0.0% nice,  0.0% idle
Mem:   257720K av,  197864K used,   59856K free,   59456K shrd,  
68852K buff
Swap:  264804K av,    1848K used,  262956K free                  
72172K cached

  PID USER     PRI  NI  SIZE  RSS SHARE STAT  LIB %CPU %MEM   TIME
COMMAND
 1902 root      19   0  2220 2220   512 R       0 92.1  0.8  16:29
ocaml
 1936 root       5   0   868  868   668 S       0  3.7  0.3   0:20
top

The value has been constant at least since I started checking it,
about ten minutes ago.

Please, gurus, explain...

Alex
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] "Nasty" functions and memory usage

[Alex Baretta]

Hendrik Tews wrote:
> 
>    let f0 = function x,y -> x,y;;
>    let f1 = function x,y -> f1(f0 x, f0 y);;
>    let ...
>    let f5 = function x,y -> f5(f4 x, f4 y);;
> 
> Can you post the correct program? For this I get
> 
>     #   let f1 = function x,y -> f1(f0 x, f0 y);;
> 
>     Characters 26-28:
>     Unbound value f1
> 
> And if I insert let rec's f5 is typechecked in less than a
> second.
> 

That's right. I screwed up. 

let f0 = function x -> x,x;;
let f1 = function x,y -> f0 ( f0 x, f0 y);;
let f2 = function x,y -> f1 ( f1 x, f1 y);;
let f3 = function x,y -> f2 ( f2 x, f2 y);;
let f4 = function x,y -> f3 ( f3 x, f3 y);;
let f5 = function x,y -> f4 ( f4 x, f4 y);;

f0 doubles the size of the type of its argument. f1 doubles twice
the size (*4) of the type of its arguents. f2 multiplies by 4
twice (*16) the size of the type of its argument. f3 multiplies by
16 twice the size of the type of its argument (*256). f4
multiplies its arguments type size by 65536. f5 by 65536**2, which
is 4294967296, or 2**(2**5)). Basically, one sees immediately that
fn has space complexity = k*2**(2**n). A nice double exponential.
Find me a computer capable of f7, now... (3.4*10**38 times the
size of the argument)

Now, my question is, how come the memory usage of the Ocaml (3.00)
front end does not grow with time as it attempts to compute the
type of, say, f6?

Alex
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] "Nasty" functions and memory usage

[Sebastien Carlier]

Alex Baretta wrote:
> Now, my question is, how come the memory usage of the Ocaml (3.00)
> front end does not grow with time as it attempts to compute the
> type of, say, f6?

I think it's pretty-printing that is actually taking a lot of time.
During inference you would only have (2**n) types because there is a
lot of sharing.  However, if you try to print the type you will really
have (2**(2**n)) nodes to traverse.

--
Sebastien
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr

Re: [Caml-list] "Nasty" functions and memory usage

[Xavier Leroy]

> So how can the memory usage of the ocaml interpreter be constant
> at 2200Kb?

It can be that it is traversing a data structure with lots of
sharing, while not allocating any long-lived data structure.
Consider for instance the following type:

                *
               / \
               \ /
                *
               / \
               ...
               \ /
                *
               / \
             'a   'b

It uses little memory, but a full (tree) traversal of it will take
a lot of time.

- Xavier Leroy
-------------------
To unsubscribe, mail caml-list-request@inria.fr.  Archives: http://caml.inria.fr