BorlandTalk.com

Martin James · Guest

I've got this array of pointers and two pointers to this array, one starts
off pointing at the top and the other pointing at the base:

dataArray=array[0..summat-1] of pointer;
...
basePointer:=@dataArray;
topPointer:=@dataArray[summat-1];

Two threads start off on this data, one eating it from the base and the
other from the top, inc-ing and dec-ing the index pointers. Eventually, the
two pointers will meet in the middle and both threads must realise that they
have hit each other with one thread, or the other, having cleanly eaten up
the last data value. The threads inc and dec the pointers via a method
function:

function incLow:boolean;
function decHigh:boolean;

so these functions should return 'true' if a data item is available via. the
changed index pointer, or 'false' if there is no more data.

How can I do this without a critical section? A CS here would be too slow
and inappropriate due to the tightness of the loop and large probability of
contention during the crash.

I should be able to work this out myself but I have a headache from the
multiThreaded sorts. I think I need beer.

Rgds,
Martin

Joe Bain · Guest

Martin James wrote:

Les Pawelczyk · Guest

Martin James · Guest

Martin James · Guest

Cristian Nicola · Guest

Very simple and elegant Very Happy

I was about to suggest this option :D

Cristian Nicola

to swap use something like:

function CAS(aDestAddr: pointer; v1: pointer; v2: integer; n1: pointer; n2:
integer): boolean;
asm
push ebx
push esi
mov esi, aDestAddr
mov eax, v1
mov edx, v2
mov ebx, n1
mov ecx, n2
{ LOCK cmpxchg8b qword ptr [esi] }
db $F0,$0F,$C7,$0E
sete result
pop esi
pop ebx
end;

and pass:
aDestAddr : the address of record holding the 2 values
v1: old base
v2: old top
n1: new base
n2: new top

In case of first function new base = old base, new top = old
top -sizeof(pointer)
In case of second function new base = old base + sizeof(pointer), new top =
old top.

"Les Pawelczyk" <les_at_pixelpointpos_dot_com> wrote

Cristian Nicola · Guest

Forgot to important things:
TYourRecord = record
Top: pointer;
Bottom: pointer;
end;

and creating a new record should be 8 byte aligned (so using normal var, or
normal memory allocation functions is NOT enough)...

Cristian Nicola

ps:

{ allocates a 8-byte align node }
function AllocMem8(size: integer): pointer;
var
p: pointer;
begin
result:= nil;
GetMem(p, size + Cool

;
if (p = nil) then
exit;
case (integer(p) and $0000000F) of
$0, $8: result:= pointer(integer(p) + Cool

;
$4, $C: result:= pointer(integer(p) + 4);
end;
if (result <> nil) then
pointer(pointer(integer(result) - 4)^):= p
else
FreeMem(p);
end;

{ deallocates a 8-byte aligned node }
procedure FreeMem8(var p: pointer);
begin
if (p <> nil) then
begin
FreeMem(pointer(pointer(integer(p) - 4)^));
p:= nil;
end;
end;

"Cristian Nicola" <n_cristian (AT) hotmail (DOT) com> wrote

Cristian Nicola · Guest

Forgot another thing:
CAS function would return false if the values have changed so the algorithm
should be:
while true do
begin
{ preserve values }
oldtop:= myrec^.top;
oldbottom:= myrec^.bottom;
{ compare the collision }
if oldtop = oldbottom then
begin
{ collision }
break;
end
else
begin
{ move one end }
if cas(myrec, oldtop, oldbottom, oldtop, oldbottom - sizeof(pointer))
then
break;
end;
end;

"Cristian Nicola" <n_cristian (AT) hotmail (DOT) com> wrote

Martin James · Guest

Thanks everybody!

I will try Les/Cristian 'LOCK CMPXCHG8B', (I remember when opcode mnemonics
were only 3 chars long - now longer than high-level language identifiers).

I was also thinking of Joe's comment.

Down at the pub last night, I thought of a cunning, 'composite' plan that
avoids most of the locking overhead. The thread-manager that runs the
threads can issue a work-request for each 'train' with a count for each
thread that is [half of one array length-1]. Even if both threads then
happen to suck on the same array, they will not be able to reach each other
and crash, so no slow locking is required. When these tasks are both done,
the 'closeness of the trains' in each array is checked. If they are still
all well apart, the tasks re-issue themselves with a count of [half of
smallest closeness-1]. Eventually, the trains in one or more of the arrays
wil be so close that there is no advantage of going through a thread-manager
dispatch cycle again. Both tasks will then be re-issued with an instruction
to continue to completion, but using the slow bus lock mechanism with the
world's longest opcode mnemonic.

Rgds,
Martin

Cristian Nicola · Guest

Really nice site:

http://faydoc.tripod.com/cpu/index.htm

Cristian

"Martin James" <mjames_falcon (AT) dial (DOT) pipex.com> wrote

Martin James · Guest

Thanks very much!

Rgds,
Martin Smile

)