[Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Brian Hurt]

Hello, all.  I'm new to Ocaml and have what is probably a frequently asked 
question.  It's actually one of the faqs which caused me question:

From:
http://caml.inria.fr/FAQ/FAQ_EXPERT-eng.html#couts

I get that the cost of list concatenation is proportional to the length of 
the first list.  So (elem :: list) is O(1) no matter what the length of 
list is.  But (list :: elem) is O(n), with n being the length of the list.

Why doesn't Ocaml keep a pointer to the last element of the list, as well 
as the first element?  This would make all list concatenation (in 
situations where you don't have to duplicate a list) an O(1) operation.  
At the cost of increasing the size of a list object.

An example of where this would come in usefull.  Consider the merge 
portion of a merge sort (yes, I know I'm duplicating code that is in the 
List module- I'm doing it so that I can learn the language.  Plus, here we 
all understand the problem).  The current implementation I have (probably 
chock full of inefficiencies) is:

let merge a b =
    (* merge sorted lists a and b into one big list *)

    let reverse_list lst =
        (* again, duplicating List module functionality for clarity *)
        let rec reverse_list_int lst accum =
            match lst with
                [] -> accum
                | x :: [] -> (x :: accum)
                | x :: tail -> reverse_list_int tail (x :: accum)
        in
            reverse_list_int lst []

    in
        let rec merge_int a b accum =
            match (a, b) with
                ( [], [] ) -> accum
                | ( ahead :: [], [] ) -> (ahead :: accum)
                | ( ahead :: atail, [] ) -> 
                                    merge_int atail b (ahead :: accum)
                | ( [] , bhead :: [] ) -> (bhead :: accum)
                | ( [] , bhead :: btail ) -> 
                                    merge_int a btail (bhead :: accum)
                | ( ahead :: atail, bhead :: btail) ->
                    if (ahead < bhead) then 
                        (* should replace this test with a call to cmp *)
                        merge_int atail b (ahead :: accum)
                    else
                        merge_int a btail (bhead :: accum)
        in
            reverse_list (merge_int a b [])
;;

Note that I've had to add a whole second function (reverse_list) which is 
O(n) just to allow me to prepend instead of append to the accumulation 
list.  The natural way to do this would be:

let merge a b =
    (* merge sorted lists a and b into one big list *)

    let rec merge_int a b accum =
        match (a, b) with
            ( [], [] ) -> accum
            | ( ahead :: [], [] ) -> (accum :: ahead)
            | ( ahead :: atail, [] ) -> 
                                merge_int atail b (accum :: ahead)
            | ( [] , bhead :: [] ) -> (accum :: bhead)
            | ( [] , bhead :: btail ) -> 
                                merge_int a btail (accum :: bhead)
            | ( ahead :: atail, bhead :: btail) ->
                if (ahead < bhead) then 
                    (* should replace this test with a call to cmp *)
                    merge_int atail b (accum :: ahead)
                else
                    merge_int a btail (accum :: bhead)
    in
        merge_int a b []
;;

Were appends O(1) instead of O(N), the second version of this code would 
be signifigantly faster, as I don't have to do the O(N) reversal of the 
list at the end.  However, since appends aren't O(1), the second version 
of the code is O(N^2)- diaster!  

My first inclination would be to make all lists include a tail pointer.  
Then, at a later point, the compiler could detect those lists which don't 
need the tail pointer, and switch back to the old style lists.

Unless there's something I'm missing.  I've only been playing with this 
language for ~2 days or so.  I am definately still a newbie.  Pointers 
and/or explanations would be greatly appreciated.

Brian



-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Noel Welsh]

O'Caml's heritage is from the functional world, so
side-effects are discouraged.  Maintaining a tail
pointer requires side-effects.  

For more insight consider that a list is defined by
its recursive definition:

List 'a :=  Cons 'a * List
        |   Null

A list is a cons cell containing an element and the
rest of the list, or null, which terminates the list. 
Now tell me which cons cell is the head, and so should
maintain the tail pointer. Welcome to a world of pain!

HTH,
Noel


__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com
-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Oleg]

