[eurolisp] http://www.dirkgerrits.com/erlisp/roadmap.html
Dirk wrote:
Is it just because threads with shared memory and locking are the best we can do for parallelism, and because socket and RPC libraries are totally adequate for distributed programming? I think the answer is no.
So do I. Therefore I was disappointed by your roadmap which talks a lot about OS threads and special (thread-local) variables. Recently I came again across Lightweight Languages Workshop 2002 http://ll2.ai.mit.edu/ You'll notice that Joe Armstrong's web server starts where Apache has already broken down due to too many concurrent users. I you go with OS threads, you'll never get there. I reread part's of Graham's On Lisp yesterday. There's one section where he mentions that a completely unperformant but working thing is still valuable to start with because it allows experimentation (similar topic idea in the article about the failure of the NIL machine/project). The reason why I want to depart from OS threads is because I expect different ways of computing arise when "threads" are extremely light weight (as in Erlang or Oz, not in UNIX), like different ways of computing arose when stack space became cheap or when memory became cheap. I.e. these days, many GNU programs allocate a few MB on the stack without shame, and programs long do in memory only what once were expensive disk-bound operations. This allows different algorithms to be used to address problems. OTOH maybe one can wait until a typical Linux can fork a 300000 threads on a 256MB machine (I haven't checked how far StateThreads and the other approaches can go). That's ~1KB per thread! Cf. http://c2.com/cgi/wiki?MessagingAsAlternativeToMultiThreading Regards, Jörg Höhle. PS: I didn't see a comp.lang.lisp thread, nor a wiki/message forum on your site and I still think eurolisp is not the right forum for this.
"Hoehle, Joerg-Cyril" <Joerg-Cyril.Hoehle@t-systems.com> writes:
Therefore I was disappointed by your roadmap which talks a lot about OS threads and special (thread-local) variables.
Sorry to hear that, care to elaborate?
Recently I came again across Lightweight Languages Workshop 2002 http://ll2.ai.mit.edu/ You'll notice that Joe Armstrong's web server starts where Apache has already broken down due to too many concurrent users. I you go with OS threads, you'll never get there.
Well OS threads are just the easiest way that Lisp offers me to implement these abstractions. As I wrote in my roadmap, I see two ways to later improve performance: * Using continuations as green threads. This would limit the points at which processes can be preempted, but that can be partially alleviated by assigning an operating system thread to every few green threads. Also, less preemption is not necessarily a problem. I've already done some work on this, but I'm currently swamped in school work. * Hacking the Common Lisp implementation. If SBCL would have more light-weight threads, then so would Erlisp. Alternatively, Erlisp could be ported to CLISP, where light-weight processes could be added to the virtual machine from scratch. CLISP also has a socket library so porting Erlisp's distribution aspects should be straightforward." This is something I'd prefer not to do, but I see no way around it if I want to match or surpass Erlang's performance. (And I /do/ want to. I apologize if my website gave you the wrong idea.)
I reread part's of Graham's On Lisp yesterday. There's one section where he mentions that a completely unperformant but working thing is still valuable to start with because it allows experimentation (similar topic idea in the article about the failure of the NIL machine/project).
That's the reason I am using OS threads at all. On Lisp's CPS macros are just not satisfactory, and a CPS code walker is more work than using an OS thread library. So I'm going to get something up and running with threads first (roadmap step 1) and then make it fast with a CPS code walker / CL implementation hacking / whatever (roadmap step 3). In fact, I think I might swap step 2 and 3 as performance in parallelism is currently more important to me than distribution.
The reason why I want to depart from OS threads is because I expect different ways of computing arise when "threads" are extremely light weight (as in Erlang or Oz, not in UNIX), like different ways of computing arose when stack space became cheap or when memory became cheap.
I am convinced of that as well. Otherwise I wouldn't see a real need for Erlisp, as a standard OS threading API would have been enough.
I.e. these days, many GNU programs allocate a few MB on the stack without shame, and programs long do in memory only what once were expensive disk-bound operations. This allows different algorithms to be used to address problems.
OTOH maybe one can wait until a typical Linux can fork a 300000 threads on a 256MB machine (I haven't checked how far StateThreads and the other approaches can go). That's ~1KB per thread!
That would be a great thing for the GNU/Linux crowd, myself included, but it wouldn't really solve anything for the rest of the world.
Cf. http://c2.com/cgi/wiki?MessagingAsAlternativeToMultiThreading
Thanks for the reference, I'll check it out.
PS: I didn't see a comp.lang.lisp thread, nor a wiki/message forum on your site and I still think eurolisp is not the right forum for this.
I did post at comp.lang.lisp: http://groups.google.com/groups?selm=87acurudww.fsf%40dirkgerrits.com&rnum=1 but there have been absolutely no replies there. I agree that a better place for discussion is needed. How about a common-lisp.net mailing list? Kind regards, Dirk Gerrits
On Wed, 03 Nov 2004 15:18:30 +0100, Dirk Gerrits <dirk@dirkgerrits.com> wrote:
I agree that a better place for discussion is needed. How about a common-lisp.net mailing list?
Maybe Clump? <http://www.caddr.com/clump/> Cheers, Edi.
Edi Weitz <edi@agharta.de> writes:
On Wed, 03 Nov 2004 15:18:30 +0100, Dirk Gerrits <dirk@dirkgerrits.com> wrote:
I agree that a better place for discussion is needed. How about a common-lisp.net mailing list?
Maybe Clump?
Sounds good to me. Thanks for the pointer Edi. Anyone opposed? Kind regards, Dirk Gerrits
: "Hoehle, Joerg-Cyril" <Joerg-Cyril.Hoehle@t-systems.com> : Dirk Gerrits <dirk@dirkgerrits.com>
Therefore I was disappointed by your roadmap which talks a lot about OS threads and special (thread-local) variables.
Sorry to hear that, care to elaborate?
After a few tens of thousands of threads (may hundreds of thousands, on modern machines with several gibibytes of RAM?), the performance of most (all) Unix kernels becomes very bad. If only because each thread eats at the very least a few kilobytes of kernel memory, and ultimately the machine runs out of memory. Green thread have a potentially much lower overhead.
* Using continuations as green threads. This would limit the points at which processes can be preempted, but that can be partially alleviated by assigning an operating system thread to every few green threads. Also, less preemption is not necessarily a problem.
With sufficient engineering and code-walking, preemption can remain possible. However, preemption necessitates proper handling of invariants, with locking, roll-back and/or roll-forward. As a cheaper way to do things, cooperative multithreading can do, and can be used automatically or semi-automatically. (Only potentially long-running routines need have (yield) statements inserted, and with proper code-walking, this can be done automatically.)
and a CPS code walker is more work than using an OS thread library. There already are CPS code walkers, in Screamer and in UCW.
Cf. http://c2.com/cgi/wiki?MessagingAsAlternativeToMultiThreading
http://groups.google.com/groups?selm=87acurudww.fsf%40dirkgerrits.com&rnum=1
I agree that a better place for discussion is needed. How about a common-lisp.net mailing list? If you create it, please subscribe me :)
[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] ... Any resemblance between the above views and those of my employer, my terminal, or the view out my window are purely coincidental. Any resemblance between the above and my own views is non-deterministic. The question of the existence of views in the absence of anyone to hold them is left as an exercise for the reader. The question of the existence of the reader is left as an exercise for the second god coefficient. (A discussion of non-orthogonal, non-integral polytheism is beyond the scope of this article.)
Hi guys. First of all, thanks for your input. Second, I owe you an apology for wasting your time. A lot of what you have supplied me with in this thread was already known to me, but I failed to make that evident on my site. Faré <fahree@gmail.com> writes:
: "Hoehle, Joerg-Cyril" <Joerg-Cyril.Hoehle@t-systems.com> : Dirk Gerrits <dirk@dirkgerrits.com>
Therefore I was disappointed by your roadmap which talks a lot about OS threads and special (thread-local) variables.
Sorry to hear that, care to elaborate?
After a few tens of thousands of threads (may hundreds of thousands, on modern machines with several gibibytes of RAM?), the performance of most (all) Unix kernels becomes very bad. If only because each thread eats at the very least a few kilobytes of kernel memory, and ultimately the machine runs out of memory. Green thread have a potentially much lower overhead.
I was more interested in the special variables comment, and about my roadmap talking "a lot" about OS threads. I realize now that I did not make that clear *at all* in my reply. Sorry.
* Using continuations as green threads. This would limit the points at which processes can be preempted, but that can be partially alleviated by assigning an operating system thread to every few green threads. Also, less preemption is not necessarily a problem.
With sufficient engineering and code-walking, preemption can remain possible.
I do not see how a process calling a Common Lisp sequence function on a large array can be preempted by sufficient engineering and code-walking. But please enlighten me, I'm just a newbie. If you meant that preemption in user functions is possible, then I think I know what you mean. In Erlang implementation, it is customary (as far as I have been able to tell so far) to have a "reduction counter" that gets decremented on every function call. When it reaches zero, the process is preempted and another process gets a chance to run, with a reset reduction counter. This shouldn't be too hard to implement in a CPS code walker, but I worry about its performance. Nevertheless, it is something I'm planning to try, as only trying it out can give me any real data on its performance.
However, preemption necessitates proper handling of invariants, with locking, roll-back and/or roll-forward. As a cheaper way to do things, cooperative multithreading can do, and can be used automatically or semi-automatically. (Only potentially long-running routines need have (yield) statements inserted, and with proper code-walking, this can be done automatically.)
What I have considered doing is to have cooperative multithreading that yields /only/ on Erlang's receive statements. I'm curious as to whether that is really as bad as it sounds. I could indeed have extra yields be added automatically, but that may be more tricky than you make it sound (or maybe I'm misinterpreting). For example, putting a yield in a tight loop might kill performance, and not putting it there might kill cooperation. Trying to solve this would bring us pretty close to the above reduction counter, wouldn't you agree?
and a CPS code walker is more work than using an OS thread library. There already are CPS code walkers, in Screamer and in UCW.
I've looked at those in Arnesi, UCW, and Screamer in the past and know that I can't use them out-of-the-box. But I could "borrow" some code and adapt it to my purposes, is that what you suggest? I am not opposed to that, althoug I think that may deprive me of a valuable Common Lisp learning experience.
Cf. http://c2.com/cgi/wiki?MessagingAsAlternativeToMultiThreading
http://groups.google.com/groups?selm=87acurudww.fsf%40dirkgerrits.com&rnum=1
I agree that a better place for discussion is needed. How about a common-lisp.net mailing list? If you create it, please subscribe me :)
After Edi's suggestion, I subscribed myself to CLUMP (http://www.caddr.com/clump/). Do you think that is a good place to continue this discussion (and future Erlisp discussions?). Kind regards, Dirk Gerrits
I could indeed have extra yields be added automatically, but that may be more tricky than you make it sound (or maybe I'm misinterpreting). For example, putting a yield in a tight loop might kill performance, and not putting it there might kill cooperation. Trying to solve this would bring us pretty close to the above reduction counter, wouldn't you agree?
Have you tried yielding only on function entry and all backward branches?
Toomas Altosaar <Toomas.Altosaar@hut.fi> writes:
I could indeed have extra yields be added automatically, but that may be more tricky than you make it sound (or maybe I'm misinterpreting). For example, putting a yield in a tight loop might kill performance, and not putting it there might kill cooperation. Trying to solve this would bring us pretty close to the above reduction counter, wouldn't you agree?
Have you tried ...
I have not tried anything at all so far. I've been swamped in schoolwork. Should be better in a week or two though.
... yielding only on function entry and all backward branches?
Hadn't thought of that yet. Thanks for the tip. Kind regards, Dirk Gerrits
On Wed, 03 Nov 2004 18:53:34 +0100, Dirk Gerrits <dirk@dirkgerrits.com> wrote:
... yielding only on function entry and all backward branches? Hadn't thought of that yet. Thanks for the tip. That's the trick notably used in RScheme, if my memory serves well. Of course, as soon as you have shared resources or any kind of synchronization that isn't encapsulated in messages (e.g. GC state, etc.), you may need more advanced techniques and/or criteria.
[ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] If atheism is a religion, then not collecting stamps is a hobby.
...
I agree that a better place for discussion is needed. How about a common-lisp.net mailing list? ...
I am very happy to find these hints (and discussions) here even if they might be slightly OT. Andreas
Hi since you guys are looking at threading issues, I would suggest that you dig up some of the old EcoLISP threading things by Giuseppe Attardi. I do not know how much of it survives in ECL, but it is worth looking up. If memory does not fail me it had a very much continuation-style concurrency model. Cheers Marco On Nov 3, 2004, at 8:17 AM, Hoehle, Joerg-Cyril wrote:
Dirk wrote:
Is it just because threads with shared memory and locking are the best we can do for parallelism, and because socket and RPC libraries are totally adequate for distributed programming? I think the answer is no.
So do I. Therefore I was disappointed by your roadmap which talks a lot about OS threads and special (thread-local) variables. Recently I came again across Lightweight Languages Workshop 2002 http://ll2.ai.mit.edu/ You'll notice that Joe Armstrong's web server starts where Apache has already broken down due to too many concurrent users. I you go with OS threads, you'll never get there.
I reread part's of Graham's On Lisp yesterday. There's one section where he mentions that a completely unperformant but working thing is still valuable to start with because it allows experimentation (similar topic idea in the article about the failure of the NIL machine/project).
The reason why I want to depart from OS threads is because I expect different ways of computing arise when "threads" are extremely light weight (as in Erlang or Oz, not in UNIX), like different ways of computing arose when stack space became cheap or when memory became cheap. I.e. these days, many GNU programs allocate a few MB on the stack without shame, and programs long do in memory only what once were expensive disk-bound operations. This allows different algorithms to be used to address problems.
OTOH maybe one can wait until a typical Linux can fork a 300000 threads on a 256MB machine (I haven't checked how far StateThreads and the other approaches can go). That's ~1KB per thread! Cf. http://c2.com/cgi/wiki?MessagingAsAlternativeToMultiThreading
Regards, Jörg Höhle. PS: I didn't see a comp.lang.lisp thread, nor a wiki/message forum on your site and I still think eurolisp is not the right forum for this.
_______________________________________________ eurolisp site list eurolisp@common-lisp.net http://common-lisp.net/mailman/listinfo/eurolisp
-- Marco Antoniotti http://bioinformatics.nyu.edu NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 715 Broadway 10th FL fax. +1 - 212 - 998 3484 New York, NY, 10003, U.S.A.
Hi Marco, Marco Antoniotti <marcoxa@cs.nyu.edu> writes:
since you guys are looking at threading issues, I would suggest that you dig up some of the old EcoLISP threading things by Giuseppe Attardi. I do not know how much of it survives in ECL, but it is worth looking up. If memory does not fail me it had a very much continuation-style concurrency model.
Well I found this: http://www.di.unipi.it/~attardi/software.html. Includes source code and documentation. I couldn't get the manual to build properly, but I read the raw LaTeX on the multithreading. Thanks for the pointer. Kind regards, Dirk Gerrits
On Nov 3, 2004, at 1:28 PM, Dirk Gerrits wrote:
Hi Marco,
Marco Antoniotti <marcoxa@cs.nyu.edu> writes:
since you guys are looking at threading issues, I would suggest that you dig up some of the old EcoLISP threading things by Giuseppe Attardi. I do not know how much of it survives in ECL, but it is worth looking up. If memory does not fail me it had a very much continuation-style concurrency model.
Well I found this: http://www.di.unipi.it/~attardi/software.html. Includes source code and documentation. I couldn't get the manual to build properly, but I read the raw LaTeX on the multithreading. Thanks for the pointer.
Sure. You are welcome. Cheers -- Marco Antoniotti http://bioinformatics.nyu.edu NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 715 Broadway 10th FL fax. +1 - 212 - 998 3484 New York, NY, 10003, U.S.A.
I will be in Milano tomorow afternoon. (I'm going back at 18h (Linate airport)) Any Milano Lisper in the area to have a drink? Marc
I won't be there, but I can suggest the Bar Basso on Viale Abruzzi :) Ciao Marco On Nov 8, 2004, at 10:58 AM, Marc Battyani wrote:
I will be in Milano tomorow afternoon. (I'm going back at 18h (Linate airport)) Any Milano Lisper in the area to have a drink?
Marc
_______________________________________________ eurolisp site list eurolisp@common-lisp.net http://common-lisp.net/mailman/listinfo/eurolisp
-- Marco Antoniotti http://bioinformatics.nyu.edu NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 715 Broadway 10th FL fax. +1 - 212 - 998 3484 New York, NY, 10003, U.S.A.
I won't be there, but I can suggest the Bar Basso on Viale Abruzzi :)
You were from Milano before NYC ? Marc
On Nov 8, 2004, at 10:58 AM, Marc Battyani wrote:
I will be in Milano tomorow afternoon. (I'm going back at 18h (Linate airport)) Any Milano Lisper in the area to have a drink?
Marc
On Nov 8, 2004, at 11:17 AM, Marc Battyani wrote:
I won't be there, but I can suggest the Bar Basso on Viale Abruzzi :)
You were from Milano before NYC ?
Yep. Actually I am from Piedmont. Just to put those Lomdards in their places. :) If it weren't for us they'd still be part of the Hapsburg Empire. :) Cheers -- Marco Antoniotti http://bioinformatics.nyu.edu NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 715 Broadway 10th FL fax. +1 - 212 - 998 3484 New York, NY, 10003, U.S.A.
On Monday 08 November 2004 20:06, Marco Antoniotti wrote:
On Nov 8, 2004, at 11:17 AM, Marc Battyani wrote:
I won't be there, but I can suggest the Bar Basso on Viale Abruzzi :)
You were from Milano before NYC ?
Yep. Actually I am from Piedmont. Just to put those Lomdards in their places. :) If it weren't for us they'd still be part of the Hapsburg Empire. :)
Hey, wasn't Umberto Ecco from Piedmont, too?
Ivan Toshkov <ivan@toshkov.org> writes:
Hey, wasn't Umberto Ecco from Piedmont, too?
Umberto Eco was born in Alessandria, in the region of Piemonte (aka piedmont). Alessandro Baricco (author of `Silk' and `Ocean Sea') is from Torino (which is the captial of Piemonte). Nietzsche lived in Torino while he wrote 'Der Antichrist' (the antichrist) and showed his first symptomes of mental illness there. and my mom is from torino too! :) -- -Marco Ring the bells that still can ring. Forget your perfect offering. There is a crack in everything. That's how the light gets in. -Leonard Cohen
On Nov 9, 2004, at 4:37 AM, Marco Baringer wrote:
Ivan Toshkov <ivan@toshkov.org> writes:
Hey, wasn't Umberto Ecco from Piedmont, too?
Umberto Eco was born in Alessandria, in the region of Piemonte (aka piedmont). Alessandro Baricco (author of `Silk' and `Ocean Sea') is from Torino (which is the captial of Piemonte). Nietzsche lived in Torino while he wrote 'Der Antichrist' (the antichrist) and showed his first symptomes of mental illness there. and my mom is from torino too! :)
Not to speak of the fantastic Cinema Museum in the "Mole Antonelliana" which is the most recognizable symbol of Turin which was originally commissioned to be main synagogue of the city. It would have been one one of the biggest synagogues of Europe, I believe. Ok. I forgot FIAT :) Cheers Marco -- Marco Antoniotti http://bioinformatics.nyu.edu NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488 715 Broadway 10th FL fax. +1 - 212 - 998 3484 New York, NY, 10003, U.S.A.
participants (10)
-
Andreas Thiele -
Dirk Gerrits -
Edi Weitz -
Faré -
Hoehle, Joerg-Cyril -
Ivan Toshkov -
Marc Battyani -
Marco Antoniotti -
Marco Baringer -
Toomas Altosaar