[Caml-list] interesting array efficiency observations

[Caml-list] interesting array efficiency observations

[briand]

I was investigating the use of 1-D bigarray's vs Array and noticed
 that the 1-D bigarray using c_layout seems to be slower than Array.

Is this an expected result ?

Thanks


Brian

------------------------------------------------------------

let n = 10000 in
let a = Array.create n 2. in
  for i = 0 to n-1 do
    for j = 0 to n-1 do
      a.(j) <- sqrt(a.(j) *. a.(j));
    done;
  done;

------------------------------------------------------------

(* #load "bigarray.cma";;*)

(* test file for big arrays. *)

(* #load "bigarray.cma";; *)

let n = 10000 in
let a = Bigarray.Array1.create Bigarray.float64 Bigarray.c_layout n in

  for i = 0 to n-1 do
    for j =0 to n-1 do
      a.{j} <- sqrt(a.{j} *. a.{j});
    done
  done
;;






-------------------
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] interesting array efficiency observations

[Yamagata Yoriyuki]

From: briand@aracnet.com
Subject: [Caml-list] interesting array efficiency observations
Date: Sat, 8 May 2004 11:13:09 -0700

> I was investigating the use of 1-D bigarray's vs Array and noticed
>  that the 1-D bigarray using c_layout seems to be slower than Array.
> 
> Is this an expected result ?

Yes, it is expected, since a.{j} expands a call of a C function, while
a.(j) expands inlined assembly codes.

--
Yamagata Yoriyuki

-------------------
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] interesting array efficiency observations

[Olivier Grisel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Yamagata Yoriyuki a écrit :
| Yes, it is expected, since a.{j} expands a call of a C function, while
| a.(j) expands inlined assembly codes.

Hello,

I have two other questions about Bigarray :
- - Bigarray seems to provide a relatively low level interface to general
multi-dimensional numerical arrays in OCaml. Do you know about a helper
library that provide higher level numerical functions such as those
provided in the Python Numeric package ? What I miss most are Ufuncs
(universal functions defined here :
http://www.pfdubois.com/numpy/html2/numpy-7.html#30906 ).
- - what is the difference of performance between Bigarray based
computation and Python Numeric based computation ?

Thanks for any hint !

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFAnWLzTsBRE+WZ2SARAu1RAKC/Fz1cSF21x3IgnRyFh1Cfo/VCDgCeLNYk
bqJDpuibGGn1ATYN739pWVk=
=a5tv
-----END PGP SIGNATURE-----

-------------------
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] interesting array efficiency observations

[Christophe TROESTLER]

On Sun, 09 May 2004, Yamagata Yoriyuki <yoriyuki@mbg.ocn.ne.jp> wrote:
> 
> From: briand@aracnet.com
>
> > I was investigating the use of 1-D bigarray's vs Array and noticed
> >  that the 1-D bigarray using c_layout seems to be slower than Array.
> 
> Yes, it is expected, since a.{j} expands a call of a C function, while
> a.(j) expands inlined assembly codes.

Is it?  Ocamlopt does inline the call when the bigarray type is fully
known, doesn't it.

ChriS

-------------------
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] interesting array efficiency observations

[Yamagata Yoriyuki]

From: Christophe TROESTLER <Christophe.Troestler@umh.ac.be>
Subject: Re: [Caml-list] interesting array efficiency observations
Date: Sun, 09 May 2004 02:25:35 +0200 (CEST)

> On Sun, 09 May 2004, Yamagata Yoriyuki <yoriyuki@mbg.ocn.ne.jp> wrote:
> > 
> > From: briand@aracnet.com
> >
> > > I was investigating the use of 1-D bigarray's vs Array and noticed
> > >  that the 1-D bigarray using c_layout seems to be slower than Array.
> > 
> > Yes, it is expected, since a.{j} expands a call of a C function, while
> > a.(j) expands inlined assembly codes.
> 
> Is it?  Ocamlopt does inline the call when the bigarray type is fully
> known, doesn't it.

Ah...  You are right.  Thanks.

$ cat test.ml
open Bigarray
type t = (int32, int32_elt, c_layout) Array1.t
let get (a:t) i = a.{i}

$ cat test.s
(... snip ...)
Test__get_184:
.L100:
        movl    %eax, %edx
.L101:  movl    young_ptr, %eax
        subl    $12, %eax
        movl    %eax, young_ptr
        cmpl    young_limit, %eax
        jb      .L102
        leal    4(%eax), %eax
        movl    $2303, -4(%eax)
        movl    $int32_ops, (%eax)
        sarl    $1, %ebx
        movl    20(%edx), %ecx
        cmpl    %ebx, %ecx
        jbe     .L104
        movl    4(%edx), %ecx
        movl    (%ecx, %ebx, 4), %ebx
        movl    %ebx, 4(%eax)
        ret
