Thread-Safe Stacks

A comprehensive C++17 library featuring five different implementations of thread-safe stacks. This project is designed to demonstrate various synchronization strategies, from simple mutex guarding to advanced fine-grained locking and memory-efficient node management.

🌟 Key Features

• Diverse Implementations: 5 distinct stack architectures tailored for different contention levels.
• Zero-Guesswork Testing: 100% coverage with Google Test (GTest) suite.
• Pro Benchmarking: Built-in performance analyzer measuring throughput in MOps/s.
• Exception Safety: Advanced use of std::shared_ptr to ensure data integrity during concurrent access.

---

🏗 Project Structure

File	Description
ModernThreadSafeStack.h	Basic wrapper around std::stack with std::mutex.
WaitingThreadSafeStack.h	Adds condition_variable to eliminate busy-waiting.
SharedPtrWaitingStack.h	Optimized for heavy objects; reduces copying via shared_ptr.
ModernLinkedStack.h	Custom linked-list; performs allocations outside the lock.
WaitLinkedStack.h	The most advanced version; linked-list with blocking support.
tests/	Google Test suite for functional verification.
main.cpp	Professional benchmark harness.

---

🚀 Benchmark Results (Developer Machine)

Configuration: 8-Core CPU | 4 Producers / 4 Consumers | 100,000 items per Producer.

Category: Light Payload (int)

Focus: Synchronization and Mutex overhead.

Implementation	Load (P/C)	Time (ms)	Throughput (MOps/s)
Basic Mutex Stack	4/4	41.43	19.308
Waiting Mutex Stack	4/4	45.03	17.766
SharedPtr Stack	4/4	170.77	4.685
Linked List Stack	4/4	143.87	5.560
Wait Linked List Stack	4/4	146.93	5.445
Waiting Mutex Stack [WAIT]	4/4	43.11	18.556
SharedPtr Stack [WAIT]	4/4	152.55	5.244
Wait Linked List Stack [WAIT]	4/4	295.95	2.703

Category: Heavy Payload (1KB Struct)

Focus: Memory throughput and lock-holding time.

Implementation	Load (P/C)	Time (ms)	Throughput (MOps/s)
Basic Mutex Stack	4/4	154.82	5.167
Waiting Mutex Stack	4/4	175.16	4.567
SharedPtr Stack	4/4	285.93	2.798
Linked List Stack	4/4	187.21	4.273
Wait Linked List Stack	4/4	185.70	4.308
Waiting Mutex Stack [WAIT]	4/4	123.54	6.476
SharedPtr Stack [WAIT]	4/4	238.62	3.353
Wait Linked List Stack [WAIT]	4/4	262.35	3.049

---

📝 Technical Analysis

1. The std::deque Advantage: The Basic and Waiting Mutex stacks (built on std::stack) significantly outperform the custom Linked-List versions. This is primarily due to std::deque's block-allocation strategy. By allocating memory in chunks rather than per-node, it minimizes calls to the global allocator and maximizes CPU cache locality.
2. The Hidden Cost of Nodes: Contrary to theoretical expectations, the "optimization" of allocating nodes outside the critical section in the Linked List and SharedPtr versions actually hindered performance. The overhead of frequent new/delete operations and the creation of std::shared_ptr control blocks (especially visible in the 285ms result) outweighed the benefits of shorter lock-holding times.
3. Efficiency of Condition Variables: In the Heavy Payload category, the Waiting Mutex Stack [WAIT] (using waitAndPop) achieved the best result (123.54ms). This demonstrates that for larger data, using a std::condition_variable is more efficient than aggressive tryPop polling, as it reduces useless lock contention when the stack is empty.
4. Scaling Observations: While Linked-List structures are often praised for concurrency, your results show that for a 4P/4C load on an 8-core machine, the contention management of a standard mutex wrapper around a contiguous-ish container (deque) is far superior to the overhead of a node-based architecture.

Recommendation: For most general-purpose applications, a Waiting Mutex Stack based on std::deque is the optimal choice. Only move to Linked-List or Lock-Free structures if you are dealing with extremely high contention or real-time requirements where individual latency spikes from std::deque reallocations are unacceptable.

---

🛠 Installation & Build

Prerequisites

• C++17 Compiler (GCC 9+, Clang 10+, MSVC 2019+)
• CMake 3.10+
• Google Test (will be fetched automatically if using CMake)

Build Instructions

# Clone the repository
git clone https://github.com/NotACat1/ThreadSafeStack.git
cd ThreadSafeStack

# Build Benchmark in Release mode (Crucial for performance!)
g++ -O3 -std=c++17 -pthread main.cpp -o benchmark
./ThreadSafeStack

---

📘 Design Philosophy

1. Reduce Critical Sections: We aim to keep the code inside std::lock_guard as minimal as possible.
2. Smart Memory Management: Using std::make_shared before locking allows multiple threads to prepare data in parallel.
3. Modern C++: Utilizing RAII, std::optional-like interfaces (via tryPop), and move semantics for maximum efficiency.