eclipse-jdt / eclipse-jdt/eclipse.jdt.core
`JavaProject.computeExpandedClasspath()` recursively expands without memoization
- Dominant language
- Java
- Stars
- 237
- Forks
- 195
- Avg merge
- 1d 12h
- Merged PRs (30d)
- 47
Description
During analysis of two heapdums shared [here](https://github.com/eclipse-pde/eclipse.pde/pull/2253#issuecomment-4054961583) the following issue was discovered as a hotspot that can benefit from optimization:
### Performance Data
| Metric | WITH transitive | WITHOUT transitive | Ratio |
|--------|----------------:|-------------------:|------:|
| Self time (µs) | 6,701,978 | 678,778 | **9.9×** |
### Description
`computeExpandedClasspath()` recursively walks the project dependency graph, expanding all `CPE_PROJECT` entries by calling `getResolvedClasspath()` and then recursing into each referenced project. With transitive dependencies, this traversal becomes significantly deeper and wider:
```java
private void computeExpandedClasspath(
ClasspathEntry referringEntry, HashMap rootIDs,
ArrayList accumulatedEntries, boolean excludeTestCode) throws JavaModelException {
IClasspathEntry[] resolvedClasspath = getResolvedClasspath(); // expensive
for (IClasspathEntry cpe : resolvedClasspath) {
ClasspathEntry entry = (ClasspathEntry) cpe;
if (excludeTestCode && entry.isTest()) continue; // calls isTest() on every entry
if (isInitialProject || entry.isExported()) {
if (entry.getEntryKind() == IClasspathEntry.CPE_PROJECT) {
// ... recurse into required project
javaProject.computeExpandedClasspath(combinedEntry, rootIDs, accumulatedEntries, ...);
}
}
}
}
```
The recursive expansion calls `getResolvedClasspath()` for the **same project multiple times** if it is a transitive dependency of multiple projects. The `rootIDs` HashMap prevents duplicate entries but not duplicate traversal — a project is only skipped if its root ID was already seen, but the traversal and `getResolvedClasspath()` call happen before the check for `CPE_PROJECT` entries.
Additionally, there is an **O(n²) linear search** when updating existing entries (lines 584–592):
```java
for (int j = 0; j < accumulatedEntries.size(); j++) {
ClasspathEntry oldEntry = accumulatedEntries.get(j);
if (oldEntry.rootID().equals(rootID)) { // linear scan!
accumulatedEntries.set(j, oldEntry.withExtraAttributeRemoved(...));
break;
}
}
```
With 100+ transitive classpath entries, this linear search is called frequently, resulting in thousands of iterations.
### Suggested Fix
1. **Memoize expanded classpath per project**: Cache the expanded classpath result per `(project, excludeTestCode)` pair so that re-expanding the same project is O(1).
2. **Replace ArrayList linear search with a HashMap index**: The linear scan at lines 584–592 should use a `HashMap` mapping `rootID` → index in `accumulatedEntries`, turning O(n) lookups into O(1).
3. **Move the `rootIDs.containsKey()` check before `getResolvedClasspath()`**: For non-project entries, the containsKey check already short-circuits. But for project entries, the resolved classpath is obtained before recursing, even if the project will be skipped.
4. Consider a **topological sort** of project dependencies and expanding bottom-up to avoid redundant work.
Contributor guide
Assessment
This issue has not been assessed yet.