Как называется эта техника блокировки?

Question

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

synchronized boolean containsSpecial() {
   return troveMap.contains(key);
}

Обратите внимание, что это карта "только для добавления": после добавления ключа она остается там навсегда (я думаю, это важно для того, что будет дальше).

Я заметил, что изменив вышеприведенное на:

boolean containsSpecial() {
    if ( troveMap.contains(key) ) {
        // most of the time (>90%) we shall pass here, dodging lock-acquisition
        return true;
    }
    synchronized (this) {
        return troveMap.contains(key);
    }
}

Я получаю ускорение на 20% при обработке моего номера (проверяется на многих запусках, при длительной работе и т. Д.).

Правильно ли выглядит эта оптимизация (зная, что если ключ есть, он останется там навсегда)?

Как называется эта техника?

EDIT

Код, который обновляет карту, вызывается гораздо реже, чем метод containsSpecial () и выглядит так (я синхронизировал весь метод):

synchronized void addSpecialKeyValue( key, value ) {
    ....
}

Answer 1

Этот код неверен.

Trove не обрабатывает одновременное использование; это как java.util.HashMap в этом отношении. Таким образом, подобно HashMap, даже на первый взгляд невинные методы только для чтения, такие как containsKey(), могут выдать исключение времени выполнения или, что еще хуже, войти в бесконечный цикл, если другой поток изменяет карту одновременно. Я не знаю внутренностей Trove, но с HashMap перефразировка при превышении коэффициента загрузки или удаление записей может вызвать сбои в других потоках, которые только читают.

Если операция занимает значительное время по сравнению с управлением блокировками, использование блокировки чтения-записи для устранения узкого места сериализации значительно повысит производительность. В документации класса для ReentrantReadWriteLock есть «Примеры использования»; Вы можете использовать второй пример для RWDictionary в качестве руководства.

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

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

Answer 2

Это называется неправильной блокировкой ;-) На самом деле, это некоторый вариант подхода двойной проверки блокировки.И оригинальная версия этого подхода просто неверна в Java.

Потокам Java разрешено хранить частные копии переменных в своей локальной памяти (представьте: локально-ядерный кэш многоядерной машины).Любой реализации Java разрешено никогда не записывать изменения обратно в глобальную память, если не происходит какая-либо синхронизация.

Итак, вполне возможно, что один из ваших потоков имеет локальную память, в которой troveMap.contains(key) оценивается как true.Поэтому он никогда не синхронизируется и никогда не получает обновленную память.

Кроме того, что происходит, когда contains() видит несогласованную память структуры данных troveMap?

Поиск модели памяти Java дляподробности.Или взгляните на эту книгу: Параллелизм Java на практике .

Answer 3

Это выглядит небезопасно для меня.В частности, несинхронизированные вызовы будут в состоянии видеть частичные обновления, либо из-за видимости памяти (предыдущая позиция не была полностью опубликована, так как вы не сказали JMM, что это необходимо), либо из-за простой старой гонки.Представьте себе, если TroveMap.contains имеет некоторую внутреннюю переменную, которая, как предполагается, не изменится в течение contains.Этот код допускает разрыв этого инварианта.

Что касается видимости памяти, то проблема заключается не в ложных отрицаниях (для этого используется синхронизированная двойная проверка), но инварианты этого потока могут быть нарушены.Например, если у них есть счетчик, и они требуют, чтобы counter == someInternalArray.length постоянно, нарушение синхронизации может нарушать это.

Моей первой мыслью было сделать ссылку на troveMap volatile и повторно- пишите ссылку каждый раз, когда вы добавляете на карту:

synchronized (this) {
    troveMap.put(key, value);
    troveMap = troveMap;
}

Таким образом, вы устанавливаете барьер памяти таким образом, что любой, кто читает troveMap, будет гарантированно видеть все, что произошлодо его самого последнего назначения - то есть его последнее состояние.Это решает проблемы с памятью, но не решает условия гонки.

В зависимости от того, насколько быстро изменяются ваши данные, может быть, фильтр Блума может помочь?Или какая-то другая структура, которая более оптимизирована для определенных быстрых путей?

Answer 4

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

Вы не говорите, какую карту вы реализовали, но реализации стандартной карты хранят ключи, назначая ссылки. Согласно спецификации языка J ava :

Запись и чтение ссылок всегда являются атомарными, независимо от того, реализованы ли они как 32- или 64-битные значения.

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

EDIT

Выше было написано в невежестве самого Trove. После небольшого исследования я обнаружил следующий пост Роба Идена (одного из разработчиков Trove) о том, являются ли карты Trove одновременными:

Trove не изменяет внутреннюю структуру при поиске. Однако это деталь реализации, а не гарантия, поэтому я не могу сказать, что она не изменится в будущих версиях.

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

Answer 5

Я думаю, что вам лучше использовать ConcurrentHashMap , который не требует явной блокировки и допускает одновременное чтение

boolean containsSpecial() {
    return troveMap.contains(key);
}

void addSpecialKeyValue( key, value ) {
    troveMap.putIfAbsent(key,value);
}

, а другой вариант - ReadWriteLock который допускает одновременное чтение, но не одновременную запись

ReadWriteLock rwlock = new ReentrantReadWriteLock();
boolean containsSpecial() {
    rwlock.readLock().lock();
    try{
        return troveMap.contains(key);
    }finally{
        rwlock.readLock().release();
    }
}

void addSpecialKeyValue( key, value ) {
    rwlock.writeLock().lock();
    try{
        //...
        troveMap.put(key,value);
    }finally{
        rwlock.writeLock().release();
    }
}

Answer 6

Почему вы изобретаете колесо? Просто используйте ConcurrentHashMap.putIfAbsent