C++ Framework - prebeta - examples "LockFreeQueue.h" & "LockFreeList.h"

220 views
Skip to first unread message

MoranTza

unread,
Jun 9, 2009, 2:21:24 PM6/9/09
to Art of Multiprocessor Programming
New Version: 1.2 (New examples "LockFreeQueue.h" & "LockFreeList.h"),
***this is pre-beta version in development ***

Download From : http://www.cs.tau.ac.il/research/moran.tzafrir/cpp_framework_new.zip
----------------------------------------------------
Notes:
----------------------------------------------------
* Two examples included "LockFreeQueue.h" & "LockFreeList.h".
* I'll be happy to get reviews on those two.
* We are trying to create easy to use Hazard-Pointers. This concept is
in development, any feedback on this is welcome.
* The memory-model is not optimized, I am working to optimize it to
SPARC-TSO, and WIN32 (currently only supported architectures).
* Support for WIN64, SPARC64, INTEL32, and INTEL64 is planned.
* Any constructive comments and bug-report is welcome.
* Please note that I am a student in a middle of a semester, so there
might be a delay.

----------------------------------------------------
Classes in the Framework
----------------------------------------------------
System
Memory

VolatileType
DummyLock
TTASLock
TASLock
ReentrantLock
ReentrantReadWriteLockSemaphore
Semaphore
Condition

ThreadLocal

AtomicInteger
AtomicLong
AtomicBoolean
AtomicReference
AtomicMarkableReference
AtomicStampedReference

HazardMemory
HazardMemory::Ptr

Integer
Random

Jason Swearingen

unread,
Jun 9, 2009, 9:49:24 PM6/9/09
to art-of-multiproc...@googlegroups.com
I haven't looked at this new framework, and I don't think I will (just because I'm a c# kind of guy) but one thing I've noticed with thread-safe frameworks is that a lot of them are not actually thread safe.

I'm not at all trying to undermine Moran's framework, I'm just raising this as a cautionary note to any/everyone attempting to create thread-safe API's

You must ensure thread safety, mostly by invoking a set of tests meant to stress the limits of your thread-safety, including attempts to recreate "implausible" but not impossible scenarios.  For example, running a test where 16 threads attempt to (randomly) add, remove, or inspect your thread-safe collection over a few billion iterations is generally what I consider the minimum for stress testing, which includes some form of journalizing so that you can determine the state your thread-safe collection should be in at the end of the test, and then compare it to the actual state.

And I bring this up, because too many frameworks I've attempted to use or reverse engineer have failed to meet this quality standard, such as this:   http://www.codeproject.com/KB/cs/AsynchronousCodeBlocks.aspx  That example suffers from concurrency issues, and ends with deadlocks and other nasty side effects, which only occurs perhaps 0.001% of the time in the critical sections.
--
- Jason

================================
Jason Swearingen  Executive Director: Novaleaf Game Studios
--------------------------------------------------------------
Jas...@Novaleaf.com  Cell: +66-089-775-0111
Office: +66-02-234-3031  Fax: +66-02-234-3032
================================

Moran Tzafrir

unread,
Jun 10, 2009, 3:21:49 AM6/10/09
to art-of-multiproc...@googlegroups.com
The C++Framework is an educational project, it tackles the following questions:
1) When studying Multicore-Programming what memory-model should be
emphasized, or concentrating on a variety of memory model is more
correct ?
2) Studying Multicore-Programming is hard as it is, it might be right
to stick to one memory model, and one set of atomic operations, like
Atomic Integer (e.g. Java like interface)?
3) Or maybe when Studying Multicore-Programming it is more important
to be exposed to a variety of memory-models, and variety of interfaces
like Java, POSIX, C#, C++0x, etc ?

Thanks, Moran.

Brian Goetz

unread,
Jun 12, 2009, 2:59:53 AM6/12/09
to art-of-multiproc...@googlegroups.com
> You must ensure thread safety, mostly by invoking a set of tests meant
> to stress the limits of your thread-safety, including attempts to
> recreate "implausible" but not impossible scenarios. For example,
> running a test where 16 threads attempt to (randomly) add, remove, or
> inspect your thread-safe collection over a few billion iterations is
> generally what I consider the minimum for stress testing, which includes
> some form of journalizing so that you can determine the state your
> thread-safe collection should be in at the end of the test, and then
> compare it to the actual state.

And writing such tests is often harder than writing the code being tested in
the first place, since the tests are concurrent programs too. For example, if
the journaling you describe entails synchronizing, you've introduced timing
biases that could well hide bugs. Doing so without synchronizing (such as by
keeping thread-local logs and merging them at certain intervals) is tricky too.

Further, running tests on concurrent code means running on a variety of
architectures, since some CPU architectures (e.g., IA32) have stronger memory
models than others, and therefore certain reorderings will not occur (at least
not due to the hardware) on such systems.

MoranTza

unread,
Jun 25, 2009, 6:41:00 PM6/25/09
to Art of Multiprocessor Programming
New version 1.3 is available http://www.cs.tau.ac.il/research/moran.tzafrir/cpp_framework_new.zip

Only Minor changes:
1) Improved Hazard-Pointer support, especially with algorithms that
need stamped reference.
2) Benchmarked the two example algorithms "LockFreeQueue.h" &
"LockFreeList.h" on Maramba with 64 threads, and NOW it seems to work
great.
3) Got good feedback from students, and in the next version I'll
include new examples, and hopefully decent documentation.

Clarification:
1) C++Framework is an educational project.
2) The main idea is to let students work with C++ without teaching
other memory model.
3) For example the student can easily translate it to C++ using the C+
+Framework, and then explore the issues like cache-misses, contention,
cache-line alignment, etc.

Thanks,
Moran.

MoranTza

unread,
Jul 25, 2009, 2:15:01 PM7/25/09
to Art of Multiprocessor Programming
New Version: 1.4 - High Performance Hazard-Pointer:

Download: http://groups.google.com/group/cpp-framework

We tested this version a lot, so it should much more stable. New
features:

1) Added "currentThread" method to Thread.
2) Added "addEndCallback" method to Thread, let you add thread
termination callbacks.
3) Added “nextLong” to Random class.
4) Better thread cleanup
5) Improved Hazard-Pointer performance, and stability. Tested with 128
threads. No memory leaks and competitive performance.
6) More examples how to use the Hazard-Pointers: "LazyList.h",
"LockFreeList.h", "LockFreeQueue.h", and “SimpleLinear.h"
7) Sorry no documentation yet.
8) In next version you can expect Linux-Intel compilation, and
documentation.

Thanks,
Moran Tzafrir.
http://www.cs.tau.ac.il/research/moran.tzafrir/



On Jun 26, 1:41 am, MoranTza <Moran...@gmail.com> wrote:
> New version 1.3 is availablehttp://www.cs.tau.ac.il/research/moran.tzafrir/cpp_framework_new.zip

Truc Nguyen Lam

unread,
Mar 18, 2016, 12:29:38 PM3/18/16
to Art of Multiprocessor Programming
Hi Moran,

This library is very useful, however, the hyperlinks seem to be not reachable.
Could you please put the links to all versions of the library?

Many thanks,
Truc
Reply all
Reply to author
Forward
0 new messages