RE: [Caml-list] Generation of streams is slow

RE: [Caml-list] Generation of streams is slow

[Dave Berry]

Two people at CMU implemented this a couple of years ago.  They called
it "destination-passing style", because the implementation passes an
uninitialised "destination" that is filled in later.  There are some
subtle interactions with the garbage collector, which they investigated.
I don't know why they didn't publish this work -- perhaps they found
some problems with it that I never heard about.

There have also been papers on automatically discovering
source-to-source transformations for this sort of optimisation.  And
there is a very old paper called "tail-recursion modulo Cons" for doing
this particular case in Lisp.

Dave.


-----Original Message-----
From: Jacques Garrigue [mailto:garrigue@kurims.kyoto-u.ac.jp]
Sent: 17 July 2001 03:37
To: avv@quasar.ipa.nw.ru
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] Generation of streams is slow


From: "Alexander V. Voinov" <avv@quasar.ipa.nw.ru>

> Sorry :-), an example in Prolog is:
> 
> f([],[]) :- !.
> f([H1|T1], [H2|T2]) :-
> 	g(H1,H2),
> 	f(T1,T2).
> 
> Last call in this case deals with the final locations of the tails of
> the lists. Though chains of indirection may be long, they are handled
by
> the garbage collection, whose launch strategy may be based more on
> heuristics than on a theory. In OCaml, if it were possible to handle
the
> special case of the _two_ last calls of the form:
> 
>     h::(make_tail arg1 argN),
> 
> that is
> 	CALL make_tail
> 	CONS
> 
> and change them to
>  
> 	PREPARE_CONS
> 	CALL make_tail
> 
> the scope of tail recursion optimization would increase. But it's
> unlikely that this idea didn't come to developers. Which may mean that
> this [being not that simple] is impossible.

You can see:
    Yasuhiko Minamide, "A functional representation of data-structures
    with a hole", POPL'98.
It does exactly that, using linear types to make sur the hole is
initialized later.

I don't know of any published compiler implementing it, but this may
exist.

Jacques
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
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/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Generation of streams is slow

[Alexander V. Voinov]

Hi All,

I've run the following program and found it to be extremely slow. Why?
Does it mean that streams are worth using only when they are built from
input text channels, and in all other cases they are just a waste of
time?

Alexander

open Printf

let gen_stream n =
  let rec gs i n =
    if i = n then [< 'n >] else [< 'i; (gs (i+1) n) >]
  in
  gs 1 n

let rec stupid_loop n s =
  if n > 0 then begin
    if n mod 1000 = 0 then (print_char('.'); flush stdout);
    let i = Stream.next s in
    if i <> n then raise (Failure "they don't match");
    stupid_loop (n+1) s
  end
  else 0;;

let _ =
  stupid_loop 1 (gen_stream 100000);;


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Daniel de Rauglaudre]

Hi,

On Fri, Jul 13, 2001 at 03:06:15PM -0700, Alexander V. Voinov wrote:

> I've run the following program and found it to be extremely slow. Why?

To be optimized, streams and parsers must be preprocessed by Camlp4.
If they are not, their code is longer, not tail recursive and can be
very very slow indeed.

Compile you file with the option -pp camlp4o.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Alexander V. Voinov]

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

Hi Daniel,

Daniel de Rauglaudre wrote:
> 
> Hi,
> 
> On Fri, Jul 13, 2001 at 03:06:15PM -0700, Alexander V. Voinov wrote:
> 
> > I've run the following program and found it to be extremely slow. Why?
> 
> To be optimized, streams and parsers must be preprocessed by Camlp4.
> If they are not, their code is longer, not tail recursive and can be
> very very slow indeed.
> 
> Compile you file with the option -pp camlp4o.

Yes, the difference is substantial, but it gets longer and longer anyway
with more elements parsed (for a slightly more complex program, which
parses the stream as it is generated) and crashes at some point.

I've attached the program (change parse_stream to parse_stream' and vice
versa).

Alexander

