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:

• Initialize: after object creation no RingBuffer is created, so we must first call Initialize to initiate RingBuffer buffer size. The minimum length is 1 link pointer. Call Initialize only once!
• InsertLeft function will insert link to the left of RingBuffer side. If buffer is full than function will return 0 in any other case will return the current buffer count value.
• InsertRight function will insert link to the right of RingBuffer side. If buffer is full than function will return 0 in any other case will return the current buffer count value.
• RemoveLeft function will remove link from the left of RingBuffer side. If buffer is empty than function return 0 any other case will return the at remove link count value.
• RemoveRight function will remove link from the right of RingBuffer side. If buffer is empty than function return 0 any other case will return the at remove link count value.
• Length property will return maximum number of links stored in RingBuffer.
• Count function will return the current count of links in RingBuffer.
• Empty function will set left and right pointer to start of memory buffer.

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