This project investigates the performance of detecting equivalent Binary Search Trees using various parallelization strategies. I analyzed the trade-offs between different concurrency models and synchronization overhead in the Go runtime.
Synchronization Analysis: Compared Goroutine-per-BST vs. Worker Pool models, identifying the sweet spot for scheduler overhead versus task granularity.
Lock Contention Study: Evaluated Channel-based communication vs. Fine-grained locking (sharded mutexes), identifying specific bottlenecks in shared data structure synchronization.
Advanced Data Structures: Implemented a thread-safe Disjoint Set Union (DSU) with path compression for equivalence tracking.
System Primitives: Utilized mutexes, wait groups, and condition variables to manage complex state transitions across concurrent workers.