Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

On Tue, Oct 04, 2005 at 07:45:12PM -0500, Brian Hurt wrote:
[...] 
> The big advantage of FP programming IMHO is not performance, but instead 
> *correctness*.  With today's multi-gigahertz machines with multi-gigabytes 
> of memory, performance isn't as critical as it used to be.  But 
> correctness- especially automatically gaurenteed correctness on projects 
> spanning hundreds of thousands of lines of code and dozens of developers 
> maintained over decades of time- starts becoming critical.

Yes, I agree on this.
I get daily messages from an buglist-mailinglist, where most often
things like typical memory-exploits are the reason of why a system
or a process can be exploited.

So, the typical "out of bounds" and "format string" problems
are typical security risks.
(Btw: is OCaml's format-string stuff from the Printf-module save in
this respect?!)


> I'd quite 
> happily trade off 10% performance for correctness, or even 50% 
> performance.

Well, if the code with correctness is nearly as fast as the code without,
it would be best.


> 
> FP is a huge gain in correctness, because it allows me to *control 
> mutability*.  If I pass a mutable data structure to a block of code there 
> is an instant implicit contract between the caller and the callee on how 
> (or wether) to modify the mutable data structure.  It doesn't matter what 
> the contract is- wether it's to not modify the structure at all, to allow 
> optional modification (either unlimited or only in certain ways), or to 
> require certain modifications- a dependency between the two different 
> peices of code exists.  And this dependency, this contract, is probably 
> undocumented and always unchecked by the compiler, which means it's a 
> maintaince nightmare waiting to happen.  One peice of code gets modified 
> to violate the contract, perhaps even unknowingly, or perhaps due to some 
> changing requirement, and untouched code thousands of lines away suddenly 
> breaks.


