[Caml-list] Looking for a real array

[Caml-list] Looking for a real array

[Eray Ozkural]

I knew this all along but looks like I neglected that an array is in fact an 
array of pointers rather than an array of contiguous storage blocks in 
memory. Is there a way to get real FORTRAN/C arrays for people who might not 
want this extra level of indirection?

val make : int -> 'a -> 'a array
 Array.make n x returns a fresh array of length n, initialized with x. All the 
elements of this new array are initially physically equal to x (in the sense 
of the == predicate). Consequently, if x is mutable, it is shared among all 
elements of the array, and modifying x through one of the array entries will 
modify all other entries at the same time. 

Regards,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
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] Looking for a real array

[Brian Hurt]

On Mon, 28 Apr 2003, Eray Ozkural wrote:

> I knew this all along but looks like I neglected that an array is in fact an 
> array of pointers rather than an array of contiguous storage blocks in 
> memory. Is there a way to get real FORTRAN/C arrays for people who might not 
> want this extra level of indirection?
> 
> val make : int -> 'a -> 'a array
>  Array.make n x returns a fresh array of length n, initialized with x. All the 
> elements of this new array are initially physically equal to x (in the sense 
> of the == predicate). Consequently, if x is mutable, it is shared among all 
> elements of the array, and modifying x through one of the array entries will 
> modify all other entries at the same time. 

If this is a problem, you might want to use Array.init instead.  Instead 
of doing (for instance):
let r = ref 0.0 in Array.make n r
which returns an array of float references, initially all r, so changing 
one changes all of them, instead do:
Array.init n (fun _ -> ref 0.0)
which creates a new reference for every element.

Having a reference in addition to the data structure is a little bit of 
overhead.  But optimization is a tricky thing- often times, what you gain 
in the straights you lose in the curves.  For example, what happens when 
some other peice of code keeps a pointer to a single element of the array, 
when the pointer to the rest of the array- and all the other elements- are 
gone?  In ocaml, the array and all the other elements become garbage, and 
the last, lone object that is not garbage stays around.  Also, copying 
becomes a big issue in my experience.

Personally, I find one extra level of dereferencing isn't that big of a 
deal.  If you're too the point where it is a big deal, you are already 
talking about hand-tuned assembly language.  My advice: stop worrying 
about minutia.  Permature optimization is the root of all evil.

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] Looking for a real array

[Eray Ozkural]

Hi Brian,

On Monday 28 April 2003 19:40, Brian Hurt wrote:
> Having a reference in addition to the data structure is a little bit of
> overhead.  But optimization is a tricky thing- often times, what you gain
> in the straights you lose in the curves.  For example, what happens when
> some other peice of code keeps a pointer to a single element of the array,
> when the pointer to the rest of the array- and all the other elements- are
> gone?  In ocaml, the array and all the other elements become garbage, and
> the last, lone object that is not garbage stays around.  Also, copying
> becomes a big issue in my experience.
>

I will happily agree that asymptotic complexity is more important than 
constant gains and that there are other book-keeping tasks that might make 
the programming more complex than necessary.

> Personally, I find one extra level of dereferencing isn't that big of a
> deal.  If you're too the point where it is a big deal, you are already
> talking about hand-tuned assembly language.  My advice: stop worrying
> about minutia.  Permature optimization is the root of all evil.

Yes, I'm coming from the land of evil optimizers. :) I spent a large portion 
of my youth hand-optimizing 68k assembly! I was really shocked when I found 
out about 2 years ago that some FORTRAN compilers could do the tricks I spent 
hours on the Amiga to perform!

To be serious, I was concerned about this fact because I have, if you recall, 
started writing a graph library. Unfortunately, it makes a big deal of space 
and time difference when I use pointers to integers rather than simply 
integers! In fact, my advisor would shoot me if I did the former. Space loss 
is evident. But the worse case comes from losing "cache coherence", a fine 
point that can change the speed 5 fold sometimes!!!!! Memory hierarchy is 
like magic!

Thanks to Brian Hurt and David Gurr who wrote off-the list that bigarrays 
would work for me. It looks like Bigarrays can do unboxed arrays of integers.

Cheers,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
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] Looking for a real array

[Brian Hurt]

On Mon, 28 Apr 2003, Eray Ozkural wrote:
> 
> Yes, I'm coming from the land of evil optimizers. :) I spent a large portion 
> of my youth hand-optimizing 68k assembly! I was really shocked when I found 
> out about 2 years ago that some FORTRAN compilers could do the tricks I spent 
> hours on the Amiga to perform!

Wow.  I was stuck on the x86.  I've never quite gotten over Amiga envy. 
 Not that I haven't spent some time hand-optimizing x86 code, now and
again. :-)

> 
> To be serious, I was concerned about this fact because I have, if you recall, 
> started writing a graph library. Unfortunately, it makes a big deal of space 
> and time difference when I use pointers to integers rather than simply 
> integers! In fact, my advisor would shoot me if I did the former. Space loss 
> is evident. But the worse case comes from losing "cache coherence", a fine 
> point that can change the speed 5 fold sometimes!!!!! Memory hierarchy is 
> like magic!

I may be confused, but I thought integers were unboxed in arrays (not 
BigArrays, just arrays).  Unless you mean references to integers?

> Thanks to Brian Hurt and David Gurr who wrote off-the list that
> bigarrays would work for me. It looks like Bigarrays can do unboxed
> arrays of integers.

