Efficiency of let/and

Efficiency of let/and

[Brian Hurt]

Say I have two variables I want to set- variable a to the value expr1 and 
variable b to the value expr2.  The two expressions are pure (no side 
effects), and neither one depends upon the other (neither expr1 nor expr2 
contain either a or b as a value), so they can be evaluated in either 
order or in parallel with no harm.  With expressions like these, I've 
gotten into the habit of using let/and to express the parallelism, that is 
I go:

 	let a = expr1
 	and b = expr2
 	in
 	...

rather than:
 	let a = expr1 in
 	let b = expr2 in

So my question is: is there any value (other than the documentation value) 
in doing this?

Just wondering.

Brian

Re: [Caml-list] Efficiency of let/and

[Jon Harrop]

On Sunday 25 September 2005 14:31, Brian Hurt wrote:
> So my question is: is there any value (other than the documentation value)
> in doing this?

Good question. I've no idea. However, I did notice that this change has been 
undone (i.e. to use "let" twice and not "and") in the stdlib.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Ant: [Caml-list] Efficiency of let/and

[Martin Chabr]

As it appears to me, there is no semantic difference
between both alternatives. It can be shown with two
dependent expressions y = 1 and z = y + 2:

# let y = 1 in
  let z = y + 2 in
  z;;
- : int = 3

# let y = 1
  and z = y + 2 in
  z;;
- : int = 3

The order is important in both cases:

# let z = y + 2 in
  let y = x + 1 in
  z;;
Characters 8-9:
  let z = y + 2 in
          ^
Unbound value y

# let z = y + 2
  and y = 1 in
  z;;
Characters 8-9:
  let z = y + 2
          ^
Unbound value y

So the "and"-form depends on the order as well and I
think the syntactic difference can be just used for
documentation. A good idea, by the way.

I hope this helps

Martin



--- Brian Hurt <bhurt@spnz.org> schrieb:

> 
> Say I have two variables I want to set- variable a
> to the value expr1 and 
> variable b to the value expr2.  The two expressions
> are pure (no side 
> effects), and neither one depends upon the other
> (neither expr1 nor expr2 
> contain either a or b as a value), so they can be
> evaluated in either 
> order or in parallel with no harm.  With expressions
> like these, I've 
> gotten into the habit of using let/and to express
> the parallelism, that is 
> I go:
> 
>  	let a = expr1
>  	and b = expr2
>  	in
>  	...
> 
> rather than:
>  	let a = expr1 in
>  	let b = expr2 in
> 
> So my question is: is there any value (other than
> the documentation value) 
> in doing this?
> 
> Just wondering.
> 
> Brian
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 



	
		
___________________________________________________________ 
Gesendet von Yahoo! Mail - Jetzt mit 1GB Speicher kostenlos - Hier anmelden: http://mail.yahoo.de

Re: Ant: [Caml-list] Efficiency of let/and

[Fernando Alegre]

There is a small advantage in using "and" instead of "in let":

# let () =
  let x = 2 and x = 5 in ();;
This variable is bound several times in this matching
# let () =
  let x = 2 in let x = 5 in ();;

Probably the second "x" should have been a "y"... so the compiler catches
that mistake.

Fernando

> >  	let a = expr1
> >  	and b = expr2
> >  	in
> >  	...
> > 
> > rather than:
> >  	let a = expr1 in
> >  	let b = expr2 in
> > 
> > So my question is: is there any value (other than
> > the documentation value) 
> > in doing this?

Re: Ant: [Caml-list] Efficiency of let/and

[William Lovas]

On Mon, Sep 26, 2005 at 06:32:40AM +0200, Martin Chabr wrote:
> As it appears to me, there is no semantic difference
> between both alternatives. It can be shown with two
> dependent expressions y = 1 and z = y + 2:

This is not universally true:

> # let y = 1
>   and z = y + 2 in
>   z;;
> - : int = 3

            Objective Caml version 3.08.1

    # let y = 1
      and z = y + 2 in
      z;;
    Unbound value y

So either you are using a version older than 3.08.1 or this is a fairly
recent change.  In the latter case, people who wish to remain backward-
compatible might eschew this style for sequential bindings, regardless
of any potential performance problems.

William

Re: Ant: [Caml-list] Efficiency of let/and

[Bill Wood]

   . . .
> This is not universally true:
> 
> > # let y = 1
> >   and z = y + 2 in
> >   z;;
> > - : int = 3
> 
>             Objective Caml version 3.08.1
> 
>     # let y = 1
>       and z = y + 2 in
>       z;;
>     Unbound value y
> 
> So either you are using a version older than 3.08.1 or this is a fairly
> recent change.  In the latter case, people who wish to remain backward-
> compatible might eschew this style for sequential bindings, regardless
> of any potential performance problems.

I'm using Objective Caml version 3.08.3 and had this interaction:
    # let y = 1
      and z = y + 2 in
        z;;
    Unbound value y
    #

 -- Bill Wood
    bill.wood@acm.org

Ant: Re: Ant: [Caml-list] Efficiency of let/and

[Martin Chabr]

Yes, you are right. Shame on me. I must have had a
bounding for y from an earlier experiment. When I
restart the interpreter, so that it is in a virgin
state, I get the same error message about unbound y as
you.

Martin

--- William Lovas <wlovas@stwing.upenn.edu> schrieb:

> On Mon, Sep 26, 2005 at 06:32:40AM +0200, Martin
> Chabr wrote:
> > As it appears to me, there is no semantic
> difference
> > between both alternatives. It can be shown with
> two
> > dependent expressions y = 1 and z = y + 2:
> 
> This is not universally true:
> 
> > # let y = 1
> >   and z = y + 2 in
> >   z;;
> > - : int = 3
> 
>             Objective Caml version 3.08.1
> 
>     # let y = 1
>       and z = y + 2 in
>       z;;
>     Unbound value y
> 
> So either you are using a version older than 3.08.1
> or this is a fairly
> recent change.  In the latter case, people who wish
> to remain backward-
> compatible might eschew this style for sequential
> bindings, regardless
> of any potential performance problems.
> 
> William
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 


Martin Chabr
Hochstrasse 28
8044 Zürich
Schweiz / Switzerland
Tel.P.: 01-261 17 24


	

	
		
___________________________________________________________ 
Gesendet von Yahoo! Mail - Jetzt mit 1GB Speicher kostenlos - Hier anmelden: http://mail.yahoo.de

Re: Ant: [Caml-list] Efficiency of let/and

[Brian Hurt]

On Mon, 26 Sep 2005, Martin Chabr wrote:

> As it appears to me, there is no semantic difference
> between both alternatives. It can be shown with two
> dependent expressions y = 1 and z = y + 2:
>
> # let y = 1 in
>  let z = y + 2 in
>  z;;
> - : int = 3

Actually, my example would be more like:
     let y = 1 in
     let z = 2 in
     ...

vr.s
     let y = 1
     and z = 2
     in
     ...

Or, more commonly, something like:
     let foo arr1 arr2 =
         (* I need the lengths of both arrays *)
         let len1 = Array.length arr1
         and len2 = Array.length arr2
         in
         ...

Syntactically and semantically there is no difference.  I was wondering if 
the ocamlopt compiler took advatange of the implicit paralellism at all.

Brian

Re: Ant: Efficiency of let/and

[Stefan Monnier]

> Syntactically and semantically there is no difference.  I was wondering if
> the ocamlopt compiler took advatange of the implicit paralellism at all.

If someone tries to use such things as `and' or
unspecified-argument-evaluation-order in the hopes that the compiler will
extract some imagined parallelism is simply deluding himself.
In some cases, the freedom to execute in any order does lead to better
code, but that code rarely if ever uses any kind of parallelism.


        Stefan

Re: [Caml-list] Re: Ant: Efficiency of let/and

[Brian Hurt]

On Mon, 26 Sep 2005, Stefan Monnier wrote:

>> Syntactically and semantically there is no difference.  I was wondering if
>> the ocamlopt compiler took advatange of the implicit paralellism at all.
>
> If someone tries to use such things as `and' or
> unspecified-argument-evaluation-order in the hopes that the compiler will
> extract some imagined parallelism is simply deluding himself.
> In some cases, the freedom to execute in any order does lead to better
> code, but that code rarely if ever uses any kind of parallelism.

I was thinking of instruction-level parallelism- the ability of the 
compiler to reorder instructions to better use the available functional 
units, not thread-level parallelism.  Sorry for not being clear there.

I'm not even sure how much extra efficiency is there to be had.  Obviously 
it'd be hard "thread" calls to complex functions, so code like:

let foo lst1 lst2 =
     let len1 = List.length lst1
     and len2 = List.length lst2
     in
     ...

