[Caml-list] Request: matrix_init function in Array

[Caml-list] Request: matrix_init function in Array

[Brian Hurt]

Any possibility we could add the following function to the Array module?

val matrix_init : int -> int -> (int -> int -> 'a) -> 'a array array

let matrix_init rows cols f =
    let g i = init cols (f i)
    in
    init rows g
;;

Actually, I'm not sure if the function should be matrix_init or 
init_matrix.  And I don't care either way.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Request: matrix_init function in Array

[Pierre Weis]

> Any possibility we could add the following function to the Array module?
> 
> val matrix_init : int -> int -> (int -> int -> 'a) -> 'a array array
> 
> let matrix_init rows cols f =
>     let g i = init cols (f i)
>     in
>     init rows g
> ;;
> 
> Actually, I'm not sure if the function should be matrix_init or 
> init_matrix.  And I don't care either way.
> 
> Brian

I think we need a Matrix module, such that it would be Matrix.init,
Matrix.make, and so on.

This would be much more convenient for beginners that are always
caught by the famous Array.make raw (Array.make column 0.0).

Hope this helps.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Request: matrix_init function in Array

[Chris Hecker]

>I think we need a Matrix module, such that it would be Matrix.init,
>Matrix.make, and so on.

I think there are way more important things to work on than a mostly 
useless and wimpy generic matrix library.

Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Request: matrix_init function in Array

[Pierre Weis]

> >I think we need a Matrix module, such that it would be Matrix.init,
> >Matrix.make, and so on.
> 
> I think there are way more important things to work on than a mostly 
> useless and wimpy generic matrix library.

I don't agree with you: a Matrix module would definitively end
questions and requests on trivial functionality about matrices. This
is a tremendously important goal to achieve, since answering to those
questions is indeed a waste of time for us: there are way more
important things to work on than answering to silly questions and
remarks on the Caml list about matrices (including induced remarks
about what is (or is not) an important thing to work on).

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Request: matrix_init function in Array

[Chris Hecker]

>I don't agree with you: a Matrix module would definitively end
>questions and requests on trivial functionality about matrices.

I just reviewed 10384 messages to caml-list from the past 2 years.  Of 
around 40 separate questions containing the word "matrix", only 3 (or 5 
being incredibly generous) would even be affected by having a Matrix 
module, and it's not clear they'd be answered.  And that's ignoring any new 
questions that might be generated by the module's existence itself if it's 
implemented.

The point is that a) there are just not many questions pertaining to this 
topic, and b) any Matrix module you guys implemented would either be a toy, 
or it'd take forever to write and still not please people who really use 
matrices for real work (which account for 90% of the questions referenced 
above).

As far as I can tell (unless I'm missing a bunch of caml-list messages), 
the questions relating to this on the caml-list are simply not worth a 
Matrix module that takes even just a couple days of the core caml team's 
time.  I can name probably 20 equivalently sized tasks that would help way 
more people who are trying to use caml and answer way more future 
questions, and that only the core team can do.

Now, if you just have a hankering to write a matrix module, that's cool, go 
for it.  But if you goal is to spend 2 days and solve as many caml 
programmers' problems as possible, this is not the place to spend it.

How about this as a counterproposal:  I will personally, promptly, and 
tirelessly answer any and all matrix related questions on the caml-list for 
the remainder of 2003 if you will work on something more important?  :)

The key thing is that anybody on this list could write the Matrix 
module.  There are lots of things that only the core caml team can do.

Okay, I'm done wasting your time.  Sorry if this came off as rude, I didn't 
intend it that way.

Thanks,
Chris


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

feature priorities (was Re: [Caml-list] Request: matrix_init function in Array)

[Ed L Cashin]

Chris Hecker <checker@d6.com> writes:

...
> I can name probably 20 equivalently sized
> tasks that would help way more people who are trying to use caml and
> answer way more future questions, and that only the core team can do.

As a new ocaml user, the two biggest missing features appear to be 

  1) a.) no multi-threading support where threads would migrate
         between processors 
     b.) ... which has underlying it: no MT-safe (and efficient)
         garbage collector 

  2) ocamlopt-generated programs cannot dynamically load
     ocamlopt-generated code.

Please correct me if I'm wrong about these two.  I don't know whether
people are already working on this or even if anyone cares about these
features.  I gave a presentation on ocaml to a linux user group
recently, and these two are the only shortcomings I could identify.
Everything else was radient praise.

