mORMot Open Source

I have release my code along with a test program, under MPL 1.1:
http://code.google.com/p/delphi-toolbox … svn29&r=29

The test program takes two parameter, the first is the number of threads, and the second is the algortihm name.

Valid algorithm names are:
4B - without using cmpxchg8b
8B - using cmpxchg8b
8BV - using the version field and cmpxchg8b

The workload is an endless cycle of get and put.
The test program will create threads, warm them up, and then run for 10 seconds.
Finally it will print out the average time used for each get-and-put cycle

On a single core, single thread, Pentium M 2.0GHz:

1 thread,   4B,   ~64 nanoseconds per cycle
4 threads,  4B,   ~64 nanoseconds per cycle

1 thread,   8B,   ~78 nanoseconds per cycle
4 threads,  8B,   ~78 nanoseconds per cycle

1 thread,   8BV,   ~77 nanoseconds per cycle
4 threads,  8BV,   ~77 nanoseconds per cycle

On a single core, hyper thread, Atom 1.6GHz:

1 thread,   4B,   ~44 nanoseconds per cycle
4 threads,  4B,   ~47 nanoseconds per cycle

1 thread,   8B,   ~73 nanoseconds per cycle
4 threads,  8B,   ~83 nanoseconds per cycle

1 thread,   8BV,   ~69 nanoseconds per cycle
4 threads,  8BV,   ~64 nanoseconds per cycle

It seems that from the absolute number POV, the 4B routines perform the best, probably for under 8 or 16 cores.
But the power of true lock-free code (8BV) is show on Atom, as the number of cores increase, the latency of all other routine goes up, while only 8BV goes down!

But again, I don't have access to more variety of machines right now, so please post your performance measurements so the general trend is more clear.

Update:
On a dual core, single thread, Core2Duo 2.4GHz:

1 thread,   4B,   ~50 nanoseconds per cycle
4 threads,  4B,   ~92 nanoseconds per cycle

1 thread,   8B,   ~61 nanoseconds per cycle
4 threads,  8B,   ~85 nanoseconds per cycle

1 thread,   8BV,   ~61 nanoseconds per cycle
4 threads,  8BV,   ~102 nanoseconds per cycle

OK now I am confused... need more data...

I think I came up with an algorithm that don't need version field for each pointer.

The old algorithm does the following:

0. Head: [Block] ----> [Block] ----> [Next]
1. Retrieve [Block] from Head
2. Retrieve [Next] from [Block]
3. CAS on Head, compare against [Block] and store [Next] if match

The new algorithm does the following:

0. Head [Block:Next] ----> [Block] ----> [Next]
1. Retrieve [Next] from Head, if [Next] = INFINITE, spin-wait-then-yield
2. CMPXCHG8B on Head, compare against [Block:Next] and store [Next:INFINITE]
Now we have [Block:Next] as the return value, the [Block] is what we need, but we need to do the next step to maintain loop invariance:
3. Retrieve [NewNext] from [Next] and replace INFINITE in Head, which becomes [Next:NewNext]

The new algorithm is free of the A-B-A problem, because the CAS is performed on both [Block] and [Next] pointers, even if ABA happened, as long as both pointer are the same, there is no error.

However, the new algorithm is slightly inefficient, in that, after a successful step 2, no thread can continue until step 3 is performed. However, this "locked" region is just 5-7 instructions long, and should not lead to a heavy penalty.

the Put(NewBlock) method is also straight forward to implement:

0. Head [Block:Next] ----> [Block] ----> [Next]
1. Retrieve [Next] from Head, if [Next] = INFINITE, spin-wait-then-yield
2. CMPXCHG8B on Head, compare against [Block:Next] and store [NewBlock:Block]

There is no "locked" region in the Put() method either.

I read the ScaleMM code where CAS1 is used, and I think I found a suspecious segment.
in TGlobalMemManager.GetBlockMemory()

...
      prevmem := bl.FFirstFreedMemBlock;
      if prevmem = nil then
        Continue;
      nextmem := prevmem.FNextFreedMemBlock;
      if CAS0(prevmem, nextmem, bl.FFirstFreedMemBlock) then
...

This code segment can suffer from the A-B-A problem. That is:

1. These line are executed
      prevmem := bl.FFirstFreedMemBlock;
      if prevmem = nil then
        Continue;
      nextmem := prevmem.FNextFreedMemBlock;

2. Before the CAS line is executed, the thread is swapped off.

Then content of bl.FFirstFreedMemBlock is changed, then changed back to the same value. (For example, another thread grabs the block A, and then freed it, and then grabs several blocks and made A the head of the chain again.)

Note that, although bl.FFirstFreedMemBlock is the same, bl.FFirstFreedMemBlock.FNextFreedMemBlock may not be the same anymore!

3. CAS is executed, and because it only looks at the pointer value, which is the same, the CAS passed. But now the pointer chain is incorrect!
In lucky cases, you will lose track of some memory blocks, and the program continues without error; but in unlucky cases, the pointer chain form a loop, and the program deadlocks.

A solution would be to append a version field to each pointer, and the version monotonically increases everytime the corresponding pointer recycles. To do this, you will need to use cmpxchg8b, which performs CAS on aligned 8 bytes at one go.

