Concurrent Futures

> There are already some steps done in this direction. A sources for
> RISC architecture generate a foo struct , which holds all interpreter
> globals.
> Also, i did some changes in Exupery to create a single struct of all
> VM globals (not only variables, but functions too).
> This was done to make it easier to get address of any global symbol
> what Exupery needs.
> I'm also experimented to replace all direct calls to function to
> indirect (i.e. foo->primAdd(x,y) instead of primAdd(x,y)). This caused
> about ~1% of speed degradation in tinyBenchmarks :)

>> The above takes care about the interpreter but there are still
>> primitives and plugins that need to be dealt with. What I would do here
>> is define operations like ioLock(struct VM) and ioUnlock(struct VM) that
>> are the effective equivalent of Python's GIL (global interpreter lock)
>> and allow exclusive access to primitives that have not been converted to
>> multi-threading yet. How exactly this conversion should happen is
>> deliberately left open here; maybe changing the VMs major proxy version
>> is the right thing to do to indicate the changed semantics. In any case,
>> the GIL allows us to readily reuse all existing plugins without having
>> to worry about conversion early on.
>>
> Or as i proposed in earlier posts, the other way could be to schedule
> all primitive calls, which currently don't support multi-threading to
> single 'main' thread.
> Then we don't need the GIL.

> Igor Stasenko wrote:
>> If you have any ideas how such VM would look like i'm glad to hear.
>
> Okay, so Josh convinced me to write up the ideas. The main problem as I
> see it with a *practical* solution to the problem is that all of the
> solutions so far require huge leaps and can't be implemented step-by-step
> (which almost certainly dooms them to failure).
>
> So what do we know and what do we actually all pretty much agree on? It's
> that we need to be able to utilize multiple cores and that we need a
> practical way to get there (if you disagree with the latter this message
> is not meant for you ;-) Running multiple processes is one option but it
> is not always sufficient. For example, some OSes would have trouble firing
> off a couple of thousand processes whereas the same OS may have no problem
> at all with a couple of thousand threads in one process. To give an
> example, starting a thread on Windows cost somewhere in the range of a
> millisecond which is admittedly slow, but still orders of magnitude faster
> than creating a new process. Then there are issues with resource sharing
> (like file handles) which are practically guaranteed not to work across
> process boundaries etc. So while there are perfectly good reasons to run
> multiple processes, there are reasons just as good to wanting to run
> multiple threads in one process.
>
> The question then is, can we find an easy way to extend the Squeak VM to
> run multiple threads and if so how? Given the simplistic nature of the
> Squeak interpreter, there is actually very little global state that is not
> encapsulated in objects on the Squeak heap - basically all the variables
> in class interpreter. So if we would put them into state that is local to
> each thread, we could trivially run multiple instances of the byte code
> interpreter in the same VM. This gets us to the two major questions:
>
> * How do we encapsulate the interpreter state?
> * How do we deal with primitives and plugins?
>
> Let's start with the first one. Obviously, the answer is "make it an
> object". The way how I would go about is by modifying the CCodeGenerator
> such that it generates all functions with an argument of type "struct VM"
> and that variable accesses prefix things properly and that all functions
> calls pass the extra argument along. In short, what used to be translated
> as:
>
> sqInt primitiveAdd(void) {
>   integerResult = stackIntegerValue(1) + stackIntegerValue(0)
>   /* etc. */
> }
>
> will then become something like here:
>
> sqInt primitiveAdd(struct VM *vm) {
>   integerResult = stackIntegerValue(vm,1) + stackIntegerValue(vm,0)
>   /* etc. */
> }
>
> This is a *purely* mechanical step that can be done independent of
> anything else. It should be possible to generate code that is entirely
> equivalent to todays code and with a bit of tweaking it should be possible
> to make that code roughly as fast as we have today (not that I think it
> matters but understanding the speed difference between this and the
> default interpreter is important for judging relative speed improvements
> later).
>
> The above takes care about the interpreter but there are still primitives
> and plugins that need to be dealt with. What I would do here is define
> operations like ioLock(struct VM) and ioUnlock(struct VM) that are the
> effective equivalent of Python's GIL (global interpreter lock) and allow
> exclusive access to primitives that have not been converted to
> multi-threading yet. How exactly this conversion should happen is
> deliberately left open here; maybe changing the VMs major proxy version is
> the right thing to do to indicate the changed semantics. In any case, the
> GIL allows us to readily reuse all existing plugins without having to
> worry about conversion early on.
>
> So now we've taken care of the two major parts of Squeak: We have the
> ability to run new interpreters and we have the ability to use primitives.
> This is when the fun begins, because at this point we have options:
>
> For example, if you are into shared-state concurrency, you might implement
> a primitive that forks a new instance of the interpreter running in the
> same object memory that your previous interpreter is running in.
>
> Or, and that would be the path that I would take, implement a primitive
> that loads an image into a new object memory (I can explain in more detail
> how memory allocation needs to work for that; it is a fairly
> straightforward scheme but a little too long for this message) and run
> that interpreter.
>
> And at this point, the *real* fun begins because we can now start to
> define the communication patterns we'd like to use (initially sockets,
> later shared memory or event queues or whatever else). We can have tiny
> worker images that only do minimal stuff but we can also do a Spoon-like
> thing where we have a "master image" that contains all the code possibly
> needed and fire off micro-images that (via imprinting) swap in just the
> code they need to run.
>
> [Whoa! I just got interrupted by a little 5.6 quake some 50 miles away]
>
> Sorry but I lost my train of thought here. Happens at 5.6 Richter ;-)
> Anyway, the main thing I'm trying to say in the above is that for a
> *practical* solution to the problem there are some steps that are pretty
> much required whichever way you look at it. And I think that regardless of
> your interest in shared state or message passing concurrency we may be
> able to define a road that leads to interesting experiments without
> sacrificing the practical artifact. A VM built like described in the above
> would be strictly a superset of the current VM so it would be able to run
> any current images and leave room for further experiments.
>
> Cheers,
>   - Andreas
>
>
>

