UDP Speed Test Version 2.93 Now Available !

"Chris Thomasson" <cristom@comcast.net> wrote in message
news:RMWdnYlPX9_6K3LbnZ2dnUVZ_ournZ2d@comcast.com...[color=blue]
> "Skybuck Flying" <spam@hotmail.com> wrote in message
> news:fcoc5m$gbe$1@news6.zwoll1.ov.home.nl...[color=green][color=darkred]
>>> Why not do a producer/consumer where producer thread generates data and
>>> consumer thread gathers it and presents it to GUI?[/color]
>>
>> The data needs only to be displayed once per second.[/color]
>
> Then the consumer would just display once per-second? Why not? It could
> dequeue a thousand messages and only display them once per-second, no?[/color]

This is how it works:

A Windows Timer is set to fire every second.

The GUI receives this timer message.

"This is the consumer"

Ofcourse the consumer can not block on some queue, that would freeze the
gui.

Bye,
Skybuck.

A thread does:

while running do
begin
lock
some code
some code
unlock
end;

So it's almost always locked... by not really so it's not a flaw.

Let's continue this discussion from the slightly less simple example I gave
in another sub thread.

I am interested in seeing if you have any alternative to replace the
critical section.

Bye,
Skybuck.

Also if you do have some alternative, some pseudo code would be just fine to
help me understand your method.

Then later we could discuss actual code.

Bye,
Skybuck.

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:fcpdr9$lao$1@news3.zwoll1.ov.home.nl...[color=blue]
>
> "Chris Thomasson" <cristom@comcast.net> wrote in message
> news:RMWdnYlPX9_6K3LbnZ2dnUVZ_ournZ2d@comcast.com...[color=green]
>> "Skybuck Flying" <spam@hotmail.com> wrote in message
>> news:fcoc5m$gbe$1@news6.zwoll1.ov.home.nl...[color=darkred]
>>>> Why not do a producer/consumer where producer thread generates data and
>>>> consumer thread gathers it and presents it to GUI?
>>>
>>> The data needs only to be displayed once per second.[/color]
>>
>> Then the consumer would just display once per-second? Why not? It could
>> dequeue a thousand messages and only display them once per-second, no?[/color]
>
> This is how it works:
>
> A Windows Timer is set to fire every second.
>
> The GUI receives this timer message.
>
> "This is the consumer"
>
> Ofcourse the consumer can not block on some queue, that would freeze the
> gui.[/color]

You can do it with GUI like this:

static queue g_q;

consumer {
message* msg = 0;
for(;;) {
WaitForGUIEvent(GUI, 1000); /* wait 100 milliseconds for event */
msg = queue_pop_try(&g_q); /* non-blocking */
if (msg) {
message_process(msg);
}
}
}

producer() {
message* msg = 0;
for(;;) {
/* wait for the need to create data */
msg = /* acquire/init a message object */
if (msg) {
queue_push(&g_q, msg);
}
}
}




We don't need a GUI. I want to do a simple Console application that creates
two threads and two single-producer/consumer queues for bi-directional
communication. Something like very simple like this:


struct thread {
spsc_queue sendq;
spsc_queue recvq;
};


thread_entry(thread *_this, thread *other) {
message* msg = /* acquire new message */
spsc_queue_push(&other->sendq);
for(;;) {
msg = spsc_queue_pop(&_this->recvq); /* blocks on empty */
message_process(msg);
spsc_queue_push(&other->sendq);
}
}


int main() {
thread worker_1, worker_2;
handle t1 = thread_start(thread_entry, &worker_1, &worker_2);
handle t2 = thread_start(thread_entry, &worker_2, &worker_1);
thread_join(t2);
thread_join(t1);
return 0;
}


We can see if a CRITICAL_SECTION based single producer/consumer queue can
beat a lock-free one. Please note that a lock-free queue of this nature does
not any interlocked instructions or any expensive #StoreLoad or #LoadStore
style memory barriers.

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:fcpdan$i2v$1@news3.zwoll1.ov.home.nl...[color=blue]
> Irrelevant example, it's too simple.
>
> What I ment is a slightly less simple example:
>
> Here is a better example:
>
> CriticalSection.Enter;
>
> A := A + 1;
> B := B + 1;
> C := C + A;
> D := D + B;
> E := E + 5;
> F := F + 7;
>
> CriticalSection.Leave;
>
> What you described is now useless.
>
> All the "counters" must remain synchronized.
>
> What is your alternative for the critical section ?[/color]