On Wednesday 25 September 2002 11:33 am, Brian Hurt wrote:
> I get that the cost of list concatenation is proportional to the length of
> the first list.  So (elem :: list) is O(1) no matter what the length of
> list is.  But (list :: elem) is O(n), with n being the length of the list.
>
> Why doesn't Ocaml keep a pointer to the last element of the list, as well
> as the first element?  This would make all list concatenation (in
> situations where you don't have to duplicate a list) an O(1) operation.  
> At the cost of increasing the size of a list object.

let a = [1; 2; 3; 4; 5; 6];;
let b = 0 :: a;;

the elements of "a" are _shared_. Now your suggestion regarding "efficient 
append" can not be used to append anything to one list, but not the other.

HTH
Oleg
-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Markus Mottl]

On Wed, 25 Sep 2002, Brian Hurt wrote:
> I get that the cost of list concatenation is proportional to the length of 
> the first list.  So (elem :: list) is O(1) no matter what the length of 
> list is.  But (list :: elem) is O(n), with n being the length of the list.

You probably mean (list @ [elem]).

> Why doesn't Ocaml keep a pointer to the last element of the list,
> as well as the first element?

Because standard lists are purely functional, i.e. you can't just
overwrite some pointer to append an element. If there are several lists
that share a common sublist, such an operation would change both lists.

E.g.:

  let l = [1; 2; 3] in
  let l1 = 0 :: l in
  let l2 = 42 :: l in
  l @ [4]

If the last operation overwrote anything in "l", this would also change
l1 and l2, thus destroying referential transparency: list variables
couldn't be used for straightforward equational reasoning anymore,
which is important if you want to e.g. proof list algorithms correct.

As you noted, keeping pointers to the previous element also makes
list nodes larger and thus more expensive both in terms of time and
space. Why have this by default if lists are most often not used in ways
that require efficiency with such operations?

If you want to have mutable lists, it's not difficult to implement them.
But be warned: you might be surprised to discover that standard lists
most often perform better in not too extreme cases.

In case you want to learn more about purely functional datastructures,
you will definitely want to read Chris Okasaki's book "Purely Functional
Data Structures", which is published by Cambridge University Press (1998).

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Brian Hurt]

Thanks to everyone for answering my question.  I think the light is 
starting to glimmer, however dim :-).

I think I'm asking the wrong question.  Is there any circumstances where 
Ocaml will reuse the cells from one list to make another list?

Consider the following Ocaml code:

    let dup_list lst =
        let rec reverse_list l accum =
            match l with
                [] -> accum
                | head :: tail -> reverse_list tail (head :: accum)
        in
            reverse_list (reverse_list lst)
    ;;

Ok, the first time through reverse_list the compiler has to allocate a 
whole new list, including a whole new set of list cells, for the 
accumlation list.  This is because the code doesn't dare modify lst.  But 
the second time reverse_list is called, it's obvious that l is the list 
allocated the first time through, and it's garbage as soon as the call 
completes.  In fact, each cell of the list is garbage after it's been 
prepended to accum.  So why not reuse the cells from l to form the accum?  
Yes, I know this violates the immutability of l.  But it seems to me that, 
with the exception of garbage creation rates, the two are identical.

Phrased this way, I start wondering how much of an optimization this
actually would be.  Ocaml has a copying garbage collector, which means
allocating new objects is cheap.  Especially if what you're doing is
duplicating a recently allocated, soon to be garbage list- like my example
above.  

Of course, appending elements to a list would only work if it was
optimized as such a "modifiable list" in the optimizer.  Which strikes me
as a dangerous proposition.  The ability to write algorithms which are
O(N) if you compile with the right optimizations, and O(N^2) if you don't
(or if you make some subtle change to the code and all of a sudden the
optimizer can modify the list anymore) strikes me as being sub-optimal.

Heh.  One of the dangers of Ocaml is that it makes the algorithm clear 
enough that it encourages you to over-optimize your algorithms in the same 
way that C encourages you to cycle count and over-optimize your 
implementations.

Brian

On Wed, 25 Sep 2002, Markus Mottl wrote:

