Обход бинарного дерева с несколькими потоками

Question

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

Каждый узел имеет ReentrantLock с именем lock, а 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();
}

РЕДАКТИРОВАТЬ: просто чтобы уточнить, мой код структурирован следующим образом: основной поток читает входные данные из файла и добавляет слова в очередь, каждый рабочий поток извлекает слова из очереди и выполняет некоторую работу (включая их сортировку и добавление их в двоичное дерево).

Answer 1

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

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

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

И, возможно, посмотрите на попытки

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

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

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

Answer 2

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

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

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

текущий TreeNode; // добавляем ReentrantReadWriteLock для каждого узла.

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

Answer 3

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

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

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

Это должно выглядеть примерно так:

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();
}

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

для подробной информации проверьте этот вопрос и его ответы

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

Answer 4

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

С другой стороны, декомпозиция задачи и параллельное выполнение частей ускорят выполнение вашей программы.

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

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

Answer 5

Похоже, вы внедрили бинарное дерево поиска, а не B-дерево.

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

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

Или это все в оперативной памяти?

ДОБАВЛЕНО: ОК, мне не ясно, насколько параллелизм может вам помочь (некоторые, может быть), но независимо от того, что я бы предложил, это выжать каждый цикл из каждого потока, который вы можете. Это то, о чем я говорю. Например, мне интересно, не выглядит ли невинно выглядящий спящий код, такой как вызовы методов «получить» и «сравнить», больше времени, чем вы могли бы ожидать. Если это так, вы можете выполнить каждый из них один, а не два или три раза - такого рода вещи.