Yes, this is a very well description of the FP-advantages.
Nevertheless, if a solution is too slow, it hinders
people from adopting FPLs for their programmig, and
software remains unsecure/unsafe, because they again and again
will choose the unsafe langauges... :(


Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[William Lovas]

On Wed, Oct 05, 2005 at 03:45:52PM +0200, Oliver Bandel wrote:
> So, the typical "out of bounds" and "format string" problems
> are typical security risks.
> (Btw: is OCaml's format-string stuff from the Printf-module save in
> this respect?!)

As far as i understand the "format string" bugs, they arise when a
programmer writes a call to printf whose first argument comes from
user input.  In O'Caml the various *printf functions require their
first argument to have type "('a, 'b, 'c) format", for some values
of 'a, 'b, and 'c.  As far as i can tell there's no way to produce
a value of this type from user input, so O'Caml should be safe.

In fact, there might even be a better reason O'Caml is safe, like
that it doesn't automatically keep looking for arguments until it
runs out of %expandos, but rather it just produces a closure that
can be applied to more arguments later.  But this is just a guess,
based on a quick 5-minute perusal of the O'Caml standard library.

cheers,
William

Ant: Re: Ant: Re: Ant: Re: [Caml-list] Avoiding shared data

[Martin Chabr]

Thomas,

what I am especially concerned about is the stack
overflow for non-tail-recursive programs. Speed is of
less importance.

By the way, we are diverting from the subject of this
thread and from the main cause of my concern:

Avoiding shared data. Why is it done that way? Who
wants to have an array or list of identical records or
sub-arrays or other sub-structures which are all
updated at the same time in the same way? In other
words, who wants to have an array or a list of
pointers which are pointing to the same thing?

Does it ever happen in OCaml if programming is done in
a purely functional way? Does it happen in Haskell?

Martin


--- Thomas Fischbacher
<Thomas.Fischbacher@Physik.Uni-Muenchen.DE> schrieb:

> 
> On Mon, 3 Oct 2005, skaller wrote:
> 
> > > I hope that one day functional language
> compilers will
> > > do that optimization for you - convert a
> > > non-tail-recursive code into a tail-recursive
> one. Do
> > > you know of some progress in that direction?
> > 
> > Isn't that just CPS? 
> 
> He presumably wanted to see a different thing, e.g. 
> automatically transforming
> 
> 
> let rec fac1 x =
>   if x = 0
>   then 1
>   else x*(fac1 (x-1))
> ;;
> 
> into
> 
> let fac2 x =
>   let rec walk so_far todo =
>     if todo = 0
>     then so_far
>     else walk (todo*so_far) (todo-1)
>   in walk 1 x
> ;;
> 
> 
> My impression is that it may indeed be possible to
> do something like this 
> for simple applications, but that the cases that can
> be covered 
> automatically presumably are so limited that an
> experienced programmer 
> will usually want to attack them by going to a
> higher form of abstraction 
> and not waste time on such things anyway.
> 
> I think that Olin Shivers indeed does have a valid
> point in pointing out 
> that writing loops in tail-recursive style has major
> disadvantages. 
> However, my impression still is that as soon as
> someone thinks in terms of 
> "I have to write a loop for this", chances are good
> that he may improve 
> his design by going back one step and ask the
> question "what do I want to 
> use that loop for?". In quite many situations, it is
> possible to express 
> one's thoughts more directly via other means, such
> as Array.map, 
> fold_left, etc. 
> 
> What I (as a pedestrian) especially do not like
> about loops is that it is
> much easier to make off-by-one errors than with any
> form of recursion 
> which contains a base-case/recursive-case analysis.
> 
> 
> Unfortunately, the OCaml native code compiler
> apparently is not yet smart 
> enough to optimize code written in such a
> higher-order style well enough 
> so that it can compete with imperative or
> tail-recursive code in 
> time-critical applications. (Though quite many
> applications in fact are 
> not.) At present, one can expect to lose about a
> factor of ~3 in
> performance.
> 
> Example:
> 
> ===>
> let timing_apply f x =
>   let t0 = Unix.gettimeofday() in
>   let f_x = f x in
>   let t1 = Unix.gettimeofday() in
>   (f_x,t1-.t0)
> ;;
> 
> let my_array_fold_left f init arr =
>   let len = Array.length arr in
>   let rec walk so_far pos =
>     if pos=len
>     then so_far
>     else walk (f so_far arr.(pos)) (1+pos)
>   in walk init 0
> ;;
> 
> 
> let test m n =
>   let arr =
>     Array.init m
>       (fun j -> Array.init n (fun k -> j*k+k))
>   in
>   let scratchpad = ref 0 in
>   (* -- *)
>   let rec frobenius1 mx =
>     Array.fold_left
>       (fun so_far row ->
> 	Array.fold_left
> 	  (fun so_far entry ->
> 	    so_far+entry*entry)
> 	  so_far row)
>       0 mx
>   in
>   let frobenius2 mx =
>     my_array_fold_left
>       (fun so_far row ->
> 	my_array_fold_left
> 	  (fun so_far entry ->
> 	    so_far+entry*entry)
> 	  so_far row)
>       0 mx
>   in
>   let frobenius3 mx =
>     begin
>       scratchpad := 0;
>       for i=0 to (Array.length mx)-1 do
> 	let row = mx.(i) in
> 	for j=0 to (Array.length row)-1 do
> 	  scratchpad:= !scratchpad + row.(j)*row.(j);
> 	done;
>       done;
>       !scratchpad
>     end
>   in
>   let frobenius4 mx =
>     let nr_rows = Array.length mx in
>     let rec walk_rows so_far nr_row =
>       if nr_row = nr_rows
>       then so_far
>       else
> 	let row = mx.(nr_row) in
> 	let len_row = Array.length row in
> 	let rec walk_cols so_far nr_col =
> 	  if nr_col = len_row
> 	  then so_far
> 	  else walk_cols (so_far+row.(nr_col)*row.(nr_col))
> (1+nr_col)
> 	in 
> 	walk_rows (walk_cols so_far 0) (1+nr_row)
>     in
>     walk_rows 0 0
>   in
>   let frobenius5 mx =
>     let nr_rows = Array.length mx in
>     let rec walk_rows so_far nr_row =
>       if nr_row = nr_rows
>       then so_far
>       else
> 	let row = mx.(nr_row) in
> 	let len_row = Array.length row in
> 	let rec walk_cols row so_far nr_col =
> 	  if nr_col = len_row
> 	  then so_far
> 	  else walk_cols row
> (so_far+row.(nr_col)*row.(nr_col)) (1+nr_col)
> 	in 
> 	walk_rows (walk_cols row so_far 0) (1+nr_row)
>     in
>     walk_rows 0 0
>   in
>   let compute_n_times n f x =
>     let rec walk k =
>       if k = n then f x
>       else
> 	let () = ignore(f x) in
> 	walk (k+1)
>     in walk 1
>   in
>   Array.map
>     (fun f -> timing_apply (compute_n_times 1000 f)
> arr)
>    
>
[|frobenius1;frobenius2;frobenius3;frobenius4;frobenius5|]
> ;;
> 
> let result = test 1000 3 in
> Array.iteri (fun nr (_,t) -> Printf.printf "%d:
> %f\n" (1+nr) t) result
> ;;
> <===
> 
> ocamlc:
> 
> 1: 0.987257
> 2: 1.196910
> 3: 0.709074
> 4: 0.858948
> 5: 0.984935
> 
> ocamlopt:
> 
=== message truncated ===



	

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

Re: Ant: Re: Ant: Re: Ant: Re: [Caml-list] Avoiding shared data

[skaller]

On Mon, 2005-10-03 at 22:03 +0200, Martin Chabr wrote:

> Avoiding shared data. Why is it done that way? Who
> wants to have an array or list of identical records or
> sub-arrays or other sub-structures which are all
> updated at the same time in the same way?

Mutable shared data is very useful: caching is
an obvious example where this is precisely what you want.

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

Re: [Caml-list] Avoiding shared data

[Brian Hurt]

On Tue, 4 Oct 2005, skaller wrote:

> Mutable shared data is very useful: caching is
> an obvious example where this is precisely what you want.

Also, occassionally mutable data allows you to do something in O(1) 
instead of O(log N).  If this extra cost is in your inner loop, it can 
slow the whole algorithm down by a factor of 10-30 fold easy.  Graph 
algorithms are especially bad for this.  Want to get a name for yourself? 
Come up with a way to represent cyclic graphs in a purely functional way 
such that given any arbtirary node, I can find out what other nodes it has 
edges to (and what their weights are) in O(1).

Brian

FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

Hello,


is there a general overvie (paper or book), where
functional and imperative approaches to solve a problem are
compared directly?

Most often people say, imperative is faster in most of all
cases, and only in some cases FP might be faster.

If there is a paper/book about problem solving and performance,
comparing different approaches I would be happy to have a pointer
to it.

Also it would be nice to find something about how
classical imperative style, OO-style and FP-style
are solving problems, and which patterns can be done
easier in the one or the other way.

I recently had a discussion about some OO-patterns
( so called "GoF"-Book) and tried to solve some of them with
OCamls module system.
Adapter and bridge was talked about. Adapter was easy in writing a simple
wrapper.
Bridge could be done with a functor. :)


So, if there are direct translations possible, where to find
comparisons?

Another interesting theme in this respect is: If not only some patterns
were adapted to Fp, but the whole problem solving approach is different,
which patterns will be unnevcessary then, because the whole structure of
the software will be different...?!



Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Michael Wohlwend]

