Улучшить производительность параллельного ArrayList без дублирования.

Я столкнулся с проблемой производительности при реализации структуры данных не дублирующийся параллельный ArrayList (или ConcurrentLinkedQueue).

public class NonDuplicateList implements Outputable {
    private Map<Term, Integer> map;
    private List<Term> terms;

    public NonDuplicateList() {
        this.map = new HashMap<>();
        this.terms = new ArrayList<>();
    }

    public synchronized int addTerm(Term term) { //bad performance :(
        Integer index = map.get(term);
        if (index == null) {
            index = terms.size();
            terms.add(term);
            map.put(term, index);
        }
        return index;
    }

    @Override
    public void output(DataOutputStream out) throws IOException {
        out.writeInt(terms.size());
        for (Term term : terms) {
            term.output(out);
        }
    }
}

Обратите внимание, что Term и NonDuplicateList реализуют интерфейс Outputable для вывода.

Чтобы сохранить потокобезопасность NonDuplicateList, я использую synchronized для защиты метода addTerm(Term), и производительность при вызове addTerm оказалась такой же плохой, как и ожидалось.

Кажется, что ConcurrentHashMap не подходит для этого случая, так как он не обеспечивает строгой согласованности данных. Есть идеи, как улучшить производительность addTerm без потери его потокобезопасности?

РЕДАКТИРОВАТЬ:

output, то есть итерация через NonDuplicateList, может быть не потокобезопасным, поскольку только один поток будет обращаться к этому методу после одновременного вызова addTerm, но addTerm должен возвращать значение индекса немедленно, как только термин добавляется в NonDuplicateList.


java multithreading arraylist concurrenthashmap
person dawnwords    schedule 28.11.2016    source источник
comment
It seems that ConcurrentHashMap isn't suitable for this case, since it doesn't keep strong data consistency - поясните пожалуйста.   -  person OldCurmudgeon    schedule 28.11.2016
comment
Я согласен, используйте ConcurrentHashMap для того, что вы делаете, не создавайте свой собственный список   -  person borowis    schedule 28.11.2016
comment
@OldCurmudgeon Я слышал, что после помещения пары ключ-значение в ConcurrentHashMap другой поток не может видеть это изменение напрямую? В моем случае повторяющийся элемент не допускается, поэтому такое несоответствие кажется неуместным.   -  person dawnwords    schedule 29.11.2016

Ответы (2)


arrow_upward
0
arrow_downward

Существует возможность повторного использования ConcurrentHashMap в вашей реализации, если вы можете пожертвовать возвращаемым типом addTerm. Вместо того, чтобы возвращать фактический индекс, вы можете вернуть boolean, который указывает, было ли добавление успешным или было создано дубликат. Это также позволит вам удалить синхронизацию методов и повысить производительность:

private ConcurrentMap<Term, Boolean> map;
private List<Term> terms;

public boolean addTerm(Term term) {
    Boolean previousValue = map.putIfAbsent(term, Boolean.TRUE);
    if (previousValue == null) {
        terms.add(term);
        return true;
    }
    return false;
}
person hoaz    schedule 28.11.2016
comment
Нельзя жертвовать возвращаемым значением индекса терминов. Любые другие предложения? - person dawnwords; 29.11.2016
comment
Не похоже, что вы можете использовать фактический индекс за пределами NonDuplicateList, зачем он вам нужен? - person hoaz; 29.11.2016
comment
В целях экономии места на индекс ссылаются другие, которые также необходимо выводить вместо использования термина «данные». - person dawnwords; 01.12.2016

arrow_upward
0
arrow_downward

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

С другой стороны, когда вам нужна синхронизация и согласованный итератор, вам понадобится альтернатива для ConcurrentHashMap. Мне приходит на ум java.util.Collections#synchronizedMap, но он использует синхронизацию на уровне объекта, поэтому каждая операция чтения/записи должна получать блокировку, что снижает производительность.

Взгляните на ConcurrentSkipListMap, который гарантирует среднюю O(log(n)) производительность в самых разных операциях. Он также имеет ряд операций, которых нет в ConcurrentHashMap: ceilingEntry/Key, floorEntry/Key и т. д. Он также поддерживает порядок сортировки, который в противном случае пришлось бы вычислять (с заметными затратами), если бы вы использовали ConcurrentHashMap. Возможно, можно было бы избавиться от list+map и вместо этого использовать ConcurrentSkipListMap. Индекс элемента может быть вычислен с использованием ConcurrentSkipListMap API.

person slawekpl    schedule 29.11.2016