Hi
This is my proposition of algorithm and its implementing multithreaded FIFO queue without lock.
First use array of pointers to handle messages.
I've use it in my program, it works.
I think it may by useful.

site: http://www.emadar.com/fpc/lockfree.htm
source: http://www.emadar.com/fpc/flqueue.pas

There is also generic implementation of the same algorithm. Its my first generic approach.
Any help appreciated.

it;s not so much text, but source is very short, its explain much better.

Darek

DarekM wrote

Hi This is my proposition of algorithm and its implementing multithreaded FIFO queue without lock.

Hmm 'Push' and 'Pop' sound like a stack, but the implementation seems to implement a FIFO indeed, with a head and tail.

You're sure about the situation where two threads are accessing head and tail at the same time, and there is only one item in your FIFO ?

Micha

Micha Nelissen pisze:

It should be enqueue and dequeue. I was left because first I try implement stack.

You're sure about the situation where two threads are accessing head and tail at the same time, and there is only one item in your FIFO ?

Of course (if CAS (interlockedCompareExchange) has proper implementation , that, I think, should be avoided
Queue is empty when tail=head,
when is not equal only one thread can receive object form queue, second make again iteration

The same with ABA problem.

Darek

What about a long running (eg daemon) application?

If temp/tail hits the upper boundary of Integer?

(If I understand it correctly)
I don't know if interlockedIncrement gives a boundary error, but if not, it still fails.
- With currently integer, it gets a negative value, once crossing 0x7fffffff, and SetObject will attempt to read/write out-of-bounds memory.
- Assuming temp/tail being unsigned: it will go from 0xffffffff to 0. "0xffffffff mod fsize" may return a value greater 0, "0x00 mod fsize" will be zero. You make an unexpected jump within the list.

Martin

Martin Friebe pisze:

Thats right.
But I can avoid this.
1. make length of tab equal power of two
2. use longword instead of integer
3.instead MOD use result:=tab[lp and fmask];
and fmask:=$F or $FF or $FFF

Thanks to find bug.

Darek

You will need to test it, but the following may also work

procedure tFlQueue.push(const tm : tNodeQueue);
var
  newTemp,
  lastTail,
  newTail : integer;
begin
  newTemp := temp;
  while newTemp >= fsize begin
    // if it is true, every thread is going to attempt to fix it, before
doing the increment.
    // this means no thread will increase the value
    //  => one thread will to succeed (since the only reason "temp NE
newTemp" is that temp has been decreased)
    // newTemp is bigger than fsize, so the result can not become negative.
interlockedCompareExchange(pointer(temp),pointer(newTemp-fsize),pointer(newTemp));
     newTemp := temp;
  end;
  newTemp:=interlockedIncrement(temp) mod fsize; // make sure we are
always in range
  lastTail:=newTemp-1;
  if lastTail < 0 then lastTail := fsize -1;
  setObject(lastTail,tm); // you can remove the "mod" in setobject
  repeat
pointer(newTail):=interlockedCompareExchange(pointer(tail),pointer(newTemp),pointer(lastTail));
  until (newTail=lastTail);
end;

The "repeat" at the end does still work. In order to set "tail" to "0" (newTemp=0) => "tail" must first get "9" (as lastTail will be 9).

Only flaw is, if fsize is close enough to the upper data tpye boundary, and enough threads do InterLockedInvrement, (after all having simultaneously passed the repeat at the start), then you can still run over the boundary.
However this can only happen if you have more threads, than (upperBoundary - fsize).
So you can specify, that it is save up to this amount of parallel threads

IMHO the unit should have a warning (in the comments) that there it is the users responsibility *not* to store more elements than fsize. There is no check, and you will loose data, if you try to do so.

But as I said, no warranty that this will work, I haven't done any testing...

Martin

Martin Friebe pisze:

 newTemp:=interlockedIncrement(temp) mod fsize; // make sure we are
always in range

It seems ok, but then we have 2 IF more.
And the same should repeat with pop

Because we cant change size of queue in run, we have to make it so big that always will be enough.
For me it should be ten time bigger, than observe maximum (1000 its only 4 kB of ram).

Ok, Ive write warning in source

And i've upload new version of program.

Darek

An if is unimportant, more important is the number of locked operations, especially on multi core systems they might eat hundreds of clock cycles.

While watching this thread, I started to ask myself 2 questions (which may be related):

They just came to mind a multi-core systems where mentioned, possible even systems with several CPUs.
(Admiringly they are more looking like they should be on an intel-mailing list, I just hope someone may know...)

1)
procedure tFLQueue.setObject(lp : integer;const aobject : tNodeQueue);
begin
tab[lp and fMask]:=aObject;
end;

The index ("lp and fMask") has been derived via "interlockedIncrement", and the surrounding code makes sure, that only one thread will access this value at this time.

But lets assume the value was read immediately before, by another core/cpu. It therefore is in that core/cpu's cache. Will this cache be invalidated/updated by a *simple* write to memory? Or will the other core/cpu see the old value from it's cache?
I am no expert on this, but from the page referred below, "lock"ed cpu-instructions, take special care of this.
I don't know about unlocked instructions?

http://static.scribd.com/docs/59o7jahfstz7r.swf?INITIAL_VIEW=width chapter 7

"caching the same memory locations are managed properly while atomic operations are performed"
What does the cache coherency do (if anything) while non atomic operations are performed?

2)
I found various references that interlockedIncrement and co, work only on 32 bit bounded data? This may or may not vary on the CPU. The Intel doc only says, it will affect execution time, but looking at the MS doc http://msdn2.microsoft.com/en-us/library/ms683614.aspx it says it must be on a 32bit boundary.
Does that affect FPC? ( as there may be none intel CPUs?)

If so, then the Implementation of the Queue would have to ensure alignment (as I believe fpc, aligns integer on 16 bit?)

Martin

Florian Klaempfl pisze:

An if is unimportant, more important is the number of locked operations, especially on multi core systems they might eat hundreds of clock cycles.

There are atomic operations, the should not eat much more than ordinal INC or ADD,
and second CAS is invoked only one time per fSize iteriations.

Darek

__

If course they are. They require no more a bus lock as in 486 times but a synchronization of all caches for this particular memory location.

I just finished a unit that provides a FIFO and similar stuff, so I'm very interested.

IMHO you should not use "push" and "put" as this suggests a LiFo ("Stack"). With my unit I mostly intended to recreate the putc() and getc() functions in glibc (though I did neither use them nor took a look at their implementations). Thus IMHO for a "FiFo" you should use a "put" and "get" notation.