My first piece of advise is to keep your locked regions of code very small.
You don't want to do complex calculations or anything that may block inside
of them. As for lock-free, well it is simply not applicable to all
situations. However, here is a ad-hoc lock-free answer to your question:

union count64 {
__int8 a;
__int8 b;
__int8 c;
__int8 d;
__int8 e;
__int8 f;
__int8 g;
__int8 h;
__int64 whole;
};


__int64 count64_inc(union count64 volatile* _this) {
count64 swap, cmp;
do {
cmp.whole = _this->whole;
swap.a = cmp.a + 1;
swap.b = cmp.b + 1;
swap.c = cmp.c + swap.a;
swap.d = cmp.d + swap.b;
swap.e = cmp.e + 5;
swap.f = cmp.f + 7;
swap.g = cmp.g + swap.d;
swap.h = cmp.h + 1;
} while (! CAS64(&_this->whole, cmp.whole, swap.whole));
return swap.whole;
}



You are generally limited to working within memory sizes that are directly
*CAS'able.; the memory also need to be properly aligned. In this case we can
use 64-bit CAS.



_______
* - CAS stand for Compare-And-Swap

I don't quite understand how your example works but here's what I understand
from it:

First of all your method/idea is to not block any code.

Your idea is to use temporarely or alternative storage.

Each thread then copies/reads values from one of the storages and update
another storage.

What does CAS do ?

And why do you call it compare and swap ?

Also why is the loop needed ?

What's the idea behind it ?

Bye,
Skybuck.

First of all I do need a GUI.

Second of all the GUI must be updated in the main thread for Delphi
applications otherwise strange things could happen.

If you do want to have a seperate thread to update some gui then the
synchronize method must be used.

Also how is the wait for gui thing suppose to work ?

Maybe you should try bringing your ideas into practice with a Delphi GUI
application :)

Furthermore I do not believe that simply creating more threads gives any
performance improvements at all.

Using more threads simply means using more context switches which means more
cpu processing power wasted.

Maybe the application would get more processing time from the operating
system because it has more threads but that's cheating.

Bye,
Skybuck.

Ok, I read up on lock free algorithm and cas and it's now clear to me what
CAS does.

It's still not clear to me how your example works.

I shall read some more about wait free algorithms.

Bye,
Skybuck.

Ok,

I shall try an attempt to explain your code:

Maybe whole means all the other variables.

__int64 count64_inc(union count64 volatile* _this)
{
count64 swap; // additional storage
count64 cmp; // additional storage
do {
cmp.whole = _this->whole; // compare storage is overwritten with
parameter

// new/swap storage is calculated based on old compare storage.
swap.a = cmp.a + 1;
swap.b = cmp.b + 1;
swap.c = cmp.c + swap.a;
swap.d = cmp.d + swap.b;
swap.e = cmp.e + 5;
swap.f = cmp.f + 7;
swap.g = cmp.g + swap.d;
swap.h = cmp.h + 1;

// cas is performend on the parameter, with the old value, and new value
// if cas fails then the above code is repeated over and over and over
and over until it succeeds.
} while (! CAS64(&_this->whole, cmp.whole, swap.whole));
return swap.whole; // finally if it succeeds the new values are returned.
}

I shall try this idea in Delphi and see what happens ;)

Ofcourse as already mentioned on wikipedia which I read... this might always
fail if something else is always updating it.

Bye,
Skybuck.

Also maybe the union is not necessary.

I shall try and work out an idea:

The data producer simply modifies it's variables.

Then once it's done it copies the variables to some external/shared storage.

This has some drawbacks:

The copy takes time, extra external/shared storage necessary.

However it could have some adventages.

For example:

The data producer only tries to copy it once.

If it fails it doesn't try again and simply continues, since the data is not
that important... newer values are ok too.

The consumer also makes his own copy of this shared data.

So two copies occur... one from the producer, and one from the consumer.

The idea is to minimize the sections of code that need to be locked.

The shared memory is a way to quickly exchange data... without having to
wait on more expensive routines like string displays or conversions...
and gui update codes.

So idea is to:

Freely read/write data in data producer.

