2
$\begingroup$

Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism.

I have implemented a Binary Search Tree, it is a very basic (naive) tree structure:

class Node:
   Node? right;
   Node? left;
   long value;

Inserting into to the tree is the usual algorithm: I compare key to value and descend left/right depending on the comparison, return if that key is exact match, or insert into an empty node.

My question concerns parallelism: Is there a way to efficiently parallelize or make concurrent search and/or insertion? I would like to have multiple threads independently inserting items.

A global mutex when needing to insert could work but given my heavy write load it ends up less efficient than a single thread, because every time I search I also then insert.

It feels like there ought to be a way to coordinate mutex locking at the sub-tree level to only lock part of the tree but perhaps there's also a lock-free way to allow concurrent search and insert for a tree?

If it helps to relax the problem, I am actually not too concerned about a race condition where if one thread begins searching for key K while another thread is also searching for key K that they both end up inserting as long as it doesn't break the tree for future inserts. ( My reasoning for this relaxed constraint is that if the probability of collision is high enough that such a data race would occur then a new overall collision will be found again in due time. ).

I am not re-balancing the tree at any point, nor is removing items a requirement. I also appreciate there are much more efficient ways to store this, especially with regards to cache etc, but I'm not yet looking for the most efficient solution of storage, just whether parallel access of this structure is possible, mostly to test the parallel bench-marking code itself.

Improve this question
$\endgroup$
9
  • $\begingroup$ Sorry if my terminology doesn't match CS literature very well, I don't have a formal CS background. $\endgroup$
    – Eterm
    Aug 4, 2022 at 15:11
  • $\begingroup$ If you could leave a comment when down-voting so I know how to clean up or improve the question then please do so. $\endgroup$
    – Eterm
    Aug 4, 2022 at 16:28
  • 1
    $\begingroup$ If you only do insertions with rebalancing, then you only need the lock at the point of insertion. I.e., if you create a right child of a node $n$, then you can place a lock on $n$. en.wikipedia.org/wiki/Double-checked_locking seems to be the way to go, i.e. the algorithm for creating a right child of node $n$ is: 1) check that $n$ doesn't have a right child. 2) lock $n$. 3) check again that $n$ doesn't have the right child (otherwise unlock and go to the child). 4) Fully construct the new node $m$. 5) Insert $m$ as the right child of $n$. 6) Unlock $n$ and you are done. $\endgroup$
    – Dmitry
    Aug 4, 2022 at 16:30
  • $\begingroup$ (previous comment: *with rebalancing -> without rebalancing) Note the following: 1) Depending on your language, there could be some nasty details. E.g. Java memory model should work fine with this approach, while C# would probably require memory barriers or something. 2) It's important that 4 goes before 5. If you create a not-fully-constructed child, then other thread can access it, and you are in trouble. 3) It's unclear how to modify tis approach if you do need rebalancing. $\endgroup$
    – Dmitry
    Aug 4, 2022 at 16:33
  • 1
    $\begingroup$ @Dmitry, Can I encourage you to write this as an answer, so we can upvote it, and so the question is treated as answered? $\endgroup$
    – D.W. ♦
    Aug 5, 2022 at 7:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.