[-- Attachment #2: test_streams.ml --]
[-- Type: text/plain, Size: 1065 bytes --]

open Printf

let gen_stream n =
  let rec gs i n =
    if i = n then begin
      printf "making last element of the stream\n"; 
      flush stdout;
      [< 'n >]
    end
    else begin
      if i mod 1000 = 0 then begin
	printf "making next element of the stream: %d\n" i; 
	flush stdout
      end;
      [< 'i; (gs (i+1) n) >] 
    end 
  in
  gs 1 n
	
let rec print_list = function
    []   -> printf "[]\n"
  | h::t -> printf "%d::" h; 
            print_list t

let rec parse_stream s =
  match s with parser
    [< 'i; s' >] -> begin 
      
      if i mod 1000 = 0 then begin
	printf "picked element %d\n" i; 
	flush stdout
      end; 
      
      i::(parse_stream s')
    end
  | [< >] -> (printf "end\n"; flush stdout; [])

let rec parse_stream' s =
  match s with parser
    [< 'i; tail = parse_stream' >] -> begin 
      
      if i mod 1000 = 0 then begin
	printf "picked element %d\n" i; 
	flush stdout
      end; 
      
      i::tail
    end
  | [< >] -> (printf "end\n"; flush stdout; [])

let _ = 
  print_list (parse_stream' (gen_stream 700000))

Re: [Caml-list] Generation of streams is slow

[Daniel de Rauglaudre]

Hi,

On Fri, Jul 13, 2001 at 07:51:09PM -0700, Alexander V. Voinov wrote:

> Yes, the difference is substantial, but it gets longer and longer anyway
> with more elements parsed (for a slightly more complex program, which
> parses the stream as it is generated) and crashes at some point.

I did not test, but looking at your code, I see that neither parse_stream
nor parse_stream' is tail recursive! It is not a question of parsers, now:
your recurive calls are never the last action.

Perhaps this version would work (not tested):

  let rec parse_stream list s =
    match s with parser
      [< 'i; s' >] -> begin 
	if i mod 1000 = 0 then begin
	  printf "picked element %d\n" i; 
	  flush stdout
	end; 
	parse_stream (i :: list) s'
      end
    | [< >] -> (printf "end\n"; flush stdout; List.rev list)

  let _ = 
    print_list (parse_stream' [] (gen_stream 700000))

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Alexander V. Voinov]

Hi Daniel,

Daniel de Rauglaudre wrote:
> > Yes, the difference is substantial, but it gets longer and longer anyway
> > with more elements parsed (for a slightly more complex program, which
> > parses the stream as it is generated) and crashes at some point.
> 
> I did not test, but looking at your code, I see that neither parse_stream
> nor parse_stream' is tail recursive! It is not a question of parsers, now:
> your recurive calls are never the last action.
> 
> Perhaps this version would work (not tested):
> 
>   let rec parse_stream list s =
>     match s with parser
>       [< 'i; s' >] -> begin
>         if i mod 1000 = 0 then begin
>           printf "picked element %d\n" i;
>           flush stdout
>         end;
>         parse_stream (i :: list) s'
>       end
>     | [< >] -> (printf "end\n"; flush stdout; List.rev list)

I see, Prolog habits are hard to leave. But this solution doesn't look
as "natural" as mine, and requires additional time to reverse the
result. I try to acquire hints for the everyday use, of lists and other
abstract sequences in this case. Not just a particular problem to solve.

Alexander
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Alexander V. Voinov]

"Alexander V. Voinov" wrote:
> > Perhaps this version would work (not tested):
> >
> >   let rec parse_stream list s =
> >     match s with parser
> >       [< 'i; s' >] -> begin
> >         if i mod 1000 = 0 then begin
> >           printf "picked element %d\n" i;
> >           flush stdout
> >         end;
> >         parse_stream (i :: list) s'
> >       end
> >     | [< >] -> (printf "end\n"; flush stdout; List.rev list)
> 
> I see, Prolog habits are hard to leave. But this solution doesn't look
> as "natural" as mine, and requires additional time to reverse the
> result. I try to acquire hints for the everyday use, of lists and other
> abstract sequences in this case. Not just a particular problem to solve.

And in general, the inability to pass free variables to be bound later
limits the tail recursion optimization. And forces to use iterations
when they exist (as they do in OCaml).

Alexander
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Daniel de Rauglaudre]

On Fri, Jul 13, 2001 at 09:40:11PM -0700, Alexander V. Voinov wrote:

> And in general, the inability to pass free variables to be bound later
> limits the tail recursion optimization. And forces to use iterations
> when they exist (as they do in OCaml).

??????? I don't understand. Can you give an example?

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Alexander V. Voinov]

Hi Daniel,

Daniel de Rauglaudre wrote:
> 
> On Fri, Jul 13, 2001 at 09:40:11PM -0700, Alexander V. Voinov wrote:
> 
> > And in general, the inability to pass free variables to be bound later
> > limits the tail recursion optimization. And forces to use iterations
> > when they exist (as they do in OCaml).
> 
> ??????? I don't understand. Can you give an example?

Sorry :-), an example in Prolog is:

f([],[]) :- !.
f([H1|T1], [H2|T2]) :-
	g(H1,H2),
	f(T1,T2).

Last call in this case deals with the final locations of the tails of
the lists. Though chains of indirection may be long, they are handled by
the garbage collection, whose launch strategy may be based more on
heuristics than on a theory. In OCaml, if it were possible to handle the
special case of the _two_ last calls of the form:

    h::(make_tail arg1 argN),

that is
	CALL make_tail
	CONS

and change them to
 
	PREPARE_CONS
	CALL make_tail

the scope of tail recursion optimization would increase. But it's
unlikely that this idea didn't come to developers. Which may mean that
this [being not that simple] is impossible.

Alexander
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Daniel de Rauglaudre]

