eclipse-jdt / eclipse-jdt/eclipse.jdt.core
`NameEnvironment.getModulesDeclaringPackage()` iterates all binary locations linearly
- Dominant language
- Java
- Stars
- 237
- Forks
- 195
- Avg merge
- 1d 12h
- Merged PRs (30d)
- 47
Description
During analysis of two heapdumps 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 |
|--------|----------------:|-------------------:|------:|
| ClasspathLocation.getModulesDeclaringPackage() (µs) | 7,443,858 | 1,671,880 | **4.5×** |
| ClasspathLocation.findClass() (µs) | 4,129,889 | 1,639,802 | **2.5×** |
### Description
`getModulesDeclaringPackage()` iterates over **all** binary locations and source locations when the lookup strategy is `Any` or `Unnamed`:
```java
public char[][] getModulesDeclaringPackage(char[][] packageName, char[] moduleName) {
// ...
case Any:
case Unnamed:
char[][] names = CharOperation.NO_CHAR_CHAR;
for (ClasspathLocation location : this.binaryLocations) { // linear scan
char[][] declaringModules = location.getModulesDeclaringPackage(pkgName, null);
if (declaringModules != null)
names = CharOperation.arrayConcat(names, declaringModules); // array copy each time!
}
for (ClasspathLocation location : this.sourceLocations) { // another linear scan
// same pattern
}
```
With transitive dependencies, `binaryLocations` is significantly larger, and this method is called for every package reference during compilation. The `CharOperation.arrayConcat()` call on every match creates a new array each time, leading to O(n²) allocation behavior when many locations declare the same package.
Similarly, `findClass()` iterates through all `binaryLocations` linearly until a match is found:
```java
for (ClasspathLocation classpathLocation : relevantLocations) {
NameEnvironmentAnswer answer = classpathLocation.findClass(...);
// ...
}
```
### Suggested Fix
1. **Index binary locations by package name**: Build a `Map>` so that `getModulesDeclaringPackage()` only checks locations known to contain a given package, rather than iterating all locations.
2. **Use ArrayList + `toArray()` instead of repeated `arrayConcat()`**: The current approach of appending to `char[][]` via `arrayConcat()` is O(n²). Collect results in a `List` first.
3. **Cache package-to-module mappings**: Since the classpath doesn't change during a build, cache the result of `getModulesDeclaringPackage()` for each `(packageName, moduleName)` pair.
Contributor guide
Assessment
This issue has not been assessed yet.