[Caml-list] Bigarray is a pig

[Caml-list] Bigarray is a pig

[Brandon J. Van Every]

I have been looking at the sources of the Bigarray implementation.  I am
chagrined to discover that not only does Bigarray cost a function call
per array element access, but a number of additional piggish things
happen per access.  To C/C++ programmers interested in performance, this
defeats the purpose of using unboxed array elements.  If I wanted to pay
function call overhead per element, for instance when communicating with
OpenGL, I'd simply call functions.

I am wondering if there is some way to present a block of C memory to
OCaml, and then have OCaml use it directly?  If so, I could envision
writing up something I'd call 'Fastarray'.  But I'm interested in any
pitfalls you might see, such as range check requirements.

In other news, I've been trying and trying to announce the next ML
S*attle meeting on Tuesday, July 27th.   E-mail me for details.  These
anti-spam filters are maddening.


Cheers,                         www.indiegamedesign.com
Brand*n Van Every               S*attle, WA

Praise Be to the caml-list Bayesian filter! It blesseth
my postings, it is evil crap!  evil crap!  evil crap!

-------------------
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] Bigarray is a pig

[Brian Hurt]

On Fri, 23 Jul 2004, Brandon J. Van Every wrote:

> I have been looking at the sources of the Bigarray implementation.  I am
> chagrined to discover that not only does Bigarray cost a function call
> per array element access, but a number of additional piggish things
> happen per access.  

If memory serves, Ocaml can optimize the access if the size and type are 
known, getting rid of the function call overhead and type specialization.  
I don't think it gets rid of the bounds checking, tho- which is good.

Can someone who actually knows what is going on clarify this?

> To C/C++ programmers interested in performance, this
> defeats the purpose of using unboxed array elements.  If I wanted to pay
> function call overhead per element, for instance when communicating with
> OpenGL, I'd simply call functions.

Function calls aren't that expensive.  From comments in other forums:
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&selm=cdjsuj%24cs6%241%40wolfberry.srv.cs.cmu.edu

may I respectfully suggest that you are prematurely optimizing?  A 
function call to a known function takes 1-2 clock cycles.  A cache miss, 
on the other hand, can take hundreds of clock cycles:
http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&threadm=45022fc8.0407221624.6fd81ad0%40posting.google.com&prev=/groups%3Fhl%3Den%26lr%3D%26ie%3DUTF-8%26group%3Dcomp.arch


-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
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] Bigarray is a pig

[Olivier Andrieu]

 "Brandon J. Van Every" [Fri, 23 Jul 2004]:
 > I have been looking at the sources of the Bigarray implementation.
 > I am chagrined to discover that not only does Bigarray cost a
 > function call per array element access, 

No. Not always: when the type of the array is completely known to the
compiler at the point the element is accessed, ocamlopt will access
the element directly, without using the generic C function.

-- 
   Olivier

-------------------
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] Bigarray is a pig

[David McClain]

I hesitate to tell you this, but have a look at my Foreign Arrays code and
you will see direct access at all times from OCaml. However, in order to
achieve this you have to commit to some very dangerous practices!

For example, OCaml only knows natively how to access unboxed contiguous
arrays of double precision. So when you need to see a foreign array directly
from OCaml it must first be converted to this format. That's okay, not
dangerous, just a potentially massive overhead on the first reference.

Secondly, the dangerous part comes in accessing the so-called Arena of the
array to direct and unsafe access from OCaml. No bounds checking here. No
function calls to each element either. The array can't move on you during GC
because it is foreign. (recent updates in my possession now conform to the
more modern Custom_tag blocks, up from the older Finalization blocks. So
these are now directly compare'able, hashable, and streamable, in addition
to being finalizable.)

With honorable respect to Xavier and the INRIA team, I did this purely for
myself, while breaking a ton of other OCaml cherished ideals as well. It
works well for me in my numerical modeling language, but the language is
explicitly unsafe. It never bombs out, mind you, but it does accept and
compile statements of utter nonsense that produce runtime errors on the
console, asking you to repeat what you said, but in a different manner...

As one respondent put it, a call is quick, and a cache miss is horrible by
comparison. You will actually generate quite a few cache misses if your
array has any significant size to it.

Cheers,

David McClain
Senior Corporate Scientist
Avisere, Inc.

+1.520.390.7738 (USA)
david.mcclain@avisere.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] Bigarray is a pig

[David McClain]

Sorry for letting my mind run ahead of my typing...

What I meant to say previously about danger, is that despite the foreign
arrays being safe from GC disruption, in order to access the arena of these
arrays you have to trick OCaml into believing that it is seeing one of its
own kind of array.

That arena address is a foreign pointer address, but this is potentially
unsafe in the face of GC because the foreign array does not actually have
the require structure to pass as an OCaml array of float. So you have to
take care never to allocate anything in the heap during arena accessing.

That is also why the only permitted access to the array arena is by means of
unsafe_get and unsafe_put. You have to be unsafe to be safe... er, yeah...
But it is very fast! It compile to direct memory reference inside the loops.

David McClain
Senior Corporate Scientist
Avisere, Inc.

+1.520.390.7738 (USA)
david.mcclain@avisere.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] Bigarray is a pig

[Brandon J. Van Every]

Olivier Andrieu wrote:
>  "Brand*n wrote:
>  > I have been looking at the sources of the Bigarray implementation.
>  > I am chagrined to discover that not only does Bigarray cost a
>  > function call per array element access,
>
> No. Not always: when the type of the array is completely known to the
> compiler at the point the element is accessed, ocamlopt will access
> the element directly, without using the generic C function.

You are saying that even though Bigarray declares its array element
access functions as EXTERN, and implements them in C code, that ocamlopt
ignores this and does something else?  Using some completely different
source code, perhaps?  (And where is that code?)

Would ocamlopt generally perform such tricks for C functions declared
EXTERN?  How?


Cheers,                         www.indiegamedesign.com
Brand*n Van Every               S*attle, WA

Praise Be to the caml-list Bayesian filter! It blesseth
my postings, it is evil crap!  evil crap!  Bigarray!
Unboxed!  Overhead!  Wondering!  chant chant chant...

-------------------
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] Bigarray is a pig

[Brandon J. Van Every]

Brian Hurt wrote:
> Brand*n wrote:
> >
> > To C/C++ programmers interested in performance, this
> > defeats the purpose of using unboxed array elements.  If I
> > wanted to pay
> > function call overhead per element, for instance when
> > communicating with OpenGL, I'd simply call functions.
>
> Function calls aren't that expensive.

I'm pretty aware, from many years of experience, what the performance
characteristics of C/C++ arrays are vs. function call access to
comparable data, over millions of iterations.  Unless ocamlopt has a way
of avoiding EXTERN Bigarray declarations, we are talking about C code.

In other words, yes function calls are expensive in C compared to the
cost of just accessing an array element.

> A function call to a known function takes 1-2 clock cycles.

Not on any CPU I've worked on.  Generally speaking, you must save state
when you make function calls, and that is never a 1-2 clock cycle
operation.  If you have ways to inline stuff, great, but generally
speaking you can't do that with EXTERN C library stubs.  I don't know if
OCaml has great compiler technology that other languages don't have.
"It's not inlineable" is the drill in the C/C++ universe.


Cheers,                         www.indiegamedesign.com
Brand*n Van Every               S*attle, WA

Praise Be to the caml-list Bayesian filter! It blesseth
my postings, it is evil crap!  evil crap!  Bigarray!
Unboxed!  Overhead!  Wondering!  chant chant chant...


-------------------
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] Bigarray is a pig

[Marcin 'Qrczak' Kowalczyk]

W liście z sob, 24-07-2004, godz. 02:07 -0700, Brandon J. Van Every
napisał:

> You are saying that even though Bigarray declares its array element
> access functions as EXTERN, and implements them in C code, that ocamlopt
> ignores this and does something else?  Using some completely different
> source code, perhaps?  (And where is that code?)

Yes.
grep bigarray */*.ml (in the top level of OCaml sources).

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

-------------------
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] Bigarray is a pig

[Markus Mottl]

On Sat, 24 Jul 2004, Brandon J. Van Every wrote:
> You are saying that even though Bigarray declares its array element
> access functions as EXTERN, and implements them in C code, that ocamlopt
> ignores this and does something else?  Using some completely different
> source code, perhaps?  (And where is that code?)

If you take a close look at bigarray.mli, you'll see that the access
functions "get" and "set" are not normal external functions but start
with a "%".  This means they are primitives that the compiler can handle
in a specific way.  Look at the file asmcomp/cmmgen.ml to see the details.

Regards,
Markus

-- 
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] Bigarray is a pig

[David McClain]

Here is a case where even paying the price of a function call, no matter how
indirect, is well worth it...

I just finished an implementation of memory mapped files for binary array
access from scientific datasets stored on disk. The implementation was in
C++ along with natural usage pseudo-pointers. Every array access has to
check whether or not the position is currently mapped into memory. If so, it
simply returns that address for get or set. If not, then it has to sync the
dirty pages to disk, then remap another segment of the file into memory
before continuing as before.

I am in the process of writing an OCaml interface to this as we speak. But
is it worth doing? My tests show that for pure sequential writing, the
memory mapped I/O is about 350% faster than using buffered I/O with
fwrite(). That's nice... but for pseudo-random access, where I sequentially
march upward in memory and write that address and the two surrounding
addresses at +/-4KB, which is similar to some scientific array access
patterns, the speed of the memory mapped I/O is 200 times faster (20,000%)
than using buffered I/O.

Of course, I chose that 4 KB as a ticklish offset because it both matches
the page frame size and will cause some stumbling in the memory mapped I/O.
And it also happens to be the more or less standard size of a buffer for
fwrite. I'm writing 24 MBytes of data overall, one longword at a time.

The effective throughput is about 72 MB/sec for sequential access and 100
MB/sec for randomized access, compared with 20 MB/sec sequential and 0.5
MB/sec randomized for fwrite buffered I/O.

Disks are slow. File systems are slower yet. By letting the Mach kernel
handle the I/O directly on page faults, I end up squeezing a lot more
performance from the data handling system. This is still orders of magnitude
slower than my effective computation rate, and so the cost of all the bounds
checking and subroutine calling is lost in the noise.

[Tests were performed on a stock 1.25 GHz G4 eMac].

David McClain
Senior Corporate Scientist
Avisere, Inc.

+1.520.390.7738 (USA)
david.mcclain@avisere.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