[Caml-list] Objects poor performance

[Caml-list] Objects poor performance

[Cezary Kaliszyk]

[-- Attachment #1.1: Type: text/plain, Size: 544 bytes --]

I tried to implement a simple double-linked list with constant time insertion
and removal. I tried just iterating over such a list with both object and
structure implementation. And these are the effects:

             Time:
Structures:  2.503s
Objects:    27.027s

The implementations are the same so why are objects that slow? I include
the tests if someone wishes to test oneself or see if anything can be
done faster.

PS. The size of stripped executable is also 2*larger with objects.
But that's not such a big problem.
-- 

[-- Attachment #1.2: object.ml --]
[-- Type: text/plain, Size: 940 bytes --]

class ['a] lst data = 
  object
    val mutable data = (data : 'a)
    val mutable prev = ((Obj.magic ()) : 'a lst)
    val mutable next = ((Obj.magic ()) : 'a lst)
    method add new_data = 
      new lst new_data in
      new_elem#set_next next;
      new_elem#set_prev (next#get_prev);
      next#set_prev new_elem;
      next <- new_elem
    method get_prev = prev
    method get_next = next
    method set_prev elem = prev <- elem
    method set_next elem = next <- elem
    method get = data
  end
;;
 
let l = new lst (0, 0);;
l#set_next l;;
l#set_prev l;;


let rec adder cnt =
  l#add (cnt, 0);
  if cnt > 0 then adder (cnt - 1)
in adder 1000;;

let rec iterator a cnt alst =
  if cnt = 0 then a else
  let (i, _) = alst#get in
  iterator (a + i) (cnt - 1) alst#get_next
;;
    
let rec test cnt =
  ignore (iterator 0 1000 l);
  if cnt = 0 then () else test (cnt - 1)
;;
  
test 1000000;;

[-- Attachment #1.3: struct.ml --]
[-- Type: text/plain, Size: 826 bytes --]

type 'a ts = {
    mutable data : 'a;
    mutable prev : 'a ts;
    mutable next : 'a ts;
  };;
      
let rec single elem =
  let ret = {
    data = elem; 
    next = Obj.magic 0;
    prev = Obj.magic 0;
  } in
  ret.next <- ret;
  ret.prev <- ret;
  ret
;;

let rec add elem ({next = n} as lst) =
  let newnext = {
    data = elem;
    prev = lst;
    next = n
  } in
  n.prev <- newnext;
  lst.next <- newnext
;;

let l = single (0, 0);;
    
let rec adder cnt =
  add (cnt, 0) l;
  if cnt > 0 then adder (cnt - 1)
in adder 1000;;
    
let rec iterator a cnt alst =
  if cnt = 0 then a else
  let (i, _) = alst.data in
  iterator (a + i) (cnt - 1) alst.next
;;
    
let rec test cnt =
  ignore (iterator 0 1000 l);
  if cnt = 0 then () else test (cnt - 1)
;;

test 1000000;;


[-- Attachment #2: Type: application/pgp-signature, Size: 254 bytes --]

Re: [Caml-list] Objects poor performance

[Michal Moskal]

On Tue, Nov 19, 2002 at 07:38:57PM +0100, Cezary Kaliszyk wrote:
> let rec single elem =
>   let ret = {
>     data = elem; 
>     next = Obj.magic 0;
>     prev = Obj.magic 0;
>   } in
>   ret.next <- ret;
>   ret.prev <- ret;
>   ret
> ;;

let rec ret = {
data = elem;
next = ret;
prev = ret;
} in ret
...

But I guess this has not much performance impact ;-)

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h
-------------------
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] Objects poor performance

[Xavier Leroy]

> I tried to implement a simple double-linked list with constant time
> insertion and removal. I tried just iterating over such a list with
> both object and structure implementation. And these are the effects:
> 
>              Time:
> Structures:  2.503s
> Objects:    27.027s
> 
> The implementations are the same so why are objects that slow?

Two reasons:

1- With the object encoding, accesses to the "prev" and "next" field
of each list cell goes through a method invocation, while in the
function encoding these are just direct accesses to record fields
(much cheaper).

2- Method invocations are always compiled down to an indirect
(computed) function call, while most function calls are optimized to
direct (static) function calls. or even inlined.  Indirect calls are
about 10 times more expensive than direct calls on modern processors.
For more info on this topic, see my PLDI'98 tutorial:

   http://pauillac.inria.fr/~xleroy/talks/tutorial-pldi98.ps.gz

- Xavier Leroy
-------------------
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