ConcurrentHashMap size() performance

Question

Whats the running time performance of ConcurrentHashMap size()? Looking at the source (this is Java7) I can't figure it out, and Im not seeing it discussed in the docs.

Here is the code

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

Answer 1

Well, my reading of the code is that the complexity is O(1).

First, if you look at the rest of the code, you will see that segments.length depends solely on the value of concurrencyLevel when the map is created. It doesn't change when the map is reallocated.

So, in the uncontended case, it is simple to see that the stuff inside the for(;;) loop will get executed twice, and that the number of iterations of the inner looks is segments.length; i.e. this is O(1) overall.

In the contended case, the performance is going to be worse because the for(;;) loop might get executed multiple times. But I still think the complexity will be O(1) relative to the map size N.

---

But having said that, it looks like size() is an expensive operation, and it will be a concurrency bottleneck if the contention is sufficient that the algorithm has to fall back on locking the entire map; i.e. retries reaches RETRIES_BEFORE_LOCK (2 in the version I looked at).