Squeak and native threads

Hello all,

Is anyone doing anything (or know of someone who is) with native threading
in squeak?  As computers begin to rely more and more on a multi-core
strategy for speed up it is going to become more and more important to
support native threading.

The squeak we have now could do some things, like having all IO primitives
be internally async IO (putting the calling squeak thread to sleep until it
gets the IO back, etc.) so that people writing such code don't need to worry
about such complexity (assuming it doesn't already do this).

But that is only going to get us so far.  At some point smalltalk will have
to go true multi-threaded.  Even Java has native threads now, but they chose
the route to maximum impact to the thread user, i.e. fine grained locking.

I have read an article recently on transactional memory [1] and it seemed to
me like this might be a great opportunity for smalltalk.  If a VM was
created for squeak that did native threads with transactional memory then I
think it might be possible that most (if not all) the code we have in the
image right now could work about the same (and my belief comes from the fact
that if we introduce real threading then any state changing operation is
going to have to be "atomic", so we wouldn't use the keyword as much as they
do).

Of course I don't personally have time to even do the little projects I
have, much less something like this.  But I was wondering if anyone had
heard about a project thinking along these lines, or maybe there is some
college studying looking for something to base a thesis on. :)

Thanks,
Jason

1. http://lambda-the-ultimate.org/node/1896

_________________________________________________________________
Communicate instantly! Use your Hotmail address to sign into Windows Live
Messenger now. http://get.live.com/messenger/overview

Well actually on Modern old technology based operating systems like  
unix, (ahem OSX)
  the I/O (file/sockets/sound) run under different pthreads  
automatically once the syscall is made.

VisualWorks has an interface for pthreads that allow you to move DLL  
calls to pthreads.

I'll note with a bit of work one could put the remain interp.c  
variables in the foo structure and have a VM that
could run multiple pthreads each hosting a VM. Of course one would  
have to clean up the platform dependent code to avoid
globals or file based static. Still the majority of work has been  
done, but there has been no interest.


On Jan 6, 2007, at 2:07 AM, J J wrote:

> Hello all,
>
> Is anyone doing anything (or know of someone who is) with native  
> threading in squeak?  As computers begin to rely more and more on a  
> multi-core strategy for speed up it is going to become more and  
> more important to support native threading.
--
========================================================================
===
John M. McIntosh <[hidden email]>
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

J J wrote:
> I have read an article recently on transactional memory [1] and it
> seemed to me like this might be a great opportunity for smalltalk.  If a
> VM was created for squeak that did native threads with transactional
> memory then I think it might be possible that most (if not all) the code
> we have in the image right now could work about the same (and my belief
> comes from the fact that if we introduce real threading then any state
> changing operation is going to have to be "atomic", so we wouldn't use
> the keyword as much as they do).

I don't understand what you mean by 'any state changing operation is
going to have to be "atomic", so we wouldn't use the keyword as much as
they do'? We would have to use the atomic keyword wherever there is a
state change - why is this less for Smalltalk?

I found http://wiki.squeak.org/squeak/537 very interesting on this whole
subject. I was especially interested in the work on Merlin/TinySelf
where message sending is (as I understand it) asynchronous. I wonder
what would be required to spike this in Squeak even if just simulated?

Thanks,
Zulq.

you can have a look at Actalk (the 1989 paper of JP briot) in a few  
lines of code you get message put in queue and each object having its  
own thread.
I can send you the paper. There is also an implementation maintained  
by serge stinckwich may be of the 1996 paper.

Stef

On 7 janv. 07, at 19:14, Zulq Alam wrote:

stephane ducasse wrote:
> you can have a look at Actalk (the 1989 paper of JP briot) in a few
> lines of code you get message put in queue and each object having its
> own thread.
> I can send you the paper. There is also an implementation maintained
> by serge stinckwich may be of the 1996 paper.
>
> Stef
Stef,

