Concurrent programming (was: Would you start a new Smalltalk project today?)

2009/3/22 Igor Stasenko <[hidden email]>:

> 2009/3/22 Michael van der Gulik <[hidden email]>:
>>
>>
>> On Sat, Mar 21, 2009 at 8:38 AM, Janko Mivšek <[hidden email]>
>> wrote:
>>>
>>> Philippe Marschall pravi:
>>> >> Michael van der Gulik wrote:
>>>
>>> >> So now it seems that Gemstone is the only multi-core capable Smalltalk
>>> >> VM :-(.
>>>
>>> > AFAIK Gemstone isn't multi-core capable as well. You can just run
>>> > multiple gems and they share the same persistent memory. Which is
>>> > similar but different.
>>>
>>> Well, Gemstone can for sure be considered as multi-core capable. Every
>>> gem runs on its own process and therefore can run on its own CPU core.
>>> All gems then share a Shared Memory Cache. So, a typical multi-core
>>> scenario.
>>>
>> By multi-core, I mean that the following code would spread CPU usage over at
>> least two cores of a CPU or computer for a while:
>>
>> | sum1 sum2 |
>>
>> sum1 := 0. sum2 := 0.
>>
>> [ 1 to: 10000000 do: [ :i | sum1 := sum1 + 1 ] ] fork.
>>
>> [ 1 to: 10000000 do: [ :i | sum2 := sum2 + 1 ] ] fork.
>>
>> (I didn't try the above so there might be obvious bugs)
>>
>> If a VM can't distribute the load for the above over two or more CPU cores,
>> I consider its multi-core capabilities a hack. No offense intended to the
>> Hydra VM.
>>
>
> Michael, that's would be too ideal to be true, especially for smalltalk.
>
> Consider the following:
>
> | array sum1 sum2 |
>
> sum1 := 0. sum2 := 0.
> array := Array new: 10.
>
> [ 1 to: 10000000 do: [ :i | array at: (10 random) put: (Array new: 10) ] ] fork.
> [ 1 to: 10000000 do: [ :i | array at: (10 random) put: (Array new: 10) ] ] fork.
> 1 to: 10000000 do: [ :i | array at: (10 random) put: (Array new: 10) ].
>
> This code reveals the following problems:
> - concurrent access to same object

> - a heavy memory allocation during running 3 processes, which at some
> point should cause GC.
> While first is more or less on the hands of developer (write a proper
> code to avoid such things), but second is a problem that you need to
> solve to be able to collect garbage in real time , when there are
> multiple threads producing it.

But what strikes me, that there are a lot of code, which never cares
about it, for instance see
Symbol class>> intern:
and in some magical fashion it works w/o problems in green threading..
i'm not sure it will continue running when you enable multiple native
threads.

There is another problem, that squeak processes is cheap (few bytes in
object memory), while allocating new native thread consumes
considerable amount of memory & address space. So, if you map
Processes to native threads, you will lose the ability in having
millions of them, instead you will be limited to thousands.

If, for example, you were trying to allocate an array of arrays concurrently, then I would write (using my namespaces :-) ):

array := Concurrent.Collections.Array new: 1000000000. " We ignore the cost of making this array to begin with :-) "
array withIndexdo: [ :each :i |
    " each will always be nil. "
    array at: i put: (Array new: 10).
].

Concurrent.Collections.Array>>withIndexDo: aBlock
     | nThreads sema |
    nThreads := 1000. " Pull this from a system setting or something. "
    sema := Semaphore withSignals: 0-nThreads. " Needs implementing: signal it -1000 times (or -999 or -1001? Unsure) "
    1 to: nThreads do: [ :i |
        [ (nThreads*i) to: (nThreads*i - 1) do: [ :j
            aBlock value: (self at: j) value: j ]

         sema signal.
         ] fork ].

    sema wait.
    ^ self.

Now consider the overhead of creating a fork vs the actual useful code
which is running within a block.
I presume, this code will run 10x times slower on a single core
processor, comparing to one w/o forks.
So, you will need to have 10 cores to match the computation time with
single core processor.

I think its not wise to introduce parallelism on such low levels (in
Concurrent.Collections.Array>>withIndexDo:). Its like hammering nails
with microscope :)

