Jason Johnson wrote:
> On 10/21/07, Peter William Lount <peter at smalltalk.org> wrote:
>   
>> tim Rowledge wrote:
>>
>> Ok, so if you really are talking about a "strict" Erlang style model
>> with ONE Smalltalk process per "image" space (whether or not they are in
>> one protected memory space or many protected memory spaces) where
>> objects are not shared with any other threads except by copying them
>> over the "serialization wire" or by "reference" then I get what you are
>> talking about.
>>     
>
> That is a strange way of putting it.  

Why? That is what Erlang achieves via it's total encapsulation of state 
that is only transferred by message passing to and back from a process. 
To achieve the same thing in Smalltalk you'd need to isolate the 
component objects running in an "image" object space with the process 
otherwise you'd be breaking the encapsulation that provides the 
protection against a large number of class es of concurrency problems.

The principle is that anytime you have more than one thread or process 
working on the same memory space, or object space, you WILL have 
concurrency issues (unless your code is just running very simple 
concurrency). The point is that in order to implement your 
utopia-vision-of-simple-problem-free-concurrency (utopia-concurrencia 
for lack of a better name) in Smalltalk you MUST isolate the objects to 
ONLY ONE thread of possible alteration of their state otherwise you end 
up with the possibility of many classes of concurrency problems. Shared 
memory problems exist even within one protected memory space and not 
just between them. To isolate the objects involved in a process you can 
have a separate object space which contains the objects that will be 
operated on. This is the Erlang way, isn't it? The thing about Erlang, 
unless I'm mistaken (and if I am mistaken I'd expect to be corrected), 
is that the objects in a process are only visible to that process until 
the results are returned. The objects that pass in and out of an Erlang 
process are only primitive data types and not complex objects. However 
for Smalltalk you'd need to pass in complex object graphs of arbitrary 
size and connectedness to be general purpose. This then results in a 
version problem.

For example, lets say that you have a graph of one million objects that 
is highly connected and you want to perform not just a simple read 
operation on it but a massive number of edits which would result in the 
graph growing by 50% and the number of connections growing by 70%. For 
speed you decide to implement the algorithms so that they can run in 
parallel upon this moderately large graph of objects. Lets say that you 
have enough compute and memory resources to split this into 10,000 
processes. Now you have the problem of sharing the one million objects 
with the 10,000 processes. That's a lot of data to move around just to 
get things started assuming that you packaged up the whole mess into a 
serial blob and spit it at the various processes. A lot of redundant 
data. Ok, maybe it's better to do this in small chunks, after all 
incrementalism is a powerful technique. For this approach you send each 
of the 10,000 processes a starting node plus a "search pattern" and the 
type of edits it will perform upon the graph along with the actual edits 
as they flow in from another source. So now you have 10,000 processes 
each vying to traverse the one million node graph scanning for patterns 
and applying edits as they find what they are looking for. Some of these 
processes will then update the "shared graph". Oh. What happens when two 
processes both update the same node in this graph but in different ways? 
Let's say one edit in one process adds a connection while the other edit 
in the other node modifies an instance variable on that node? Let's say 
that these two edits occur at the same time and are mutually exclusive - 
that is both edits would break the object's own internal consistency 
rules. So now you have two edits that either must both fail, or one must 
succeed while the other fails or the other must succeed - both can't 
succeed. Now you've got a problem that the magical erlang message 
passing won't solve.

If it does what is the erlang solution to this million node parallel 
editing problem?

Now someone mentioned Software Transactional Memory (STM) so briefly 
that it would be easy to miss. Is that your solution? If so you still 
have other concurrency issues, object versioning issues, plus more to 
deal with. No solution is a panacea for all problems unless you are an 
advocate of silver bullet solutions.

The problem of editing a large graph of objects with many parallel 
threads is the generalized case of a nasty and complex set of 
concurrency and transactional issues. There are many ways to solve this. 
If you reply to this example I would hope that you do so fully 
explaining how you'd handle the concurrency and - importantly - the 
object consistency issues.

> The fact is, Erlang has many processes per image.  

Yes, I understand that early tests indicate that Erlang can handle 
approximately 100,000 or so processes at a time without hickups while 
Java can handle about 8,000 or so before blowing up. I don't know what 
the various Smalltalks can handle, but I doubt it's as high as Erlang 
and is more likely less than even Java - just a guess though. Maybe 
someone has worked it out.