Freely read data in data consumer.

Only the copieing of data from producer to shared memory or from shared
memory to consumer is locked.

And it's locked in such a way that the producer can simply continue if the
consumer has it locked.

So far this would only work for a read only consumer.

Suppose consumer needs to alter data.... then it needs to copy back the data
to the shared memory.

Suppose the data producer meanwhile altered it's copy then ofcourse a race
condition has occured.

If both threads needs to alter data then a thread might have to throw away
his calculations and start over with the newly updated memory.

Might be interesting..

I'll give it a try and see what happens.

Me wonders though... if copieing would be faster than waiting for a critical
section.

Bye,
Skybuck.

Hi,

I have created a little test/benchmark program, to compare these "CAS"
locking/unlocking ideas against critical sections.

I suspect Windows probably uses CAS for critical sections so this test might
be really dumb expect there are some differences in the way it's used, the
first technique uses copies+cas, the second technique simply uses shared
data+critical sections.

So the way the locking is used is different, so maybe not so dumb after all:

One conclusion can be drawn:

The critical section method is of higher quality, the screen gets updated on
a more regular basis.

Performance-wise it's inconclusive, maybe if the producers did more complex
calculations differences might start showing.

// *** Begin of Code ***

program Project1;

{$APPTYPE CONSOLE}

{

Test Lock Free Idea's

Version 0.01 created on 19 september 2007 by Skybuck Flying

Investigate idea to write non locking or lock free code

Idea is to copy data, modify one copy, while the others remain stable.

The stable copies or used by those that needed synchronized data.

This simple benchmark compares my own Locking/Unlocking Techniques against
CriticalSections.

I am not yet sure if the locking/unlocking techniques work perfeclty.

So far I can see one problem: Delphi strings which are copy-on-write which
might give problems for
locking/unlocking code/data copies.

This is where critical section might be safer.

Benchmark conclusion:

More or less inconclusive, code performs more or less the same, the critical
sections probably slightly
faster because of less code overhead.

Maybe if the data producer did more complex calculations it might become an
interesting technique.

However when thing can clearly be seen if the comments are uncommented.

The locking/unlocking mechanism is of less quality because the try lock
might fail and then nothing
will be updated to the screen !

}

{$RangeChecks OFF}
{$OverflowChecks Off}

uses
SysUtils, Classes, Windows, SyncObjs;

// Skybuck's Atomic TryLock Algorithm/Method:
function TryLock( var ParaLock : LongBool ) : LongBool;
begin
result := not LongBool( InterlockedCompareExchange( Integer(ParaLock),
Integer(LongBool(True)), Integer(LongBool(False)) ) );
end;

// Skybuck's Atomic TryUnLock Algorithm/Method:
function TryUnlock( var ParaLock : LongBool ) : LongBool;
begin
result := LongBool( InterlockedCompareExchange( Integer(ParaLock),
Integer(LongBool(False)), Integer(LongBool(True)) ) );
end;

type
TsharedData = record
mCriticalSection : TcriticalSection; // for critical producer/consumer
mLocked : LongBool;
mA : integer;
mB : integer;
mC : double;
mD : string;
mF : byte;
mG : word;
mRuns : int64;
end;

TProducer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

TConsumer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

TCriticalProducer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

TCriticalConsumer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

var
mProducerCopy : TsharedData;
mConsumerCopy : TsharedData;
mSharedCopy : TsharedData;

procedure TProducer.Execute;
begin
while not Terminated do
begin
with mProducerCopy do
begin
// lock our memory.
if TryLock( mLocked ) then
begin
mA := mA + 1;
mB := mB + 2;
mC := mC + 3;
mD := 'Hello: ' + IntToStr(mA);
mF := mF + 4;
mG := mG + 5;
mRuns := mRuns + 1;

// now try locking the memory of the others which should be updated with
our data
// if the lock fails, to bad, do no update, and simply continue with our
own data.

if TryLock( mConsumerCopy.mLocked ) then
begin
mConsumerCopy.mA := mA;
mConsumerCopy.mB := mB;
mConsumerCopy.mC := mC;
mConsumerCopy.mD := mD; // could be a problem, since it's reference
counted, we must force a copy somehow
mConsumerCopy.mF := mF;
mConsumerCopy.mG := mG;

