caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] Unboxing: how to do it best?
@ 2011-01-15 12:02 Eray Ozkural
  2011-01-15 12:38 ` Guillaume Yziquel
                   ` (2 more replies)
  0 siblings, 3 replies; 10+ messages in thread
From: Eray Ozkural @ 2011-01-15 12:02 UTC (permalink / raw)
  To: Caml List

[-- Attachment #1: Type: text/plain, Size: 852 bytes --]

It's obvious that avoiding pointer chasing, improving locality and reducing
storage will in some cases improve performance considerably. I've found many
discussions about unboxing, but I haven't seen any solutions that would
satisfy high-performance-computing programmers, who would probably like to
have better (i.e. fine-grained) control over memory layout (unboxing double
arrays isn't enough). In C++ this is trivial, because C++ is just an
abstraction of assembly code. To cut it short,  could not we have basically
the same affordances of C++ in ocaml by annotating type definitions to
indicate where unboxing would be forced? Such annotations aren't a new idea
in programming languages, specifically HPF was based largely on parallel
storage annotations.

Regards,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara

[-- Attachment #2: Type: text/html, Size: 952 bytes --]

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [Caml-list] Unboxing: how to do it best?
  2011-01-15 12:02 [Caml-list] Unboxing: how to do it best? Eray Ozkural
@ 2011-01-15 12:38 ` Guillaume Yziquel
  2011-01-15 14:00   ` Eray Ozkural
  2011-01-15 12:41 ` bluestorm
  2011-01-16 17:03 ` Jon Harrop
  2 siblings, 1 reply; 10+ messages in thread
From: Guillaume Yziquel @ 2011-01-15 12:38 UTC (permalink / raw)
  To: Eray Ozkural; +Cc: Caml List

Le Saturday 15 Jan 2011 à 14:02:11 (+0200), Eray Ozkural a écrit :
>    It's obvious that avoiding pointer chasing, improving locality and
>    reducing storage will in some cases improve performance considerably.
>    I've found many discussions about unboxing, but I haven't seen any
>    solutions that would satisfy high-performance-computing programmers,
>    who would probably like to have better (i.e. fine-grained) control over
>    memory layout (unboxing double arrays isn't enough). In C++ this is
>    trivial, because C++ is just an abstraction of assembly code. To cut it
>    short,  could not we have basically the same affordances of C++ in
>    ocaml by annotating type definitions to indicate where unboxing would
>    be forced? Such annotations aren't a new idea in programming languages,
>    specifically HPF was based largely on parallel storage annotations.
> 
>    Regards,
>    --
>    Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University,
>    Ankara

If you do not care about having the annotation available at runtime
instead of being something static (after all, MPI datatypes are
available at runtime), you could go for encapsulating type information
in first class modules representing datatypes.

Then, for instance, given a datatype, you may wish to construct the
datatype of an array of such types. Such a function needs to know
details about the way OCaml boxes or unboxes different kinds of arrays,
and it can be done (though rather awkwardly in my case).

So first-class modules encapsulating datatype information seems to me a
worthwile option and the only solution I could come with to mimic what
would be done in C++ with traits.

As for 'annotating type definitions', where would you put the line as to
what 'annotating' means? Using type-conv-like Camlp4 processing?

But as to avoiding pointer chasing, I think there's no workaround to the
way OCaml handles memory. The only solution I can come of is the
obvious: use arrays or bigarrays and smart datatypes.

-- 
     Guillaume Yziquel


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [Caml-list] Unboxing: how to do it best?
  2011-01-15 12:02 [Caml-list] Unboxing: how to do it best? Eray Ozkural
  2011-01-15 12:38 ` Guillaume Yziquel
@ 2011-01-15 12:41 ` bluestorm
  2011-01-15 13:37   ` Eray Ozkural
  2011-01-16 17:03 ` Jon Harrop
  2 siblings, 1 reply; 10+ messages in thread
From: bluestorm @ 2011-01-15 12:41 UTC (permalink / raw)
  To: Eray Ozkural; +Cc: Caml List

[-- Attachment #1: Type: text/plain, Size: 1944 bytes --]

I don't think it is easily possible inside Caml, as the data representation
is tightly bound to the runtime system, and it would be very delicate to
change it.

If you are interested in the relevant litterature, you may want to see for
example the bibliography on "Unboxing data representations" of
  http://pauillac.inria.fr/~xleroy/talks/references-pldi98.html
In particular, you may be interested in the Peyton-Jones and Launchbury
paper, as they implemented their ideas into the GHC Haskell compiler which
support some unboxed types.

If you want to optimize the kernel of an existing OCaml program with unboxed
manipulations, I think your best bet would be to switch to a lower-level
language for your kernel. This is very common in scripting languages where
you generally implement the -- hopefully tiny -- performance-sensitive parts
of your program in C. You still reap the benefits of OCaml abstractions for
the larger, less performance-sensitive part of your program.


On Sat, Jan 15, 2011 at 1:02 PM, Eray Ozkural <examachine@gmail.com> wrote:

> It's obvious that avoiding pointer chasing, improving locality and reducing
> storage will in some cases improve performance considerably. I've found many
> discussions about unboxing, but I haven't seen any solutions that would
> satisfy high-performance-computing programmers, who would probably like to
> have better (i.e. fine-grained) control over memory layout (unboxing double
> arrays isn't enough). In C++ this is trivial, because C++ is just an
> abstraction of assembly code. To cut it short,  could not we have basically
> the same affordances of C++ in ocaml by annotating type definitions to
> indicate where unboxing would be forced? Such annotations aren't a new idea
> in programming languages, specifically HPF was based largely on parallel
> storage annotations.
>
> Regards,
>
> --
> Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
>
>
>

[-- Attachment #2: Type: text/html, Size: 2507 bytes --]

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [Caml-list] Unboxing: how to do it best?
  2011-01-15 12:41 ` bluestorm
@ 2011-01-15 13:37   ` Eray Ozkural
  0 siblings, 0 replies; 10+ messages in thread
From: Eray Ozkural @ 2011-01-15 13:37 UTC (permalink / raw)
  To: bluestorm; +Cc: Caml List

[-- Attachment #1: Type: text/plain, Size: 3088 bytes --]

Except that ocaml is hardly a slow scripting language, on many levels it's
directly comparable to C++ code. In my opinion, ocaml should be usable all
the way down to the kernel code. For many complex algorithms and data
structures, using C++ with all the zero-overhead level-headed
template-bloated pages-long low-level intricate imperative code you'll get a
very small constant factor improvement. For an actual non-trivial search
code I got only twice the speed of the ocaml code, even though I used
vectors instead of lists throughout. Not worth the effort at all. I wouldn't
even attempt it if I hadn't had to port the code to C++.

Thanks for the references by the way, I am actually interested in this. I'm
thinking of its extensions (i.e. distributed memory architectures, shared
memory cannot scale anyway).

Best,

On Sat, Jan 15, 2011 at 2:41 PM, bluestorm <bluestorm.dylc@gmail.com> wrote:

> I don't think it is easily possible inside Caml, as the data representation
> is tightly bound to the runtime system, and it would be very delicate to
> change it.
>
> If you are interested in the relevant litterature, you may want to see for
> example the bibliography on "Unboxing data representations" of
>   http://pauillac.inria.fr/~xleroy/talks/references-pldi98.html
> In particular, you may be interested in the Peyton-Jones and Launchbury
> paper, as they implemented their ideas into the GHC Haskell compiler which
> support some unboxed types.
>
> If you want to optimize the kernel of an existing OCaml program with
> unboxed manipulations, I think your best bet would be to switch to a
> lower-level language for your kernel. This is very common in scripting
> languages where you generally implement the -- hopefully tiny --
> performance-sensitive parts of your program in C. You still reap the
> benefits of OCaml abstractions for the larger, less performance-sensitive
> part of your program.
>
>
> On Sat, Jan 15, 2011 at 1:02 PM, Eray Ozkural <examachine@gmail.com>wrote:
>
>> It's obvious that avoiding pointer chasing, improving locality and
>> reducing storage will in some cases improve performance considerably. I've
>> found many discussions about unboxing, but I haven't seen any solutions that
>> would satisfy high-performance-computing programmers, who would probably
>> like to have better (i.e. fine-grained) control over memory layout (unboxing
>> double arrays isn't enough). In C++ this is trivial, because C++ is just an
>> abstraction of assembly code. To cut it short,  could not we have basically
>> the same affordances of C++ in ocaml by annotating type definitions to
>> indicate where unboxing would be forced? Such annotations aren't a new idea
>> in programming languages, specifically HPF was based largely on parallel
>> storage annotations.
>>
>> Regards,
>>
>> --
>> Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
>>
>>
>>
>


-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 4100 bytes --]

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [Caml-list] Unboxing: how to do it best?
  2011-01-15 12:38 ` Guillaume Yziquel
@ 2011-01-15 14:00   ` Eray Ozkural
  2011-01-15 17:23     ` Guillaume Yziquel
  0 siblings, 1 reply; 10+ messages in thread
From: Eray Ozkural @ 2011-01-15 14:00 UTC (permalink / raw)
  To: Guillaume Yziquel; +Cc: Caml List

[-- Attachment #1: Type: text/plain, Size: 2619 bytes --]

On Sat, Jan 15, 2011 at 2:38 PM, Guillaume Yziquel <
guillaume.yziquel@citycable.ch> wrote:
>
>
> If you do not care about having the annotation available at runtime
> instead of being something static (after all, MPI datatypes are
> available at runtime), you could go for encapsulating type information
> in first class modules representing datatypes.
>
> Then, for instance, given a datatype, you may wish to construct the
> datatype of an array of such types. Such a function needs to know
> details about the way OCaml boxes or unboxes different kinds of arrays,
> and it can be done (though rather awkwardly in my case).
>
> So first-class modules encapsulating datatype information seems to me a
> worthwile option and the only solution I could come with to mimic what
> would be done in C++ with traits.
>


 Hi Guillaume,

That's a good idea.

Theoretically a functor transforms programs. Radical program rewriting would
be just the thing to do with a functor, but I'd rather have it in the
compiler.

After all program-transformation is what an optimization pass is
essentially. There is absolutely nothing wrong with doing it in a high-level
way, as long as it doesn't introduce runtime overhead.

Has anyone designed a cool compiler like that? :)


As for 'annotating type definitions', where would you put the line as to
> what 'annotating' means? Using type-conv-like Camlp4 processing?
>
>
I haven't thought much about the implementation, except verifying that it's
just an extension of the present kinds of unboxing in the runtime.

What I would like is something like (thinking of a typical simulation
datatype):

type cvector4 = ][ (complex * complex * complex * complex)

where ][ would be a "type operator" enforcing a flattened representation of
the type expression it is applied to. It would just change the layout so it
would be equivalent to the same type without the unboxing op.

Preprocessing might be one way to implement it, but i don't think it's an
easy implementation at any rate.

Just a small idea that I couldn't let slip from my mind.

But as to avoiding pointer chasing, I think there's no workaround to the
> way OCaml handles memory. The only solution I can come of is the
> obvious: use arrays or bigarrays and smart datatypes.
>

Smart datatypes is OK, I think you could substitute many datatypes with such
a thing, but I'm not sure how easy that would be to do in real-world
programming?

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 3787 bytes --]

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [Caml-list] Unboxing: how to do it best?
  2011-01-15 14:00   ` Eray Ozkural
@ 2011-01-15 17:23     ` Guillaume Yziquel
  2011-01-15 18:33       ` Eray Ozkural
  0 siblings, 1 reply; 10+ messages in thread
From: Guillaume Yziquel @ 2011-01-15 17:23 UTC (permalink / raw)
  To: Eray Ozkural; +Cc: Caml List

Le Saturday 15 Jan 2011 à 16:00:21 (+0200), Eray Ozkural a écrit :
>    On Sat, Jan 15, 2011 at 2:38 PM, Guillaume Yziquel
>    <[1]guillaume.yziquel@citycable.ch> wrote:
> 
>      Then, for instance, given a datatype, you may wish to construct the
>      datatype of an array of such types. Such a function needs to know
>      details about the way OCaml boxes or unboxes different kinds of
>      arrays,
>      and it can be done (though rather awkwardly in my case).
> 
>     Hi Guillaume,

Hi.

>    That's a good idea.
>    Theoretically a functor transforms programs. Radical program rewriting
>    would be just the thing to do with a functor, but I'd rather have it in
>    the compiler.

I wasn't thinking of applying functors to rewrite / specialise (whatever
you call it) some code to a datatype.

I was more thinking of having a first-class module as a regular value
that provides, when you unpack it, sufficient information to know how to
cross the barriers from OCaml to C or Fortran or whatever, and then send
it or receive it via an MPI implementation (since that's what I'm
looking at). Which means all your HPC primitives must know how to read
properly the datatype info enclosed in your first-class module.

I'm saying first-class module, because it can be typed as 'value datatype.
You only know what the 'value it is supposed to encode is, and have all
the typing info of how to deal with it encapsulated in the first-class
module and not leaking into the rest of your code.

It's not program rewriting, and there is overhead, but I guess it can be
kept quite low.

>    After all program-transformation is what an optimization pass is
>    essentially. There is absolutely nothing wrong with doing it in a
>    high-level way, as long as it doesn't introduce runtime overhead.
>    Has anyone designed a cool compiler like that? :)

I'm not for the moment interested in the 'compiler' aspect of that. The
solution I propose does cost some overhead reading the first-class module
at runtime. Not really sure if functorising things fully would be a real
performance benefit in my case. Functorising things too much makes
things quite ugly to maintain.

>      As for 'annotating type definitions', where would you put the line
>      as to
>      what 'annotating' means? Using type-conv-like Camlp4 processing?
> 
>    I haven't thought much about the implementation, except verifying that
>    it's just an extension of the present kinds of unboxing in the
>    runtime.

Not entirely following you here, but bubbling the runtime unboxing up
into the syntax appears risky at best.

>    What I would like is something like (thinking of a typical simulation
>    datatype):
>    type cvector4 = ][ (complex * complex * complex * complex)
>    where ][ would be a "type operator" enforcing a flattened
>    representation of the type expression it is applied to. It would just
>    change the layout so it would be equivalent to the same type without
>    the unboxing op.

If I'm not mistaking tuples or records of floats are already unboxed at
runtime. Not seeing the great benefit here.

But for an complex algebraic datatype you may think about the following:
Instead of having, essentially, structured blocks with pointers to other
blocks, you could define a "'value packed" type which would represent
flattened OCaml 'values. You have locality there. The issue then is
twofold:

-1- You need information to pack and unpack, and as you do not want to
pack and unpack too much, you will have problems dealing with packed
values in your OCaml code.

-2- The mentioned information to pack and unpack will have an
uncomfortable representation to deal with, as you still need the GC to
operate correctly on the packed values. So bit-twiddling headaches when
recursively packing or unpacking values. And fun when encountering
cycles of values. Not to mention polymorphic comparison.

To sum up: A complete solution covering all OCaml types and values for
packing doesn't seem realistic (at least I do not see how to pack in a
same block, a custom block, and array of floats and a structured block,
without uterly confusing the GC). Baby steps and dealing systematically
with the corner cases as they pop seems a realistic approach however,
but with limited scope of applicability.

>    Preprocessing might be one way to implement it, but i don't think it's
>    an easy implementation at any rate.
>    Just a small idea that I couldn't let slip from my mind.

For what you propose, preprocessing seems less important than correct
typing.

>      But as to avoiding pointer chasing, I think there's no workaround to
>      the
>      way OCaml handles memory. The only solution I can come of is the
>      obvious: use arrays or bigarrays and smart datatypes.
> 
>    Smart datatypes is OK, I think you could substitute many datatypes with
>    such a thing, but I'm not sure how easy that would be to do in
>    real-world programming?

Pretty uncomfortable I guess.

-- 
     Guillaume Yziquel


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [Caml-list] Unboxing: how to do it best?
  2011-01-15 17:23     ` Guillaume Yziquel
@ 2011-01-15 18:33       ` Eray Ozkural
  2011-01-16 16:53         ` Jon Harrop
  2011-01-18 23:49         ` Guillaume Yziquel
  0 siblings, 2 replies; 10+ messages in thread
From: Eray Ozkural @ 2011-01-15 18:33 UTC (permalink / raw)
  To: Guillaume Yziquel; +Cc: Caml List

[-- Attachment #1: Type: text/plain, Size: 4254 bytes --]

On Sat, Jan 15, 2011 at 7:23 PM, Guillaume Yziquel <
guillaume.yziquel@citycable.ch> wrote:

> Le Saturday 15 Jan 2011 à 16:00:21 (+0200), Eray Ozkural a écrit :
> >    On Sat, Jan 15, 2011 at 2:38 PM, Guillaume Yziquel
> >    <[1]guillaume.yziquel@citycable.ch> wrote:
> >
> >      Then, for instance, given a datatype, you may wish to construct the
> >      datatype of an array of such types. Such a function needs to know
> >      details about the way OCaml boxes or unboxes different kinds of
> >      arrays,
> >      and it can be done (though rather awkwardly in my case).
>
>
Awkwardly, but how? :)



> >    That's a good idea.
> >    Theoretically a functor transforms programs. Radical program rewriting
> >    would be just the thing to do with a functor, but I'd rather have it
> in
> >    the compiler.
>
> I wasn't thinking of applying functors to rewrite / specialise (whatever
> you call it) some code to a datatype.
>
>
Ok, you mean exactly like C++ type traits, where a static namespace provides
further type information. In OCaml that'd be a module, right.


> I was more thinking of having a first-class module as a regular value
> that provides, when you unpack it, sufficient information to know how to
> cross the barriers from OCaml to C or Fortran or whatever, and then send
> it or receive it via an MPI implementation (since that's what I'm
> looking at). Which means all your HPC primitives must know how to read
> properly the datatype info enclosed in your first-class module.
>

I didn't really have MPI types on my mind, but it would surely be nice to be
able to integrate nicely with MPI as well, though I think the Marshal module
isn't costly (I made a small benchmark).

What I had in mind was, say, I have this CA simulation or spiking neural net
simulation code or a cell simulation, or a quantum chromodynamics
simulation, maybe a visualization of an irregular mesh, or some other
non-trivial scientific computing application where it's difficult to reduce
everything to float arrays. Because usually you will have either vectors, or
graphs of complex atomic structures and then this boxing is going to
seriously hurt performance, as performance is hurt when you try to write any
serious algorithm in Java in an OO fashion because everything is a pointer.
When you have to start writing every algorithm in an awkward and bloated way
to maintain some sense of performance, the benefit of the language quickly
vanishes. (Main reason why Java should never be used except for toy web
apps!) And then the HPC guy will have to turn to the portable assembly of
C++, right?


> I'm saying first-class module, because it can be typed as 'value datatype.
> You only know what the 'value it is supposed to encode is, and have all
> the typing info of how to deal with it encapsulated in the first-class
> module and not leaking into the rest of your code.
>

Ok, care to give a minimal example? How do you pass and use the module
value? This sounds interesting enough. You seem to be using the module to
encapsulate encoding/decoding functions. Which is fine but how is it enough?
How would that apply to changing the memory layout of a data type (or to
provide an unboxed array of such values)? I thought you would be generating
another module that represents the same type as an array of ints, and
somehow convert the types transparently. How do you propose to do it?

>    What I would like is something like (thinking of a typical simulation
> >    datatype):
> >    type cvector4 = ][ (complex * complex * complex * complex)
> >    where ][ would be a "type operator" enforcing a flattened
> >    representation of the type expression it is applied to. It would just
> >    change the layout so it would be equivalent to the same type without
> >    the unboxing op.
>
> If I'm not mistaking tuples or records of floats are already unboxed at
> runtime. Not seeing the great benefit here.
>

Yes, but the above is not a tuple of floats.

Best,

-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 5666 bytes --]

^ permalink raw reply	[flat|nested] 10+ messages in thread

* RE: [Caml-list] Unboxing: how to do it best?
  2011-01-15 18:33       ` Eray Ozkural
@ 2011-01-16 16:53         ` Jon Harrop
  2011-01-18 23:49         ` Guillaume Yziquel
  1 sibling, 0 replies; 10+ messages in thread
From: Jon Harrop @ 2011-01-16 16:53 UTC (permalink / raw)
  To: 'Eray Ozkural'; +Cc: 'Caml List'

Eray wrote:
> What I had in mind was, say, I have this CA simulation or spiking neural
net
> simulation code or a cell simulation, or a quantum chromodynamics
simulation,
> maybe a visualization of an irregular mesh, or some other non-trivial
scientific
> computing application where it's difficult to reduce everything to float
arrays.

FWIW, my ray tracer benchmark was specifically designed to reflect the
performance characteristics of such programs. 

Cheers,
Jon.



^ permalink raw reply	[flat|nested] 10+ messages in thread

* RE: [Caml-list] Unboxing: how to do it best?
  2011-01-15 12:02 [Caml-list] Unboxing: how to do it best? Eray Ozkural
  2011-01-15 12:38 ` Guillaume Yziquel
  2011-01-15 12:41 ` bluestorm
@ 2011-01-16 17:03 ` Jon Harrop
  2 siblings, 0 replies; 10+ messages in thread
From: Jon Harrop @ 2011-01-16 17:03 UTC (permalink / raw)
  To: 'Eray Ozkural', 'Caml List'

Eray wrote:
> It's obvious that avoiding pointer chasing, improving locality and
reducing storage
> will in some cases improve performance considerably.

Yes. Generic hash tables are my favourite example where this hurts. Java and
OCaml can be over an order of magnitude slower than .NET due to boxing in
that case.

> I've found many discussions about unboxing, but I haven't seen any
solutions that
> would satisfy high-performance-computing programmers, who would probably
like to
> have better (i.e. fine-grained) control over memory layout (unboxing
double arrays
> isn't enough). In C++ this is trivial, because C++ is just an abstraction
of assembly
> code. To cut it short, could not we have basically the same affordances of
C++ in
> ocaml by annotating type definitions to indicate where unboxing would be
forced?
> Such annotations aren't a new idea in programming languages, specifically
HPF was
> based largely on parallel storage annotations.

Yes, .NET already does what you are describing: unboxed types are called
"value types". For example, you can allocate an array of structs and refer
to them by array index rather than reference in order to avoid all
allocations and garbage collections. Some people have used this approach to
write low-latency software that never incurs a garbage collection during
steady state operation. I have recently been writing prototype garbage
collectors in F# using the same technique to great effect.

HPC programmers using OCaml will have to settle for generating code from
OCaml when you need to escape its data representation. HLVM is an example of
how this might be done and was specifically designed with HPC in mind.

Cheers,
Jon.



^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [Caml-list] Unboxing: how to do it best?
  2011-01-15 18:33       ` Eray Ozkural
  2011-01-16 16:53         ` Jon Harrop
@ 2011-01-18 23:49         ` Guillaume Yziquel
  1 sibling, 0 replies; 10+ messages in thread
From: Guillaume Yziquel @ 2011-01-18 23:49 UTC (permalink / raw)
  To: Eray Ozkural; +Cc: Caml List

Le Saturday 15 Jan 2011 à 20:33:33 (+0200), Eray Ozkural a écrit :
>  On Sat, Jan 15, 2011 at 7:23 PM, Guillaume Yziquel
>  <[1]guillaume.yziquel@citycable.ch> wrote:
> 
>    Le Saturday 15 Jan 2011 à 16:00:21 (+0200), Eray Ozkural a écrit :
> 
>  >  On Sat, Jan 15, 2011 at 2:38 PM, Guillaume Yziquel
> 
>  >  <[1][2]guillaume.yziquel@citycable.ch> wrote:
>  >
>  >  Then, for instance, given a datatype, you may wish to construct
>  >  the datatype of an array of such types. Such a function needs to
>  >  know details about the way OCaml boxes or unboxes different kinds of
>  >  arrays, and it can be done (though rather awkwardly in my case).
> 
>  Awkwardly, but how? :)

See the function 'array' at the end of the file:

https://github.com/yziquel/OCaml-MPI/blob/master/ocamltype.p4.ml

(This code is far from clean, quite compact and ugly, but it shows it can be
done).

You here have a function that converts the a given datatype for type t
to a datatype for type t array.

>  Ok, you mean exactly like C++ type traits, where a static namespace
>  provides further type information. In OCaml that'd be a module, right.

Less static than type traits, but yes, similar in a sense.

>  I was more thinking of having a first-class module as a regular
>  value that provides, when you unpack it, sufficient information to know
>  how to cross the barriers from OCaml to C or Fortran or whatever, and then
>  send it or receive it via an MPI implementation (since that's what I'm
>  looking at). Which means all your HPC primitives must know how to
>  read properly the datatype info enclosed in your first-class module.

The contents of this first-class module is available here:

https://github.com/yziquel/OCaml-MPI/blob/master/ocamltype.p4.sig.mli

The real C hack is the 'how_to_fill' value in this module, which maps to
the switch(how) block in the following X-macro:

https://github.com/yziquel/OCaml-MPI/blob/master/messages.macro.c

This macro is used by the stub functions in

https://github.com/yziquel/OCaml-MPI/blob/master/messages.c

and these stub functions receive the 'how' value from the first-class
module datatype. It then gets arguably easier to write SPMD code which
transfers values that type-check properly with their datatype's type.

>    What I had in mind was, say, I have this CA simulation or spiking
>    neural net simulation code or a cell simulation, or a quantum
>    chromodynamics simulation, maybe a visualization of an irregular mesh,
>    or some other non-trivial scientific computing application where it's
>    difficult to reduce everything to float arrays. Because usually you
>    will have either vectors, or graphs of complex atomic structures and
>    then this boxing is going to seriously hurt performance, as performance
>    is hurt when you try to write any serious algorithm in Java in an OO
>    fashion because everything is a pointer. When you have to start writing
>    every algorithm in an awkward and bloated way to maintain some sense of
>    performance, the benefit of the language quickly vanishes. (Main reason
>    why Java should never be used except for toy web apps!) And then the
>    HPC guy will have to turn to the portable assembly of C++, right?

Possible.
 
>      I'm saying first-class module, because it can be typed as 'value
>      datatype.
>      You only know what the 'value it is supposed to encode is, and have
>      all
>      the typing info of how to deal with it encapsulated in the
>      first-class
>      module and not leaking into the rest of your code.
> 
>    Ok, care to give a minimal example? How do you pass and use the module
>    value? This sounds interesting enough. You seem to be using the module
>    to encapsulate encoding/decoding functions.

Yes.

>    Which is fine but how is it enough? How would that apply to changing
>    the memory layout of a data type (or to provide an unboxed array of such
>    values)? I thought you would be generating another module that represents
>    the same type as an array of ints, and somehow convert the types
>    transparently. How do you propose to do it?

No, it doesn't suit the specific unboxing needs you care about. What you
want really is to change the way the values are represented in memory.
You really want somehow another type of block in which you can quickly
read an OCaml value. Possibly a specific block tag for your purposes
that would advise the GC how your block packs values and how to update
pointers inside, or some workaround. You could possibly use
first-class modules to know how to read and write such a packed block
in a type-safe way, but I'd guess you'd hurt performance too much for
your purposes doing that depending on what you do.

>    >    What I would like is something like (thinking of a typical
>    simulation
>    >    datatype):
>    >    type cvector4 = ][ (complex * complex * complex * complex)
>    >    where ][ would be a "type operator" enforcing a flattened
>    >    representation of the type expression it is applied to. It would
>    just
>    >    change the layout so it would be equivalent to the same type
>    without
>    >    the unboxing op.
> 
>      If I'm not mistaking tuples or records of floats are already unboxed
>      at
>      runtime. Not seeing the great benefit here.
> 
> 
>    Yes, but the above is not a tuple of floats.
>    Best,

Well then, you could probably do something with Camlp4, but you're in
for quite some pain as far as I can see.

I imagine you could generate the first-class module for packed values
(with readers/decoders/encoders/writers in them) depending on the
']['-like type declarations. But it hardly seems fun to do.

-- 
     Guillaume Yziquel


^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2011-01-18 23:50 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-01-15 12:02 [Caml-list] Unboxing: how to do it best? Eray Ozkural
2011-01-15 12:38 ` Guillaume Yziquel
2011-01-15 14:00   ` Eray Ozkural
2011-01-15 17:23     ` Guillaume Yziquel
2011-01-15 18:33       ` Eray Ozkural
2011-01-16 16:53         ` Jon Harrop
2011-01-18 23:49         ` Guillaume Yziquel
2011-01-15 12:41 ` bluestorm
2011-01-15 13:37   ` Eray Ozkural
2011-01-16 17:03 ` Jon Harrop

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).