wouldn't be helped- it'd be computationally infeasible for the compiler to 
interleave the two different calls to List.length.  So you'd pretty 
obviously be limited to "simple" expressions, at which point the CPU's own 
prefetching and reordering is likely to do the work for you wether the 
compiler does it or not.  In fact, the CPU's reordering can start 
executing the code to List.length lst2 speculatively before the call to 
List.length lst1 is complete, and in that sense the CPU's reordering is 
more capable then what the compiler can do (this, BTW, is the fundamental 
problem with the Itanium).

Brian

Re: [Caml-list] Re: Ant: Efficiency of let/and

[skaller]

On Mon, 2005-09-26 at 11:30 -0500, Brian Hurt wrote:

> I'm not even sure how much extra efficiency is there to be had.  Obviously 
> it'd be hard "thread" calls to complex functions, 

Why? Hyperthreading allows two completely independent processes
to execute on a hyperthread enabled P4 .. the hardware can already
do it .. even better with dual core.

There is no lack of small scale low level parallelism in 
modern computing systems, just a lack of software that knows
how to take advantage of it.

There are plenty of places in an average program where one
can determine parallel execution would be ok, so it is really
a lack of capability in the software.

I personally don't think of this as real parallelism,
that's something you get on a machine with K's or M's
of processing units .. eg the human eye.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Re: Ant: Efficiency of let/and

[Brian Hurt]

On Tue, 27 Sep 2005, skaller wrote:

> On Mon, 2005-09-26 at 11:30 -0500, Brian Hurt wrote:
>
>> I'm not even sure how much extra efficiency is there to be had.  Obviously
>> it'd be hard "thread" calls to complex functions,
>
> Why? Hyperthreading allows two completely independent processes
> to execute on a hyperthread enabled P4 .. the hardware can already
> do it .. even better with dual core.

Creating a new kernel-level process/thread (required to get code executing 
on a different processor or pseudo-processor) is generally expensive.  You 
don't want to do it except for very large functions.  And then, once you 
do have the second thread of execution, you now have all the fun of 
multithreaded code- race conditions and deadlocks and livelocks, oh my.

I have contemplated writting a purely-functional (no imperitive) language 
that does micro-threads ala cilk- but it's more work than I really want to 
put in to that project.

>
> There is no lack of small scale low level parallelism in
> modern computing systems, just a lack of software that knows
> how to take advantage of it.

The benefit may be there, theoretically, but practical considerations may 
make it not worth the effort to go after the benefit.

>
> There are plenty of places in an average program where one
> can determine parallel execution would be ok, so it is really
> a lack of capability in the software.
>
> I personally don't think of this as real parallelism,
> that's something you get on a machine with K's or M's
> of processing units .. eg the human eye.

Heh.  We've hit the point where we have so many transistors on a chip we 
literally don't know what to do with them all- we have no idea how to 
spend the transistors to provide more than very small incremental 
performance improvements to single-threaded execution.  Which is why the 
sudden interest in parallelism (Symmetric Mult-Threading aka 
Hyperthreading, multi-core chips, etc.).  The problem is that the theory 
on how to write race condition/deadlock/livelock -free code isn't there, 
to my knowledge (someone please prove me wrong).

Brian

Re: [Caml-list] Re: Ant: Efficiency of let/and

[Alan Falloon]

Brian Hurt wrote:

> On Tue, 27 Sep 2005, skaller wrote:
>
>> I personally don't think of this as real parallelism,
>> that's something you get on a machine with K's or M's
>> of processing units .. eg the human eye.
>
>
> Heh.  We've hit the point where we have so many transistors on a chip 
> we literally don't know what to do with them all- we have no idea how 
> to spend the transistors to provide more than very small incremental 
> performance improvements to single-threaded execution.  Which is why 
> the sudden interest in parallelism (Symmetric Mult-Threading aka 
> Hyperthreading, multi-core chips, etc.).  The problem is that the 
> theory on how to write race condition/deadlock/livelock -free code 
> isn't there, to my knowledge (someone please prove me wrong).

I did see a paper called "Composable Memory Transactions" by some of the 
more well know Haskell researchers  its avaliable at  
http://got.net/~landauer/cs/fp/ea8-composablememory_stm.pdf

The idea is to introduce new concurrency abstractions (a replacement for 
mutex and friends) that are composable to make it easy to reason about 
thread-safe sections in isolation.

Re: [Caml-list] Re: Ant: Efficiency of let/and