TryUnLock( mConsumerCopy.mLocked );
end;

TryUnLock( mLocked ); // should always succeed me thinks :)
end; // else do nothing
end;
end;
end;

procedure TConsumer.Execute;
begin
while not Terminated do
begin
// Sleep( 1000 );

with mConsumerCopy do
begin
// try to lock our memory
if TryLock( mLocked ) then
begin

mA := mA + 1;
mA := mB;
mC := mC + 3;
(*

writeln('Lockedxx:');
writeln( mA );
writeln( mB );
writeln( mC );
writeln( mD );
writeln( mF );
writeln( mG );
*)

// unlock it
TryUnLock( mLocked );
end;
end;
end;
end;

procedure TCriticalProducer.Execute;
begin
while not Terminated do
begin
with mSharedCopy do
begin
mCriticalSection.Enter;

mA := mA + 1;
mB := mB + 2;
mC := mC + 3;
mD := 'Hello: ' + IntToStr(mA);
mF := mF + 4;
mG := mG + 5;
mRuns := mRuns + 1;

mCriticalSection.Leave;
end;
end;
end;

procedure TCriticalConsumer.Execute;
begin
while not Terminated do
begin
with mSharedCopy do
begin
// Sleep( 1000 );

mCriticalSection.Enter;

// Let's do something crazy instead to full test it

mA := mA + 1;
mA := mB;
mC := mC + 3;

(*

writeln('Critical:');



writeln( mA );
writeln( mB );
writeln( mC );
writeln( mD );
writeln( mF );
writeln( mG );
*)

mCriticalSection.Leave;
end;
end;
end;

procedure ClearCopy( ParaCopy : TSharedData );
begin
with ParaCopy do
begin
mLocked := false;
mA := 0;
mB := 0;
mC := 0;
Pointer(mD) := nil;
mF := 0;
mG := 0;
end;
end;

procedure Main;
var
mProducer : TProducer;
mConsumer : TConsumer;

mCriticalProducer : TCriticalProducer;
mCriticalConsumer : TCriticalConsumer;

begin
writeln('program started');

ClearCopy( mProducerCopy );
ClearCopy( mConsumerCopy );
ClearCopy( mSharedCopy );

mSharedCopy.mCriticalSection := TCriticalSection.Create;

// perform locked test
mProducer := TProducer.Create(True);
mProducer.FreeOnTerminate := false;

mConsumer := TConsumer.Create(True);
mConsumer.FreeOnTerminate := false;

// wait 1 second so program can be loaded
Sleep( 1000 );

mProducer.Resume;
mConsumer.Resume;

sleep(10000);

mConsumer.Terminate;
mProducer.Terminate;

mConsumer.WaitFor;
mConsumer.Free;

mProducer.WaitFor;
mProducer.Free;

// perform critical test

mCriticalProducer := TCriticalProducer.Create(True);
mCriticalProducer.FreeOnTerminate := false;

mCriticalConsumer := TCriticalConsumer.Create(True);
mCriticalConsumer.FreeOnTerminate := false;

// wait 1 second so program can be loaded
Sleep( 1000 );

mCriticalProducer.Resume;
mCriticalConsumer.Resume;

sleep(10000);

mCriticalConsumer.Terminate;
mCriticalProducer.Terminate;

mCriticalConsumer.WaitFor;
mCriticalConsumer.Free;

mCriticalProducer.WaitFor;
mCriticalProducer.Free;

mSharedCopy.mCriticalSection.Free;

WriteLn('Locked Producer Runs : ', mProducerCopy.mRuns );
WriteLn('Critical Producer Runs: ', mSharedCopy.mRuns );

writeln('press enter to exit');
readln;

writeln('program finished');
end;

begin
try
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
end.

// *** End of Code ***

Enjoy ;)

Bye,
Skybuck =D

Yup the TryLock method I wrote is probably the same as
TCriticalSection.TryEnter :)

Here is the same program slightly modified to use TryEnter instead ;)

// *** Begin of Code ***

program Project1;

{$APPTYPE CONSOLE}

{

Test Lock Free Idea's

Version 0.01 created on 19 september 2007 by Skybuck Flying

Investigate idea to write non locking or lock free code

Idea is to copy data, modify one copy, while the others remain stable.

The stable copies are used by those that needed synchronized data.

This simple benchmark compares my own Locking/Unlocking Techniques against
CriticalSections.

I am not yet sure if the locking/unlocking techniques work perfeclty.

So far I can see one problem: Delphi strings which are copy-on-write which
might give problems for
locking/unlocking code/data copies.

This is where critical section might be safer.

Benchmark conclusion:

More or less inconclusive, code performs more or less the same, the critical
sections probably slightly
faster because of less code overhead.

Maybe if the data producer did more complex calculations it might become an
interesting technique.

However one thing can clearly be seen if the comments are uncommented.

The locking/unlocking mechanism is of less quality because the try lock
might fail and then nothing
will be updated to the screen !

}

{

Version 0.02 created on 19 september 2007 by Skybuck Flying

Apperently Delphi 2007 has a new member for TCriticalSection which is not
that well documented...

It's probably actually the same as "my" TryLock method lol

To prove this the code will be replaced with that method to see if it works
the same :)

Yup it works.

}


{$RangeChecks OFF}
{$OverflowChecks Off}

uses
SysUtils,
Classes,
Windows,
SyncObjs;

// Skybuck's Atomic TryLock Algorithm/Method:
// disabled
{

function TryLock( var ParaLock : LongBool ) : LongBool;
begin
result := not LongBool( InterlockedCompareExchange( Integer(ParaLock),
Integer(LongBool(True)), Integer(LongBool(False)) ) );
end;

// Skybuck's Atomic TryUnLock Algorithm/Method:
function TryUnlock( var ParaLock : LongBool ) : LongBool;
begin
result := LongBool( InterlockedCompareExchange( Integer(ParaLock),
Integer(LongBool(False)), Integer(LongBool(True)) ) );
end;
}

type
TsharedData = record
mCriticalSection : TcriticalSection; // for critical producer/consumer
mLocked : LongBool;
mA : integer;
mB : integer;
mC : double;
mD : string;
mF : byte;
mG : word;
mRuns : int64;
end;

TProducer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

TConsumer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

TCriticalProducer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

TCriticalConsumer = class(Tthread)
private

protected
procedure Execute; override;

public

end;

var
mProducerCopy : TsharedData;
mConsumerCopy : TsharedData;
mSharedCopy : TsharedData;

procedure TProducer.Execute;
begin
while not Terminated do
begin
with mProducerCopy do
begin
// lock our memory.
// if TryLock( mLocked ) then

if mCriticalSection.TryEnter then
begin
mA := mA + 1;
mB := mB + 2;
mC := mC + 3;
mD := 'Hello: ' + IntToStr(mA);
mF := mF + 4;
mG := mG + 5;
mRuns := mRuns + 1;

// now try locking the memory of the others which should be updated with
our data
// if the lock fails, to bad, do no update, and simply continue with our
own data.

if mConsumerCopy.mCriticalSection.TryEnter then
begin
mConsumerCopy.mA := mA;
mConsumerCopy.mB := mB;
mConsumerCopy.mC := mC;
mConsumerCopy.mD := mD; // could be a problem, since it's reference
counted, we must force a copy somehow
mConsumerCopy.mF := mF;
mConsumerCopy.mG := mG;

mConsumerCopy.mCriticalSection.Leave;
end;

mCriticalSection.Leave;
end; // else do nothing
end;
end;
end;

procedure TConsumer.Execute;
begin
while not Terminated do
begin
// Sleep( 1000 );

with mConsumerCopy do
begin
// try to lock our memory
if mCriticalSection.TryEnter then
begin

mA := mA + 1;
mA := mB;
mC := mC + 3;
(*

writeln('Lockedxx:');
writeln( mA );
writeln( mB );
writeln( mC );
writeln( mD );
writeln( mF );
writeln( mG );
*)

// unlock it
mCriticalSection.Leave;
end;
end;
end;
end;

procedure TCriticalProducer.Execute;
begin
while not Terminated do
begin
with mSharedCopy do
begin
mCriticalSection.Enter;

mA := mA + 1;
mB := mB + 2;
mC := mC + 3;
mD := 'Hello: ' + IntToStr(mA);
mF := mF + 4;
mG := mG + 5;
mRuns := mRuns + 1;

mCriticalSection.Leave;
end;
end;
end;

procedure TCriticalConsumer.Execute;
begin
while not Terminated do
begin
with mSharedCopy do
begin
// Sleep( 1000 );

mCriticalSection.Enter;

// Let's do something crazy instead to full test it

mA := mA + 1;
mA := mB;
mC := mC + 3;

(*

writeln('Critical:');



writeln( mA );
writeln( mB );
writeln( mC );
writeln( mD );
writeln( mF );
writeln( mG );
*)

mCriticalSection.Leave;
end;
end;
end;

procedure ClearCopy( ParaCopy : TSharedData );
begin
with ParaCopy do
begin
mLocked := false;
mA := 0;
mB := 0;
mC := 0;
Pointer(mD) := nil;
mF := 0;
mG := 0;
end;
end;

procedure Main;
var
mProducer : TProducer;
mConsumer : TConsumer;

mCriticalProducer : TCriticalProducer;
mCriticalConsumer : TCriticalConsumer;

begin
writeln('program started');

ClearCopy( mProducerCopy );
ClearCopy( mConsumerCopy );
ClearCopy( mSharedCopy );

mProducerCopy.mCriticalSection := TCriticalSection.Create;
mConsumerCopy.mCriticalSection := TCriticalSection.Create;
mSharedCopy.mCriticalSection := TCriticalSection.Create;

// perform locked test
mProducer := TProducer.Create(True);
mProducer.FreeOnTerminate := false;

mConsumer := TConsumer.Create(True);
mConsumer.FreeOnTerminate := false;

// wait 1 second so program can be loaded
Sleep( 1000 );

mProducer.Resume;
mConsumer.Resume;

sleep(10000);

mConsumer.Terminate;
mProducer.Terminate;

mConsumer.WaitFor;
mConsumer.Free;

mProducer.WaitFor;
mProducer.Free;

// perform critical test

mCriticalProducer := TCriticalProducer.Create(True);
mCriticalProducer.FreeOnTerminate := false;

mCriticalConsumer := TCriticalConsumer.Create(True);
mCriticalConsumer.FreeOnTerminate := false;

// wait 1 second so program can be loaded
Sleep( 1000 );

mCriticalProducer.Resume;
mCriticalConsumer.Resume;

sleep(10000);

mCriticalConsumer.Terminate;
mCriticalProducer.Terminate;

mCriticalConsumer.WaitFor;
mCriticalConsumer.Free;

mCriticalProducer.WaitFor;
mCriticalProducer.Free;

mProducerCopy.mCriticalSection.Free;
mConsumerCopy.mCriticalSection.Free;
mSharedCopy.mCriticalSection.Free;

WriteLn('Locked Producer Runs : ', mProducerCopy.mRuns );
WriteLn('Critical Producer Runs: ', mSharedCopy.mRuns );

writeln('press enter to exit');
readln;

writeln('program finished');
end;

begin
try
Main;
except
on E:Exception do
Writeln(E.Classname, ': ', E.Message);
end;
end.

// *** End of Code ***

Again Enjoy LOL :)

I am starting to be like you: Writing useless code LOL :) ?!? ;) :) ???

Bye,
Skybuck.

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:fcq5em$ihb$1@news3.zwoll1.ov.home.nl...[color=blue]
> Hi,
>
> I have created a little test/benchmark program, to compare these "CAS"
> locking/unlocking ideas against critical sections.[/color]
[...]

Well, that program did not have lock-free code in it; you are still using
locks. Try_Lock is not the same as lock-free CAS update. You basically
comparing:

if (try_lock(...) {
<critical-section>
unlock();
}

with:

lock(...)
<critical-section>
unlock(...)


That's lock-based vs. lock-based...



For a lock-free vs. lock-based test of a counter, the code can look like
this:

/* lock-free counter */
void inc(int volatile *psrc) {
int cmp;
do {
cmp = *psrc;
} while(! CAS(psrc, cmp, cmp + 1));
}

/* lock-based counter */
void inc(int volatile *psrc) {
lock();
(*psrc)++;
unlock();
}


Once you hit the lock-based code with multiple-threads you will see the
negative effect of blocking occur. Here is some Delphi code you can look at:

[url]http://groups.google.com/group/comp.programming.threads/msg/1c88f35820683e7b[/url]

The author of that code was trying to wrap up some functionality of my
AppCore library. I would examine his Delphi code. Humm... Where can I get a
good Delphi compiler and IDE Skybuck? I guess I can fool around with
something and perhaps be better able to help to write a lock-free algorithm
in it.

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:fcq69t$5uh$1@news6.zwoll1.ov.home.nl...[color=blue]
> Yup the TryLock method I wrote is probably the same as
> TCriticalSection.TryEnter :)[/color]
[...]

