Re: About array

Re: About array

[Damien Doligez]

>From: Anton Moscal <msk@post.tepkom.ru>

>Evaluation `f i' can cause GC call -> we must use modify function. Really
>we can check address of our fresh array after each `f i'. While this
>address remains unchanged we have no need to call `modify'. I think this
>will be good.

Wrong.  There is no guarantee that the GC will move your fresh array.
In most cases it will not because the array will already be in the
major heap.


>I made the following experiment:

[replacing Array.init with a home-brewed version]


>time became 0.97 sec (but this version will not work
>with float arrays)

Indeed, it only works with int arrays.  And the only reason it's
faster is because it's monomorphic.  All your GC-oriented "magic"
amounts to nothing (you're not avoiding the call to "modify").
In fact, with this "init" function is even faster:

    let init l (f : int -> int) =
      if l = 0 then [||] else
       let res = create l (f 0) in
       for i = 1 to pred l do
         unsafe_set res i (f i)
       done;
       res
    ;;

(i.e. the standard library's "init" with a type constraint)

-- Damien

Re: About array

[Anton Moscal]

On Tue, 12 Oct 1999, Damien Doligez wrote:

> >From: Anton Moscal <msk@post.tepkom.ru>
> 
> >Evaluation `f i' can cause GC call -> we must use modify function. Really
> >we can check address of our fresh array after each `f i'. While this
> >address remains unchanged we have no need to call `modify'. I think this
> >will be good.
> 
> Wrong.  There is no guarantee that the GC will move your fresh array.
> In most cases it will not because the array will already be in the
> major heap.

Oops, this is an error. But correct test can be easily written in C
(simply test address range)

> >I made the following experiment:
> 
> [replacing Array.init with a home-brewed version]
> 
> 
> >time became 0.97 sec (but this version will not work
> >with float arrays)
> 
> Indeed, it only works with int arrays.  And the only reason it's

I think it will be works in the current implementation with array of any
types except float (if we replace algorithm for testing for array location
in young heap on correct version). Why not? (of course this is not correct
code from point of view of the language definition)

Regards,
Anton

Re: About array

[Anton Moscal]

> On Sun, 10 Oct 1999, skaller wrote:
> > 
> > > > Assignment to array element can be very ineffictive in O'Caml due to the
> > > > following reasons:
> > > >
> > > > 1)O'Caml uses generational GC.
> 
> This is only true for array containning pointer, not array of float or integer.

This is true for array, which CAN contains pointer (i.e. for polymorphic 
type 'a array this is also true).

> 
> But this raise the following question:
> Is the function Array.init implemented to solve the GC problem mentioned above
> ?

I saw in array.ml sources and found the following implementations of
Array.init:
========================
let init l f =
  if l = 0 then [||] else
   let res = create l (f 0) in
   for i = 1 to pred l do
     unsafe_set res i (f i)
   done;
   res
=======================

I.e. answer is "No". 

Good implementation (even in assembly) is not so simple: immediately after
memory allocation we can write to array without `modify'
function call until first minor GC call. 

Evaluation `f i' can cause GC call -> we must use modify function. Really
we can check address of our fresh array after each `f i'. While this
address remains unchanged we have no need to call `modify'. I think this
will be good.

I made the following experiment:

==============================
let inc a = 
  Array.init (Array.length a) (fun i->a.(i)+1);;

let rec test (a:int array) = function
   0 -> a
 | n -> test (inc a) (n-1)
;;

test (Array.create 1000 0) 2000;;
==============================
runs 1.44 sec (on 586/133 mHz)
(with -unsafe option). `init' is exact copy of Array.init.

When I replace standard `init' function by the following code:
==============================
let init l f =
  if l = 0 then [||] else
  let res = Array.create l (f 0) in
  let addr = ((Obj.magic res):int) lsr 1 in
  let res' = ((Obj.magic res):(int array))
in
    for i = 1 to pred l do
      let x = f i in
      if addr = ((Obj.magic res):int) lsr 1
then
        Array.unsafe_set res' i x
      else
        Array.unsafe_set res i x
    done;
  res
==============================
time became 0.97 sec (but this version will not work
with float arrays)

Regards,
Anton Moscal