Hi,

On Sat, Jul 14, 2001 at 11:08:09AM -0700, Alexander V. Voinov wrote:

>     h::(make_tail arg1 argN),
> that is
> 	CALL make_tail
> 	CONS
> and change them to
> 	PREPARE_CONS
> 	CALL make_tail
> the scope of tail recursion optimization would increase. But it's
> unlikely that this idea didn't come to developers. Which may mean that
> this [being not that simple] is impossible.

It supposes that the order of evaluation could be variable. If we
imagine a constructor C with 5 parameters. If we evalutate:

      C (a, b, c, d, e)

Here, the order of evaluation is a-b-c-d-e or e-d-c-b-a, I don't know,
but in some logical order. If the tail recursion is, say, on the third
parameter c, it supposes that a, b, d and e be evaluated before. And
what policy use if, say, d is another tail recursion?

In OCaml the evaluation order is not - supposed to be - specified. In
this case, it would less be specified, since it could change depending
on the parameters. Interesting... But I don't know if it is possible to
implement that in the code generation.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Alexander V. Voinov]

Hi Daniel,

Daniel de Rauglaudre wrote:
> Here, the order of evaluation is a-b-c-d-e or e-d-c-b-a, I don't know,
> but in some logical order. If the tail recursion is, say, on the third
> parameter c, it supposes that a, b, d and e be evaluated before. And
> what policy use if, say, d is another tail recursion?

I probably need to reread the docs, but as I remember it was stressed
that the presence of imperative features, eps. mutable values, doesn't
allow for much indeterminism in the evaluation order. Because it legally
matters what was the order of evaluation of a-b-c-d-e if some of them
change global values, which are used in the others.

Alexander
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Alexander V. Voinov]

Daniel de Rauglaudre wrote:
> 
> Hi,
> 
> On Sat, Jul 14, 2001 at 11:08:09AM -0700, Alexander V. Voinov wrote:
> 
> >     h::(make_tail arg1 argN),
> > that is
> >       CALL make_tail
> >       CONS
> > and change them to
> >       PREPARE_CONS
> >       CALL make_tail
> > the scope of tail recursion optimization would increase. But it's
> > unlikely that this idea didn't come to developers. Which may mean that
> > this [being not that simple] is impossible.
> 
> It supposes that the order of evaluation could be variable. If we
> imagine a constructor C with 5 parameters. If we evalutate:
> 
>       C (a, b, c, d, e)

I don't understand, however, the argument about the order of evaluation
in _this_ case, that is of h::(make_tail args). The value of `h' is
supposed to be computed to this point, and whatever side effects are
present in `make_tail', they cannot influence the result of ::, which is
context-independent. The only difference might be the exceptions, which
can appear in `make_tail' and propagate somewhere, but the result will
not be returned anyway (the call to :: is supposed to be the _last_), so
it doesn't matter if :: is prepared to accept it or not.

Or to introduce a special version of ::, say :!:, which ensures that the
call to make_tail is really the last.

Alexander
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Daniel de Rauglaudre]

Hi,

On Sat, Jul 14, 2001 at 02:59:40PM -0700, Alexander V. Voinov wrote:

> I don't understand, however, the argument about the order of evaluation

This was not an argument, just a remark. IMHO, the problem is more how
to implement the fact that the called function must patch a constructor
parameter instead of returning a value. But I have no idea of the
difficulty of implementing that.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Jacques Garrigue]

From: "Alexander V. Voinov" <avv@quasar.ipa.nw.ru>

> Sorry :-), an example in Prolog is:
> 
> f([],[]) :- !.
> f([H1|T1], [H2|T2]) :-
> 	g(H1,H2),
> 	f(T1,T2).
> 
> Last call in this case deals with the final locations of the tails of
> the lists. Though chains of indirection may be long, they are handled by
> the garbage collection, whose launch strategy may be based more on
> heuristics than on a theory. In OCaml, if it were possible to handle the
> special case of the _two_ last calls of the form:
> 
>     h::(make_tail arg1 argN),
> 
> that is
> 	CALL make_tail
> 	CONS
> 
> and change them to
>  
> 	PREPARE_CONS
> 	CALL make_tail
> 
> the scope of tail recursion optimization would increase. But it's
> unlikely that this idea didn't come to developers. Which may mean that
> this [being not that simple] is impossible.

You can see:
    Yasuhiko Minamide, "A functional representation of data-structures
    with a hole", POPL'98.
It does exactly that, using linear types to make sur the hole is
initialized later.

I don't know of any published compiler implementing it, but this may
exist.

Jacques
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Daniel de Rauglaudre]

Hi,

On Fri, Jul 13, 2001 at 09:15:04PM -0700, Alexander V. Voinov wrote:

> I see, Prolog habits are hard to leave. But this solution doesn't look
> as "natural" as mine

It is not, indeed, but if you have long lists, it is the normal approach.
You would have the same problem with List.map which is not tail recursive
either.

> and requires additional time to reverse the result.

Exact, but List.rev is tail recursive.

All non tail recursive functions can be rewritten in a recursive way
by adding the accumulator value as parameter. If if is a list, it is
reversed and you have to reverse it.

A way to avoid that (I mean creation of a reversed list and reversion)
is to use mutable types, what the list type is not.

> I try to acquire hints for the everyday use, of lists and other
> abstract sequences in this case. Not just a particular problem to solve.

In the List module, some functions are tail recursive, other not. It has
been planed for non too big lists. If you have big lists, you have to be
careful of that. You may have to write your own functions in some cases.

Also be careful of code enclosed by try..with: it prevents tail
recursion. A "try a with b -> c" enclosing a recursive call in "a" must
be rewritten as:

    match (try Some a with b -> None) with
      Some x -> a
    | None -> c

It is heavy code, but mandatory: I often use it.

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Generation of streams is slow

[Chris Hecker]

>A way to avoid that (I mean creation of a reversed list and reversion)
>is to use mutable types, what the list type is not.

Has anybody written a simple "circular linked list" implementation in ocaml?  Basically, you'd want it to act exactly like the built in lists, but appends and finding the tail elemeent are O(1).

It doesn't seem possible to make this as convenient as the built in list, since :: doesn't seem to be redefinable, and I don't know how you'd make this work in pattern matching.  Is there any work on making user defined abstract types work in pattern matching?

Chris


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr