Перемещение двоичного дерева с несколькими потоками

Question

Итак, я работаю над конкурсом скорости на Java. У меня есть (количество процессоров) потоков, которые работают, и все они должны добавить к двоичному дереву. Первоначально я просто использовал синхронизированный метод добавления, но я хотел сделать так, чтобы потоки могли следовать друг за другом через дерево (каждый поток имеет только блокировку объекта, к которому он обращается). К сожалению, даже для очень большого файла (48 000 строк) мое новое двоичное дерево медленнее старого. Я предполагаю, что это потому, что я получаю и отпускаю блокировку каждый раз, когда я двигаюсь в дереве. Это лучший способ сделать это или есть лучший способ?

Каждый узел имеет блокировку с именем ReentrantLock и getLock() и releaseLock(), просто вызывает lock.lock() и lock.unlock();

Мой код:

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) > 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) > 0) { 
     previous.setLeft(sortedWord, word); 
    } 
    else { 
     previous.setRight(sortedWord, word); 
    } 
    previous.releaseLock(); 
} 

EDIT: Просто для уточнения, мой код структурирована следующим образом: Основной поток читает данные из файла и добавляет слова в очереди, каждый рабочий поток тянуть слова из очереди и выполняет некоторую работу (включая их сортировку и добавление в двоичное дерево).

Answer 1

Вы можете попробовать использовать обновляемую блокировку чтения/записи (возможно, ее называют обновляемой общей блокировкой или т. П., Я не знаю, что предоставляет Java): используйте один RWLock для всего дерева. Перед обходом B-Tree вы приобретаете блокировку чтения (общего доступа) и вы отпускаете ее, когда это делается (один приобретать и один выпуск в методе добавления, не более).

В точке, где у вас есть изменить B-Tree, вы приобретаете блокировку записи (эксклюзивную) (или «обновление» от чтения до блокировки записи), вставьте узел и понизите его в считываемую (общую) блокировку ,

С помощью этой технологии также можно удалить синхронизацию для проверки и вставки головного узла!

Это должно выглядеть как-то так:

public void add(String sortedWord, String word) { 

    lock.read(); 

    if (head == null) { 
     lock.upgrade(); 
     head = new TreeNode(sortedWord, word); 
     lock.downgrade(); 
     lock.unlock(); 
     return; 
    } 

    TreeNode current = head, previous = null; 
    while (current != null) { 

      if (current.getSortedWord().equals(sortedWord)) { 
        lock.upgrade(); 
        current.add(word); 
        lock.downgrade(); 
        lock.unlock(); 
        return; 
      } 

      .. more tree traversal, do not touch the lock here .. 
      ... 

    } 

    if (previous.compareTo(sortedWord) > 0) { 
     lock.upgrade(); 
     previous.setLeft(sortedWord, word); 
     lock.downgrade(); 
    } 
    else { 
     lock.upgrade(); 
     previous.setRight(sortedWord, word); 
     lock.downgrade(); 
    } 

    lock.unlock(); 
} 

К сожалению, через некоторое прибегая к помощи я не мог найти подходящую «ugradeable» rwlock для Java. «class ReentrantReadWriteLock» не обновляется, однако вместо обновления вы можете разблокировать чтение, затем заблокировать запись и (очень важно): пересмотреть условие, которое приведет к этим линиям снова (например, if(current.getSortedWord().equals(sortedWord)) {...}). Это важно, потому что другой поток, возможно, изменил ситуацию между разблокировкой чтения и блокировкой записи.

for details check this question and its answers

В конце обхода В-дерева будет работать параллельно. Только при обнаружении целевого узла поток получает эксклюзивную блокировку (и другие потоки будут блокироваться только на время вставки).

Answer 2

Рассматривая один набор данных в строке, 48k линий не так уж и много, и вы можете иметь только дикие догадки о том, как ваша операционная система и виртуальная машина будут блокировать ваш файл IO, чтобы сделать его как можно быстрее.

Пытаться использовать парадигму производителя/потребителя может быть проблематично здесь, так как вам необходимо сбалансировать накладные расходы на блокировки против фактического количества ввода-вывода. Вы можете получить более высокую производительность, если попытаетесь улучшить способ работы с файлом IO (рассмотрите что-то вроде mmap()).

Answer 3

Я бы сказал, что делать это так: не способ пойти, даже не принимая во внимание проблемы с синхронизацией.

Возможно, проблема в том, что эта реализация медленнее исходной полностью синхронизированной версии, но большая проблема заключается в том, что блокировка в этой реализации не является надежной.

Представьте себе, например, что вы проходите null для сортировкиWord; это приведет к выбросу NullPointerException, что означает, что вы в конечном итоге держитесь за блокировку в текущем потоке и, следовательно, оставляете свою структуру данных в несогласованном состоянии. С другой стороны, если вы просто synchronize этот метод, вам не нужно беспокоиться о таких вещах. С другой стороны, синхронизированная версия работает быстрее, это простой выбор.

