UNDF: UNDF-2026-000000415

hazelcast-0001 — QueueContainer.compareAndRemove() O(Q×D) membership test

Classification

Field	Value
CWE	CWE-407: Algorithmic Complexity — Linear Membership Test in Outer Loop
Severity	HIGH
Component	`hazelcast/src/main/java/com/hazelcast/collection/impl/queue/QueueContainer.java`
Method	`compareAndRemove(Collection<Data> dataList, boolean retain)`
Lines	801–820
Public API	`IQueue.removeAll(Collection)` / `IQueue.retainAll(Collection)`

Defective Code

// QueueContainer.java:801-820
public Map<Long, Data> compareAndRemove(Collection<Data> dataList, boolean retain) {
    LinkedHashMap<Long, Data> map = new LinkedHashMap<>();
    for (QueueItem item : getItemQueue()) {           // O(Q) outer loop
        if (item.getSerializedObject() == null && store.isEnabled()) {
            ...load(item)...
        }
        boolean contains = dataList.contains(item.getSerializedObject()); // O(D) per item
        if ((retain && !contains) || (!retain && contains)) {
            map.put(item.getItemId(), item.getSerializedObject());
        }
    }
    mapIterateAndRemove(map);
    return map;
}

dataList is always constructed as an ArrayList<Data> by QueueProxyImpl.getDataList(). getItemQueue() returns a LinkedList<QueueItem> (or PriorityQueue).

Root Cause

ArrayList.contains() is O(D) — it performs a linear scan. Called inside an O(Q) outer loop over every queue item, total cost is O(Q × D).

With a large distributed queue (Q = 100 000 items) and a removal batch (D = 1 000 elements), this is 100 million comparisons instead of 100 001.

Fix

Pre-build a HashSet<Data> from dataList before the outer loop.

public Map<Long, Data> compareAndRemove(Collection<Data> dataList, boolean retain) {
    Set<Data> dataSet = new HashSet<>(dataList);          // O(D) one-time setup
    LinkedHashMap<Long, Data> map = new LinkedHashMap<>();
    for (QueueItem item : getItemQueue()) {               // O(Q)
        if (item.getSerializedObject() == null && store.isEnabled()) {
            ...load(item)...
        }
        boolean contains = dataSet.contains(item.getSerializedObject()); // O(1)
        if ((retain && !contains) || (!retain && contains)) {
            map.put(item.getItemId(), item.getSerializedObject());
        }
    }
    mapIterateAndRemove(map);
    return map;
}

Complexity

	Before	After
`compareAndRemove`	O(Q × D)	O(Q + D)
`IQueue.removeAll(D items)` on Q-item queue	O(Q × D)	O(Q + D)
`IQueue.retainAll(D items)` on Q-item queue	O(Q × D)	O(Q + D)

Speedup Estimate

At Q = 1 000, D = 1 000 (all-distinct): ~500× fewer comparisons. At Q = 10 000, D = 500: ~250× fewer comparisons.

2.8 KiB Raw Permalink Blame History Unescape Escape