> On Wed, 25 Sep 2002, Brian Hurt wrote:
> > I get that the cost of list concatenation is proportional to the length of 
> > the first list.  So (elem :: list) is O(1) no matter what the length of 
> > list is.  But (list :: elem) is O(n), with n being the length of the list.
> 
> You probably mean (list @ [elem]).
> 
> > Why doesn't Ocaml keep a pointer to the last element of the list,
> > as well as the first element?
> 
> Because standard lists are purely functional, i.e. you can't just
> overwrite some pointer to append an element. If there are several lists
> that share a common sublist, such an operation would change both lists.
> 
> E.g.:
> 
>   let l = [1; 2; 3] in
>   let l1 = 0 :: l in
>   let l2 = 42 :: l in
>   l @ [4]
> 
> If the last operation overwrote anything in "l", this would also change
> l1 and l2, thus destroying referential transparency: list variables
> couldn't be used for straightforward equational reasoning anymore,
> which is important if you want to e.g. proof list algorithms correct.
> 
> As you noted, keeping pointers to the previous element also makes
> list nodes larger and thus more expensive both in terms of time and
> space. Why have this by default if lists are most often not used in ways
> that require efficiency with such operations?
> 
> If you want to have mutable lists, it's not difficult to implement them.
> But be warned: you might be surprised to discover that standard lists
> most often perform better in not too extreme cases.
> 
> In case you want to learn more about purely functional datastructures,
> you will definitely want to read Chris Okasaki's book "Purely Functional
> Data Structures", which is published by Cambridge University Press (1998).
> 
> Regards,
> Markus Mottl
> 
> 

-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Markus Mottl]

On Wed, 25 Sep 2002, Brian Hurt wrote:
> I think I'm asking the wrong question.  Is there any circumstances where 
> Ocaml will reuse the cells from one list to make another list?
> 
> Consider the following Ocaml code:
> 
>     let dup_list lst =
>         let rec reverse_list l accum =
>             match l with
>                 [] -> accum
>                 | head :: tail -> reverse_list tail (head :: accum)
>         in
>             reverse_list (reverse_list lst)
>     ;;

Thanks to referential transparency of purely functional code it is easy
to prove by induction that twice reversing a list will yield the original
list again (home exercise :-).

However, you shouldn't expect that current compiler technology is
strong enough to exploit such equivalences even though some automated
theorem provers manage to prove them without human help. Most real world
high-level optimizers already struggle with doing partial evaluation
correctly and efficiently, not even to mention trickier stuff like above.

> Ok, the first time through reverse_list the compiler has to allocate a 
> whole new list, including a whole new set of list cells, for the 
> accumlation list.  This is because the code doesn't dare modify lst.  But 
> the second time reverse_list is called, it's obvious that l is the list 
> allocated the first time through, and it's garbage as soon as the call 
> completes.  In fact, each cell of the list is garbage after it's been 
> prepended to accum.  So why not reuse the cells from l to form the accum?  
> Yes, I know this violates the immutability of l.  But it seems to me that, 
> with the exception of garbage creation rates, the two are identical.

Yes, the two are indeed equivalent. And since our lists are purely
functional, there is no danger of overwriting them (it) during reuse. The
only noticable computational effect is that things will run faster after
your transformation.

> Phrased this way, I start wondering how much of an optimization this
> actually would be.

It's pretty demanding! Search space size for finding suitable high-level
transformations usually grows exponentially with the number of definitions
to consider. There are, however, certain classes of transformations that
can be found and applied somewhat efficiently. The Haskell-compiler
implements some of them (e.g. deforestation, which concerns the
elimination of certain intermediate datastructures).

One question is an economic one: where do compiler writers invest
their time? As the OCaml-compiler shows, you can gain really a lot by
forgetting about high-level optimizations (it doesn't even perform
common subexpression elimination) and by writing good backends
for machine-code generation instead. The problem is that the "easy"
high-level transformation usually do not give you so much speedup,
whereas the tricky ones (some can even yield super-exponential speedups)
boost compilation times by some orders of magnitude. Few developers want
to spend their life time waiting for their compilers to finish...

In case you want to learn more about automating functional program
transformations, you might find a hopefully somewhat understandable
introduction in my MSc-thesis (just skip the mistakes ;-)

  http://www.oefai.at/~markus/msc_thesis

> Heh.  One of the dangers of Ocaml is that it makes the algorithm clear
> enough that it encourages you to over-optimize your algorithms in
> the same way that C encourages you to cycle count and over-optimize
> your implementations.

This may happen at times. It is generally a good idea to just write the
simplest implementation you can imagine, profile your program and then
optimize it. Very often the simplest algorithm is also among the best
so it seldom pays to start optimizing before your program actually works.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Florian Hars]