Answer 4

Блокировка и разблокировка - это накладные расходы, и чем больше вы это сделаете, тем медленнее будет ваша программа.

С другой стороны, разложение задачи и работающих частей параллельно сделает вашу программу более быстрой.

Где находится точка «безубыточности», зависит от количества соперников за конкретный замок в вашей программе и системной архитектуры, на которой выполняется программа. Если есть небольшая разногласия (как представляется, в этой программе) и многих процессоров, это может быть хорошим подходом. Однако, поскольку количество потоков уменьшается, накладные расходы будут доминировать, а параллельная программа будет медленнее. Вы должны определить свою программу на целевой платформе, чтобы определить это.

Другой вариант рассмотрения - неблокирующий подход с использованием неизменяемых структур.Вместо того, чтобы изменять список, например, вы можете добавить старый (связанный) список к новому узлу, затем с помощью операции compareAndSet на AtomicReference, убедитесь, что вы выиграли гонку данных, чтобы установить коллекцию words в текущем дереве. Если нет, попробуйте еще раз. Вы можете использовать AtomicReferences для левого и правого детей в ваших узлах дерева. Будет ли это быстрее или нет, опять же, нужно будет протестировать на целевой платформе.

Answer 5

Другое дело. Определенно нет места для бинарного дерева в критическом для производительности коде. Поведение кэширования убьет всю производительность. У него должен быть намного больший фанат (одна строка кеша). [Edit] С бинарным деревом вы получаете доступ к слишком много несмежной памяти. Взгляните на материал о деревьях Джуди.

И вы, вероятно, захотите начать с основания хотя бы одного символа перед началом дерева.

И сначала выполните сравнение по ключевому слову int, а не по строке.

И возможно смотреть на

пытается

и избавиться от всех потоков и синхронизации. Просто попробуйте связать проблему с доступом к памяти.

Я бы сделал это несколько иначе. Я бы использовал поток для каждого первого символа строки и дал им свой собственный BTree (или, возможно, Trie). Я помещал неблокирующую рабочую очередь в каждый поток и заполнял их на основе первого символа строки. Вы можете получить еще большую производительность, предварительно дождав очередь добавления и выполнив сортировку слияния в BTree. В BTree я использовал бы клавиши int, представляющие первые 4 символа, только ссылаясь на строки на листах.

В соревновании по скорости вы надеетесь получить доступ к памяти и, следовательно, не нужны для потоков. Если нет, вы все равно делаете слишком много обработки на строку.

Answer 6

У меня есть немой вопрос: поскольку вы читаете и изменяете файл, вы будете полностью ограничены тем, насколько быстро голова чтения/записи может перемещаться и диск может вращаться. Так что же полезно использовать потоки и процессоры? Диск не может делать сразу две вещи.

Или это все в ОЗУ?

ADDED: Хорошо, мне не ясно, насколько параллелизм может помочь вам здесь (некоторые, может быть), но независимо от того, что я предлагаю, выжимаете каждый цикл из каждого потока, который вы можете. This is what I'm talking about. Например, мне кажется, что если невинно выглядящий спящий код, такой как призывы к методам «получить» и «сравнить», занимает больше времени, чем вы могли ожидать. Если они есть, вы можете сделать каждый из них один раз, а не 2 или 3 раза - что-то вроде этого.

Answer 7

Я бы на самом деле начал смотреть на использование compare() и equals() и посмотреть, можно ли там что-то улучшить. Вы можете обернуть объект String в другом классе другим, оптимизированным для вашего метода usecase, compare(). Например, рассмотрите возможность использования hashCode() вместо equals(). Хэш-код кэшируется, поэтому будущие вызовы будут намного быстрее. Рассмотрите возможность интернирования строк. Я не знаю, примет ли vm столько строк, но стоит проверить.

(это будет комментарий к ответу, но слишком многословный).

При чтении узлов вам необходимо получить блокировку чтения для каждого узла по мере его достижения. Если вы читаете-заблокируете все дерево, то ничего не получите. Как только вы достигнете узла, который хотите изменить, вы освободите блокировку чтения для этого узла и попытаетесь получить блокировку записи. Код будет выглядеть примерно так:

TreeNode current; // добавьте ReentrantReadWriteLock к каждому узлу.

// введите текущий узел:
current.getLock(). ReadLock(). Lock(); ....
если (isTheRightPlace (ток) {
current.getLock() блокировкой чтения() разблокировать();
current.getLock() блокировку записи() блокировка(); // NB: getLock возвращает ConcurrentRWLock
// сделать материал затем снять блокировку
current.getLock() блокировку записи() разблокировать();....
} еще {
current.getLock() блокировкой чтения() разблокировать();
}

Answer 8

Кажется, что вы использовали двоичное дерево поиска, а не B-Tree.

В любом случае, рассмотрели ли вы использование ConcurrentSkipListMap? Это упорядоченная структура данных (введенная в Java 6), которая должна иметь хороший параллелизм.