[Stefan Monnier]

> chips, etc.).  The problem is that the theory on how to write race
> condition/deadlock/livelock -free code isn't there, to my knowledge

I think the theory is pretty much there.  The problem is to put it
into practice.


        Stefan

Re: [Caml-list] Re: Ant: Efficiency of let/and

[Brian Hurt]

On Tue, 27 Sep 2005, Stefan Monnier wrote:

>> chips, etc.).  The problem is that the theory on how to write race
>> condition/deadlock/livelock -free code isn't there, to my knowledge
>
> I think the theory is pretty much there.  The problem is to put it
> into practice.

I'm not 100% sure it is.  Oh, it is for the "trivial" questions- like will 
this program run to completion and will it return the right answer?  But 
it isn't there yet (to my knowledge) on the more difficult questions, like 
can I automatically tune this program to efficiently use N threads (where 
both N=1 and N ~ millions are interesting values)?  And what is the 
minimum amount of synchronization this program requires at N threads? 
Etc.

IMHO, we need to take synchronization out of the hands of the programmer 
just like we took garbage collection out of the hands of the programmer. 
But, then again, I'm widely regarded as a radical :-).

Brian

Re: [Caml-list] Re: Ant: Efficiency of let/and

[skaller]

On Mon, 2005-09-26 at 12:05 -0400, Stefan Monnier wrote:
> > Syntactically and semantically there is no difference.  I was wondering if
> > the ocamlopt compiler took advatange of the implicit paralellism at all.
> 
> If someone tries to use such things as `and' or
> unspecified-argument-evaluation-order in the hopes that the compiler will
> extract some imagined parallelism is simply deluding himself.
> In some cases, the freedom to execute in any order does lead to better
> code, but that code rarely if ever uses any kind of parallelism.

This is not so at all. Limited Parallelism is indeed found in all 
modern processors, which can, for example, distribute multiple
instructions on several pipelines, decode in parallel with
computing values, or perform several integer and/or floating
operations simultaneously.

In fact, as far back as 197x, the Cyber 70 could do this,
in fact it relied on it. In particular, register calculations
and memory fetches and stores we always done in parallel,
automatically, until a join point. When you did a load,
for example, the next instruction would be executed
immediately, without waiting for the load to complete,
provided it didn't use the register being loaded
(and I think .. it would then proceed to the next instruction,
and execute THAT whilst suspending the previous one, provided
it used distinct registers .. but I'm not sure).

It may well be that this has no impact on Ocaml code.
However it certainly DOES have an impact on low level C code.

In addition, parallel assignment is a major benefit,
not because the assignments are done concurrently,
but because it can save memory. For example:

	x,y = 1,2

cf

	x,y = y,x

The first pair of assignments is faster and uses no temporaries,
the second requires a temporary. So an arbitrary parallel
assignment can, in fact, be optimised to reduce the number
of temporaries used, and thus the number of operations.

Parallel assignments as written aren't that useful, however
there is a particular optimisation of great benefit
which is requires parallel assignment: self-tail-recursion.

In this case, the assignment arises through reusing the
same closure, and the optimisation is of the form:

	x,y,x = f(x,y,z), g(x,y,z), h(x,y,x)
	goto start

In particular, the argument of the new invocation can
depend on the argument of the old invocation, and,
in tuple form the assignment would, without analysis,
require a temporary the size of the argument:

	tmp = f(x,y,z), g(x,y,z), h(x,y,z)
	x,y,z = tmp

Which, in the worst case, *doubles* the number
of assignments, and thus the cost of looping --
in a tight inner loop this can be critical.

In a language like Ocaml, a parallel operation can have
a major performance advantage, because it explicitly
indicates to the compiler that the order of evaluation
is irrelevant: due to side-effects and separate compilation,
the order of evaluation of sequential assignments is likely
to be fixed, and therefore cannot be optimised.

I do not know whether Ocaml does parallel assignment
optimisations on self-tail recursions .. but I can
tell you that Felix DOES. Perhaps this is why it
calculates Ackermann's function faster than Ocaml and C?
[I have no idea of the real reason .. but it does]

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Re: Ant: Efficiency of let/and

[Stefan Monnier]

>> If someone tries to use such things as `and' or
>> unspecified-argument-evaluation-order in the hopes that the compiler will
>> extract some imagined parallelism is simply deluding himself.
>> In some cases, the freedom to execute in any order does lead to better
>> code, but that code rarely if ever uses any kind of parallelism.