> Many more then you could ever get as real
> processes or native threads (as a test I made a little program that
> spawned 64 *thousand* threads and passed messages between them on my
> laptop).
>   

That's only because the current crop of operating systems were designed 
and envisioned when a few hundred processes and threads was considered a 
lot. Also because native operating system processes take a lot of resources.


> But with their model, process creation is extremely cheap.  And since
> there is no sharing as far as the language is concerned, there is no
> need for locking to slow everything down.
>   

Yes, and how would the no sharing be implemented in Smalltalk?

How would you solve the concurrency one million node editing problem 
above without locking in your utopian threading implementation?


> Smalltalk can do this too. I think it needs a little work still, but
> I'm optimistic about what can be done here.
>   

What would you do to Smalltalk to make it do this. So far you and the 
others have been very short on specifics and have just argued that 
something magical can be done to make concurrency happen without locks. 
A few papers and web sites have been linked to but no one has written 
down what they are proposing or what they mean past it can be done.

I'll grant you that you can see that it can be done. Please illuminate 
what it is that you see can be done in detail and how you might do it. 
Thanks.


>> However, you'll still end up with concurrency control issues and you've
>> got an object version explosion problem occurring as well. How will you
>> control concurrency problems with your simplified system? Is there a
>> succinct description of the way that Erlang does it? Would that apply to
>> Smalltalk?
>>     
>
> Much like how Smalltalk does it, as it turns out.  That is, you don't
> have a version problem so much as you have "old" and "new".  So when
> ready you send the "upgrade" message to  the system and all new calls
> to the main functions of a process will be the new version.  All
> currently running code will access the old code until it's completion,
> and all new code runs in the new space.
>   

Ok, so there would be 10,000 separate process-object-spaces with the one 
million nodes being edited and new nodes being created in each of these 
10,000 separate spaces. How do you expect to "merge" the results and 
solve the edits that will inevitably cause "logical data inconsistency" 
collisions?


>> You simplified concurrency system also dramatically alters the Smalltalk
>> paradigm.
>>     
>
> The current paradigm is fine-grained locked/shared state. 

So?


>  In my opinion and the opinion of many (probably most in fact, outside of the
> Java community) people who are more expert is this area then you or I,
> we *have* to move away from this paradigm.
>   

Why? Please provide more than anticidal or belief driven comments for 
this point of view. What are the reasons? What is it that you'd be 
moving towards?


>   
>> Is this the approach that Cincom is using in their Visual Works system?
>> They seem to not be embracing the notion of native threads.
>>     
>
> Thank God. :)
>   

It's a huge mistake on their part in my humble view.

While it may be easy from the point of view of adapting their image it's 
a huge mistake. I've had many people comment that that's one of the 
reasons that Java is better than Smalltalk - it already works with 
multiple cpu cores. Yes they have to solve the concurrency problems, but 
those are NO WORSE than the concurrency problems that already exist 
within Smalltalk when running with a single native process and multiple 
(green threads aka) Smalltalk Processes. No different. Do you actually 
get that? If you don't then you fail to appreciate that the approach 
that Cincom is taking isn't going to solve the concurrency problems 
since - unless they correct me on this - it seems that their direction 
is to simply have N-instances of their image (in the same memory space 
or in separate operating system processes) where N would frequently be 
the same as the number of cores on the computer (or server) in question 
(although the instances could be more or less as needed). Each 
individual image would still have the problems of multi-threading within 
it IF AND ONLY IF there are multiple threads forked. Then you have all 
the same concurrency problems that happen with multiple threads on 
objects in one memory space. Sure this is a simpler approach for them as 
they don't have to completely toss their current virtual machine design 
- they can hack it by simply using one image space per native processor 
or per native operating system process. Then all they need is a cheap 
and dirty distributed object transport system to move object graphs 
(complete or partial) around between the various images. This will work 
for them and ALL Smalltalk systems including Squeak. In fact this can 
work now essentially with unmodified Smalltalk systems - all that's 
reallly needed is the distributed objects framework and there are a few 
of those kicking around.

This is of course a far cry from the radical concurrency system that is 
being proposed by the erlangization concurrency proponents.



>   
>> However it's
>> also unlikely that they are embracing the notion of only ONE Smalltalk
>> process per image either.
>>     
>
> If I understand you correctly, then I would suggest not to use the
> word "image" as this is confusing.  Another way to put it would be
> "each process has it's own view of the world".  And honestly, what is
> the problem you see with this?
>   