> Rob
>
> ----- Original Message -----
> From: "Andreas Raab" <[hidden email]>
> To: "The general-purpose Squeak developers list"
> <[hidden email]>
> Sent: Tuesday, October 30, 2007 8:53 PM
> Subject: Thoughts on a concurrent Squeak VM (was: Re: Concurrent Futures)
>
>
> > Igor Stasenko wrote:
> >> If you have any ideas how such VM would look like i'm glad to hear.
> >
> > Okay, so Josh convinced me to write up the ideas. The main problem as I
> > see it with a *practical* solution to the problem is that all of the
> > solutions so far require huge leaps and can't be implemented step-by-step
> > (which almost certainly dooms them to failure).
> >
> > So what do we know and what do we actually all pretty much agree on? It's
> > that we need to be able to utilize multiple cores and that we need a
> > practical way to get there (if you disagree with the latter this message
> > is not meant for you ;-) Running multiple processes is one option but it
> > is not always sufficient. For example, some OSes would have trouble firing
> > off a couple of thousand processes whereas the same OS may have no problem
> > at all with a couple of thousand threads in one process. To give an
> > example, starting a thread on Windows cost somewhere in the range of a
> > millisecond which is admittedly slow, but still orders of magnitude faster
> > than creating a new process. Then there are issues with resource sharing
> > (like file handles) which are practically guaranteed not to work across
> > process boundaries etc. So while there are perfectly good reasons to run
> > multiple processes, there are reasons just as good to wanting to run
> > multiple threads in one process.
> >
> > The question then is, can we find an easy way to extend the Squeak VM to
> > run multiple threads and if so how? Given the simplistic nature of the
> > Squeak interpreter, there is actually very little global state that is not
> > encapsulated in objects on the Squeak heap - basically all the variables
> > in class interpreter. So if we would put them into state that is local to
> > each thread, we could trivially run multiple instances of the byte code
> > interpreter in the same VM. This gets us to the two major questions:
> >
> > * How do we encapsulate the interpreter state?
> > * How do we deal with primitives and plugins?
> >
> > Let's start with the first one. Obviously, the answer is "make it an
> > object". The way how I would go about is by modifying the CCodeGenerator
> > such that it generates all functions with an argument of type "struct VM"
> > and that variable accesses prefix things properly and that all functions
> > calls pass the extra argument along. In short, what used to be translated
> > as:
> >
> > sqInt primitiveAdd(void) {
> >   integerResult = stackIntegerValue(1) + stackIntegerValue(0)
> >   /* etc. */
> > }
> >
> > will then become something like here:
> >
> > sqInt primitiveAdd(struct VM *vm) {
> >   integerResult = stackIntegerValue(vm,1) + stackIntegerValue(vm,0)
> >   /* etc. */
> > }
> >
> > This is a *purely* mechanical step that can be done independent of
> > anything else. It should be possible to generate code that is entirely
> > equivalent to todays code and with a bit of tweaking it should be possible
> > to make that code roughly as fast as we have today (not that I think it
> > matters but understanding the speed difference between this and the
> > default interpreter is important for judging relative speed improvements
> > later).
> >
> > The above takes care about the interpreter but there are still primitives
> > and plugins that need to be dealt with. What I would do here is define
> > operations like ioLock(struct VM) and ioUnlock(struct VM) that are the
> > effective equivalent of Python's GIL (global interpreter lock) and allow
> > exclusive access to primitives that have not been converted to
> > multi-threading yet. How exactly this conversion should happen is
> > deliberately left open here; maybe changing the VMs major proxy version is
> > the right thing to do to indicate the changed semantics. In any case, the
> > GIL allows us to readily reuse all existing plugins without having to
> > worry about conversion early on.
> >
> > So now we've taken care of the two major parts of Squeak: We have the
> > ability to run new interpreters and we have the ability to use primitives.
> > This is when the fun begins, because at this point we have options:
> >
> > For example, if you are into shared-state concurrency, you might implement
> > a primitive that forks a new instance of the interpreter running in the
> > same object memory that your previous interpreter is running in.
> >
> > Or, and that would be the path that I would take, implement a primitive
> > that loads an image into a new object memory (I can explain in more detail
> > how memory allocation needs to work for that; it is a fairly
> > straightforward scheme but a little too long for this message) and run
> > that interpreter.
> >
> > And at this point, the *real* fun begins because we can now start to
> > define the communication patterns we'd like to use (initially sockets,
> > later shared memory or event queues or whatever else). We can have tiny
> > worker images that only do minimal stuff but we can also do a Spoon-like
> > thing where we have a "master image" that contains all the code possibly
> > needed and fire off micro-images that (via imprinting) swap in just the
> > code they need to run.
> >
> > [Whoa! I just got interrupted by a little 5.6 quake some 50 miles away]
> >
> > Sorry but I lost my train of thought here. Happens at 5.6 Richter ;-)
> > Anyway, the main thing I'm trying to say in the above is that for a
> > *practical* solution to the problem there are some steps that are pretty
> > much required whichever way you look at it. And I think that regardless of
> > your interest in shared state or message passing concurrency we may be
> > able to define a road that leads to interesting experiments without
> > sacrificing the practical artifact. A VM built like described in the above
> > would be strictly a superset of the current VM so it would be able to run
> > any current images and leave room for further experiments.
> >
> > Cheers,
> >   - Andreas
> >
> >
> >
>
>
>

> On 31/10/2007, Rob Withers <[hidden email]> wrote:
>> Andreas,
>>
>> What about using C++?  There would be some degradation of performance.
>> However, there would be the benefit of structuring the VM classes, of not
>> having to add VM as an argument everywhere, and it may even be possible
>> to
>> subclass Thread so we know where the thread-local storage is.
>>
> I'd rather prefer to make modifications to slang to be able to
> generate VM sources for any target language/platform and keep platform
> dependent code in image instead in separate file(s). This all to
> simplify build process and to keep all things together.

> Rob Withers wrote:
>> What about using C++?  There would be some degradation of performance.
>> However, there would be the benefit of structuring the VM classes, of not
>> having to add VM as an argument everywhere, and it may even be possible
>> to subclass Thread so we know where the thread-local storage is.
>
> For the VM internally, I don't really care. Since this is generated code
> there is really no difference to me. For plugins it is not feasible to use
> C++ since name mangling not standardized so you can't link reliably to C++
> APIs.

> I would like to mention some of my previous work in this area:
>
> - tinySelf 1 (1996)
> http://www.lsi.usp.br/~jecel/tiny.html#rel1
>
> This was a Self interepreter written in Self which implemented the one
> thread per object model. All messages were future messages but since
> sending a message to an unresolved future would block, you would have
> deadlock on any recursion (direct or indirect). This problem was  
> solved
> by detecting the cycles and preempting the blocked mesasge with the  
> one
> it depends on. This results in interleaved execution, but since the
> semantics are exactly the same as in a sequential execution of the
> recursive code any bugs that appear won't be due to concurrency.
>
> I was able to test simple expressions and was very happy with how much
> parallelism I was able to extract from seemingly sequential code,  
> but I
> made the mistake of introducing a significant optimization (tail send
> elimination) that made debugging so much harder that I was unable to
> finish in the two weeks that I was able to dedicate to this project.
>
> - 64 node Smalltalk machine (1992)
> http://www.lsi.usp.br/~jecel/ms8702.html
>
> The most interesting result in this project was the notion that most
> objects in the system are immutable at any given time and that a
> security system might be used to detect this. For example, just  
> because
> you can edit some font today doesn't mean that you will do it. And if
> you and everyone currently logged on the local system only have read
> permission for that font then it is effectively immutable. Only  
> when the
> font's owner logs in is this assumption invalid.
>
> The advantage of knowing that an object is immutable is that you can
> replicate it and you can allow multiple threads to access it at the  
> same
> time.
>
> The only paper in English from this project describes how adaptive
> compilation could be used to trim away excessive concurrency by
> transforming future message passing into sequential message passing  
> (the
> semantics allow this) and then inlining them away. So if a machine has
> 64 processors and the application initially starts out with 10  
> thousand
> threads, the compiler will eventually change this into code with  
> 200 or
> so threads (some are blocked at any given instant, so going down to 64
> threads would not be good)..
> http://www.lsi.usp.br/~jecel/jabs1.html
>
> - operating system in an Objective-C like language (1988)
> http://www.lsi.usp.br/~jecel/atos.html (this page has download  
> links but
> the text still hasn't been written)
>
> This operating system for 286 machine used the virtual memory of that
> hardware to isolate groups of objects, with one thread per group. This
> would be similar to the vat/island model. All messages were sent in
> exactly the same way and if the receiver was a local object then it  
> was
> just a fancy subroutine call but for remote objects you got a "segment
> not present" fault and the message was packed up and sent to the other
> task (possibly over the network). All messages were synchronous  
> since I
> was not aware of futures at that time.
>
> -- current model --
>
> I moved back to the one thread per object group model since I feel  
> that
> makes it easier for programmers to control things without having to
> worry to much about details most of the time. Since my target is
> children this is particularly important. An alternative that I
> experimented with was having a separation between active and passive
> objects. A passive object could be known only to a single active one,
> but it is just too hard to program without ever accidentally letting
> references to passive objects "leak". With the group/vat/island model
> there is just one kind of object and things are simpler for the
> programmer (but more complicated for the implementor). I have a
> limitation that you can only create new objects in your own group  
> or in
> an entirely new group - I think forcing some other random group to
> create an object for you is rude, though of course you can always ask
> for an object there to please do it.
>
> Some of the loaded groups are read/write but many are read-only. The
> latter don't actually have their own threads but instead their code
> executes in the thread of the calling group. I have hardware  
> support for
> this.
>
> Speaking of hardware, I would like to stress how fantastically slow
> (relatively speaking) main memory is these days. If I have a good
> network connecting processor cores in a single chip then I can  
> probably
> send a message from one to another, get a reply, send a second message
> and get another reply in the time that it takes to read a byte from
> external RAM. So we should start thinking of DDR SDRAM as a really  
> fast
> disk to swap objects to/from and not as a shared memory. We should  
> start
> to take message passing seriously.
>
> -- Jecel
>

> ----- Original Message ----- From: "Andreas Raab"  
> <[hidden email]>
> To: "The general-purpose Squeak developers list" <squeak-
> [hidden email]>
> Sent: Wednesday, October 31, 2007 9:37 AM
> Subject: Re: Thoughts on a concurrent Squeak VM
>
>
>> Rob Withers wrote:
>>> What about using C++?  There would be some degradation of  
>>> performance. However, there would be the benefit of structuring  
>>> the VM classes, of not having to add VM as an argument  
>>> everywhere, and it may even be possible to subclass Thread so we  
>>> know where the thread-local storage is.
>>
>> For the VM internally, I don't really care. Since this is  
>> generated code there is really no difference to me. For plugins it  
>> is not feasible to use C++ since name mangling not standardized so  
>> you can't link reliably to C++ APIs.
>
> That's true that it's internal to the VM so it shouldn't matter.  I  
> suppose the benefi of structuring the classes was more of an in  
> image issue with me. Even using C, we could separate off the  
> primitives into a Primitives class and compile with ObjectMemory,  
> Interpreter, and Primitives so they are all generated in the same  
> file.  Then we would just need to make sure the  
> InterpreterSimulator knew about the Primitives class.  The same  
> issue as would apply if ObjectMemory and Interpreter were no longer  
> part of the same hierarchy.
>
> It makes sense that primitives would have a problem with name  
> mangling, so named primitives can't be in C++ classes...indexed  
> could be, though, as long as the primitive table were initialized  
> with the mangled names.