-------------
Adding a sleep(1) helps to hide the ABA problem, but not sleep(0) nor yieldtothread(). The reason is that, sleep(1) forces the thread to give up current time slice, so that, when the thread wake up, it will have a whole new time slice. Then, it is very likely to completely execute the entire loop once, without being swapped off in the middle, which hides the ABA problem.

However, it is not the right fix, because the very first attempt is executed without the whole time slice guarantee. If the ABA problem manifest on the very first try, the memory still will be corrupt.

(Adding a sleep(1) before the first attempt would probably completely hide the problem, but it will bring the performance down to hell... )

If you must use sleep(1) to "avoid" some race condition, this is *not* the right fix, you are just hiding the bug on your machine, and this bug is bound to happen on some other machine.

One more thing, please don't stuck SwitchToThread() or even Sleep() into a benign-named "CAS" function, it will lead to maintenance nightmare.
If you must do it, name the function CAS_AND_SLEEP_ON_FAIL().

Actually the number of threads does not matter that much, at least in real life. Even if there are 100 threads, if 90 of them are not requesting memory at the same time, then there are only 10 competing threads, not 100. And more over, what matters is just that single thread and holds your lock, all other threads can be ignored.

The question boils down to the following: if the thread A that holds the lock is executing and will be done faster than a context switch, then it is better to spin wait; if A is switched off, or will take a long time to finish, then it is better to backoff. Since user program have no control over context switch, the problem is probablistic.

This resembles the classic "rent or buy" problem, consider each spin is a "rent", and a context switch/sleep is a "buy", I think the optimal answer would not be "always rent" or "always buy", but rent a few times then buy.

Context switch and LOCK are two different things.

LOCK ensures the operation of an instruction is atomic, i.e. no other cores can do things that interfere with this operation; LOCK only applies to individual instructions, and no context switch can happen inside an instruction, locked or not.

Context switch happens on individual cores, and do not concern other cores - no context switch does not mean atomic (other core can fiddle with your memory at any time).

WinSxS is a monster, and you cannot avoid it.
It is because Windows uses it for a lot of internal libraries, such as for common controls library, which you have not license to redistribute.

Anyway, I am just commenting to share a probably not-so-well-known quirk (API bug) of WinSxS. I encountered this when I tried to programmatically switch context to load a specific version of common controls library.

The background (skip this paragraph if you don't care):
I wrote a plug-in dll for a third party exe file which is written in another language. I wanted to use an XP style common control but the main executable is not boundled with the manifest.
So, I decided to boundle the manifest in my DLL, and programmatically create an SxS activation context using the boundled DLL before trying to load commctls.

The quirk:
The CreateActCtx API has two mode of operations, in the first mode, it takes an external manifest xml file, and in the second, a resource from a loaded module.

On XP and Vista, the second mode has a bug: although the file name parameter should not be used, you cannot pass null, you have to pass some valid memory address. Otherwise the API fails.

On Win7, this bug is secretly fixed, and in a totally incompatible way. Now you must pass null in the file name when you use module resource, otherwise the API fails. So the quirk workaround I had fails again on Win7 and I have to resort to check system versions and activate workaround accordingly...

I guess they thought nobody ever used the SxS, and it is mostly just for them to make their stuff work properly...

One more note: So far, this bug presists acorss SPs -- XP SP123 and Vista SP1 all has this bug, which is GOOD. I sincerely HOPE they don't "fix" this thing in the next Vista SP, otherwise I will have to add more complicated SP detection to make my program work!

If you recompile system.pas, then you will need to recompile every single source in the runtime to make it match with the modified system.pas.
Every one of them.

Yes, stack based memory allocate is definitely faster, agreed.

But as I said, extra careness is needed on the programmer side, especially when writing a library, or calling external libraries, because you can't control the stack when you don't have the execution control (i.e. the external caller may only leave you a tiny stack, or the external callee may demand too much stack space than you have left for it)

And, sometimes a stack overflow exhibit totally weird behavior, it is hard to detect or debug.

> If a block memory is used outside the thread which created it, a copy will be made.

Who is going to make the copy?

If the user thread does the copy, then locking is needed, since the owner thread may operation the memory during the copy, and thus leading to race condition. (RCU works only if ALL write accesses are first made in a separate copy, so in order to make your scheme an RCU, even the owner thread need to make a copy of its memory block before doing any update -- this is one of the case I mentioned that the writer is penalized for faster reads)

if the owner thread does the copy, then the user thread needs to provide synchronized access to its memory manager, and most likely via some kind of locking. (Say, a memory block owned by thread A is going to be passed to thread B, then thread A needs to ask thread B's memory manager for a chunk of memory before A can perform the copy...)

True, local heap can avoid locking, but there will be other problems introduced:
1. Some application uses massive multi-threading, if each thread opens a local heap, then the address space may get very fragmented. (When Delphi eventually move to 64bit, we probably won't have to worry about it anymore... )
2. Each heap would need an instance of memory manager, and then there will be inter-op problems. If a piece of memory is passed between threads, it has to be somehow "linked" to its allocator memory manager instance otherwise there will be problem freeing it. And also the free operation needs to be synchronized, probably using LOCK, maybe RCU -- but I think it is too heavy weighted for memory management.