My unit provides an (optionally automatically growing and shrinking) FiFo fast byte handling. It has putc and getc (with the same parameters (Integer!) as it's done in glibc), plus unget() and unput() for revers operations (which in fact implements FiFo behavior). Moreover it provides a TStream based interface handling blocks of bytes for all these operations.

It does not yet have any locking mechanism ! I have been thinking about this but did not start to implement it.

Moreover I do like that your component provides a "generic" interface. (finally a good use for this paradigm <g> ).

I have to think a bit more about the locking mechanism you suggest.

I intended to use a single word as a semaphore to protect the access to the structure and fall back to an OS-based wait (e.g. by TCriticalSection) if it can't be acquired. This is how a FUTEX works in Linux (maybe TCriticalSection even already uses such algorithm)

-Michael

Some Typos:

It has putc() and getc() (with the same parameters (Integer!) as it's done in glibc), plus ungetc() and unputc() for reverse operations (which in fact implements LiFo Stack behavior).

-Michael

Michael Schnell pisze:

I have to think a bit more about the locking mechanism you suggest.

I;ve added some links on my site

FUTEX is based on atomic operation, the same as I used. but with lockfree algorithms You don't protect

FUTEX is based on atomic operation, the same as I used. but with lockfree algorithms You don't protect understand this, but I'm nut sure that this really is advantageous.

Any atomic operation in a multicore system with a cache for each core imposes a delay for cache synchronization. Thus as little as possible "lock" operations should be issued. 99,99% of the calls will not see another processor or thread concurrently working on the FiFo data.

The implementation similar to Futex in the no blocked case needs one lock operation on entry and one on exit. Thus using a thing similar to FUTEX needs some 2,0001 locked operations per call.

An implementation with a single lock operation per call - if possible - would be better, of course.

-Michael

Michael Schnell pisze:

Any implementation of thread synchronization need care of cache. FUTEX, which rely on atomic primitives can't be faster than primitives alone.

In lockfree algorithms we don't block data any
time others threads can process data.

Many of researches claim that lockfree algorithms are faster, specially with many concurrent threads.

Thus as little as possible "lock" operations should be issued. 99,99% of the calls will not see another processor or thread concurrently working on the FiFo data.

You have to prevent data loss, when You have hazard with concurrent process see: http://en.wikipedia.org/wiki/Concurrency_control And when You block access do data, others thread stop.

The implementation similar to Futex in the no blocked case needs one lock operation on entry and one on exit. Thus using a thing similar to FUTEX needs some 2,0001 locked operations per call. \

I don;t understand this

Darek

Florian Klaempfl pisze:

We don't need wait to synchronize caches. It will be done by hardware. And i think synchronize cache with ram don't eat hundreads clock cycles. And CMPXCHG has automatic locking asserted, as normal instruction can't persist so long (Intel don't mention about this)
This is also use to implement semaphores (suggest from Intel) , thus should be save and fast.

Form intel about caching:
http://www.intel.com/design/processor/manuals/253668.pdf

Intel Architecture Compatibility
Beginning with the Pentium Pro processor, when the LOCK prefix is prefixed to an instruction
and the memory area being accessed is cached internally in the processor, the LOCK# signal is
generally not asserted. Instead, only the processors cache is locked. Here, the processors cache
coherency mechanism insures that the operation is carried out atomically with regards to
memory. Refer to Section 7.1.4., Effects of a LOCK Operation on Internal Processor Caches in
Chapter 7, Multiple-Processor Management of the Intel Architecture Software Developers
Manual, Volume 3, the for more information on locking of caches.

Darek

ehm... according to your pdf:

For the P6 family processors, locked operations serialize all outstanding load and store operations (that is, wait for them to complete). This rule is also true for the Pentium 4 and Intel Xeon processors, with one exception. Load operations that reference weakly ordered memory types (such as the WC memory type) may not be serialized.

And i think synchronize cache with ram don't eat hundreads clock cycles.

I think it does, why else do we need cache ?

And CMPXCHG has automatic locking asserted, as normal instruction can't persist so long (Intel don't mention about this) This is also use to implement semaphores (suggest from Intel) , thus should be save and fast.

first, yes, second, thats relative.

Marc

We don't need wait to synchronize caches. It will be done by hardware.

Right. but waiting performed by the hardware does not take less long than waiting performed by software :-) .

And i think synchronize cache with ram don't eat hundreads clock cycles.

In all cashed that contain the memory location, the appropriate cache line will be invalidated. Thus it needs to be reloaded from main memory before it can be accessed by the processor. This might introduce a huge delay in a processor a long time after the the locking instruction was performed by some different processor.

-Michael

The point is, it simply affects all processor. Its much better than an entercriticalsection but it is not only twice the time of a simply inc or whatever.

Any implementation of thread synchronization need care of cache. FUTEX, which rely on atomic primitives can't be faster than primitives alone.

I said that (using locking instructions to implement a semaphore) I might implement something that works similar to FUTEX. I don't intend to _use_ FUTEX.

In lockfree algorithms we don't block data any time others threads can process data.

Of course that is what the software sees. But the use of the "lock" instruction will stall this (and other) threads nonetheless. So we can discuss what way is the most effective: IMHO that which uses the fewest count of lock instructions in the pass when no blocking due to concurrent access is necessary.

You have to prevent data loss, when You have hazard with concurrent process see: http://en.wikipedia.org/wiki/Concurrency_control And when You block access do data, others thread stop.

The blocking due to concurrency will occur very seldom. So the implementation of the program path that only checks for the need of blocking and sets the semaphore (which needs to be done with the appropriate bus-lock hardware support) but does not actually block is the critical issue.

-Michael

I want two give my two cent's too.