> On Oct 31, 2007, at 17:57 , Rob Withers wrote:
>
>> ----- Original Message ----- From: "Andreas Raab"  <[hidden email]>
>> To: "The general-purpose Squeak developers list" <squeak-
>> [hidden email]>
>> Sent: Wednesday, October 31, 2007 9:37 AM
>> Subject: Re: Thoughts on a concurrent Squeak VM
>>
>>
>>> Rob Withers wrote:
>>>> What about using C++?  There would be some degradation of  performance.
>>>> However, there would be the benefit of structuring  the VM classes, of
>>>> not having to add VM as an argument  everywhere, and it may even be
>>>> possible to subclass Thread so we  know where the thread-local storage
>>>> is.
>>>
>>> For the VM internally, I don't really care. Since this is  generated
>>> code there is really no difference to me. For plugins it  is not
>>> feasible to use C++ since name mangling not standardized so  you can't
>>> link reliably to C++ APIs.
>>
>> That's true that it's internal to the VM so it shouldn't matter.  I
>> suppose the benefi of structuring the classes was more of an in  image
>> issue with me. Even using C, we could separate off the  primitives into a
>> Primitives class and compile with ObjectMemory,  Interpreter, and
>> Primitives so they are all generated in the same  file.  Then we would
>> just need to make sure the  InterpreterSimulator knew about the
>> Primitives class.  The same  issue as would apply if ObjectMemory and
>> Interpreter were no longer  part of the same hierarchy.
>>
>> It makes sense that primitives would have a problem with name  mangling,
>> so named primitives can't be in C++ classes...indexed  could be, though,
>> as long as the primitive table were initialized  with the mangled names.
>
> I don't see any point in switching to C++.

>
> ----- Original Message -----
> From: "Igor Stasenko" <[hidden email]>
> To: "The general-purpose Squeak developers list"
> <[hidden email]>
> Sent: Wednesday, October 31, 2007 9:39 AM
> Subject: Re: Thoughts on a concurrent Squeak VM (was: Re: Concurrent
> Futures)
>
>
> > On 31/10/2007, Rob Withers <[hidden email]> wrote:
> >> Andreas,
> >>
> >> What about using C++?  There would be some degradation of performance.
> >> However, there would be the benefit of structuring the VM classes, of not
> >> having to add VM as an argument everywhere, and it may even be possible
> >> to
> >> subclass Thread so we know where the thread-local storage is.
> >>
> > I'd rather prefer to make modifications to slang to be able to
> > generate VM sources for any target language/platform and keep platform
> > dependent code in image instead in separate file(s). This all to
> > simplify build process and to keep all things together.
>
> You mean subclassing a Thread class?  Is that platform dependent?  If so, I
> didn't know that and I agree with you - it's should be out in a separate
> file, if used at all.
>

