Databases
StackOverflow2013
Postsdbo
POTraversing a Binary Tree with multiple threads
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTraversing a Binary Tree with multiple threads
    primarykey
    data
    text
    <p>So I'm working on a speed contest in Java. I have (number of processors) threads doing work, and they all need to add to a binary tree. Originally I just used a synchronized add method, but I wanted to make it so threads could follow each other through the tree (each thread only has the lock on the object it's accessing). Unfortunately, even for a very large file (48,000 lines), my new binary tree is slower than the old one. I assume this is because I'm getting and releasing a lock every time I move in the tree. Is this the best way to do this or is there a better way?</p> <p>Each node has a ReentrantLock named lock, and getLock() and releaseLock() just call lock.lock() and lock.unlock();</p> <p>My code:</p> <pre><code>public void add(String sortedWord, String word) { synchronized(this){ if (head == null) { head = new TreeNode(sortedWord, word); return; } head.getLock(); } TreeNode current = head, previous = null; while (current != null) { // If this is an anagram of another word in the list.. if (current.getSortedWord().equals(sortedWord)) { current.add(word); current.releaseLock(); return; } // New word is less than current word else if (current.compareTo(sortedWord) &gt; 0) { previous = current; current = current.getLeft(); if(current != null){ current.getLock(); previous.releaseLock(); } } // New word greater than current word else { previous = current; current = current.getRight(); if(current != null){ current.getLock(); previous.releaseLock(); } } } if (previous.compareTo(sortedWord) &gt; 0) { previous.setLeft(sortedWord, word); } else { previous.setRight(sortedWord, word); } previous.releaseLock(); } </code></pre> <p>EDIT: Just to clarify, my code is structured like this: The main thread reads input from a file and adds the words to a queue, each worker thread pull words from the queue and does some work (including sorting them and adding them to the binary tree).</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USBrendan Long
    1. USBrendan Long
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTraversing a Binary Tree with multiple threads
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POTraversing a Binary Tree with multiple threads
      1. USP.K
      1. VTFavorite
    3. VO
      singulars
      1. POTraversing a Binary Tree with multiple threads
      1. USNitinS
      1. VTFavorite
    1. COOne small suggestion: instead of NumberOfProcessors threads, you might want to subtract one - because the OS will use one at least, defining a thread per processor pretty much guarantees some context-swapping overhead.
      singulars
      1. POTraversing a Binary Tree with multiple threads
      1. USCPerkins
    2. COI figured it would be fine because it's not unreasonable to assume that the threads will be waiting on each other a lot.
      singulars
      1. POTraversing a Binary Tree with multiple threads
      1. USBrendan Long
    3. COIf they're waiting on each other, that's not good, because they're not working.
      singulars
      1. POTraversing a Binary Tree with multiple threads
      1. USMike Dunlavey
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload