Re: Check if all 256 bits are clear or set ?

Conceptually this is very smart to invert the logic !

Your idea (Peter 'Shaggy' Haywood) has given me a new idea for the code:

Instead of wasting cpu cycles/times checking everything instead only check what is needed to come to a certain "inverted conclusions".

It is indeed not necessary to check all bits to see if they are all clear, if one of them is not clear then obviously the data is not empty, and the function can exit earlier.

It is indeed not necessary to check all bits to see if they are all set, if one of them is not set then obviously the data is not full, and the function can exit earlier.

HAHA ! Pretty smart and brilliant ! ;) =D

Or is it ? hmmmm

Maybe not.... it depends...

Let's analyze code below:

{$ifdef WIN32}
function TData.IsEmpty : boolean;
type
TUInt32Array = packed array[0..7] of longword;
var
vResult : longword;
begin
result := False;

vResult :=
TUInt32Array(mData)[0] or
TUInt32Array(mData)[1] or
TUInt32Array(mData)[2] or
TUInt32Array(mData)[3] or
TUInt32Array(mData)[4] or
TUInt32Array(mData)[5] or
TUInt32Array(mData)[6] or
TUInt32Array(mData)[7];

if vResult = 0 then
begin
result := True;
end;
end;
{$endif}

Theoretically it needs to pull in 8x 32 bit integers, this could strain the memory bus somewhat, slow down the cpu, while it's waiting for data.... and it may pollute the l1 data cache unnecessarily.

On the other hand it does only one branch comparison.

Now the alternative would be to do 8 branch comparisons. Perhaps there is a golden ground in the middle, maybe only do 2 or 4 comparisons that is a possibility as well.

So different combinations could be tried to see which one performs best.

Here is where a little bit of artificial intelligence could be handy.

The application could measure all versions during active/real world usage with statisticall data tracking... for the first few minutes or so...

Then once another variations and statistics collected it can switch to non-statistical methods and pick the one which it believes is the fastest.

Anyway let's create a worst case counter example and analyze that, untested code:

To cool thing is this also gets rid of the extra variable.

function TData.IsEmpty : boolean;
type
TUInt32Array = packed array[0..7] of longword;
begin
result := False;

// if not empty then exit.
if TUInt32Array(mData)[0]) <> 0 then exit;
if TUInt32Array(mData)[1]) <> 0 then exit;
if TUInt32Array(mData)[2]) <> 0 then exit;
if TUInt32Array(mData)[3]) <> 0 then exit;
if TUInt32Array(mData)[4]) <> 0 then exit;
if TUInt32Array(mData)[5]) <> 0 then exit;
if TUInt32Array(mData)[6]) <> 0 then exit;
if TUInt32Array(mData)[7]) <> 0 then exit;

result := True; // if execution reaches here then return true.
end;
{$endif}

Pretty cool,

These are still 8 data accesses, no or instructions, 8 comparisons, possibly 8 jumps

On average this will probably run at 4,4,4

It will take up some more branch predicators, less data cache

Hard to say which one will run faster ;)  for now my bet would be on the first one, because or instructions are 1 cycle and produces can be 15 or something.

However data access can be in the range of 400 nanoseconds, maybe 400 cycles, that could severely impact performance.

And this this newer version might run faster, depends on how could the L1 data cache lining is, if it's good maybe 10 cycles per data access... for a average total of 40.

Hmmm... I may have to benchmark this sometime ! ;)

And the isFull version:

// untested code

{$ifdef WIN32}
function TData.IsFull : boolean;
type
TUInt32Array = packed array[0..7] of longword;
begin
result := False;

// if not full exit
if TUInt32Array(mData)[0] <> $FFFFFFFF then exit;
if TUInt32Array(mData)[1] <> $FFFFFFFF then exit;
if TUInt32Array(mData)[2] <> $FFFFFFFF then exit;
if TUInt32Array(mData)[3] <> $FFFFFFFF then exit;
if TUInt32Array(mData)[4] <> $FFFFFFFF then exit;
if TUInt32Array(mData)[5] <> $FFFFFFFF then exit;
if TUInt32Array(mData)[6] <> $FFFFFFFF then exit;
if TUInt32Array(mData)[7] <> $FFFFFFFF then exit;

result := True;
end;
{$endif} 

Ok interesting,

Now we truely have something to benchmark ! ;) =D

I am kinda busy so this will have to wait time a further time, but other people are welcome to benchmark this themselfes ! ;) :)

Bye for now,
  And thanks for the feedback and ideas !
    Skybuck Flying ! =D