Why 50K Records Took 40 Seconds: The Hidden Cost of List.contains() in Loops
A permission sync task processing 50,000 records ran in 40 seconds despite sub-second SQL queries; profiling revealed the bottleneck was an O(n²) List.contains() inside a stream filter, and replacing the List with a HashSet cut the diff calculation from 38 seconds to milliseconds, demonstrating how data structure choice dominates batch performance.
The Problem: Fast SQL, Slow Java
A permission synchronization task needed to compare 50,000 incoming permissions against 50,000 existing permissions, inserting missing ones and removing stale ones. Database queries took ~1 second total, and bulk writes took a few hundred milliseconds, yet the whole job ran for over 40 seconds. Initial suspicion fell on the database, but indexes and execution plans were fine.
Profiling Reveals the Real Culprit
Breaking down the stages showed:
Query upstream permissions: 420ms
Query local permissions: 510ms
Compute differences: 38,721ms
Bulk write to DB: 680msThe compute differences step consumed 38 seconds. The code looked clean:
List existingUserIds = existingPermissions.stream()
.map(Permission::getUserId)
.toList();
List toInsert = incomingPermissions.stream()
.filter(permission -> !existingUserIds.contains(permission.getUserId()))
.toList();Why List.contains() Is Not a Simple Lookup
For an ArrayList, contains() performs a linear scan, comparing each element via equals(). With 50,000 existing IDs and 50,000 incoming permissions, the filter invokes contains() 50,000 times, each scanning up to 50,000 elements — approaching 2.5 billion comparisons (O(n × m)).
The code looks like a single filter line, but the actual work is billions of equals() calls.
Why It Survives Development and Test
Local data might be 200 old + 300 new permissions — only ~60,000 comparisons, unnoticeable. Test environments with a few thousand records show slight slowness. Production hits 50,000 each, and the quadratic growth explodes. If both sides double to 100,000, time doesn't just double; it quadruples.
The Fix: Replace List with HashSet
Since the only requirement is existence checking, a Set provides O(1) average lookup via hashing.
Set existingUserIds = existingPermissions.stream()
.map(Permission::getUserId)
.collect(Collectors.toSet());
List toInsert = incomingPermissions.stream()
.filter(permission -> !existingUserIds.contains(permission.getUserId()))
.toList();Result: difference computation dropped from ~38 seconds to a few hundred milliseconds. CPU utilization, previously pinned on one core doing endless Long.equals() and String.equals(), fell dramatically.
Hidden Variant: Nested Streams
Another pattern found in the codebase:
List usersToDisable = localUsers.stream()
.filter(local -> remoteUsers.stream()
.noneMatch(remote -> remote.getEmployeeNo().equals(local.getEmployeeNo())))
.toList();This reads clearly — "find local users not in remote" — but still does a full scan of remoteUsers for every localUser. The fix is the same: build a Set of remote employee numbers first.
Set remoteEmployeeNos = remoteUsers.stream()
.map(User::getEmployeeNo)
.collect(Collectors.toSet());
List usersToDisable = localUsers.stream()
.filter(user -> !remoteEmployeeNos.contains(user.getEmployeeNo()))
.toList();When You Need the Object, Use a Map
If the logic requires retrieving the existing permission object (e.g., to update it), a Map keyed by the lookup field is appropriate:
Map existingMap = existingPermissions.stream()
.collect(Collectors.toMap(Permission::getUserId, Function.identity()));
for (Permission incoming : incomingPermissions) {
Permission existing = existingMap.get(incoming.getUserId());
if (existing == null) {
toInsert.add(incoming);
continue;
}
if (hasChanged(existing, incoming)) {
toUpdate.add(merge(existing, incoming));
}
}The Map not only speeds up lookups but also expresses the business rule: userId is the lookup key for this permission batch .
Duplicate Key Pitfall
Collectors.toMapthrows IllegalStateException on duplicate keys. If the business guarantees one permission per user, the exception correctly surfaces bad data. If a user can have multiple permissions, use Collectors.groupingBy to produce a Map<UserId, List<Permission>>.
Database JOIN vs. Java JOIN
Loading two tables (e.g., 50,000 users and 2,000 departments) and joining in Java with nested streams repeats the same quadratic mistake. If the data originates from the same database, a SQL JOIN is usually better. If sources are heterogeneous (DB, API, Redis, another service), build a Map in Java for the smaller dataset.
Pattern to Watch: Loop Scanning a Collection
Common forms:
for (Order o : orders) if (vipUserIds.contains(o.getUserId())) ...— if vipUserIds is an ArrayList, check its size.
for (Product p : products) categories.stream().filter(...).findFirst()users.stream().filter(u -> blackList.stream().noneMatch(...))All share the same structure: outer iteration × inner full scan. If both collections can reach thousands, compute the rough product (e.g., 50,000 × 50,000 = 2.5 billion) and consider an index ( Set / Map) built once in O(n).
Set/Map Are Not Free — Use Them Where They Pay Off
If a list is only iterated sequentially ( for (Item i : items) process(i)), converting to HashSet adds memory overhead with no benefit. The transformation pays off when the same collection is repeatedly queried for existence or key-based retrieval, especially inside a large outer loop.
Also, only store the minimal key needed for lookup. If you only need to check employeeNo, build a Set<String> of employee numbers, not a Set<UserEntity>.
Beyond 50K: Memory and Pagination
At millions of records, holding multiple List, Set, and Map instances may exceed heap. Then consider paginated reads, batch comparisons, temporary database tables, bulk SQL joins, or streaming processing. Optimization is layered: solve the current scale's biggest bottleneck, then reassess.
Summary of the Fix
Only a few lines changed:
// Before
List existingIds = existingPermissions.stream()
.map(Permission::getUserId)
.toList();
// After
Set existingIds = existingPermissions.stream()
.map(Permission::getUserId)
.collect(Collectors.toSet());No database hardware upgrades, no JVM tuning, no thread pool changes, no SQL rewrites. The entire difference calculation went from tens of seconds to milliseconds.
Java performance often isn't about GC magic or JIT flags. It's about not making 50,000 items scan another 50,000 items one by one.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