Brian Hurt wrote:
> Consider the following Ocaml code:
> 
>     let dup_list lst =
>         let rec reverse_list l accum =
>             match l with
>                 [] -> accum
>                 | head :: tail -> reverse_list tail (head :: accum)
>         in
>             reverse_list (reverse_list lst)

This should probably be reverse_list (reverse_list lst []) []

>     ;;
[...]
> So why not reuse the cells from l to form the accum?  

To optimize reverse_list in the way you propose, the compiler would have to be 
smart enough to see that reverse_list is only ever called twice, so as to 
return (a list that is equivalent to) the original list. (If reverse_list were 
called in any other context, the optimazition would be illegal, since it 
destroys the original list). But then the compiler would know enough to perform 
the correct optimization of your code to

let dup_list lst = lst

and then eliminate all calls to dup_list entirely. But since the same effect 
can be had by not introducing the function in the first place, it would be a 
royal waste of ressources to make the compiler detect this case.

> Yes, I know this violates the immutability of l.  But it seems to me that, 
> with the exception of garbage creation rates, the two are identical.

Yes, of course. Your dup_list is one of the most expensive no-ops you can 
perform on a list.

The point is: unlike in languages of the Fortran heritage (C, Java...), 
variables in functional languges designate values and are not names for 
physical storage locations. To add to the confusion, ocaml blurs this by 
supporting both physical (==, !=) and value (=, <>) comparisions:

$ ledit ocaml
         Objective Caml version 3.06

# let dup_list lst =
   let rec reverse_list l accum =
     match l with
           [] -> accum
       | head :: tail -> reverse_list tail (head :: accum)
     in
     reverse_list (reverse_list lst []) []
     ;;
val dup_list : 'a list -> 'a list = <fun>
# let l = [1; 2; 3];;
val l : int list = [1; 2; 3]
# let l' = dup_list l;;
val l' : int list = [1; 2; 3]
# l = l';;
- : bool = true
# l == l';;
- : bool = false

This last inequality is the *only* difference between using

let l' = dup_list l

and using

let l' = l

and it would disappear if your optimazation were performed (since then dup_list 
would just return its argument restored to its original state). So there is no 
reason not to use the second, simpler and more efficient version.

Even with your dup_list, the contents of the two list are physically the same:

# let m = [ref 1; ref 2; ref 3];;
val m : int ref list = [{contents = 1}; {contents = 2}; {contents = 3}]
# let m' = dup_list m;;
val m' : int ref list = [{contents = 1}; {contents = 2}; {contents = 3}]
# m == m';;
- : bool = false
# List.hd m == List.hd m';;
- : bool = true
# List.hd m := 42;;
- : unit = ()
# m';;
- : int ref list = [{contents = 42}; {contents = 2}; {contents = 3}]

Yours, Florian.

-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Probably FAQ: Why is list-append (list :: elem) so expensive?

[Kontra, Gergely]

>I get that the cost of list concatenation is proportional to the length of 
>the first list.  So (elem :: list) is O(1) no matter what the length of 
>list is.  But (list :: elem) is O(n), with n being the length of the list.
[...]
>An example of where this would come in usefull.  Consider the merge 
>portion of a merge sort (yes, I know I'm duplicating code that is in the 
>List module- I'm doing it so that I can learn the language.  Plus, here we 
>all understand the problem).  The current implementation I have (probably 
>chock full of inefficiencies) is:

If you want to build up a list from the beginning to the tail, just
append the new elements before the list, and then reverse the list.

(* Sorry, new to ocaml, my syntax may be SML-ish *)

(* tail-recursive function to reverse a list *)
let reverse List =
	(* returns a list like: (reverse L2) @ L1 *)
	let rec revapp L1 L2 =
		match L2 with
		| []     -> L1
		| hd::tl -> revapp hd::L1 tl
	in revapp [] List

Since reversing is not so slow, this might be, what you want.

Gergő

+-[Kontra, Gergely @ Budapest University of Technology and Economics]-+
|         Email: kgergely@mcl.hu,  kgergely@turul.eet.bme.hu          |
|  URL:   turul.eet.bme.hu/~kgergely    Mobile: (+36 20) 356 9656     |
+-------"Olyan langesz vagyok, hogy poroltoval kellene jarnom!"-------+
.
Magyar php mirror es magyar php dokumentacio: http://hu.php.net

-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners