Analyzing performance of thread-safe implementations of BSTs
By Tuesday, 25th April’s checkpoint we have completed a coarse grained implementation of our binary search trees. In doing so, we’ve established a framework which should allow the other implementations to function as a drop-in replacement, thus requiring minimal code changes. We’ve additionally begun development of our own testing harness which has both a single-threaded and multi-threaded implementation testing for correctness. The combination of this test suite with the coarse grained reference solution should make the implementations of the other two implementations simpler and faster to develop.
Based on our progress this past week, we believe we will have an adequate amount of time to complete the main stated deliverables (comparison of coarse-grained, fine-grained, and lock-free BSTs), but will have little to no time left to work on any of the additional goals we had mentioned. This is largely based on the amount of time it took to develop the multithreading capabilities of the testing harness. Our experiences, as described below, raise potential concerns about the consistency of our measurements, so we would prefer to spend additional time ensuring that the analysis that we do make is accurate, rather than spending minimal time generating a simple set of results for the analysis and then beginning work on “nice-to-haves”. Below, we’ve reiterated our planned goals for the pararallelism competition.
The first major deliverable for the project is the completion of 3 different implementations of concurrent binary search trees. They are:
- Coarse-grained locking tree
- Fine-grained locking tree
- Lock-free tree
The novel part of our project, however, is the evaluation and comparison of the performance characteristics of the three different tree structures that we will develop. Specifically, we intend to evaluate the performance under the following load conditions, varying the number of threads and the amount of contention.
- Read-only workload
- Insert-only workload
- Delete-heavy workload
For the parallelism competition, we plan on showing graphs describing our performance results across these different workloads. We additionally want to present some analysis about why we believe the results to be as they are.
In developing the test harness, we had no difficulty testing for correctness in a single-threaded case. However, ensuring consistency across test iterations in the multi-threaded case is proving to be challenging. We are attempting to mitigate these concerns by using the law of large numbers, and simply making long, repeated attempts in order to attempt to tease out any potential race conditions or similar concurrency issues. While we’re reasonably confident in the test harness’ ability to find bugs, we are somewhat concerned that determining accurate performance scores may be more difficult than we had originally anticipated.
We have yet to begin working with the fine grained locking and lock free implementations, so it is difficult to judge the expected level of difficulty. It appears that the fine-grained locking version should not be significantly more complex than the coarse grained locking implementation, and that the large majority of the difficulty will be found in the lock-free implementation. For this reason, we’ve allocated approximately half a week of schedule time for the fine-grained locking solution while giving an entire week to the lock-free implementation.
Developed by Vasu Agrawal and Lukas Peraza.