Ok. How will you implement that?


> Right now, if you run two separate images with only one thread or
> process, then you have two processes that each have their own set of
> objects in their own space interacting with each other.
>   

Yes, exactly. This is the illusion that Erlang provides. This can also 
be achieved now with ANY Smalltalk version just by starting multiple 
images - one for each core if you want to map them that way as may be 
"natural" to want to do.


> Now we add a way for one image to send a message *between* images.
>   

Yes. That can be done now.


> Perhaps the VM can detect when we are trying to do this, but instead
> of complicating the default Smalltalk message sending subsystem, lets
> make it explicit with some special binary message:
>
> Processes at: 'value computer' ! computeValue.
>   

There isn't any need for new syntax with the "!" character. Now sure 
you're using it with a binary message selector "!" but why obfuscate it. 
I'd recommend using a keyword selector for better clarity. Thanks.

> Now we have the ability to send messages locally within a process, and
> a way of freely sending between processes.  No locking and the
> problems associated with locking.
>   

Not so. You'd have to transmit - in my example above - one million 
objects to the various images and have them compute and return their 
resutls which would then have to be combined in a manner that leaves the 
graph of objects in a consistent state with one and a half million 
objects and 70% more interconnections between them. It is this parallel 
updating of many parts of the same data graph that will require the 
concurrency controls.


> So, now what is stopping us from moving this separate process *inside
> the same image*?  

Nothing but you've got to address the concurrency problem that I've 
mentioned above.


> If you fork a process and he starts making objects,
> no other processes have references to those objects.  No shared state
> issue there.  This part could work right now today with no changes to
> the VM.
>   

Are you talking about forking a new operating system process with a copy 
of the image? The "copied" objects or the objects that were in the 
"image" to begin with are "duplicates" (or N-plicates really) which is a 
real headache if they get modified in multiple images and need to be 
"recombined" into one real persistent state.

These are object database problems and attempting to split the 
processing into multiple threads to avoid the "locking" issues does not 
solve the problem. It just pushes it further away. While it might work 
for some applications like telephone switching systems it can't 
generalize to ALL types of problems which could benefit from concurrency 
solutions. That's wishful thinking and a pipe dream otherwise known as a 
silver bullet.


> The only issue I can think of are globals, 

All Object Databases have a couple of rooted objects. Maybe many more 
than a couple.


> the most obvious being
> class side variables.  Note that even classes themselves are not an
> issue because without class side variables, they are effect free
> (well, obviously basicNew would have to be looked at).
>   

I'm not sure what you mean.


> But I think this issue is solvable.  The VM could take a "copy on
> write" approach on classes/globals.  That is, a class should be side
> effect free (to itself, i.e. it's the same after every call), so let
> all processes share the memory space where meta-class objects live.
> But as soon as any process tries to modify the class in some way
> (literally, it would be the class modifying itself), he gets his own
> copy.  Processes must not see changes made by other processes, so a
> modification to a global class is a "local only" change.
>   

Yes, a variant of the Software Transactional Memory. However, you still 
have the problems mentioned above.


> Of course the only big thing left would be; what happens when we add a
> new class.  But Erlang has had success with the old/new space
> approach, and what Smalltalk has now is very similar.
>   

Having two spaces, old and new space, won't solve the problems mentioned 
above when you have N processes (threads) running on M-objects in 
parallel and need to combine the results of the parallel computations.

Many problems have this "split processes off with their chunk of data" 
and "recombine" the results. Many of these problems are simplified - if 
possible - so that the results can't collide with the issues presented 
above. However, we are not talking about those special cases - such as 
parallel ray tracing algorithms. We are talking about the completely 
generic cases that occur in general purpose and every day use of code in 
Smalltalk applications - such as the massive Smalltalk business database 
front end applications which are typical at many corporations today and 
which utilize many threads to accomplish their parallel tasks in order 
to speed up the user experience. A real world consequence of this is 
increased productivity of thousands of users day in and day out at these 
corporations.

Maybe your applications aren't a complex as these but I don't see the 
benefits of an Erlang ONLY approach. I do see the benefit of STM and 
Erlang approaches in some cases but why intentionally limit the tool box 
to just a few cases? It makes no sense to ignore the harsh reality of 
concurrency issues by picking a limited set of solutions.

All the best,

Peter William Lount
Peter at smalltalk.org

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20071023/54cd96e9/attachment.htm