That's why i'm saying its too good to be true.
Introducing parallelism at such low levels will be a waste. I leaning
toward island model. This is a middle point between no sharing, like
in Hydra and sharing everything, like in what you proposing.

On Mon, Mar 23, 2009 at 12:34 PM, Igor Stasenko <[hidden email]> wrote:

Now consider the overhead of creating a fork vs the actual useful code
which is running within a block.
I presume, this code will run 10x times slower on a single core
processor, comparing to one w/o forks.
So, you will need to have 10 cores to match the computation time with
single core processor.

I think its not wise to introduce parallelism on such low levels (in
Concurrent.Collections.Array>>withIndexDo:). Its like hammering nails
with microscope :)

That's why i'm saying its too good to be true.
Introducing parallelism at such low levels will be a waste. I leaning
toward island model. This is a middle point between no sharing, like
in Hydra and sharing everything, like in what you proposing.

10 times slower? Sounds like a made-up number to me...

" Using 101 threads: "
c := ConcurrentArray new: 1000001.
Time millisecondsToRun: [c withIndexDo: [ :each :i | c at: i put: i asString. ]].     
5711
5626
6074

" Using 11 threads: "
c := ConcurrentArray new: 1000001.
Time millisecondsToRun: [c withIndexDo: [ :each :i | c at: i put: i asString. ]].
3086
3406
3256

" Using 1 thread: "
d := Array new: 1000001.
Time millisecondsToRun: [d withIndexDo: [ :each :i | d at: i put: i asString]].   
2426
2610
2599

My implementation is 1/2 to 1/3 the speed of the single-threaded Array. If the blocks did more work, then the overhead would be lower and some benefit would be gained from using multiple cores.

I don't have a good idea of where the overhead is going - maybe it's being lost in the block copying that is needed to work around Squeak's deficiencies? Or maybe it's waiting for the scheduler to do its stuff?

Implementation attached, MIT license if you're picky.

On Mon, Mar 23, 2009 at 2:21 PM, Michael van der Gulik <[hidden email]> wrote:

On Mon, Mar 23, 2009 at 12:34 PM, Igor Stasenko <[hidden email]> wrote:

Now consider the overhead of creating a fork vs the actual useful code
which is running within a block.
I presume, this code will run 10x times slower on a single core
processor, comparing to one w/o forks.
So, you will need to have 10 cores to match the computation time with
single core processor.

I think its not wise to introduce parallelism on such low levels (in
Concurrent.Collections.Array>>withIndexDo:). Its like hammering nails
with microscope :)

That's why i'm saying its too good to be true.
Introducing parallelism at such low levels will be a waste. I leaning
toward island model. This is a middle point between no sharing, like
in Hydra and sharing everything, like in what you proposing.

10 times slower? Sounds like a made-up number to me...

" Using 101 threads: "
c := ConcurrentArray new: 1000001.
Time millisecondsToRun: [c withIndexDo: [ :each :i | c at: i put: i asString. ]].     
5711
5626
6074

" Using 11 threads: "
c := ConcurrentArray new: 1000001.
Time millisecondsToRun: [c withIndexDo: [ :each :i | c at: i put: i asString. ]].
3086
3406
3256

" Using 1 thread: "
d := Array new: 1000001.
Time millisecondsToRun: [d withIndexDo: [ :each :i | d at: i put: i asString]].   
2426
2610
2599

My implementation is 1/2 to 1/3 the speed of the single-threaded Array. If the blocks did more work, then the overhead would be lower and some benefit would be gained from using multiple cores.

I don't have a good idea of where the overhead is going - maybe it's being lost in the block copying that is needed to work around Squeak's deficiencies? Or maybe it's waiting for the scheduler to do its stuff?

Implementation attached, MIT license if you're picky.

I just tried it on VisualWorks as well. I removed the block copying and renamed the method to "keysDo:" (I never thought of an array like that before... keys and values).

d := Array new: 1000001.
Time millisecondsToRun: [d keysDo: [ :i | d at: i put: i printString]].         
1180
982
1008

" Using 101 threads "
c := ConcurrentArray new: 1000001.

Time millisecondsToRun: [c keysDo: [ :i | c at: i put: i printString. ]].       
 1072
1120
962

At this stage, I'm suspicous about the results :-).