What few lines of code?  And can this be done to selected objects, so as
to permit sensible factorization of object systems into threads?

I've asked this same question before: http://wiki.squeak.org/squeak/552

In all seriousness, I still believe that a clean breakthrough would be a
vital long term enabling devolopment for Croquet in particular, and Squeak
generally.

Is this paper online (or can it be scanned and legally posted online?

    Thanks,

        Ed Boyce

Ah, ausome.

>
>VisualWorks has an interface for pthreads that allow you to move DLL  calls
>to pthreads.

Dolphin has "overlapping" calls, which are probably similar.

>I'll note with a bit of work one could put the remain interp.c  variables
>in the foo structure and have a VM that
>could run multiple pthreads each hosting a VM. Of course one would  have to
>clean up the platform dependent code to avoid
>globals or file based static. Still the majority of work has been  done,
>but there has been no interest.

Could you define "a bit of work"?  You think like 3 months work for the
average guy?  More/Less?
I'm sure there was less interest before because the threading world is
harder to work in then the non-threading world.  But it is getting more
important every day, so I thought this deserved some looking into.

Thanks very much for your reply,
J

_________________________________________________________________
Fixing up the home? Live Search can help
http://imagine-windowslive.com/search/kits/default.aspx?kit=improve&locale=en-US&source=hmemailtaglinenov06&FORM=WLMTAG

Well my thinking with that was:  If you change an instance variable you are
changing shared state (but I could be wrong here).  The main point was that
for this to be really useful, it needs be as non-intrusive as possible in
the common case.  That is, the best would be if some change could be made
and squeak was suddenly capable of running in multiple threads with the
current code base.

_________________________________________________________________
Fixing up the home? Live Search can help
http://imagine-windowslive.com/search/kits/default.aspx?kit=improve&locale=en-US&source=hmemailtaglinenov06&FORM=WLMTAG

On Jan 8, 2007, at 10:10 PM, J J wrote:
>>
>
> Could you define "a bit of work"?  You think like 3 months work for  
> the average guy?  More/Less?
> I'm sure there was less interest before because the threading world  
> is harder to work in then the non-threading world.  But it is  
> getting more important every day, so I thought this deserved some  
> looking into.

Well the original intent was to enable the VM to use one code segment  
and multiple data structures. The hard part was convincing SLANG to  
extrude almost all the interpreter.c
global variables as variables in a structure.

At the time I did this many years ago some variables were not put  
into the structure because the address of the variables were needed,  
however this usage has I see been
deleted for these two variables.

sqInt extraVMMemory;
usqInt memory;

The follow three elements are initialized, but a startup routine  
could do that work if passed the data structure before the  
interpreter is started.

void *primitiveTable
char* obsoleteIndexedPrimitiveTable[][3] =
const char* obsoleteNamedPrimitiveTable[][3] = {


mmm this is a const now, so not needed in the structure
const char *interpreterVersion = "Squeak3.8 of '5 May 2005' [latest  
update: #6665]";

exupery uses this one, but again I'll guess it could go into the  
structure.
sqInt (*compilerHooks[26])();

LIkely these two could go into the structure.
void* showSurfaceFn;
struct VirtualMachine* interpreterProxy;


So that is a couple of hours/day or so of work.
Now of course you would need to look at the different platform files  
that you need and make them global variable safe too.

However in doing all this it really just let you run multiple VM's in  
the same address space, which is different from  having smalltalk  
threads somehow mapped to
processor threads.

--
========================================================================
===
John M. McIntosh <[hidden email]>
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

I have been looking at:

http://www-poleia.lip6.fr/~briot/actalk/papers/PAPERS.html

Ed Boyce wrote:
> Is this paper online (or can it be scanned and legally posted online?

"Ed Boyce" <[hidden email]> writes:

Googling for "Actalk 1989 paper JP briot" yields

    http://citeseer.ist.psu.edu/briot89actalk.html

which has copies in several formats.

frank

J J-6 wrote

That is, the best would be if some change could be made
and squeak was suddenly capable of running in multiple threads with the
current code base.

I agree and that is why I found the active object + asynchronous messages model interesting. From what I can tell (so far) there appears to be even less impact. In a transactional system you would need some sort of transactional construct like BlockClosure>>atomicValue:anObject which seems unpleasant to me. Furthremore, I imagine the cost of having implicit transactions for every instance variable would be significantly high.

Aha.  Ok, I was hoping to have a way that smalltalk could make use of native
threads.  I guess we would want the user to be able to choose since "green"
threads are still the best method in some cases.

_________________________________________________________________
Your Hotmail address already works to sign into Windows Live Messenger! Get
it now
http://clk.atdmt.com/MSN/go/msnnkwme0020000001msn/direct/01/?href=http://get.live.com/messenger/overview

Well, I think the transactional approach could work nice as well (of course
squeak already has semaphore style fine grain locking if you really want
that).

>From a synchronization point of view, there are only two cases to worry
about (I think):

1) Object getting into an invalid state due to an update
2) Updates getting lost

In case 1, only the object can know if it is in an invalid state or not, so
this has to be explicit:

Object subclass: #BankAccount
        instanceVariableNames: 'balance'
        classVariableNames: ''
        poolDictionaries: ''
        category: 'Banking'

BankAccount>>withdraw: aNumber

  balance := balance - aNumber.

  balance < 0 ifTrue: [ OverDrawn raise ].

  ^ balance

BankAccount>>deposit: aNumber
  balance := balance + aNumber.
  ^ balance.

BankAccount>>transfer: aNumber to: anAccount
  ^ [
    anAccount deposit: aNumber.
    self withdraw: aNumber.
  ] asAtomicBlock value.


If another thread drops the account below 0 while #transfer:to: is running,
the #withdraw: will throw an exception, undo the deposit (or simply throw
away the uncommited changes) and propagate the exception up (as the caller
would expect).