> On 31/10/2007, Jason Johnson <[hidden email]> wrote:
> > On 10/30/07, Igor Stasenko <[hidden email]> wrote:
> > >
> > > Most of reasons why CPU not utilized at 100% is using a blocking I/O
> > > calls. Then a simplest solution to not use them and instead of blowing
> > > up the number of threads use asynchronous I/O . Most major platforms
> > > support asynchronous I/O and there are many libraries which support
> > > async data handling almost in each area we need for. We just need to
> > > build on top of them.
> >
> > Good point.  How many kinds of I/O in Squeak is currently blocking?  I
> > think I heard networking blocks, what about disk?
> >
> All socket/file IO primitives using blocking calls.
> To what i see, there is only one set of async primitives -
> AsyncFilePlugin. But i'm not sure if it used at first place (i.e.
> replaces a FilePlugin).
> I think Andreas could answer on this more precisely.
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

> On 31/10/2007, Rob Withers <[hidden email]> wrote:
> >
> > ----- Original Message -----
> > From: "Igor Stasenko" <[hidden email]>
> > To: "The general-purpose Squeak developers list"
> > <[hidden email]>
> > Sent: Wednesday, October 31, 2007 9:39 AM
> > Subject: Re: Thoughts on a concurrent Squeak VM (was: Re: Concurrent
> > Futures)
> >
> >
> > > On 31/10/2007, Rob Withers <[hidden email]> wrote:
> > >> Andreas,
> > >>
> > >> What about using C++?  There would be some degradation of performance.
> > >> However, there would be the benefit of structuring the VM classes, of not
> > >> having to add VM as an argument everywhere, and it may even be possible
> > >> to
> > >> subclass Thread so we know where the thread-local storage is.
> > >>
> > > I'd rather prefer to make modifications to slang to be able to
> > > generate VM sources for any target language/platform and keep platform
> > > dependent code in image instead in separate file(s). This all to
> > > simplify build process and to keep all things together.
> >
> > You mean subclassing a Thread class?  Is that platform dependent?  If so, I
> > didn't know that and I agree with you - it's should be out in a separate
> > file, if used at all.
> >
> No, i mean to keep ALL plugins code in corresponding methods, and
> never use external sources.
> For example, a SocketPlugin can have subclasses Win32SocketPlugin,
> UnixSocketPlugin
> and in these subclasses we should keep a code for different platforms.
> But not in .c sources.
>
> > cheers,
> > Rob
> >
> >
> >
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
>

> Igor Stasenko wrote:
> > There are already some steps done in this direction. A sources for
> > RISC architecture generate a foo struct , which holds all interpreter
> > globals.
> > Also, i did some changes in Exupery to create a single struct of all
> > VM globals (not only variables, but functions too).
> > This was done to make it easier to get address of any global symbol
> > what Exupery needs.
> > I'm also experimented to replace all direct calls to function to
> > indirect (i.e. foo->primAdd(x,y) instead of primAdd(x,y)). This caused
> > about ~1% of speed degradation in tinyBenchmarks :)
>
> Ah, indeed, I forgot about that.
>
> > Also, moving forward on this renders an InterpreterProxy struct
> > useless, because we can just pass an address to our 'foo' struct to
> > plugins which already contains everything what plugin can reach.
>
> But this isn't quite true. One of the reasons for the proxy is to
> abstract from the actual implementation since C doesn't do proper name
> lookup for names but rather uses indexes. And so, if you happen to add
> or remove a method from that struct, your plugins will be screwed ;-)
>

> On 31/10/2007, Rob Withers <[hidden email]> wrote:
> >
> > ----- Original Message -----
> > From: "Igor Stasenko" <[hidden email]>
> > > I'd rather prefer to make modifications to slang to be able to
> > > generate VM sources for any target language/platform and keep platform
> > > dependent code in image instead in separate file(s). This all to
> > > simplify build process and to keep all things together.
> >
> > You mean subclassing a Thread class?  Is that platform dependent?  If so, I
> > didn't know that and I agree with you - it's should be out in a separate
> > file, if used at all.
> >
> No, i mean to keep ALL plugins code in corresponding methods, and
> never use external sources.
> For example, a SocketPlugin can have subclasses Win32SocketPlugin,
> UnixSocketPlugin
> and in these subclasses we should keep a code for different platforms.
> But not in .c sources.