* [Caml-list] Two questions on the OCAML runtime system and compiler,
@ 2013-09-30 12:43 Sungwoo Park
2013-09-30 13:24 ` Leo White
` (2 more replies)
0 siblings, 3 replies; 6+ messages in thread
From: Sungwoo Park @ 2013-09-30 12:43 UTC (permalink / raw)
To: caml-list; +Cc: Sungwoo Park
Dear Caml users,
We are currently experimenting with a parallel Ocaml runtime system, in which
each thread maintains its own old and young heaps and runs in parallel with
other threads, without sharing a global lock as in the current Ocaml runtime
system while sharing the whole memory space. We have made changes to the
current Ocaml compiler (4.00.1), and now the parallel compiler generates
parallel code that runs on the parallel Ocaml runtime system. It is a
cross-compiler and we can build it with any version of the Ocaml compiler,
including the parallel compiler itself.
This is a project very similar to Luca Saiu's reentrant multi-runtime system
(https://github.com/lucasaiu/ocaml), and we benefited very much from Luca's
code at several early stages in the development. Similarly to Luca's work, our
runtime system is reentrant.
As the next step toward a parallel runtime system with a shared heap, we are
struggling to redefine the tag format. I have two specific questions on the
compiler and the runtime system. Any comment and help would be greatly
appreciated.
Question 1.
When we reassign tag numbers for block types, the runtime system crashes for
some applications. We thought we made all necessary changes to the source code
(in byterun/mlvalues.h, utils/config.mlp, and several files in bytecomp/) to
reflect the new tag numbers. However the runtime system often crashes, for
example, when it accesses the Lazy module, which in turn accesses the Obj
module, in testsuite/tests/misc/hamming.ml. I wonder what other parts in the
source code we should revise after reassigning tag numbers.
(Our finding is that this is not a problem due to the parallel runtime system,
as we could reproduce the same outcome on the sequential runtime system.)
Question 2.
On a 64-bit system, can we safely get rid of the page table, in particular
caml_page_table_lookup(), if the header of each block is redesigned to include
a field indicating which memory area it resides (old heap, young heap, static
data, etc)? I wonder what other purposes the page table serves, other than
determining the memory area for a given pointer.
(Perhaps adding a new field in the header would be too impractical on a 32-bit
system, but on a 64-bit system, we can affort to allocate quite a few bits for
new fields in the header. Windows might need the page table to check if a given
pointer points to code, but luckily we don't need to consider Windows for our
purpose.)
Thank you very much!
--- Sungwoo Park
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Two questions on the OCAML runtime system and compiler,
2013-09-30 12:43 [Caml-list] Two questions on the OCAML runtime system and compiler, Sungwoo Park
@ 2013-09-30 13:24 ` Leo White
2013-09-30 14:23 ` Yotam Barnoy
2013-09-30 14:08 ` Jacques-Henri Jourdan
[not found] ` <138054732239801.04758.localhost@localhost>
2 siblings, 1 reply; 6+ messages in thread
From: Leo White @ 2013-09-30 13:24 UTC (permalink / raw)
To: Sungwoo Park; +Cc: caml-list
We are also experimenting with a parallel OCaml runtime system at
OCamlLabs (https://github.com/ocamllabs/ocaml/tree/multicore). Out of
interest is the source for your experimental compiler and runtime available
anywhere?
With respect to the page table, I don't think it serves any other
purpose. I know various people have been looking into removing
it (or at least removing it from common operations) without the addition
of a bit field in the header. So it is possible you could avoid changing
the header layout in your version of the compiler as well.
Regards,
Leo White
Sungwoo Park <gla@postech.ac.kr> writes:
> Dear Caml users,
>
> We are currently experimenting with a parallel Ocaml runtime system, in which
> each thread maintains its own old and young heaps and runs in parallel with
> other threads, without sharing a global lock as in the current Ocaml runtime
> system while sharing the whole memory space. We have made changes to the
> current Ocaml compiler (4.00.1), and now the parallel compiler generates
> parallel code that runs on the parallel Ocaml runtime system. It is a
> cross-compiler and we can build it with any version of the Ocaml compiler,
> including the parallel compiler itself.
>
> This is a project very similar to Luca Saiu's reentrant multi-runtime system
> (https://github.com/lucasaiu/ocaml), and we benefited very much from Luca's
> code at several early stages in the development. Similarly to Luca's work, our
> runtime system is reentrant.
>
> As the next step toward a parallel runtime system with a shared heap, we are
> struggling to redefine the tag format. I have two specific questions on the
> compiler and the runtime system. Any comment and help would be greatly
> appreciated.
>
> Question 1.
>
> When we reassign tag numbers for block types, the runtime system crashes for
> some applications. We thought we made all necessary changes to the source code
> (in byterun/mlvalues.h, utils/config.mlp, and several files in bytecomp/) to
> reflect the new tag numbers. However the runtime system often crashes, for
> example, when it accesses the Lazy module, which in turn accesses the Obj
> module, in testsuite/tests/misc/hamming.ml. I wonder what other parts in the
> source code we should revise after reassigning tag numbers.
>
> (Our finding is that this is not a problem due to the parallel runtime system,
> as we could reproduce the same outcome on the sequential runtime system.)
>
> Question 2.
>
> On a 64-bit system, can we safely get rid of the page table, in particular
> caml_page_table_lookup(), if the header of each block is redesigned to include
> a field indicating which memory area it resides (old heap, young heap, static
> data, etc)? I wonder what other purposes the page table serves, other than
> determining the memory area for a given pointer.
>
> (Perhaps adding a new field in the header would be too impractical on a 32-bit
> system, but on a 64-bit system, we can affort to allocate quite a few bits for
> new fields in the header. Windows might need the page table to check if a given
> pointer points to code, but luckily we don't need to consider Windows for our
> purpose.)
>
> Thank you very much!
>
> --- Sungwoo Park
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Two questions on the OCAML runtime system and compiler,
2013-09-30 12:43 [Caml-list] Two questions on the OCAML runtime system and compiler, Sungwoo Park
2013-09-30 13:24 ` Leo White
@ 2013-09-30 14:08 ` Jacques-Henri Jourdan
[not found] ` <138054732239801.04758.localhost@localhost>
2 siblings, 0 replies; 6+ messages in thread
From: Jacques-Henri Jourdan @ 2013-09-30 14:08 UTC (permalink / raw)
To: caml-list
>
> Question 2.
>
> On a 64-bit system, can we safely get rid of the page table, in
> particular
> caml_page_table_lookup(), if the header of each block is redesigned to
> include
> a field indicating which memory area it resides (old heap, young heap,
> static
> data, etc)? I wonder what other purposes the page table serves, other
> than
> determining the memory area for a given pointer.
The OCaml runtime is designed so that pointers in the heap can point to
objects outside the OCaml heap, as long as they are 2-aligned. That is,
bindings for C libraries are allowed to return C pointers (eg. allocated
using malloc) as OCaml values. However, I do not know how many actual
bindings make use of this feature.
--
JHJ
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Two questions on the OCAML runtime system and compiler,
2013-09-30 13:24 ` Leo White
@ 2013-09-30 14:23 ` Yotam Barnoy
2013-09-30 14:39 ` Yotam Barnoy
0 siblings, 1 reply; 6+ messages in thread
From: Yotam Barnoy @ 2013-09-30 14:23 UTC (permalink / raw)
To: Leo White; +Cc: Sungwoo Park, Ocaml Mailing List
[-- Attachment #1: Type: text/plain, Size: 4545 bytes --]
From what I understand, Luca's patch is going to be mainstreamed sometime
in the not-so-distant future, so it might make sense to work directly off
of his branch, no?
The problem you're having is that every caml_page_table_lookup() needs to
acquire the heap allocator's lock, right? Perhaps you can make this access
lockless. If the global page table is a persistent data structure, like a
Map (but in C of course) and the allocator creates a new data structure
root every time a block is allocated from/released from the OS, then all
you would need is a boolean per thread indicating that it's seen the new
global root before the allocator can go ahead and deallocate whatever
blocks need to be deallocated from the old persistent trees. Since blocks
shouldn't be allocated from the OS that frequently, this shouldn't be too
expensive.
Yotam
On Mon, Sep 30, 2013 at 9:24 AM, Leo White <lpw25@cam.ac.uk> wrote:
>
> We are also experimenting with a parallel OCaml runtime system at
> OCamlLabs (https://github.com/ocamllabs/ocaml/tree/multicore). Out of
> interest is the source for your experimental compiler and runtime available
> anywhere?
>
> With respect to the page table, I don't think it serves any other
> purpose. I know various people have been looking into removing
> it (or at least removing it from common operations) without the addition
> of a bit field in the header. So it is possible you could avoid changing
> the header layout in your version of the compiler as well.
>
> Regards,
>
> Leo White
>
> Sungwoo Park <gla@postech.ac.kr> writes:
>
> > Dear Caml users,
> >
> > We are currently experimenting with a parallel Ocaml runtime system, in
> which
> > each thread maintains its own old and young heaps and runs in parallel
> with
> > other threads, without sharing a global lock as in the current Ocaml
> runtime
> > system while sharing the whole memory space. We have made changes to the
> > current Ocaml compiler (4.00.1), and now the parallel compiler generates
> > parallel code that runs on the parallel Ocaml runtime system. It is a
> > cross-compiler and we can build it with any version of the Ocaml
> compiler,
> > including the parallel compiler itself.
> >
> > This is a project very similar to Luca Saiu's reentrant multi-runtime
> system
> > (https://github.com/lucasaiu/ocaml), and we benefited very much from
> Luca's
> > code at several early stages in the development. Similarly to Luca's
> work, our
> > runtime system is reentrant.
> >
> > As the next step toward a parallel runtime system with a shared heap, we
> are
> > struggling to redefine the tag format. I have two specific questions on
> the
> > compiler and the runtime system. Any comment and help would be greatly
> > appreciated.
> >
> > Question 1.
> >
> > When we reassign tag numbers for block types, the runtime system crashes
> for
> > some applications. We thought we made all necessary changes to the
> source code
> > (in byterun/mlvalues.h, utils/config.mlp, and several files in
> bytecomp/) to
> > reflect the new tag numbers. However the runtime system often crashes,
> for
> > example, when it accesses the Lazy module, which in turn accesses the Obj
> > module, in testsuite/tests/misc/hamming.ml. I wonder what other parts
> in the
> > source code we should revise after reassigning tag numbers.
> >
> > (Our finding is that this is not a problem due to the parallel runtime
> system,
> > as we could reproduce the same outcome on the sequential runtime system.)
> >
> > Question 2.
> >
> > On a 64-bit system, can we safely get rid of the page table, in
> particular
> > caml_page_table_lookup(), if the header of each block is redesigned to
> include
> > a field indicating which memory area it resides (old heap, young heap,
> static
> > data, etc)? I wonder what other purposes the page table serves, other
> than
> > determining the memory area for a given pointer.
> >
> > (Perhaps adding a new field in the header would be too impractical on a
> 32-bit
> > system, but on a 64-bit system, we can affort to allocate quite a few
> bits for
> > new fields in the header. Windows might need the page table to check if
> a given
> > pointer points to code, but luckily we don't need to consider Windows
> for our
> > purpose.)
> >
> > Thank you very much!
> >
> > --- Sungwoo Park
>
> --
> Caml-list mailing list. Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
[-- Attachment #2: Type: text/html, Size: 5768 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Two questions on the OCAML runtime system and compiler,
2013-09-30 14:23 ` Yotam Barnoy
@ 2013-09-30 14:39 ` Yotam Barnoy
0 siblings, 0 replies; 6+ messages in thread
From: Yotam Barnoy @ 2013-09-30 14:39 UTC (permalink / raw)
To: Leo White; +Cc: Sungwoo Park, Ocaml Mailing List
[-- Attachment #1: Type: text/plain, Size: 5133 bytes --]
A simpler option would be to use a hash table, and to put deallocations in
a log with timestamps. When threads access caml_page_table_lookup(), they
write a timestamp into their respective slot. OS block deallocations can
only be carried out when all threads have seen the deallocations in the
hash table already up to the timestamp of the deallocation.
Yotam
On Mon, Sep 30, 2013 at 10:23 AM, Yotam Barnoy <yotambarnoy@gmail.com>wrote:
> From what I understand, Luca's patch is going to be mainstreamed sometime
> in the not-so-distant future, so it might make sense to work directly off
> of his branch, no?
>
> The problem you're having is that every caml_page_table_lookup() needs to
> acquire the heap allocator's lock, right? Perhaps you can make this access
> lockless. If the global page table is a persistent data structure, like a
> Map (but in C of course) and the allocator creates a new data structure
> root every time a block is allocated from/released from the OS, then all
> you would need is a boolean per thread indicating that it's seen the new
> global root before the allocator can go ahead and deallocate whatever
> blocks need to be deallocated from the old persistent trees. Since blocks
> shouldn't be allocated from the OS that frequently, this shouldn't be too
> expensive.
>
> Yotam
>
>
> On Mon, Sep 30, 2013 at 9:24 AM, Leo White <lpw25@cam.ac.uk> wrote:
>
>>
>> We are also experimenting with a parallel OCaml runtime system at
>> OCamlLabs (https://github.com/ocamllabs/ocaml/tree/multicore). Out of
>> interest is the source for your experimental compiler and runtime
>> available
>> anywhere?
>>
>> With respect to the page table, I don't think it serves any other
>> purpose. I know various people have been looking into removing
>> it (or at least removing it from common operations) without the addition
>> of a bit field in the header. So it is possible you could avoid changing
>> the header layout in your version of the compiler as well.
>>
>> Regards,
>>
>> Leo White
>>
>> Sungwoo Park <gla@postech.ac.kr> writes:
>>
>> > Dear Caml users,
>> >
>> > We are currently experimenting with a parallel Ocaml runtime system, in
>> which
>> > each thread maintains its own old and young heaps and runs in parallel
>> with
>> > other threads, without sharing a global lock as in the current Ocaml
>> runtime
>> > system while sharing the whole memory space. We have made changes to the
>> > current Ocaml compiler (4.00.1), and now the parallel compiler generates
>> > parallel code that runs on the parallel Ocaml runtime system. It is a
>> > cross-compiler and we can build it with any version of the Ocaml
>> compiler,
>> > including the parallel compiler itself.
>> >
>> > This is a project very similar to Luca Saiu's reentrant multi-runtime
>> system
>> > (https://github.com/lucasaiu/ocaml), and we benefited very much from
>> Luca's
>> > code at several early stages in the development. Similarly to Luca's
>> work, our
>> > runtime system is reentrant.
>> >
>> > As the next step toward a parallel runtime system with a shared heap,
>> we are
>> > struggling to redefine the tag format. I have two specific questions on
>> the
>> > compiler and the runtime system. Any comment and help would be greatly
>> > appreciated.
>> >
>> > Question 1.
>> >
>> > When we reassign tag numbers for block types, the runtime system
>> crashes for
>> > some applications. We thought we made all necessary changes to the
>> source code
>> > (in byterun/mlvalues.h, utils/config.mlp, and several files in
>> bytecomp/) to
>> > reflect the new tag numbers. However the runtime system often crashes,
>> for
>> > example, when it accesses the Lazy module, which in turn accesses the
>> Obj
>> > module, in testsuite/tests/misc/hamming.ml. I wonder what other parts
>> in the
>> > source code we should revise after reassigning tag numbers.
>> >
>> > (Our finding is that this is not a problem due to the parallel runtime
>> system,
>> > as we could reproduce the same outcome on the sequential runtime
>> system.)
>> >
>> > Question 2.
>> >
>> > On a 64-bit system, can we safely get rid of the page table, in
>> particular
>> > caml_page_table_lookup(), if the header of each block is redesigned to
>> include
>> > a field indicating which memory area it resides (old heap, young heap,
>> static
>> > data, etc)? I wonder what other purposes the page table serves, other
>> than
>> > determining the memory area for a given pointer.
>> >
>> > (Perhaps adding a new field in the header would be too impractical on a
>> 32-bit
>> > system, but on a 64-bit system, we can affort to allocate quite a few
>> bits for
>> > new fields in the header. Windows might need the page table to check if
>> a given
>> > pointer points to code, but luckily we don't need to consider Windows
>> for our
>> > purpose.)
>> >
>> > Thank you very much!
>> >
>> > --- Sungwoo Park
>>
>> --
>> Caml-list mailing list. Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>
>
[-- Attachment #2: Type: text/html, Size: 6698 bytes --]
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] Two questions on the OCAML runtime system and compiler,
[not found] ` <138054732239801.04758.localhost@localhost>
@ 2013-10-01 3:30 ` Sungwoo Park
0 siblings, 0 replies; 6+ messages in thread
From: Sungwoo Park @ 2013-10-01 3:30 UTC (permalink / raw)
To: Leo White; +Cc: caml-list
Thank you for letting me know about your project at OCamlLabs. Our source code
is available at:
https://github.com/qkrgud55/ocamlmulti.git
It is used only internally by our group and is not ready for release yet. So,
it might be hard to follow all the changes.
If the page table has no other purpose, it is a good news for us. Thanks a lot
for the good news :-)
Sincerely,
--- Sungwoo Park
On Mon, 30 Sep 2013, Leo White wrote:
>
> We are also experimenting with a parallel OCaml runtime system at
> OCamlLabs (https://github.com/ocamllabs/ocaml/tree/multicore). Out of
> interest is the source for your experimental compiler and runtime available
> anywhere?
>
> With respect to the page table, I don't think it serves any other
> purpose. I know various people have been looking into removing
> it (or at least removing it from common operations) without the addition
> of a bit field in the header. So it is possible you could avoid changing
> the header layout in your version of the compiler as well.
>
> Regards,
>
> Leo White
>
> Sungwoo Park <gla@postech.ac.kr> writes:
>
>> Dear Caml users,
>>
>> We are currently experimenting with a parallel Ocaml runtime system, in which
>> each thread maintains its own old and young heaps and runs in parallel with
>> other threads, without sharing a global lock as in the current Ocaml runtime
>> system while sharing the whole memory space. We have made changes to the
>> current Ocaml compiler (4.00.1), and now the parallel compiler generates
>> parallel code that runs on the parallel Ocaml runtime system. It is a
>> cross-compiler and we can build it with any version of the Ocaml compiler,
>> including the parallel compiler itself.
>>
>> This is a project very similar to Luca Saiu's reentrant multi-runtime system
>> (https://github.com/lucasaiu/ocaml), and we benefited very much from Luca's
>> code at several early stages in the development. Similarly to Luca's work, our
>> runtime system is reentrant.
>>
>> As the next step toward a parallel runtime system with a shared heap, we are
>> struggling to redefine the tag format. I have two specific questions on the
>> compiler and the runtime system. Any comment and help would be greatly
>> appreciated.
>>
>> Question 1.
>>
>> When we reassign tag numbers for block types, the runtime system crashes for
>> some applications. We thought we made all necessary changes to the source code
>> (in byterun/mlvalues.h, utils/config.mlp, and several files in bytecomp/) to
>> reflect the new tag numbers. However the runtime system often crashes, for
>> example, when it accesses the Lazy module, which in turn accesses the Obj
>> module, in testsuite/tests/misc/hamming.ml. I wonder what other parts in the
>> source code we should revise after reassigning tag numbers.
>>
>> (Our finding is that this is not a problem due to the parallel runtime system,
>> as we could reproduce the same outcome on the sequential runtime system.)
>>
>> Question 2.
>>
>> On a 64-bit system, can we safely get rid of the page table, in particular
>> caml_page_table_lookup(), if the header of each block is redesigned to include
>> a field indicating which memory area it resides (old heap, young heap, static
>> data, etc)? I wonder what other purposes the page table serves, other than
>> determining the memory area for a given pointer.
>>
>> (Perhaps adding a new field in the header would be too impractical on a 32-bit
>> system, but on a 64-bit system, we can affort to allocate quite a few bits for
>> new fields in the header. Windows might need the page table to check if a given
>> pointer points to code, but luckily we don't need to consider Windows for our
>> purpose.)
>>
>> Thank you very much!
>>
>> --- Sungwoo Park
>
>
>
>
>
>
>
>
>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2013-10-01 3:24 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-09-30 12:43 [Caml-list] Two questions on the OCAML runtime system and compiler, Sungwoo Park
2013-09-30 13:24 ` Leo White
2013-09-30 14:23 ` Yotam Barnoy
2013-09-30 14:39 ` Yotam Barnoy
2013-09-30 14:08 ` Jacques-Henri Jourdan
[not found] ` <138054732239801.04758.localhost@localhost>
2013-10-01 3:30 ` Sungwoo Park
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).