Now the harder one: missed updates.  My thought on this was, maybe everthing
on the right of := could be considered atomic.  This might let most of the
current code run ok in the presence of threads.

Of course the AtomicBlock class will have to use primitives to do the
book-keeping needed, but I think smalltalk might be in a fairly unique
position to take advantage of for optimizations.  For example, if the VM
sees there is only 1 thread, then skip the book-keeping.  Transactional
memory is generally slower with 1-4 threads, but I think with the example
optimization it could be at least as fast as fine-grained locking when
running a single thread.

Thanks,
J

_________________________________________________________________
Find sales, coupons, and free shipping, all in one place!  MSN Shopping
Sales & Deals
http://shopping.msn.com/content/shp/?ctid=198,ptnrid=176,ptnrdata=200639

Since almost every method contains some sort of transaction, how about simply making all methods an implicit transaction?

J J-6 wrote

BankAccount>>withdraw: aNumber

  balance := balance - aNumber.

  balance < 0 ifTrue: [ OverDrawn raise ].

  ^ balance

BankAccount>>deposit: aNumber
  balance := balance + aNumber.
  ^ balance.

BankAccount>>transfer: aNumber to: anAccount
  ^ [
    anAccount deposit: aNumber.
    self withdraw: aNumber.
  ] asAtomicBlock value.

=P

I've been trolling about squeak threading for years and years and years.
Ever since I gots me my dual Athlon.

I even started working on it before my hard drive crashed several years
ago. One of the issues that has held me back of late has been the long
trumpeted transition to 64-bit safe code. -- a major overhaul that could
not be paralelled with a similar major overhaul involving threading.

