Производительность ConcurrentHashMap size ()

Какова производительность во время выполнения ConcurrentHashMap size()? Глядя на источник (это Java7), я не могу понять его, и я не вижу, как это обсуждается в документах.

Вот код 

 public int size() {
        // Try a few times to get accurate count. On failure due to
        // continuous async changes in table, resort to locking.
        final Segment<K,V>[] segments = this.segments;
        int size;
        boolean overflow; // true if size overflows 32 bits
        long sum;         // sum of modCounts
        long last = 0L;   // previous sum
        int retries = -1; // first iteration isn't retry
        try {
            for (;;) {
                if (retries++ == RETRIES_BEFORE_LOCK) {
                    for (int j = 0; j < segments.length; ++j)
                        ensureSegment(j).lock(); // force creation
                }
                sum = 0L;
                size = 0;
                overflow = false;
                for (int j = 0; j < segments.length; ++j) {
                    Segment<K,V> seg = segmentAt(segments, j);
                    if (seg != null) {
                        sum += seg.modCount;
                        int c = seg.count;
                        if (c < 0 || (size += c) < 0)
                            overflow = true;
                    }
                }
                if (sum == last)
                    break;
                last = sum;
            }
        } finally {
            if (retries > RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    segmentAt(segments, j).unlock();
            }
        }
        return overflow ? Integer.MAX_VALUE : size;
    }
1 3
performance concurrenthashmap

1 ответ:

Ну, мое понимание кода таково, что сложность равна O(1).

Во-первых, если вы посмотрите на остальную часть кода, Вы увидите, что segments.length зависит исключительно от значения concurrencyLevel при создании карты. Он не меняется, когда карта перераспределяется.

Таким образом, в незапланированном случае легко увидеть, что материал внутри цикла for(;;) будет выполняться дважды, и что число итераций внутреннего вида равно segments.length; т. е. это O(1) в общем и целом.

В рассматриваемом случае производительность будет хуже, потому что цикл for(;;) может выполняться несколько раз. Но я все еще думаю, что сложность будет O(1) относительно размера карты N.

Но, сказав это, похоже, что size() является дорогостоящей операцией, и это будет узким местом параллелизма, если утверждение достаточно, что алгоритм должен вернуться к блокировке всей карты; т. е. retries достигает RETRIES_BEFORE_LOCK (2 в версии, которую я искал на).

5