In the last 4 years, we developed a billing application (fpc/linux/daemons) for VOIP calls.
The application bills in realtime cdr records generated from the telko switch.
In one hour there are up to 15000 records to bill. In one month there are estim. 5 million
billed records in the database. (You must process estimately 7 Events, Start Call Event, Stop Call Event, Intermediate Timestamps to get one of the 5 million CDR's).
(CDR := http://en.wikipedia.org/wiki/Call_detail_record)

In short: We must process a huge amount of data fast...

The application must find start and stop events in 7 different inmemory data structures.
We use a multithreaded concept. A database reader, mediator threads (finding start and stop)
,guiding threads (finding customers to call-id's),a rating threads (making the price splitting a long the
time and destination axis), a db writing thread (writing results), a fraud detection thread (checking per customer limits). All threads use the same inmemory data structures.

The overall speed of the application is critical, as it makes a difference if a re(rating) of a
month for 10000 Telko customers producing 10.000.000 of CDR's on 10000 phone bills takes 6 hours or
6 Weeks :-) (On a simple Multicore System)

We were (re)implemented the thing 3 times. The code is around 100.000 Lines.

Our conclusions for COMPLEX Algorithms are: (We read more often then we write)

Involved Locking Structures:

A)-> TSemaphores / Critical Sections
Slow:-> Cause slow Writers block Readers too much
Deadlock Bugs -> if wrong Locking order -> Hard to debug. Priority Inversion: High Priority operations gets blocked due to lock held by
low prio thread. (Even harder to debug)

B)->Multireader, Single Writer Locks
Faster:-> Due to the Multi Reader, Single Writer Locks Much more Deadlock(!) Bugs, due to much more Readers. Priority Inversion: High Priority operations gets blocked due to lock held by
low prio thread.

C) Lockfree Structures
No Deadlocks possible, No priority inversion,
No needless Waiting on Semaphores, if the Scheduler puts a Thread out of the execution path
while in a Critical Section or holding a Lock.

Currently we have B) Running in Real World and C) Running in Testing.

C) Is not fully implemented due to large algorithmic changes. But in prototypes and testing
Case C) is very promising because it is several times faster (not serveral percents) than
Cases A and B).

The time spent on debugging A) and B) was enormous.

I think we all could need a good lockfree datastructure library for Freepascal.
Our current implementation is not suitable as it don't cares for multiplatform, and
64 Bit architectures and is too tightly bound with our internals.

But if someone is interested, we could work together to make something new.
At least i have some links as starting points.

BTW:
We are searching for a FPC/Delphi Programmer willing to work here in our small team
in Graz/Austria.

helmut

Very interesting stuff indeed !

In your case of course my idea of using something similar to FUTEX supposedly will not help much, as it would prevent unnecessary system calls done by semaphore handlers like "TCriticalSection" and thus reduce the overhead, but will not cure things like priority inversion and unnecessary waits for locked structures. So of course I do see that a lockfree implementation is the way to go. This definitively holds for tasks were the duration of the necessary lock is quite big. My initial intention was a byte FIFO. Here, IMHO, the additional effort for a lock free implementation might be in vain, as the act of transferring the byte in and out the FiFo (or Stack) is minimal.

Do you already have a theoretical background to decide when/how a lockfree implementation can be done. Do you think a lockfree version of TThreadList could be done and perform decently ? OTOH TThreadList is very bed for implementing a FIFO. What should be the specs of a component that would be useful for most of what can be done with TThreadList plus where a fast FiFo is needed.

I'll forward your offer for collaboration to a friend of mine who in fact is Austrian but lives in Germany. He does not want a Job, as he is a consultant, but he is very comfortable with large Delphi Language projects and even with Telephony applications. So he might be a useful partner for you.

-Michael

I write web server in FPC. I invented lock-free FIFO Queue because I need fast message queue between threads (socket and user interface). I think it is simple, fast and don't need memory management and garbage collections.
I think I have idea to implement priority queue too. Simple list can be implement by Valois (or others) algorithm. But i don't have real-word constraint. FPC has implemented all needed atomic instruction on most platforms. Thus I'm ready to work on this subject.

Darek