-- 
--Ed L Cashin            |   PGP public key:
  ecashin@uga.edu        |   http://noserose.net/e/pgp/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Request: matrix_init function in Array

[Brian Hurt]

Here's my problem with a matrix module: when I see a module named Matrix,
I immediately think linear algebra- BLAS.  A full-on BLAS implementation
might be usefull, but probably way more work than most people think it 
would be to do right.  Oh, doing it the obvious way would be simple enough 
for anyone who passed linear algebra.  Doing it right gives you a 10x or 
better speed up.

Two papers anyone who *wants* to do a full-on Ocaml BLAS should read 
(IMHO) are:

http://citeseer.nj.nec.com/luj00oolala.html
(BLAS isn't the only, or necessarily even the best, interface)

http://www.irisa.fr/bibli/publi/pi/1994/803/803.html
(Shows the importance of blocking *and* copying in matrix operations)

Throw in vectorizing kernels using SSE-2, and you've got yourself a fair 
bit of work there.

Brian

On Thu, 13 Feb 2003, Chris Hecker wrote:

> 
> >I don't agree with you: a Matrix module would definitively end
> >questions and requests on trivial functionality about matrices.
> 
> I just reviewed 10384 messages to caml-list from the past 2 years.  Of 
> around 40 separate questions containing the word "matrix", only 3 (or 5 
> being incredibly generous) would even be affected by having a Matrix 
> module, and it's not clear they'd be answered.  And that's ignoring any new 
> questions that might be generated by the module's existence itself if it's 
> implemented.
> 
> The point is that a) there are just not many questions pertaining to this 
> topic, and b) any Matrix module you guys implemented would either be a toy, 
> or it'd take forever to write and still not please people who really use 
> matrices for real work (which account for 90% of the questions referenced 
> above).
> 
> As far as I can tell (unless I'm missing a bunch of caml-list messages), 
> the questions relating to this on the caml-list are simply not worth a 
> Matrix module that takes even just a couple days of the core caml team's 
> time.  I can name probably 20 equivalently sized tasks that would help way 
> more people who are trying to use caml and answer way more future 
> questions, and that only the core team can do.
> 
> Now, if you just have a hankering to write a matrix module, that's cool, go 
> for it.  But if you goal is to spend 2 days and solve as many caml 
> programmers' problems as possible, this is not the place to spend it.
> 
> How about this as a counterproposal:  I will personally, promptly, and 
> tirelessly answer any and all matrix related questions on the caml-list for 
> the remainder of 2003 if you will work on something more important?  :)
> 
> The key thing is that anybody on this list could write the Matrix 
> module.  There are lots of things that only the core caml team can do.
> 
> Okay, I'm done wasting your time.  Sorry if this came off as rude, I didn't 
> intend it that way.
> 
> Thanks,
> Chris
> 
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: feature priorities (was Re: [Caml-list] Request: matrix_init function in Array)

[brogoff]

I'm of the opinion that the implementors know best how to set their   
priorities, so I don't feel compelled to volunteer their time for the 
projects I find important. It's like that sign around the public swimming 
pools when I was growing up which said something like "Don't pee in our pool 
and we won't swim in your toilet." 

That said, it would be nice if there were some sort of roadmap which mentioned 
what was being planned for the future, with the understanding that anything 
could change, that there would be no hard dates for features, and that whiners 
who kept haranguing the list about their favorite feature would be shot in the 
stomach, rolled in honey, and staked to a fire-ant mound in the desert sun. 

My own short-list is very different from Ed's, as I don't care too much about 
multithreading right now. Also, I try to separate *language* features from 
implementation/library features. So, while I'd love it if I could call 
ocamlopt generated native code from bytecode programs, or have a MLton style 
supre-duper global optimizer, or have unsafe ops in Bigarray, those aren't on 
my short list. So, at the risk of exposing myself to the punishment I describe 
above, here it is, in roughly descending priority, with the caveat that I may 
change my mind at any time

(1) Extensional polymorphism, since that brings type safe value IO, 
    overloading, and dynamics to ML. 
(2) Some way to make type definitions which had a type expression and a 
    functor instantiation in a recursive relationship. I suppose that for 
    all intents and purposes that is the same as recursive modules. 
(3) More polymorphic records, a la SML#, or something like that. 
(4) Some way to extend the class of tail recursive functions, as discussed 
    recently in this list. 