Bingo! :^)

Try one of these Delphi versions:

[url]http://cc.codegear.com/free/delphi[/url]

I myself have CodeGear Delphi 2007.

You could try one of the personal editions so it doesn't expire I think.

Also the "minimum" Delphi version is called:

Turbo Delphi Explorer.

I don't quite understand the difference between Turbo Delphi Explorer and
Delphi 2007, since I never tried Turbo Delphi Explorer.

But the screenshots look similiar. Turbo Delphi Explorer is probably just a
stripped down version of Delphi 2007.

[url]http://www.codegear.com/products/turbo[/url]

Maybe I should try it sometime... But stripped down versions kinda scare
me.. I am scared I might miss some important feature... or I am scared I
can't compile somebody elses code/website code :)

I think for you Turbo Delphi Explorer might be enough to try out Win32 +
Threading + GUI + IDE + Debugger and such development ;) in Delphi/Pascal.

Otherwise try Delphi 2005 Personal... but I think that one probably less
good because it's older.

I think Turbo Delphi Explorer just as new as Delphi 2007 :)

Bye,
Skybuck.

"Chris Thomasson" <cristom@comcast.net> wrote in message
news:EJudnUkZvKd5AG3bnZ2dnUVZ_oytnZ2d@comcast.com...[color=blue]
> "Skybuck Flying" <spam@hotmail.com> wrote in message
> news:fcq5em$ihb$1@news3.zwoll1.ov.home.nl...[color=green]
>> Hi,
>>
>> I have created a little test/benchmark program, to compare these "CAS"
>> locking/unlocking ideas against critical sections.[/color]
> [...]
>
> Well, that program did not have lock-free code in it; you are still using
> locks. Try_Lock is not the same as lock-free CAS update. You basically
> comparing:
>
> if (try_lock(...) {
> <critical-section>
> unlock();
> }
>
> with:
>
> lock(...)
> <critical-section>
> unlock(...)
>
>
> That's lock-based vs. lock-based...[/color]

There is a difference:

The first one will continue.

The second one will block.

So it's continued-lock-based vs blocking-lock-based ;)
[color=blue]
> For a lock-free vs. lock-based test of a counter, the code can look like
> this:[/color]

What you describe below is not really lock free.

It's actually worse than my "continued lock based" method.

At least my method doesn't block.

Your method "blocks" because of the while loop.
[color=blue]
> /* lock-free counter */
> void inc(int volatile *psrc) {
> int cmp;
> do {
> cmp = *psrc;
> } while(! CAS(psrc, cmp, cmp + 1));
> }
>
> /* lock-based counter */
> void inc(int volatile *psrc) {
> lock();
> (*psrc)++;
> unlock();
> }
>[/color]

You see, you think you invented something, but in fact it's even slightly
worse ;)

Bye,
Skybuck.

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:fcq7ur$qu5$1@news6.zwoll1.ov.home.nl...[color=blue]
>
> "Chris Thomasson" <cristom@comcast.net> wrote in message
> news:EJudnUkZvKd5AG3bnZ2dnUVZ_oytnZ2d@comcast.com...[color=green]
>> "Skybuck Flying" <spam@hotmail.com> wrote in message
>> news:fcq5em$ihb$1@news3.zwoll1.ov.home.nl...[color=darkred]
>>> Hi,[/color][/color][/color]
[...][color=blue]
> What you describe below is not really lock free.
>
> It's actually worse than my "continued lock based" method.[/color]

Using try lock is nothing new:

[url]http://groups.google.com/group/comp.programming.threads/msg/a3e38e27df971e0d[/url]

[url]http://groups.google.com/group/comp.programming.threads/browse_frm/thread/f80fb2901b42e447[/url]


[color=blue]
> At least my method doesn't block.
>
> Your method "blocks" because of the while loop.[/color]

You confusion the work block with spin; blocking imples a thread has wait on
a kernel waitset which is different than spinning on CAS. My example was
lock-free; not wait-free. Anyway, here is a loop-less version that does not
spin:


