Faster TMultiReadExclusiveWriteSynchronizer?

Question

Is there a faster kind of TMultiReadExclusiveWriteSynchronizer out there? FastCode perhaps?

Starting with Windows Vista, Microsoft added a Slim Reader/Writer lock. It performs much better than Delphi's TMultiReadExclusiveWriteSynchronizer. Unfortunately it only exists in Windows Vista and later, something which few customers actually have yet.

Presumably the concepts in use inside a Slim Reader/Writer lock could be redone in native Delphi code - but has anyone done it?

i have a situation where acquiring and releasing locks on a TMultiReadExclusiveWriteSynchronizer (even when there's no contention - a single thread), causes 100% overhead (the operation time doubles). i can run without locking, but then my class is no longer thread-safe.

Is there a faster TMultiReadExclusiveWriteSynchronizer?

Note: If i use a TCriticalSection i only suffer a 2% performance hit (although critical sections are known to be fast when the acquire succeeds, i.e. while it's single threaded and there's no contention). The downside of a CS is that i lose the "multiple readers" capability.

The Measurements

Using TMultiReadExclusiveWriteSynchronizer a sizable amount of time is spent inside BeginRead and EndRead:

i then ported the code to use Window's own SlimReaderWriter Lock (which some code rewrite, as it doesn't support recursive lock taking), and profiled the resutls:

• TMultiReadExclusiveWriteSynchronizer: 10,698 ns per iteration
  10,697,772,613 ns to iterate 1,000,000 times

• SRWLock: 8,802 ns per iteration
  8,801,678,339 ns to iterate 1,000,000 times

• Omni Reader-Writer lock: 8,941 ns per iteration
  8,940,552,487 ns to iterate 1,000,000 times