.L102:  call    caml_call_gc
.L103:  jmp     .L101
.L104:  call    caml_array_bound_error
        .text
        .align  16
        .globl  Test__entry
        .type   Test__entry,@function

-------------------
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] interesting array efficiency observations

[Xavier Leroy]

> I was investigating the use of 1-D bigarray's vs Array and noticed
>  that the 1-D bigarray using c_layout seems to be slower than Array.
> Is this an expected result ?

Yes.  When compiling to bytecode (or at the top-level), all bigarray
accesses go through a generic access function that is polymorphic over
the number of dimensions, the array type and the array layout, and is
therefore somewhat expensive.  

When compiling to native code, efficient inline code is generated
instead for accesses to 1, 2 and 3-dimensional arrays, provided the
full type of the bigarray (including layout and element type) is known.
In this case, the inline access code is almost as efficient as that
for accessing a regular array: just one extra indirection.

- 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

Re: [Caml-list] interesting array efficiency observations

[malc]

On Sat, 8 May 2004 briand@aracnet.com wrote:

>
> I was investigating the use of 1-D bigarray's vs Array and noticed
>  that the 1-D bigarray using c_layout seems to be slower than Array.
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=ISO-8859-1&threadm=fa.hj2u7jv.t1ms25%40ifi.uio.no&rnum=1&prev=/groups%3Fq%3Dfa.caml%2Bbigarray%2Bmalc%26hl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DISO-8859-1%26selm%3Dfa.hj2u7jv.t1ms25%2540ifi.uio.no%26rnum%3D1

-- 
mailto:malc@pulsesoft.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] interesting array efficiency observations

[briand]

Perfect.

Thanks for the link.

However, I have a question :-)

>From the link:

   let f a x y = 1 + a.{x,y}

has a polymorphic type (int, 'a, 'b) Bigarray.Array2.t -> int -> int -> int
and compiles down to a library function call.  However,

    open Bigarray
    let f (a : (int, int_elt, c_layout) Array2.t) x y = 1 + a.{x,y}

is monomorphic and will be compiled much more efficiently by ocamlopt.

So what if I have declared a variable, i.e.

let the_a = Bigarray.Array2.create Bigarray.float64 Bigarray.c_layout 5 5;;

and now I invoke f 

  f the_a 1 2

Why would the_a be treated polymorphically ??

the_a is very clearly defined as a very specific Bigarray and so the
compiler will know this in the call to f, and will do the correct
thing, right ?

Isn't the type annotation in the function redundant in such a case ?

Thanks


Brian

>>>>> "malc" == malc  <malc@pulsesoft.com> writes:

  malc> On Sat, 8 May 2004 briand@aracnet.com wrote:
  >>  I was investigating the use of 1-D bigarray's vs Array and
  >> noticed that the 1-D bigarray using c_layout seems to be slower
  >> than Array.

  malc> http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=ISO-8859-1&threadm=fa.hj2u7jv.t1ms25%40ifi.uio.no&rnum=1&prev=/groups%3Fq%3Dfa.caml%2Bbigarray%2Bmalc%26hl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DISO-8859-1%26selm%3Dfa.hj2u7jv.t1ms25%2540ifi.uio.no%26rnum%3D1

  malc> -- mailto:malc@pulsesoft.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] interesting array efficiency observations

[Christophe TROESTLER]

On Mon, 10 May 2004, briand@aracnet.com wrote:
> 
>    let f a x y = 1 + a.{x,y}
> 
> has a polymorphic type (int, 'a, 'b) Bigarray.Array2.t -> int -> int -> int
> and compiles down to a library function call.
>
> let the_a = Bigarray.Array2.create Bigarray.float64 Bigarray.c_layout 5 5;;
>
>   f the_a 1 2
> 
> Why would the_a be treated polymorphically ??

The function [f] _could_ be specialized when applied to a monomorphic
type.  However, when do you do that: when you define the function (but
then you end up compiling [f] for all combinations of 'a and 'b...) or
when the function is applied (a kind of function inlining)?

The first solution is not that nice (unnecessary increase of code
size) but I have a question for the second:

    Is it possible that [f] be inlined and then specialized or the
    compiler does not do that?  This question also holds for,
    e.g. [min (f x) (g x)], may [min] be inlined and then specialized
    if it is known for example that [f x] and [g x] are [int]?

Cheers,
ChriS

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