As far as I know, that project has stagnated and disappeared. The CVS
code, last I checked, was inconsistant and unusable. The 3.8 beta VMs
worked great (I can't remember the working configurations right now...)
but were never released to the website. The VM on the website is, as of
about a month ago, 3.7. -- while the image is on 3.9

The best that can be done for cheap is a PVM style system oriented
factorization of the VM where different sub-images are given different
responsibilities. These are then run in paralel, possibly even over
multiple hosts. This presents numerous problems. Most notable of which
being maintaining version consistency across the entire network. It's
main advantage is that it can be done without getting to deep into the VM.

A better solution will require a rewrite of the C-code translator. Only
someone with intimate knowledge of the compiler classes can do this
correctly. The new version must not include any examples of "class = Foo
 ifTrue: [bar]." where Foo almost always = Interpreter. It must also
create appropriate structs for each instance of each class. This is
critical because it permits the separation of Interpreter and
ObjectMemory which, in turn, permits a single ObjectMemory to manage and
GC the VM while multiple instances of Interpreter run around processing
Smalltalk threads.

For reason of my long term involvement in this subject, I am probably
the foremost expert on this specific subject, as well as the most
prolific troll. Second honors going to Ed Boyce.


--
|/-\|/-\|

But they don't.  Only variables updates (NOTE: most reads don't) do.


_________________________________________________________________
The MSN Entertainment Guide to Golden Globes is here.  Get all the scoop.
http://tv.msn.com/tv/globes2007/?icid=nctagline2

Sorry, I meant in your BankAccount example. I was thinking about some
kind of switch to make specific Objects begin implicit transactions for
each message received. This switch could optionally be used in
conjunction with explicit transactions. The goal being to reduce the
code changes required.

| bankAccount |
bankAccount := BankAccount new.

" implicit transactions for all methods "
bankAccount shareAll

" implicit transactions for only #transfer:to "
bankAccount share: #transfer:to

" no implicit transactions "
bankAccount shareNone

I greatly prefer the asynch/active model as none of this seems necessary
(from what I have read so far). As far as I can tell, the developer need
not do *anything* different to benefit and be protected from
concurrency.

J J wrote:
> But they don't.  Only variables updates (NOTE: most reads don't) do.

But my example (theoretically) worked as written.  Everything to the right
of the := is protected so saying "balance := balance - aNumber" doesn't risk
losing the update.  And even without this, so long as calls to #withdraw:
and #deposit: are always done in #transfer:to: they are protected by *that
method's* atomic operation.

That is one of the great things about STM (software transactional memory);
you can compose atomic operations transparently.  That is, you can just use
methods and not be so concerned about if they do atomic operations or not.  
That is quite a departure from fine-grained locking code.


_________________________________________________________________
Type your favorite song.  Get a customized station.  Try MSN Radio powered
by Pandora. http://radio.msn.com/?icid=T002MSN03A07001

J J wrote:
> But my example (theoretically) worked as written.

I'm not saying it doesn't. I was trying to find a way of avoiding the
'asAtomicBlock value' construct which I don't like and believe will be
more common than you expect.

 > That is one of the great things about STM (software transactional
 > memory); you can compose atomic operations transparently.

Agreed but I'm not convinced it fits from a human perspective. As a
concept, message sending is intuitive. The same cannot be said of atomic
transactions. I believe the solution for Smalltalk lies in something
equally as intuitive and explainable in terms of objects and messages.

Well, it is the method used by RDBMS's that have been popular for quite some
time, so at least the concept is well covered.  This actually brings
something out of another recent thread (what are RDBMS's good for?):
Relational DB's have been doing for years what we are having to do more and
more now with memory: handle lots of simultaneously connections to a back
end data store.

But if you prefer message passing, you can have that right now.  If you are
not sharing state then it isn't really a thread anyway, you may as well run
a different image and pass messages between them.

Though supporting this idea directly in the language like Erlang lets you
create processes very quickly and many more then you normally could.

_________________________________________________________________
>From photos to predictions, The MSN Entertainment Guide to Golden Globes has
it all. http://tv.msn.com/tv/globes2007/?icid=nctagline1