A 17% improvement when using SRWLocks (aka Omni's spinning lock).

Now, i cannot switch the code permanantly over to use Windows Vista SRWLocks, as there are some entire enterprises of customers that are still on Windows XP.

The Slim locks are just careful use of InterlockedCompareExchange functions; but more careful than i can successfully use. I'm this far away from just stealing the 140 machine instructions involved, and have it done.

Bonus Reading

• Is Critical Section always faster?
• How to write fast multi-thread Delphi applications

Answer 1

TOmniMREW from OmniThreadLibrary claims to be faster and more lightweight:

OTL is an excellent threading lib, BTW.

Sample Code

TOmniReaderWriterLock = class(TInterfacedObject, IReaderWriterLock)
private
   omrewReference: Integer;
public
   { IReaderWriterLock }
   procedure BeginRead;
   procedure EndRead;
   procedure BeginWrite;
   procedure EndWrite;
end;

{ TOmniReaderWriterLock }

procedure TOmniReaderWriterLock.BeginRead;
var
  currentReference: Integer;
begin
    //Wait on writer to reset write flag so Reference.Bit0 must be 0 than increase Reference
    repeat
        currentReference := Integer(omrewReference) and not 1;
    until currentReference = Integer(InterlockedCompareExchange(Pointer(omrewReference), Pointer(Integer(currentReference) + 2), Pointer(currentReference)));
end;

procedure TOmniReaderWriterLock.EndRead;
begin
    //Decrease omrewReference
    InterlockedExchangeAdd(@omrewReference, -2);
end;

procedure TOmniReaderWriterLock.BeginWrite;
var
    currentReference: integer;
begin
    //Wait on writer to reset write flag so omrewReference.Bit0 must be 0 then set omrewReference.Bit0
    repeat
        currentReference := omrewReference and (not 1);
    until currentReference = Integer(InterlockedCompareExchange(Pointer(omrewReference), Pointer(currentReference+1), Pointer(currentReference)));

    //Now wait on all readers
    repeat
    until omrewReference = 1;
end;

procedure TOmniReaderWriterLock.EndWrite;
begin
    omrewReference := 0;
end;

Answer 2

In the end i used a compromise solution. The Omni reader-writer lock uses "slim" principles (spinning bit-manipulations). Like Window's own, it doesn't support lock escalation. I've tested it, and it doesn't seem to lockup crash or deadlock.

In the end i used a fallback situation. The most generic of generic interfaces to support "read-write" concepts:

IReaderWriterLock = interface
   ['{6C4150D0-7B13-446D-9D8E-866B66723320}']
   procedure BeginRead;
   procedure EndRead;
   procedure BeginWrite;
   procedure EndWrite;
end;

And then we decide at runtime which implementation to use. If we're on Windows Vista or new, use Window's own SlimReaderWriter, otherwise fallback to Omni version:

TReaderWriterLock = class(TObject)
public
   class function Create: IReaderWriterLock;
end;

class function TReaderWriterLock.Create: IReaderWriterLock;
begin
   if Win32MajorVersion >= 6 then //SRWLocks were introduced with Vista/Server 2008 (Windows version 6.0)
   begin
      //Use the Windows built-in Slim ReaderWriter lock
      Result := TSlimReaderWriterLock.Create;
   end
   else
   begin
      //XP and earlier fallback to Omni equivalent
      Result := TOmniReaderWriterLock.Create;
   end;
end;

Note: Any code is released into the public domain. No attribution required.

Answer 3

The Delphi TMultiReadExclusiveWriteSynchronizer is very sophisticated - it can be acquired recursively and you can update from Read to Write.

This comes with a cost, which in this case means managing a bucket of shared state per thread. As the Windows thread-local mechanics (accessible via threadvar) is too simplistic for this (not able cope with several MREWS instances) it is done in a rather inefficient way – see the RTL or JCL sources – the implementations are quite similar, sharing bad performance and update-deadlock risk.

First ensure you really need the MREWS functionality – I assume, according to proportional size of locking overhead to the workload, you will be much better off with a TCriticalSection.

If you really-really need it, go with the Delphi implementation and watch out for the possible hidden unlock in BeginWrite – see it's documentation and return value meaning.

It is possible to implement a Vista-like SRW using the Interlocked functions or inline assembly, but it's not worth the effort in most cases.

Answer 4

The JCL has a MREWS that is a different implementation which might work for you. Not sure what version of windows it requires.

http://wiki.delphi-jedi.org/wiki/JCL_Help:TJclMultiReadExclusiveWrite

http://wiki.delphi-jedi.org/index.php?title=JEDI_Code_Library

Answer 5

Try this? It can be used as a normal variable:

type myclass=class
              Lock:TOBRWLock;
              function ReadIt:Integer;
              procedure WriteIt(A:Integer);
             end;  
function ReadIt:Integer;
begin;
 Lock.LockRead;
 Result:=GetVal;
 Lock.UnLockRead;
end;

There is much space for improvement and you can build from here varieties that favour read above write or just act differently depending on the need.

const ldFree    = 0;
      ldReading = 1;
      ldWriting = 2;
type TOBRWLock          = record
                 [Volatile]WritersWaiting,
                           ReadersWaiting,
                           ReadersReading,
                           Disposition    : Integer;
                           procedure LockRead;
                           procedure LockWrite;
                           procedure UnlockRead;
                           procedure UnlockWrite;
                           procedure UnReadWrite;
                           procedure UnWriteRead;
                          end;

procedure TOBRWLock.LockRead;
var SpinCnt : NativeUInt;
    I       : Integer;
begin
 SpinCnt:=0;
 TInterlocked.Increment(ReadersWaiting);
 repeat
  if (Disposition=ldReading)
     then begin
           I:=TInterlocked.Increment(ReadersReading);
           if (Disposition<>ldReading) or (I=1)(*Only 1 read reference or Disposition changed, suspicious, rather retry*)
              then begin
                    TInterlocked.Decrement(ReadersReading);
                    continue;
                   end
              else begin(*Success*)
                    TInterlocked.Decrement(ReadersWaiting);
                    break;
                   end;
          end;
  if (WritersWaiting<>0)or(Disposition<>ldFree)
     then begin
           SpinBackoff(SpinCnt);
           continue;
          end;
  if TInterlocked.CompareExchange(Disposition,ldReading,ldFree)=ldFree
     then begin
           TInterlocked.Increment(ReadersReading);
           TInterlocked.Decrement(ReadersWaiting);
           break;
          end;
  SpinBackoff(SpinCnt);
 until False;
end;

procedure TOBRWLock.LockWrite;
var SpinCnt : NativeUInt;
begin
 SpinCnt:=0;
 TInterlocked.Increment(WritersWaiting);
 repeat
  if (Disposition<>ldFree)
     then begin
           SpinBackoff(SpinCnt);
           continue;
          end;
  if TInterlocked.CompareExchange(Disposition,ldWriting,ldFree)=ldFree
     then begin
           TInterlocked.Decrement(WritersWaiting);
           break;
          end
     else SpinBackoff(SpinCnt);
 until False;
end;

procedure TOBRWLock.UnlockRead;
begin
 {$IFDEF DEBUG}
 if Disposition<>ldReading
    then raise Exception.Create('UnlockRead a lock that is not Reading');
 {$ENDIF}
 TInterlocked.Decrement(ReadersReading);
 if ReadersReading=0
    then begin;
          if TInterlocked.CompareExchange(Disposition,ldFree,ldReading)<>ldReading
             then raise Exception.Create('Impossible 310');
         end;
end;

procedure TOBRWLock.UnlockWrite;
begin
 {$IFDEF DEBUG}
 if Disposition<>ldWriting
    then raise Exception.Create('UnlockWrite a lock that is not Writing');
 {$ENDIF}
 if TInterlocked.CompareExchange(Disposition,ldFree,ldWriting)<>ldWriting
    then raise Exception.Create('Impossible 321');
end;

procedure TOBRWLock.UnReadWrite;
var SpinCnt : NativeUInt;
begin
 {$IFDEF DEBUG}
 if Disposition<>ldReading
    then raise Exception.Create('UnReadWrite a lock that is not Reading');
 {$ENDIF}
 TInterlocked.Increment(WritersWaiting);
 SpinCnt:=0;
 repeat
  if ReadersReading=1(*Only me reading*)
     then begin;
           if TInterlocked.CompareExchange(Disposition,ldWriting,ldReading)<>ldReading(*Must always succeed*)
              then raise Exception.Create('Impossible 337');
           TInterlocked.Decrement(ReadersReading);
           TInterlocked.Decrement(WritersWaiting);
           break;
          end;
  SpinBackoff(SpinCnt);
 until False;
end;