We chose 6 projects out of the more than 30 that we received this year.
This page has links to the full text of the accepted proposals.
http://osp.janestcapital.com/wordpress/?p=22
y
--
Yaron Minsky <ymi...@janestcapital.com>
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
The projects look fantastic! Is it really feasible to implement a concurrent
run-time in such a short time?
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e
Hi,
Let me just express my thanks for this initiative -- all of the six
projects you picked are very relevant and address the most pressing
needs of the community!
I have some additional comments on some of these projects:
multicore - I reckon it won't be difficult to find people willing to
test the new GC; but should this project be successful, are there
plans to merge it into mainstream?
menhir - there's another feature that Menhir could benefit from:
better integration with Ulex; I believe that Menhir's developers
have already expressed their intention of doing this -- are there
any developments on that front?
qtcaml - I realise this project aims to complete only the first stage
(it is after all a significant effort); still, it is a huge step
forward, so cheers for that. As previously discussed on this list,
there are many among us who think of Qt as the best toolkit for
developing graphical apps and have therefore longed for Ocaml
bindings.
Cheers,
Dario Teixeira
__________________________________________________________
Sent from Yahoo! Mail.
A Smarter Email http://uk.docs.yahoo.com/nowyoucan.html
We spoke with Xavier before accepting this project. If the project is
successful and the results are of sufficiently high quality, at least
some of the results have a real chance of making it into mainstream.
> menhir - there's another feature that Menhir could benefit from:
> better integration with Ulex; I believe that Menhir's developers
> have already expressed their intention of doing this -- are there
> any developments on that front?
I suggest forwarding any suggestions along those lines to Francois
Pottier, who is mentoring the Menhir project. I have heard nothing on
this front.
> qtcaml - I realise this project aims to complete only the first stage
> (it is after all a significant effort); still, it is a huge step
> forward, so cheers for that. As previously discussed on this list,
> there are many among us who think of Qt as the best toolkit for
> developing graphical apps and have therefore longed for Ocaml
> bindings.
I agree that this is a pretty exciting project if it pans out.
> Cheers,
> Dario Teixeira
>
>
>
> __________________________________________________________
> Sent from Yahoo! Mail.
> A Smarter Email http://uk.docs.yahoo.com/nowyoucan.html
>
--
Yaron Minsky <ymi...@janestcapital.com>
- How "stoppy" would a stop-the-world parallel GC be in practice? The more
parallelism
you have, the more work is done, the higher the frequency of a major
collection.
- Would major allocations be serialized? What about other serialization
points?
- I'm afraid true concurrency will introduce an awful lot of bugs in native
bindings. Thread-unsafe libraries will have to be replaced (Str, etc.)
Also what would be the CPU
and memory costs? Don't concurrent GCs require extra colors?
- In case of performance impacts, will the old single-threaded mode still be
available?
The argument that "you'll get the same old perfomance if you run it in
single-threaded mode"
is not valid IMHO. Many people will use a thread here or there and then you
won't realistically be able to run in single-threaded mode.
But then we can't pretend multi-core doesn't exist. A suggestion: making
the parallel GC available only on 64-bit seems a reasonable restriction (if
that's ever needed.)
Also Damien Doligez (in addition to Xavier Leroy) certainly have nice things
to say about all this.
--
Berke Durak
Nothing so far (actually, we didn't express anything, as far as I know).
That said, I can add your suggestion to the to-do list. I have never
used ulex, so I don't know what needs to be done; suggestions welcome.
How does ocamlyacc support ulex (assuming it does)?
--
François Pottier
Francois...@inria.fr
http://cristal.inria.fr/~fpottier/
All this project are great. I thank Jane St Capital for choosing them.
Maybe, these projects can be hosted in http://forge.ocamlcore.org
Regards,
Sylvain Le Gall
I can understand why you are all excited about parallelism in OCaml, and
most of your questions/suggestions seem relevant.
However, for the technical questions about the choices of the
implementation, it is way too early for us to answer them.
About the bugs in library bindings, I'm afraid you are spotting a really
problematic problem. For example, if I remember well, gtk C functions
have to be called within the same thread in C (which is a smart way for
them to say that their code isn't reentrant), and this may raise a
problem if we add real parallelism to OCaml. But you understand that
rewriting lablgtk and/or programs using it is out of scope.
You also noticed that the task is not trivial, and are concerned about
the feasibility. In fact, we most probably won't have the time to find
the best solution.
So our proposal is to let this project be more "a first reusable step
toward parallelism in OCaml" than "a parallel OCaml".
More practically, we propose the following subtasks:
1. To strip down the current run-time library, rewriting some parts
which are too much dependent on the current GC
2. To clean the (small) parts of the compiler preventing us from
changing the allocator (for example, OCaml inlines some allocations by
directly emitting code which modifies the heap pointer).
3. To define a clean and documented interface for adding new GCs,
ideally adding a run-time switch to choose the GC.
4. To to reinject the current GC, or a simpler sequential GC we
already wrote for another work, using this interface to validate the
approach.
5. To design a first parallel GC, simple enough for us to be able to
test and benchmark it before the end of the project and to implement it
within our interface.
With such an approach, we believe that the projet has a much greater
chance to survive and perhaps be in integrated upstream.
Also, with such a generic GC plugging interface, libraries will be able
to provide specific GCs. For example including some tricks to be able to
run gtk-like non reentrant C calls, or dedicated to tasks which are
currently problematic due to the current allocation mecanism, like
MLGMP.
We'll probably open a blog or wiki to inform you about the progression,
and collect suggestions and concerns.
Regards, and many thanks for your interest.
Benjamin Canou.
> Nothing so far (actually, we didn't express anything, as far as I know).
This topic was discussed some months ago in the context of an OSR:
http://caml.inria.fr/pub/ml-archives/caml-list/2008/01/90d4ab8fcf1d472711d127030ef4cf85.en.html
> That said, I can add your suggestion to the to-do list. I have never
> used ulex, so I don't know what needs to be done; suggestions welcome.
> How does ocamlyacc support ulex (assuming it does)?
It doesn't... ;-) Actually, the guiding example here would be Dypgen,
which allows the user to specify the type of the lexer buffer:
http://dypgen.free.fr/ (See Section 13.5 of the Dypgen manual)
Cheers,
Dario
__________________________________________________________
Sent from Yahoo! Mail.
A Smarter Email http://uk.docs.yahoo.com/nowyoucan.html
_______________________________________________
> - How "stoppy" would a stop-the-world parallel GC be in practice?
> The more parallelism you have, the more work is done, the higher the
> frequency of a major collection.
By Amdahl's law, a stop-the-world GC cannot scale well, but it might
be good enough for 2 to 4 cores. For instance, assuming a sequential
program that spends 25% of its time in garbage collection and
parallelizes with low overhead, you would get a speedup of 2 on
a 4-core machine. A related question is how long it takes to stop a
large number of threads. But only experimentation can tell.
> - I'm afraid true concurrency will introduce an awful lot of bugs in
> native bindings. Thread-unsafe libraries will have to be replaced
> (Str, etc.)
Libraries with stateful APIs (such as Str, but also Hashtbl, etc)
already need user-level locking to be safely used in concurrent programs,
even with today's concurrent-but-not-parallel threading model for Caml.
The only additional problem I can see is with C bindings that expose a
functional API but have global state in their implementation, but I'm
not sure there are many. So, I wouldn't worry too much about this at
the moment. But there are more acute problems with global C state in
the Caml run-time system itself (see below).
> Also what would be the CPU and memory costs? Don't concurrent GCs
> require extra colors?
Not the ones I know.
Benjamin Canou wrote:
> So our proposal is to let this project be more "a first reusable step
> toward parallelism in OCaml" than "a parallel OCaml".
> More practically, we propose the following subtasks:
> 1. To strip down the current run-time library, rewriting some parts
> which are too much dependent on the current GC
> 2. To clean the (small) parts of the compiler preventing us from
> changing the allocator (for example, OCaml inlines some allocations by
> directly emitting code which modifies the heap pointer).
> 3. To define a clean and documented interface for adding new GCs,
> ideally adding a run-time switch to choose the GC.
> 4. To to reinject the current GC, or a simpler sequential GC we
> already wrote for another work, using this interface to validate the
> approach.
> 5. To design a first parallel GC, simple enough for us to be able to
> test and benchmark it before the end of the project and to implement it
> within our interface.
This sounds globally reasonable for a first step, although you should
be careful not to completely shift your objectives from parallelism to
plug-in GCs.
There are two point that I'd like to emphasize. The first step towards
any form of true parallelism in Caml (including message-passing
between threads having their own heaps and sequential GCs) is to clean
up the numerous global C variables that the run-time system uses.
But maybe this was implicit in your point 1.
Another crucial point is the ability to stop all threads and obtain
their roots, which is not obvious at all and a prerequisite for any
form of concurrent garbage collection.
At any rate, it's probably better not to ask too many questions at
this point and let you concentrate on the task at hand. Feel free to
contact me and Damien Doligez for specific questions or general
advice.
- Xavier Leroy
One remark on EasyOCaml:
I think it is essential for a didactic tool that the error messages are easily
localizable. For the purposes I might want to use it, any English error message
is equivalent to "Something is wrong with that program, but I won't tell you what."
Yours, Florian.
--
#!/bin/sh -
set - `type -p $0` 'tr [a-m][n-z]RUXJAKBOZ [n-z][a-m]EH$W/@OBM' fu XUBZRA.fvt\
angher echo;while [ "$5" != "" ];do shift;done;$4 "gbhpu $3;znvy sKunef.qr<$3\
&&frq -a -rc "`$4 "$0"|$1`">$3;rpub 'Jr ner Svtangher bs Obet.'"|$1|`$4 $2|$1`
> By Amdahl's law, a stop-the-world GC cannot scale well, but it might
> be good enough for 2 to 4 cores. For instance, assuming a sequential
> program that spends 25% of its time in garbage collection and
> parallelizes with low overhead, you would get a speedup of 2 on
> a 4-core machine.
No a very bright prospect. Many people already have dual cores under their desks,
so quad cores should be the norm in a year or two. I'd hate to see Ocaml
become one of the slower languages.
> A related question is how long it takes to stop a
> large number of threads. But only experimentation can tell.
> ..
> Another crucial point is the ability to stop all threads and obtain
> their roots, which is not obvious at all and a prerequisite for any
> form of concurrent garbage collection.
Stopping the world in our heavily threaded ExaVM for GC is quite painful
since the threads often run in native C/C++ code which naturally
has no business checking the stop condition as often as Exascript code,
giving very poor performance on multi-core machines (we got something like
10-15% CPU usage on a 32-core machine)
XL:
> There are two points that I'd like to emphasize. The first step towards
> any form of true parallelism in Caml (including message-passing
> between threads having their own heaps and sequential GCs) is to clean
> up the numerous global C variables that the run-time system uses.
> But maybe this was implicit in your point 1.
Besides moving the interpreter/runtime global state into some datastructure,
what about emitted asm code that references things like caml_young_limit?
Those would have to be made thread-specific. Why not allocate one or two
of these extra x86-64 registers for storing those?
That could also be an occasion to "librarify" the interpreter in order to
allow multiple Ocaml interpreters/run-times to execute in the same process (with
disjoint heaps).
That way one could embed multiple Ocaml libraries in programs written in other
languages (which could allow easier monetization of Ocaml software ;).
Also, we could explore alternate paths to paralellism, such as running multiple
Ocaml interpreters/runtimes in different threads with disjoint heaps.
Those threads would run truly in parallel on different CPUs.
Then, we could try different custom solutions for cheap inter-thread communication.
For example, we could write a Marshal derivative that emits a simpler inter-thread
representation. It would work under the hypothesis that the deserializing process
runs the same code as the serializing one, on the same machine, at the same time.
This would allow to remove some serialization overhead:
- No need to compact integers for a byte-based serialization format
- No need to worry about endianness or float representations
- No need to outputting or verify program MD5s for functions
- Native data could be passed as-is.
Thus we would have one process running n threads, but those threads having disjoint
heap spaces, allowing for fully parallel GC and execution (distinct heap spaces mean reduced
cache/bus contention), exchanging data in shared memory thru an inter-thread
Marshal module.
(Note that using n processes with shared memory would not be
as convenient:
- You'd need to set up shared memory segment using IPC, /dev/shm or other
unportable, OS-specific mechanisms.
- You won't be able to use native multi-threaded libraries
- You won't be able to share file desriptors or common C code/data.
- You won't be able to use inter-thread signaling/synchronization mechanisms,
for your implementation)
People would then write libraries for shared immutable data, or a shared store,
probably using a STM-like approach. Those could probably be written in Ocaml.
Also some POSIX thread synchronization mechanisms (mutexes, etc.) could be exposed
as Ocaml types.
As for the interpreter threads, they could use lightweight threads or classic Ocaml
serializing threads for their internal non-parallel concurrency.
I personally don't believe much in fine-grained parallelism using threads and locks
because it makes the GC difficult, relies on the notoriously difficult to use and
non-composable synchronization mechanisms such as locks and mutexes, doesn't
scale to distributed computing, and doesn't run as fast as most people think it would
because of bus/cache contention.
> At any rate, it's probably better not to ask too many questions at
> this point and let you concentrate on the task at hand. Feel free to
> contact me and Damien Doligez for specific questions or general
> advice.
I certainly don't want to discourage anyone from writing a parallel GC!
--
Berke DURAK
The dual core Athlon64 X2 CPUs used in our machines were released three years
ago.
> so quad cores should be the norm in a year or two.
Quad cores are already the norm.
An *eight* core Dell Precision T7400 now costs only £1,171. Our desktop
machines will be replaced with these eight core machines before the end of
this year.
> I'd hate to see Ocaml become one of the slower languages.
For many applications, that already happened.
> That way one could embed multiple Ocaml libraries in programs written in
> other languages (which could allow easier monetization of Ocaml software
> ;).
There are many other issues that prevent the commercialization of OCaml
libraries.
> Also, we could explore alternate paths to paralellism, such as running
> multiple Ocaml interpreters/runtimes in different threads with disjoint
> heaps. Those threads would run truly in parallel on different CPUs.
Communication is too slow for that to be useful outside a few niche
applications.
> I personally don't believe much in fine-grained parallelism using threads
> and locks because it makes the GC difficult,
This is certainly a difficult problem but you cannot compete without a
concurrent GC now.
> relies on the notoriously difficult to use and non-composable
> synchronization mechanisms such as locks and mutexes,
Locks are actually very usable in F# thanks to the ubiquity of immutable data
structures and the availability of higher-order functions.
Microsoft's Task Parallel Library (TPL) for .NET makes data parallelism
without explicit locks even easier.
> doesn't scale to distributed computing,
Irrelevant. The vast majority of people have multicore machines and not
distributed clusters. Distributed computing may become importantant in
desktop machines when we exceed 256 cores but that will not happen in the
next decade.
> and doesn't run as fast as most people think it would because of bus/cache
> contention.
With the latest version of .NET, F# now beats OCaml on most benchmarks.
> I certainly don't want to discourage anyone from writing a parallel GC!
Indeed, a concurrent GC is essential for the survival of the OCaml language,
whether that culminates from this project or is "borrowed" by OCamlJava.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e
_______________________________________________