Different Brian, I think.

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] Looking for a real array

[Eray Ozkural]

On Monday 28 April 2003 21:43, Brian Hurt wrote:
> I may be confused, but I thought integers were unboxed in arrays (not
> BigArrays, just arrays).  Unless you mean references to integers?
>

Okay, I might be a little confused, forgive me. I thought, implementation 
wise, when I say
let a = [| 6, 3, 5, 7, 8 |]
it's implemented by ocaml as
int** a;
in C speak.

Right or wrong? (Fearing that I might be demoted to beginner status now :P )

>
> Different Brian, I think.
>

Ah, no, you did reply all off-list ;)

Cheers,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
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] Looking for a real array

[Brian Hurt]

On Mon, 28 Apr 2003, Eray Ozkural wrote:

> On Monday 28 April 2003 21:43, Brian Hurt wrote:
> > I may be confused, but I thought integers were unboxed in arrays (not
> > BigArrays, just arrays).  Unless you mean references to integers?
> >
> 
> Okay, I might be a little confused, forgive me. I thought, implementation 
> wise, when I say
> let a = [| 6, 3, 5, 7, 8 |]

Start with, I think you meant [| 6; 3; 5; 7; 8 |].  Notice the semicolons.  
I say this only because I've been caught on this several times before :-}.

> it's implemented by ocaml as
> int** a;
> in C speak.

I thought ints were always unboxed.  They fit into a word.  That's why 
they're 31 bits, not 32 bits- the low bit is a tag so the GC can 
differentiate pointers from ints.

Hopefully someone who can speak authoritiatively will speak up.

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] Looking for a real array

[Eray Ozkural]

On Monday 28 April 2003 22:05, Brian Hurt wrote:
> > Okay, I might be a little confused, forgive me. I thought, implementation
> > wise, when I say
> > let a = [| 6, 3, 5, 7, 8 |]
>
> Start with, I think you meant [| 6; 3; 5; 7; 8 |].  Notice the semicolons.
> I say this only because I've been caught on this several times before :-}.

hush. it will become evident that I used haskell too much :P

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
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] Looking for a real array

[Falk Hueffner]

Eray Ozkural <exa@kablonet.com.tr> writes:

> Okay, I might be a little confused, forgive me. I thought, implementation 
> wise, when I say
> let a = [| 6, 3, 5, 7, 8 |]
> it's implemented by ocaml as
> int** a;
> in C speak.
> 
> Right or wrong? (Fearing that I might be demoted to beginner status
> now :P )

Wrong. foo array corresponds to foo*, and ints are not boxed, so int
array is like int*.

-- 
	Falk

-------------------
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] Looking for a real array

[Karl Zilles]

Eray Ozkural wrote:

 > On Monday 28 April 2003 21:43, Brian Hurt wrote:
 >
 >> I may be confused, but I thought integers were unboxed in arrays (not
 >> BigArrays, just arrays).  Unless you mean references to integers?
 >>
 >
 >
 > Okay, I might be a little confused, forgive me. I thought, 
implementation wise, when I say
 > let a = [| 6, 3, 5, 7, 8 |]
 > it's implemented by ocaml as
 > int** a;
 > in C speak.
 >
 > Right or wrong? (Fearing that I might be demoted to beginner status 
now :P )
 >

In the "Interfacing with C" section of the manual:

---
18.3.3     Arrays

Arrays of integers and pointers are represented like tuples, that is, as 
pointers to blocks tagged 0. They are accessed with the Field macro for 
reading and the modify function for writing.

Arrays of floating-point numbers (type float array) have a special, 
unboxed, more efficient representation. These arrays are represented by 
pointers to blocks with tag Double_array_tag. They should be accessed 
with the Double_field and Store_double_field macros.
---

So it looks like the standard ocaml 31 bit integers arrays are unboxed, 
as are floats arrays.



-------------------
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] Looking for a real array

[Markus Mottl]

On Mon, 28 Apr 2003, Eray Ozkural wrote:
> Thanks to Brian Hurt and David Gurr who wrote off-the list that bigarrays 
> would work for me. It looks like Bigarrays can do unboxed arrays of integers.

Normal arrays always use unboxed (tagged) integers so there is no need
to use the Bigarray module unless you need very large arrays. Normal
float arrays, too, are unboxed, but only when the compiler can infer at
compile time that they are guaranteed to be float arrays.

Regards,
Markus Mottl

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
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] Looking for a real array

[Hal Daume III]

> to use the Bigarray module unless you need very large arrays. Normal
> float arrays, too, are unboxed, but only when the compiler can infer at
> compile time that they are guaranteed to be float arrays.

Does this also apply if I have an abstract type defined in another module:

  > type foo = float

and then have a foo array?

 - Hal

-------------------
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] Looking for a real array

[Markus Mottl]

On Tue, 29 Apr 2003, Hal Daume III wrote:
> > to use the Bigarray module unless you need very large arrays. Normal
> > float arrays, too, are unboxed, but only when the compiler can infer at
> > compile time that they are guaranteed to be float arrays.
> 
> Does this also apply if I have an abstract type defined in another module:
> 
>   > type foo = float
> 
> and then have a foo array?

No, because the compiler cannot see then that it is a float when the
type is abstract. Internally (in the module implementation) however,
the compiler may well use unboxed foo arrays.

Regards,
Markus Mottl

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

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