AppCore: A Portable High-Performance Thread Synchronization Library

An Effective Marriage between Lock-Free and Lock-Based Algorithms


This page presents a scaleable single-producer/consumer lock-free queue and an atomic operations api for the i686. There is also a full-blown hazard pointer implementation that is used to create an atomic reference count api. This makes it possible to create a single-word atomic C++ smart pointer. A very crude smart pointer class is included as a proof of concept. The code is made up of bits and pieces from my “new and improved” AppCore Library. I can't reveal the entire library until I completely finish its documentation. However, the presented algorithm provides a highly-efficient method for thread-to-thread communication. The code compiles with gcc or msvc++ and relies on pthreads; no dependence on windows headers. It should compile with gcc on many operating systems that provide pthreads under i686 cpu's. The lock-free queue does not rely on any “atomic operations”. It uses simple loads and stores guarded with memory barriers. All of its “critical-sequences” are contained in externally assembled functions ( read all ) in order to prevent a rouge C compiler from reordering anything that would corrupt the data-structure. The queue allocates its nodes from a three-level cache. The first level is a local per-thread LIFO, the second is a global lock-free LIFO, and the third is malloc/free. The lock-free data-structures are padded and forcefully aligned on separate cache lines. Unfortunately, all of this is necessary to achieve scaleable thread-to-thread communication. Test the presented code, and compare and contrast its performance against a "traditional lock-based" solution for a single-producer/consumer queue. You just may find that lock-free thread-to-thread communication can be stable, simple, and "useful" after all... ;)


****This site is under construction****



Contact

Remove nospam and underscores: nospam_cristom@nospam_charter.net
I also post and discuss information on AppCore to comp.programming.threads


Links

A Fast-Pathed POSIX Thread library

"Mostly" Lock-Free Word-Based Atomic Reference Counting (source)

An extremely beautiful photography site: HazeltinePhotography.com


Code Status

- Completed: Feb. 21, 2005: Added atomic api
- Completed: Feb. 21, 2005: Critical update! Slays simple mem leak wrt tls caused by stupid cut&paste error! ;(...
- Completed: Mar. 14, 2005: Added hazard-pointers
- Completed: Mar. 25, 2005: Critical update! Added updated assembly files. Re-download
- Completed: Mar. 30, 2005: Added simple MSVC 6.0 workspaces and Dev-C++ project files
- Completed: Apr. 18, 2005: Fixed pthread related memory leak that only shows up on Linux. Re-download
- Completed: May 2, 2005: Minor code updates and other various performance enhancements. Re-download
- Completed: May 3, 2005: Found and removed a small bug wrt SMR & node cache. It’s hard to trip, but it will crash if it does. Its fixed so you should probably re-download.
- Completed: May 10, 2005: Found and removed the last SMR & node cache related bug. Again, it can be hard to trip. Re-download
- Completed: May 14, 2005: Found and removed alloca scoping bug.
- Completed: Jan 28, 2008: Found and removed a memory visibility issue in the eventcount API; re-download!
- Completed: Jan 29, 2008: Added some new API functions in the eventcount and spsc queue API’s; re-download!
- Currently: Verifying that AppCore is now bug free! :)


Downloads

appcore version: 0.0.2 / arch: i686 ( pre-alpha )
The MSVC 6.0 workspaces and the Dev-C++ projects build the appcore.dll in the c:/winnt/system32 directory. This may need to be changed to suite your needs.


Project File Index(s)

appcore project