6. August 2009 by Gorazd Jernejc

Last modification: 3. September 2009

 

 

Lock-Free Multi-Thread Read/Write Conflict Optimised Ring Buffer, Queue And Stack For Delphi Pascal.

 

 On Internet we can find a lot of ring buffer lock-free solutions, but the speed/reliability is more or less critical!

This RingBuffer is consequence of cooperation with OmniThreadLibry project.

Ring buffer is also known as Circular buffer.

 

 Here I will introduce fast lock-free ring buffer structure, which can be base for other lock free structures, such a queue or a stack.

 

 

RingBuffer Implementation

 

Let's take a look to the following diagram of RingBuffer visualization:

 

 

Ring Buffer will store only a pointer (PDATA or link) of some memory locations, and of course our RingBuffer isn't ideal so it is limited by maximum length defined at Initialize. All informations about RingBuffer are stored in TRingBuffer record.

 

  TRingBuffer = record

    Left       : TReferencedPtr;

    Right      : TReferencedPtr;

    Length     : integer;

    EndBuffer  : pointer;

    Buffer     : record end;

  end; { TgjRingBuffer }

 

Variable Left points on utmost left link of ring buffer. The Right variable points on utmost right first, free link in reserved memory. When Left and Right have the same value the RingBuffer is empty.

 

When we are calling function InsertLeft then at first decrement Left pointer, after that we compare Left and Right pointers, if there are the same, then RingBuffer is full, at last we will copy link location. Certainly all this operation is lock-free and without multi threads conflict like ABA.

 

Length is a maximum number of Link-s stored in RingBuffer.

 

EndBuffer is pointer on last link in reserved memory.

 

Buffer is pointer on allocated memory in which is stored our RingBuffer. Any link in Buffer is composed from pointer (PDATA or link) and Reference, look TReferencedPtr. Reference is used to prevent ABA conflicts.

 

 

RingBuffer Class

 

  TgjRingBuffer = class(TObject)

  strict private

    rbRingBuffer      : PRingBuffer;

    rbRingBufferMemPtr: pointer;

    class var rbLoopTicks: cardinal;

    procedure MeasureExecutionTimes;

  protected

    procedure Empty; inline;

    function  GetLength: integer; inline;

  public

    destructor Destroy; override;

    function  Count: integer; inline;

    procedure Initialize(const Length: integer);

    function  InsertLeft(const link: pointer): integer; inline;

    function  InsertRight(const link: pointer): integer; inline;

    function  RemoveLeft(var link: pointer): integer; inline;

    function  RemoveRight(var link: pointer): integer; inline;

    property  Length: integer read GetLength;

  end; { TgjRingBuffer }

 

 

Use of the TgjRingBuffer object is very simple:

 

 

Queue Implementation

 

RingBuffer has all properties of Queue so Dequeue and Enqueue are just inherited.

 

function TgjQueue.Dequeue(var link: pointer): integer;

begin

  result := inherited RemoveRight(link);

end; { TgjQueue.Dequeue }

 

function TgjQueue.Enqueue(const link: pointer): integer;

begin

  result := inherited InsertLeft(link);

end; { TgjQueue.Enqueue }

 

Stack Implementation

 

RingBuffer has also all properties of Stack. The situation is similar as at queue. Check the source code for implementation.

 

 

 

WORNINGS:

1) RingBuffer is intended for multi-core CPUs and use XMM instructions so CPU must support SSE2. The minimum CPU level is Pentium 4.

2) RingBuffer sprce is written for Delphi 2007.

 

 

Ring Buffer Multi Read/Write Flow Queue Test

 

Test program works on MS WIN XP or higher MS OS!

Reader and writer tasks are very simple to rich maximum data bandwidth between threads.

On may computer: QuadCore Intel Core 2 Quad Q6600, 2400 MHz and memory DDR2-800 (400 MHz) is typical bandwidth higher then 1.000.000 links (msg) per second. Test program support up to 128 Read and up to 128 write tasks.

If we run all 256 Read and Write tasks the bandwidth is still more than 1.000.000 msg/s!

 

 

History:

 

1.00: 4. August 2009

·   First official release.

 

1.01: 17. August 2009

·   TgjRingBuffer.Initialize: Ensured 16-byte buffer alignment.

·   Added SSE2 test in initialization section.

 

1.02: 20. August 2009

·   TgjRingBuffer.Length is stored now in TRingBuffer record.

·   TgjRingBuffer.Count: Now call faster GetRingBufferDistance.

 

1.03: 27. August 2009

·   Functions InsertLeft, InsertRight, RemoveLeft and RemoveRight now return the current position in ring buffer. If buffer is full or empty than will return 0.

 

3. September 2009

Added ring buffer flow queue test.

 

DOWNLOAD: RingBuffer.zip