/* returns previous value using wait-free */
bool count_add_try(int volatile *psrc, int count, int *pprev) {
int const cmp = *psrc;
if (CAS(psrc, cmp, cmp + count))) {
if (pprev) { *pprev = cmp; }
return true;
}
return false;
}

/* returns previous value using lock-free */
int count_add(int volatile *psrc, int count) {
while(! count_add_try(psrc, count));
}


/* non-blocking example */
static int volatile shared_count = 0;

multiple_threads() {
for(;;) {
int prev;

if (count_add_try(&shared_count, 1, &prev)) {
/* update gui with previous counter value */

} else {
/* work on something else */
}

/* do some work */
}
}





[color=blue]
> You see, you think you invented something, but in fact it's even slightly
> worse ;)[/color]

I don't claim to invent using CAS in a loop. That has been around for ages.
I advise you to read the following post in great detail:

[url]http://groups.google.com/group/comp.programming.threads/msg/113d2d6f90563eda[/url]

Maybe you are re-implementing something that has already been implemented ?!

The big question is:

Do CriticalSections.Enter, Leave and TryEnter spin on 'cas' or do they do
something else (On Windows XP) ? ;)

Bye,
Skybuck.

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:fcq7pi$8g4$1@news6.zwoll1.ov.home.nl...[color=blue]
> Try one of these Delphi versions:
>
> [url]http://cc.codegear.com/free/delphi[/url]
>
> I myself have CodeGear Delphi 2007.[/color]
[...][color=blue]
> But the screenshots look similiar. Turbo Delphi Explorer is probably just
> a stripped down version of Delphi 2007.
>[/color]
[...]

I downloaded turbo Delphi. I will play around with it for a while and see if
I can get anywhere. BTW, there is no pesky garbage collector in this
language right?

"Skybuck Flying" <spam@hotmail.com> wrote in message
news:fcr723$uj7$1@news2.zwoll1.ov.home.nl...[color=blue]
> Maybe you are re-implementing something that has already been implemented
> ?!
>
> The big question is:
>
> Do CriticalSections.Enter, Leave and TryEnter spin on 'cas' or do they do
> something else (On Windows XP) ? ;)[/color]

CriticalSections have to perform interlocked rmw and memory barrier
instructions to enforce the coherency of a piece of state that can be
considered a proxy. For example, take a look at my implementation of
Peterson's classic algorithm:

[url]http://groups.google.com/group/comp.programming.threads/browse_frm/thread/c49c0658e2607317[/url]

What does the operations on the shared variables the algorithm has to
perform actually have to do with the datum contained in its critical
section?

See I can lock and unlock this mutual exclusion technique multiple times and
it won't touch any state whatsoever... Example:

lock();
unlock();


Useless because the 'lock/unlock' operations DO NOT touch user data; agreed?
I can lock and unlock all day long, which means I am using expensive
interlocked rmw and membar instructions for nothing. Here is the kicker... A
lock-free algorithm can use the same instructions contained in the 'lock'
operation of a mutex to mutate actual user state.

PLEASE READ THE FOLLOWING:

[url]http://groups.google.com/group/comp.programming.threads/msg/113d2d6f90563eda[/url]


read it once... Read it again... and again.



You should gather that the instructions that a mutex uses operates on the
state of the lock; not ANY state contained in any of its critical-sections.
A lock-free operation either modifies user shared state, or not. A lock has
to work on its on state BEFORE it can even think about allowing the
programmer of its various critical sections to issue loads and stores on
shared data. Again, lock-free operation either mutates actual user state, or
nothing. Lock-based has to play around with its own PERSONAL state before it
can decide to let anybody do anything.


Another try:


a lock-free operation on a simple monotonic counter would either increment
the counter, or fail. A lock-based operation would have to try and modify
its own state that has nothing to do with the counter BEFORE it can do
anything. This has overheads... BTW, when the lock-based algorithm swings
its private state into something that says it can proceed, well, it
subsequently will be forced to undo that state change in the form of an
unlock operation. Of course the unlock will be calling membars (e.g.,
#LoadStore | #StoreStore to be exact using SPARC notation) to actually
perform the mutation which allows another thread to get a chance.


Does that make any sense to you at all?