On Tuesday 04 October 2005 18:47, Oliver Bandel wrote:
>
> So, if there are direct translations possible, where to find
> comparisons?
>

there is a paper "Design Patterns in OCaml"  which describes various patterns:
http://people.csail.mit.edu/dnj/teaching/6898/projects/vicente-wagner.pdf

cheers,
 Michael

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Tuesday 04 October 2005 23:38, Michael Wohlwend wrote:
> there is a paper "Design Patterns in OCaml"  which describes various
> patterns:
> http://people.csail.mit.edu/dnj/teaching/6898/projects/vicente-wagner.pdf

I think I read this paper some time ago but it was interesting to read it 
again. Firstly, it gives only 3 references, doesn't appear to be complete, I 
think it is out of date and it appears to be written from the point of view 
of a dynamic typer. Secondly, I was never a fan of "design patterns".

As they say, several "design patterns" have trivial counterparts in FPLs, 
roughly: Singleton = module structure, Facade = module signature, Command = 
currying, Memento = dynamic type checking, and Strategy = HOFs.

The paper repeatedly states that modules cannot be mutually recursive. AFAIK, 
this has not been true for some time.

In the section about the "Observer" pattern, they state "a meaningless method 
call must be inserted into the code because OCaml's static checker cannot 
infer the type of the ...". Can the meaningless method not be replaced with a 
type declaration?

Perhaps the "State" pattern can be better represented by reusing polymorphic 
variants.

Overall, I'd say that the idea of design patterns is reasonable but the GOFs 
work is not relevant to OCaml - the study will need to be redone from 
scratch. I am much more interested in the automation of the factoring of code 
patterns, although I've yet to actually study it...

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

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Christopher A. Watford]

On 10/4/05, Oliver Bandel <oliver@first.in-berlin.de> wrote:
> Hello,
>
> is there a general overvie (paper or book), where
> functional and imperative approaches to solve a problem are
> compared directly?
>
> Most often people say, imperative is faster in most of all
> cases, and only in some cases FP might be faster.
>
> If there is a paper/book about problem solving and performance,
> comparing different approaches I would be happy to have a pointer
> to it.
>
> Also it would be nice to find something about how
> classical imperative style, OO-style and FP-style
> are solving problems, and which patterns can be done
> easier in the one or the other way.
>
> I recently had a discussion about some OO-patterns
> ( so called "GoF"-Book) and tried to solve some of them with
> OCamls module system.
> Adapter and bridge was talked about. Adapter was easy in writing a simple
> wrapper.
> Bridge could be done with a functor. :)
>
> So, if there are direct translations possible, where to find
> comparisons?
>
> Another interesting theme in this respect is: If not only some patterns
> were adapted to Fp, but the whole problem solving approach is different,
> which patterns will be unnevcessary then, because the whole structure of
> the software will be different...?!
>
> Ciao,
>   Oliver

Sigh, your question only begs for trolls to pop out of the corners.

It would probably be best to keep these questions off this list. Far
too often they go off into the deep end of the 'my language is better
than your language' debates. Obviously members of this list are going
to be biased towards functional languages and will probably give you
biased articles to read or biased papers. Not necessarily biased in a
bad way, just more likely to show functional languages in a good
light.

A poor place to start reading on the subject of what language is best
is The Computer Language Shootout [1]. An even worse place to start
reading is this list.

The actual performance for any program will depend largely on your
ability to program well for the language and for the specific compiler
you choose.

I would say it's obvious that some patterns are easier to *write* in a
certain language, but that hardly shows which language is *best* speed
wise. Your example shows one pattern functional languages are well
suited for, however, I'm sure an experienced C programmer could show
you an example of that pattern which is both efficient and easy to
read (I know I know people on this list may disagree).

This list is best for asking OCaml questions and is awful for asking
for what language is best for what, nobody agrees.

--
Christopher A. Watford
christopher.watford@gmail.com

[1] http://shootout.alioth.debian.org/

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Tuesday 04 October 2005 23:39, Christopher A. Watford wrote:
> This list is best for asking OCaml questions and is awful for asking
> for what language is best for what, nobody agrees.

Oliver was asking which of three programming paradigms is best under different 
circumstances. OCaml provides all three so I think this can be taken as an 
OCaml-specific question and is fine for this list.

I for one would be very interested in reading information on this. I'll check 
out the design patterns paper - thanks Michael.

My impression is that:

1. Data structure heavy code is often easier to write in a functional style. 
See the "n"th-nearest neighbour example from my book:

  http://www.ffconsultancy.com/products/ocaml_for_scientists/complete/

2. GUI code is more easily written with a stateful imperative front and often 
a functional back end.

I have yet to really exploit OCaml's OO capabilities.

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

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Oliver Bandel]

On Tue, Oct 04, 2005 at 06:39:28PM -0400, Christopher A. Watford wrote:
[...] 
> This list is best for asking OCaml questions and is awful for asking
> for what language is best for what, nobody agrees.
[...] 


I was not asking, what language is better for soimething, or best at all.
I asked for what programming style/paradigm is best used to solve
certain problems.

As OCaml provides more than one programming paradigm, for me
it's the best language I ever had programmed in (some
other features are also fine).

So the question goes in a different direction:
  How to solve problems best, if you have the possibility
  do do it in different ways.

Well, every programmer can choose it's own way, but if certain areas
are well known to do them in a certain way best, it  makes sense
to go that direction.

For example, I'm not really a fan of OO-programming, but when
programming GUI-software I think it would be the best choice,
and FP-programming lacks flexibility here (if not using
a DSL to create GUI-code, which then is separately compiled).

Ciao,
   Oliver

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Jon Harrop]

On Wednesday 05 October 2005 13:10, Oliver Bandel wrote:
> For example, I'm not really a fan of OO-programming, but when
> programming GUI-software I think it would be the best choice,
> and FP-programming lacks flexibility here (if not using
> a DSL to create GUI-code, which then is separately compiled).

I am finding ordinary FP perfectly adequate for GUI programming. My GUI 
programming may be unorthodox, however. :-)

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

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[skaller]

On Wed, 2005-10-05 at 14:10 +0200, Oliver Bandel wrote:

> For example, I'm not really a fan of OO-programming, but when
> programming GUI-software I think it would be the best choice,
> and FP-programming lacks flexibility here 

I contend that concurrent programming is best here.
However, I don't know: I have a tool (Felix) to explore
this, but haven't got around to actually trying the
one-thread/one-widget paradigm. 

The OO solution is reactive and requires you to maintain
the whole widget state without use of the stack, thereby
discarding everything that is known about block structured
and functional programming, and going back to the bad old
days of the early 70s with a flat state space, except that
the state space is partitioned into objects.

The thread based solution control inverts this paradigm,
giving you a stack and control flow for every widget,
this is *active* or algorithmic programming. So I content
it must be better, because it not only partitions the state
space as OO does, it *also* partitions the control space,
and allows you to use all the advantages of a functional
or block structured style.

Actually, in practice, I expect a mix of the solutions
will be best. The reason is: we know a LOT about
state machines. So subparts of problems which correspond
to them can easily be programmed and reasoned about,
simply because we have lots of mature theory.

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

Re: FP/IP and performance (in general) and Patterns... (Re: [Caml-list] Avoiding shared data)

[Brian Hurt]

On Tue, 4 Oct 2005, Oliver Bandel wrote:

> Most often people say, imperative is faster in most of all
> cases, and only in some cases FP might be faster.

The general argument here is that if the FP solution is faster, the 
imperitive language can just implement the FP solution.  My answer to that 
is that imperitive programming languages discourage you from thinking in 
certain ways rather strongly- while the FP solution may be faster, it's 
not "natural".

The big advantage of FP programming IMHO is not performance, but instead 
*correctness*.  With today's multi-gigahertz machines with multi-gigabytes 
of memory, performance isn't as critical as it used to be.  But 
correctness- especially automatically gaurenteed correctness on projects 
spanning hundreds of thousands of lines of code and dozens of developers 
maintained over decades of time- starts becoming critical.  I'd quite 
happily trade off 10% performance for correctness, or even 50% 
performance.

FP is a huge gain in correctness, because it allows me to *control 
mutability*.  If I pass a mutable data structure to a block of code there 
is an instant implicit contract between the caller and the callee on how 
(or wether) to modify the mutable data structure.  It doesn't matter what 
the contract is- wether it's to not modify the structure at all, to allow 
optional modification (either unlimited or only in certain ways), or to 
require certain modifications- a dependency between the two different 
peices of code exists.  And this dependency, this contract, is probably 
undocumented and always unchecked by the compiler, which means it's a 
maintaince nightmare waiting to happen.  One peice of code gets modified 
to violate the contract, perhaps even unknowingly, or perhaps due to some 
changing requirement, and untouched code thousands of lines away suddenly 
breaks.

Note that such a bidirectional dependency can be implemented in functional 
code- the called code returns a new copy of the modified structure to the 
calling code, which the calling code then adopts and uses.  But notice 
that such a bidirectional dependency is explicitly stated in the code, and 
automatically checked by the compiler.  And the calling code has the 
option of wether or not to allow the modification (or to use both the old 
and the new copy).

Java programmers are begining to tumble to this advantage- notice the 
increasing popularity of immutable objects (starting with Int and Float), 
and Java Beans.

> I recently had a discussion about some OO-patterns
> ( so called "GoF"-Book) and tried to solve some of them with
> OCamls module system.
> Adapter and bridge was talked about. Adapter was easy in writing a simple
> wrapper.
> Bridge could be done with a functor. :)

Some of the patterns are doable with modules.  Singleton, for example, is 
a classic module pattern.  Many of the patterns aren't, however.  An 
important comment here is that modules are NOT weird and broken objects. 
A better point of comparison is C++ templates, except that 95+% of the use 
of templates in C++ is to implement universal types, i.e. a C++ programmer 
writes "list<A>" where an Ocaml programmer would write "'a list".

>
> Another interesting theme in this respect is: If not only some patterns
> were adapted to Fp, but the whole problem solving approach is different,
> which patterns will be unnevcessary then, because the whole structure of
> the software will be different...?!

There are patterns in every programming idiom.  The GoF book was just 
Object Oriented patterns- but there are procedural patterns, and 
functional patterns, and logic patterns, etc.

Brian