-- Brian

PS: If you want to flame about my choices, at least do so in a useful manner. 
    At least it's a more interesting topic to me than the endless license 
    flamewar ;-).

On Thu, 13 Feb 2003, Ed L Cashin wrote:
> Chris Hecker <checker@d6.com> writes:
> 
> ...
> > I can name probably 20 equivalently sized
> > tasks that would help way more people who are trying to use caml and
> > answer way more future questions, and that only the core team can do.
> 
> As a new ocaml user, the two biggest missing features appear to be 
> 
>   1) a.) no multi-threading support where threads would migrate
>          between processors 
>      b.) ... which has underlying it: no MT-safe (and efficient)
>          garbage collector 
> 
>   2) ocamlopt-generated programs cannot dynamically load
>      ocamlopt-generated code.
> 
> Please correct me if I'm wrong about these two.  I don't know whether
> people are already working on this or even if anyone cares about these
> features.  I gave a presentation on ocaml to a linux user group
> recently, and these two are the only shortcomings I could identify.
> Everything else was radient praise.
> 
> -- 
> --Ed L Cashin            |   PGP public key:
>   ecashin@uga.edu        |   http://noserose.net/e/pgp/
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: feature priorities (was Re: [Caml-list] Request: matrix_init function in Array)

[rich]

Can I add my own rather more real-world feature requests!

1) A common database interface. Something like the Perl DBI would
   be ideal. (In fact I've been thinking about writing this myself,
   but I'm not really experienced enough with OCAML yet).

2) A solid Apache/OCAML API. It should at least allow you to write
   CGI scripts, *and* have the bytecode cached in memory*. Ideally it
   would expose the full Apache API like mod_perl.

This is just my take on the situation, and I know that the OCAML
guys have much more important things to do :-)

Rich.

* I'm pretty sure mod_ocaml doesn't do this at the moment, but my
apologies if I'm wrong ...

-- 
Richard Jones, Red Hat Inc. (London, UK) http://www.redhat.com/software/ccm
http://www.annexia.org/ Freshmeat projects: http://freshmeat.net/users/rwmj
C2LIB is a library of basic Perl/STL-like types for C. Vectors, hashes,
trees, string funcs, pool allocator: http://www.annexia.org/freeware/c2lib/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: feature priorities (was Re: [Caml-list] Request: matrix_init function in Array)

[Alessandro Baretta]

rich@annexia.org wrote:
> Can I add my own rather more real-world feature requests!
> 
> 1) A common database interface. Something like the Perl DBI would
>    be ideal. (In fact I've been thinking about writing this myself,
>    but I'm not really experienced enough with OCAML yet).
> 
> 2) A solid Apache/OCAML API. It should at least allow you to write
>    CGI scripts, *and* have the bytecode cached in memory*. Ideally it
>    would expose the full Apache API like mod_perl.

I have worked on both needs myself. The two projects are 
still at a very early stage, but both work pretty well and 
have already been used in a commercial project. I plan on 
releasing the two packages as soon as my new leased line is 
up and my web site will be accessibile. This might take 
another month, but if you're in a real hurry, I can mail you 
a tarred distro.

I hope my work will be able to address such concerns as yours.

Have fun.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: feature priorities (was Re: [Caml-list] Request: matrix_init function in Array)

[Alessandro Baretta]

Vitaly Lugovsky wrote:
> On Mon, 17 Feb 2003, Alessandro Baretta wrote:

>  Can you use SourceForge for this projects?
> 
> P.S. I'm interested in generic DB interface (and I can port my
> oci8ml to it)...


I am a bit anxious about publicizing my work on Sourceforge 
right now. As I mentioned, although both the Db_interface 
module and the Xcaml web application platform work, they are 
still at a very early stage of development.

But, then again, maybe if I shared my work on Sourceforge 
some kind soul and Caml guru might lend a hand, so that the 
work might proceed faster.

I'll look into this possibility. If I decide to move to 
sourceforge I'll drop a line to the list.

Alex

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Re: feature priorities (multithreading)

[James Leifer]

>   1) a.) no multi-threading support where threads would migrate
>          between processors 
>      b.) ... which has underlying it: no MT-safe (and efficient)
>          garbage collector 

These were/are some of the goals of Jocaml
(http://pauillac.inria.fr/jocaml/).

Unfortunately, the version of Jocaml available is based on an old
version of Ocaml (1.07) and the development has stalled for the
moment.

What kind of multithreading features do you need?  It would be
interesting to understand what would be useful in Ocaml, especially
from people who have worked with Erlang, for example.

Best wishes,

James Leifer
INRIA Rocquencourt
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[cashin]

James Leifer <James.Leifer@inria.fr> writes:

...
> What kind of multithreading features do you need?  It would be
> interesting to understand what would be useful in Ocaml, especially
> from people who have worked with Erlang, for example.

Personally, I try to avoid threads because they usually make my
programs less portable and sometimes more complex.  But many people
who do parallelizable computation, like scientific computations
involving matrices, like to increase performance by taking advantage
of SMP architectures.

If the threads in a program only run on one processor, then all you
have is the overhead.  If they run on different processors at the same
time, with access to the same main memory but with independent caches,
then the performance benefits start to compensate for the extra
complexity of multithreading.

-- 
--Ed L Cashin            |   PGP public key:
  ecashin@uga.edu        |   http://noserose.net/e/pgp/

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[Ranjan Bagchi]

I've been reading LtU lately (lambda.weblogs.com) and
came across this paper:
http://www.sics.se/~joe/apachevsyaws.html detailing a
high-performance web-server written in Erlang.

One point here is that the threads in Erlang uses a
ton of "microthreads" which don't use OS Threads at
all (and don't incur the overhead).  Stackless python
(www.stackless.com) does this too, and is able to
support massive concurrency.

Ranjan

--- cashin@cs.uga.edu wrote:
> James Leifer <James.Leifer@inria.fr> writes:
> 
> ...
> > What kind of multithreading features do you need? 
> It would be
> > interesting to understand what would be useful in
> Ocaml, especially
> > from people who have worked with Erlang, for
> example.
> 
> Personally, I try to avoid threads because they
> usually make my
> programs less portable and sometimes more complex. 
> But many people
> who do parallelizable computation, like scientific
> computations
> involving matrices, like to increase performance by
> taking advantage
> of SMP architectures.
> 
> If the threads in a program only run on one
> processor, then all you
> have is the overhead.  If they run on different
> processors at the same
> time, with access to the same main memory but with
> independent caches,
> then the performance benefits start to compensate
> for the extra
> complexity of multithreading.
> 
> -- 
> --Ed L Cashin            |   PGP public key:
>   ecashin@uga.edu        |  
> http://noserose.net/e/pgp/
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr
> Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ:
> http://caml.inria.fr/FAQ/
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> 
> 
> 


__________________________________________________
Do you Yahoo!?
Yahoo! Shopping - Send Flowers for Valentine's Day
http://shopping.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[Brian Hurt]

On Wed, 19 Feb 2003 cashin@cs.uga.edu wrote:

> James Leifer <James.Leifer@inria.fr> writes:
> 
> ...
> > What kind of multithreading features do you need?  It would be
> > interesting to understand what would be useful in Ocaml, especially
> > from people who have worked with Erlang, for example.
> 
> Personally, I try to avoid threads because they usually make my
> programs less portable and sometimes more complex.  But many people
> who do parallelizable computation, like scientific computations
> involving matrices, like to increase performance by taking advantage
> of SMP architectures.
> 
> If the threads in a program only run on one processor, then all you
> have is the overhead.  If they run on different processors at the same
> time, with access to the same main memory but with independent caches,
> then the performance benefits start to compensate for the extra
> complexity of multithreading.
> 

With the increasing popularity of SMT CPUs (for example, the P4, and
comming soon the Power5), multithreading for performance will become more
usefull.  For multithreading for performance, I like the cilk interface
myself:

http://supertech.lcs.mit.edu/cilk/

I still haven't wrapped my brain around JoCaml yet, so I can't say which 
is better.  What I like about Cilk is that it allows you to effectively 
use a single CPU, or hundreds, with the same executable.

There is a second use for multithreading: responsiveness.  In a GUI
program, you have multiple threads going at once.  One is responding to
GUI events, the others are performing various time consuming tasks.  The
alternative is to be continually polling the GUI- and if you forget to do
that, you annoy your users.  An example of this would be browsers- one (or
more) threads are downloading files from the web server, while another
thread is waiting on the GUI.  So when you hit 'stop', the GUI can wake up
and actually stop downloading the pages.  Note that cilk style
multithreading would *not* be usefull for solving this problem- cilk is
purely a speed improvement.  This is more why Java added multithreading.

Note that cilk-style multithreading only makes sense with SMP, or at least 
SMT, environments and kernel-level threads.  Java-style multithreading 
works just fine with userspace threads.

Multithreading is more difficult to program than single threading, there 
is no doubt about that.  Although, interestingly enough, I think purely 
functional programs would be easier to multithread than imperitive 
programs.  The big bugbear of multithreaded programs- race conditions- are 
a side effect of, well, side effects.

I've toyed occassional with the idea of having the compiler or run time 
environment add synchronization automatically.  If possible, this would be 
the holy grail of multithreaded programming.  The idea would be that 
objects only visible to one thread don't need any sort of synchronization.  
It's objects visible from two or more threads that need synchronization.  
So a garbage collection like algorithm could detect those objects that 
need synchronization and add it.  Static analysis might also be usefull- I 
don't know.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[Noel Welsh]

--- Brian Hurt <brian.hurt@qlogic.com> wrote:
> I've toyed occassional with the idea of having the
> compiler or run time 
> environment add synchronization automatically.  

I believe the SAC language

  http://www.informatik.uni-kiel.de/~sacbase/

automatically parallelises matrix operations to take
advantage of SMP machines.  I believe this does at
least part of what you're interesting in.

The alternative is to have no synchronisation, wich is
essentially what Erlang does.  Message passing is the
only way threads can communicate, and messages are
asynchronous and lossy.  An Erlang process is purely
functional so there can be no race conditions.

Noel


__________________________________________________
Do you Yahoo!?
Yahoo! Shopping - Send Flowers for Valentine's Day
http://shopping.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[Brian Hurt]

On Wed, 19 Feb 2003, Ranjan Bagchi wrote:

> I've been reading LtU lately (lambda.weblogs.com) and
> came across this paper:
> http://www.sics.se/~joe/apachevsyaws.html detailing a
> high-performance web-server written in Erlang.
> 
> One point here is that the threads in Erlang uses a
> ton of "microthreads" which don't use OS Threads at
> all (and don't incur the overhead).  Stackless python
> (www.stackless.com) does this too, and is able to
> support massive concurrency.

Yep.  These are called "userspace" or "green" threads.  They're fairly 
easy to do- all you have to do is swap stacks.  Some experimentation on my 
part showed that on a P4, you could task switch between two such user 
space threads in 30-60 clock cycles on the x86- less expensive than a 
cache miss.

User space threads have some problems.  First off, they don't take 
advantage of multiple CPUs, or SMT CPUs.  Second, and more importantly, if 
one thread blocks- either by doing blocking I/O, or page faulting- all 
threads block.

A better approach is what's called the M-by-N approach.  You have M kernel 
level threads (so you can take advantage of M parallel CPUs) each 
executing threads from a pool of N user space threads.  This gives you the 
best of both worlds.

Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[Will Benton]

On Wed, Feb 19, 2003 at 11:45:52AM -0600, Brian Hurt wrote:

> A better approach is what's called the M-by-N approach.  You have M kernel 
> level threads (so you can take advantage of M parallel CPUs) each 
> executing threads from a pool of N user space threads.  This gives you the 
> best of both worlds.

Not necessarily -- most m:n threads packages have non-preemptive user
thread schedulers, which means that a compute-intensive user thread that
never enters the kernel and doesn't yield the processor can monopolize
a kernel thread.  That might be a pathological example (since if
you're trying to run >N compute-intensive threads on N processors,
you're in trouble), but someone might argue that an application that
context-switches enough to *require* m:n instead of 1:1 is
pathological in a different way.

If you need preemptability, then the best-of-both-worlds approach is
to find a system on which kernel thread context switches are cheap.
:-)  (Making KT switches cheap seems to be the direction that the
industry is going -- Sun, for example, has dropped their m:n threads
package for solaris.)



best,
wb

---
Will Benton
willb@acm.org 
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[Brian Hurt]

On Wed, 19 Feb 2003, Will Benton wrote:

> On Wed, Feb 19, 2003 at 11:45:52AM -0600, Brian Hurt wrote:
> 
> > A better approach is what's called the M-by-N approach.  You have M kernel 
> > level threads (so you can take advantage of M parallel CPUs) each 
> > executing threads from a pool of N user space threads.  This gives you the 
> > best of both worlds.
> 
> Not necessarily -- most m:n threads packages have non-preemptive user
> thread schedulers, which means that a compute-intensive user thread that
> never enters the kernel and doesn't yield the processor can monopolize
> a kernel thread.  That might be a pathological example (since if
> you're trying to run >N compute-intensive threads on N processors,
> you're in trouble), but someone might argue that an application that
> context-switches enough to *require* m:n instead of 1:1 is
> pathological in a different way.

Co-operative scheduling is easier- but does run into the problem you point 
out, with the possibility of deadlock.

> 
> If you need preemptability, then the best-of-both-worlds approach is
> to find a system on which kernel thread context switches are cheap.
> :-)  (Making KT switches cheap seems to be the direction that the
> industry is going -- Sun, for example, has dropped their m:n threads
> package for solaris.)
> 

Part of the of the question is "what do you mean by 'cheap'"?  The last 
time I had firm numbers of how much a true task switch cost was the i386- 
and that was 300-500 clock cycles.  Which on a 33MHz machine was a 
signifigant cost.  300-500 clocks on a 3GHz machine is signifigantly 
cheaper- in fact, 300 clocks is about the cost of an unpredictable cache 
miss on the P4.  Also, large portions of the cost of a task switch is 
related to swapping out the memory map- cache and TLB misses and flushing.
If you're swapping between different processes with the same memory space 
(i.e. you don't have to flush TLB or cache), then I could see the cost 
being close to the cost of just saving/restoring the registers- i.e. about 
30-60 clock cycles.

I could easily see Sun saying that it wasn't worth it to do true M:N in 
the face of this.  The savings just aren't signifigant enough to make it 
worthwhile- *if* your operating systems can handle 1,000s of threads 
(until recently, Linux couldn't).  Solaris definately can.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Re: feature priorities (multithreading)

[Michel Schinz]

cashin@cs.uga.edu writes:

[...]

> Personally, I try to avoid threads because they usually make my
> programs less portable and sometimes more complex.

[...]

> If the threads in a program only run on one processor, then all you
> have is the overhead.

I don't agree here, some programs are inherently multi-threaded.

Take GUIs for example. Most GUI toolkits today are based on an event
loop, which waits for events and dispatches them to various
call-backs. This event loop is nothing more than a poor-man's
scheduler. It is a poor solution to the problem, though, because this
scheduler is not preemptive, and this means that your call-backs have
to execute quickly for the application to be responsive. It also means
that if your "threads" have a state, this state must be saved
explicitly between calls.

All applications which use Posix's "select" function are also
screaming for threads. When you use "select", you wait for one of
several events to happen, and when one happens you typically dispatch
to one event handling function. This is, again, nothing but an ad-hoc
scheduler.

John Reppy's book "Concurrent Programming in ML" contains several
examples of the usefulness of threads.

Michel.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: feature priorities (multithreading)

[Brian Hurt]

On Thu, 20 Feb 2003, Michel Schinz wrote:

> I don't agree here, some programs are inherently multi-threaded.

I agree here, but...

> 
> Take GUIs for example. Most GUI toolkits today are based on an event
> loop, which waits for events and dispatches them to various
> call-backs. This event loop is nothing more than a poor-man's
> scheduler. It is a poor solution to the problem, though, because this
> scheduler is not preemptive, and this means that your call-backs have
> to execute quickly for the application to be responsive. It also means
> that if your "threads" have a state, this state must be saved
> explicitly between calls.

Each kernel level thread has overhead.  On Linux, it's like 8K.  So the 
difference between spawning one thread or two is irrelevent- but the 
difference between spawning one thread and two thousand is important.

Also, you have a dispatching problem.  What the OS hands to the 
application is a message like "the mouse clicked at location (x, y)".  The 
application then needs to figure out that location (x, y) just happens to 
be in the OK button, and call the correct callback.

> 
> All applications which use Posix's "select" function are also
> screaming for threads. When you use "select", you wait for one of
> several events to happen, and when one happens you typically dispatch
> to one event handling function. This is, again, nothing but an ad-hoc
> scheduler.

Again, select has uses- especially if there is going to be a lot of time 
between events.  As an example, take a look at inetd.

> 
> John Reppy's book "Concurrent Programming in ML" contains several
> examples of the usefulness of threads.
> 

Threads are most definately usefull- but so is select and event dispatch 
loops, in their place.  Use the right tool for the job.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners