Woops, checking if all 256 bits are empty or full is only one part of it hihihihi.

Now I need a way to check if all 256 pointers are empty or full if I want to achieve the same efficiency savings and alignment for the rest of the data structures ;)

A pointer can either be 4 bytes or 8 bytes depending on the compiler settings, 32 bits or 64 bits.

So here is where code gets a bit more tricky, and here is where AVX-512 or something might actually help a lot for more advanced computers.

I am all ears and give me your best shot at this ! ;)

In this case a empty pointer can be considered some arbitrary value like 1
In this case a full pointer can be considered some arbitrary value like 2

Or at least values which are not used by virtual memory managers.

The lower 64K range might be safe in windows.

In another technique could be to assign global pointers there own address to take out this address range from the compiler so it cannot allocate it to anything else, example:

var
const_empty : pointer;
const_full : pointer;

begin
const_empty := @const_empty;
const_full := @const_full;
end;

So this is where the real AVX-512 or whatever challenge might begin ! ;)

a special data structure could also be created which contains these pointers setup for easier checking for example:

64 bitters:
AllFull[0] := const_full;
AllFull[1] := const_full;
AllFull[2] := const_full;
AllFull[3] := const_full;

AllEmpty[0] := const_empty;
AllEmpty[1] := const_empty;
AllEmpty[2] := const_empty;
AllEmpty[3] := const_empty;

So basically this is like checking for nil or null but different, with a special meaning so the code can make sense of the data structure if it was supposed to contain full or empty data structures but now instead it contains only a pointer indicating what it was ;) So now you get a bit of an idea of what this "secret" data structure was capable of ! LOL.

Bye,
Skybuck =D

I have created a "professional" github page, so you guys can download the example source code properly and quickly using GIT and don't have to hassle with newsgroup crappy messaging formats:

TData and TLink optimization project

https://github.com/SkybuckFlying/TDataTLinkOptimizationProject

The aim of the project is to:

Optimize the IsEmpty and IsFull routines for TData and TLink.
Optimize the Empty and Full routines for TData and TLink.
Implement WIN64 platform support by implementing BitSet and BitReset.

YES BABY ! =D It's 2021 ! Time to start sharing code a little bit more professionally and effectively and actually good usuable.

However in case you don't know how to use GIT and still want to have a look at the source code then I will post it here anyway,

we can also discuss further ideas for optimization on newsgroups, I am particularly interested in any high speed assembler assistence for x86 and/or x64 instruction set !

unit UnitTDataTLink;

{

TestProgram/Optimization Project for TData and TLink

version 0.02 created on 29 october 2021 by Skybuck Flying

TData contains an array of 32 bytes, in other words 256 bits.
TLink contains an array of 256 pointers.

The mission of this project is to optimize the IsEmpty and IsFull functions
to run as fast as possible on modern x86/x64 processors.

Bonus would be to optimize Empty and Full routines, however beware
the TLink structure uses special pointer values for empty and full.

The verification routines do not need to be optimized and should not
be optimized and are only there to verify any optimized code.

I will sure this code in github for easy downloading and uploading.

Would be cool to get some help with optimizing this code.

The original code used a mCount : byte; member to optimize the code
however this increases the TData structure to 33 bytes which could
be causing misalignment and consumes 3% more memory.

The TLink structure would also fit better if mCount is illiminated.

Both structures contained a mCount : byte variable and have been removed.

Now the same functionality to check for empty and full should be implemented
with as fast as code as possible without using any extra member fields
for the structures to keep them memory efficient like this.

Perhaps these link functions can be optimized with AVX-512 or so ?

}

{

version 0.03 created on 29 october 2021 by Skybuck Flying

Console program turned into multi-device-application project for
multi-platform support.

Project and Source files seperated into seperate folders to avoid
file clutter.

Only WIN32 platform currently implemented.

Other platforms possible thanks to multi-device-project/applicaation.

For some reason it was not possible to add platforms to a console project.

So I modified code so it can work with a multi-device-application, this
added a lot of platforms.

WIN64 platform support is desired !

The rest would be a bonus !

}

interface

uses
Classes; // for TStrings

type
TData = packed record
mData : packed array[0..31] of byte;

procedure Empty;
procedure Full;

function IsEmpty : boolean;
function IsFull : boolean;

// debug routines
function VerifyIsEmpty : boolean;
function VerifyIsFull : boolean;
function VerifyOne : boolean;
function VerifyRandomButOne : boolean;
procedure VerifyAll;
end;

TLink = packed record
mLink : packed array[0..255] of pointer;

procedure Empty;
procedure Full;

function IsEmpty : boolean;
function IsFull : boolean;

// debug routines
function VerifyIsEmpty : boolean;
function VerifyIsFull : boolean;
function VerifyOne : boolean;
function VerifyRandomButOne : boolean;
procedure VerifyAll;
end;

procedure MainTestProgram( ParaOutput : TStrings );

implementation

uses
SysUtils; // for IntToStr

const
ConstDataTestLoops = 1000000; // one million ! =D
ConstLinkTestLoops = 100000; // one hundred thousand ! =D

var
const_empty : pointer;
const_full : pointer;

var
vOutput : TStrings;

procedure OutputMessage( ParaString : string );
begin
vOutput.Add( ParaString );
end;

// only works on win32 platform, need win64 platform versions !

{$ifdef WIN32}
// unlocked versions (multi-threading-unsafe)
procedure BitReset( ParaMemory : pointer; ParaBitIndex : integer );
asm
btr [eax], edx
end;

procedure BitSet( ParaMemory : pointer; ParaBitIndex : integer );
asm
bts [eax], edx
end;

// locked versions (multi-threading-safe)
procedure LockedBitReset( ParaMemory : pointer; ParaBitIndex : integer );
asm
LOCK btr [eax], edx
end;

procedure LockedBitSet( ParaMemory : pointer; ParaBitIndex : integer );
asm
LOCK bts [eax], edx
end;
{$endif}

{$ifdef WIN64}
// unlocked versions (multi-threading-unsafe)
// optimize me ?
procedure BitReset( ParaMemory : pointer; ParaBitIndex : integer );
begin
// to be implemented
ERROR NOT IMPLEMENTED
end;

procedure BitSet( ParaMemory : pointer; ParaBitIndex : integer );
begin
// to be implemented
ERROR NOT IMPLEMENTED
end;

// not really required for this test program but would be nice to have a 64 bit version of this as well.
procedure LockedBitReset( ParaMemory : pointer; ParaBitIndex : integer );
begin

end;

procedure LockedBitSet( ParaMemory : pointer; ParaBitIndex : integer );
begin

end;
{$endif}

{$ifdef WIN32}
procedure TData.Empty;
type
TUInt32Array = packed array[0..7] of UInt32;
begin
TUInt32Array(mData)[0] := 0;
TUInt32Array(mData)[1] := 0;
TUInt32Array(mData)[2] := 0;
TUInt32Array(mData)[3] := 0;
TUInt32Array(mData)[4] := 0;
TUInt32Array(mData)[5] := 0;
TUInt32Array(mData)[6] := 0;
TUInt32Array(mData)[7] := 0;
end;
{$endif}

{$ifdef WIN64}
procedure TData.Empty;
type
TUInt64Array = packed array[0..3] of UInt64;
begin
TUInt64Array(mData)[0] := 0;
TUInt64Array(mData)[1] := 0;
TUInt64Array(mData)[2] := 0;
TUInt64Array(mData)[3] := 0;
end;
{$endif}

{$ifdef WIN32}
procedure TData.Full;
type
TUInt32Array = packed array[0..7] of longword;
begin
// 11223344
TUInt32Array(mData)[0] := $FFFFFFFF;
TUInt32Array(mData)[1] := $FFFFFFFF;
TUInt32Array(mData)[2] := $FFFFFFFF;
TUInt32Array(mData)[3] := $FFFFFFFF;
TUInt32Array(mData)[4] := $FFFFFFFF;
TUInt32Array(mData)[5] := $FFFFFFFF;
TUInt32Array(mData)[6] := $FFFFFFFF;
TUInt32Array(mData)[7] := $FFFFFFFF;
end;
{$endif}

{$ifdef WIN64}
procedure TData.Full;
type
TUInt64Array = packed array[0..3] of UInt64;
begin
// 1122334455667788
TUInt64Array(mData)[0] := $FFFFFFFFFFFFFFFF;
TUInt64Array(mData)[1] := $FFFFFFFFFFFFFFFF;
TUInt64Array(mData)[2] := $FFFFFFFFFFFFFFFF;
TUInt64Array(mData)[3] := $FFFFFFFFFFFFFFFF;
end;
{$endif}

{$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}

{$ifdef WIN64}
function TData.IsEmpty : boolean;
type
TUInt64Array = packed array[0..3] of UInt64;
var
vResult : UInt64;
begin
result := False;

vResult :=
TUInt64Array(mData)[0] or
TUInt64Array(mData)[1] or
TUInt64Array(mData)[2] or
TUInt64Array(mData)[3];

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

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

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

// 11223344
if vResult = $FFFFFFFF then
begin
result := True;
end;
end;
{$endif}

{$ifdef WIN64}
function TData.IsFull : boolean;
type
TUInt64Array = packed array[0..3] of UInt64;
var
vResult : UInt64;
begin
result := False;

vResult :=
TUInt64Array(mData)[0] and
TUInt64Array(mData)[1] and
TUInt64Array(mData)[2] and
TUInt64Array(mData)[3];

// 1122334455667788
if vResult = $FFFFFFFFFFFFFFFF then
begin
result := True;
end;
end;
{$endif}

// TData verification routines

function TData.VerifyIsEmpty : boolean;
var
vIndex : integer;
begin
result := True;
for vIndex := 0 to 31 do
begin
if mData[vIndex] <> 0 then
begin
result := False;
end;
end;
end;