> This is not so at all. Limited Parallelism is indeed found in all 
> modern processors, which can, for example, distribute multiple
> instructions on several pipelines, decode in parallel with
> computing values, or perform several integer and/or floating
> operations simultaneously.

This has nothing to do with what I said.  Compilers can equally take
advantage of ILP with a `let' or with a specified evaluation order.


        Stefan

Re: Ant: [Caml-list] Efficiency of let/and

[Mackenzie Straight]

On 9/26/05, Brian Hurt <bhurt@spnz.org> wrote:
> Syntactically and semantically there is no difference.  I was wondering if
> the ocamlopt compiler took advatange of the implicit paralellism at all.

In any case, it makes (as far as I know) no difference which syntax you use:

% ocaml -drawlambda
        Objective Caml version 3.08.3

# let foo a1 a2 = let l1 = Array.length a1 and l2 = Array.length a2 in l1+l2;;
(let
  (foo/65
     (function a1/66 a2/67
       (let (l1/68 (array.length a1/66) l2/69 (array.length a2/67))
         (+ l1/68 l2/69))))
  (apply (field 1 (global Toploop!)) "foo" foo/65))
val foo : 'a array -> 'b array -> int = <fun>
# let bar a1 a2 = let l1 = Array.length a1 in let l2 = Array.length a2
in l1+l2;;
(let
  (bar/70
     (function a1/71 a2/72
       (let (l1/73 (array.length a1/71) l2/74 (array.length a2/72))
         (+ l1/73 l2/74))))
  (apply (field 1 (global Toploop!)) "bar" bar/70))
val bar : 'a array -> 'b array -> int = <fun>

Re: Ant: [Caml-list] Efficiency of let/and

[Marius Nita]

Martin Chabr wrote:
> As it appears to me, there is no semantic difference
> between both alternatives.

I've always thought that there was. In the `and' form, the bindings 
cannot depend on each other. The program you pasted shouldn't run in any 
(recent) OCaml toplevel. Are you using a really old one or something?

-marius

It can be shown with two
> dependent expressions y = 1 and z = y + 2:
> 
> # let y = 1 in
>   let z = y + 2 in
>   z;;
> - : int = 3
> 
> # let y = 1
>   and z = y + 2 in
>   z;;
> - : int = 3
> 
> The order is important in both cases:
> 
> # let z = y + 2 in
>   let y = x + 1 in
>   z;;
> Characters 8-9:
>   let z = y + 2 in
>           ^
> Unbound value y
> 
> # let z = y + 2
>   and y = 1 in
>   z;;
> Characters 8-9:
>   let z = y + 2
>           ^
> Unbound value y
> 
> So the "and"-form depends on the order as well and I
> think the syntactic difference can be just used for
> documentation. A good idea, by the way.
> 
> I hope this helps
> 
> Martin
> 
> 
> 
> --- Brian Hurt <bhurt@spnz.org> schrieb:
> 
>> Say I have two variables I want to set- variable a
>> to the value expr1 and 
>> variable b to the value expr2.  The two expressions
>> are pure (no side 
>> effects), and neither one depends upon the other
>> (neither expr1 nor expr2 
>> contain either a or b as a value), so they can be
>> evaluated in either 
>> order or in parallel with no harm.  With expressions
>> like these, I've 
>> gotten into the habit of using let/and to express
>> the parallelism, that is 
>> I go:
>>
>>  	let a = expr1
>>  	and b = expr2
>>  	in
>>  	...
>>
>> rather than:
>>  	let a = expr1 in
>>  	let b = expr2 in
>>
>> So my question is: is there any value (other than
>> the documentation value) 
>> in doing this?
>>
>> Just wondering.
>>
>> Brian
>>
>> _______________________________________________
>> Caml-list mailing list. Subscription management:
>>
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
>> Archives: http://caml.inria.fr
>> Beginner's list:
>> http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
> 
> 
> 
> 	
> 		
> ___________________________________________________________ 
> Gesendet von Yahoo! Mail - Jetzt mit 1GB Speicher kostenlos - Hier anmelden: http://mail.yahoo.de
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: Ant: [Caml-list] Efficiency of let/and

[David McClain]

I have understood that the "and" syntax was needed to support the creation
of mutually recursive bindings. While it can also be used as a form of
"parallel let" within a function definition, it is vitally important for the
mutual recursion case.

- David McClain, Tucson, AZ, USA