Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

`AbstractDataTreeNode.indexOfChild()` is called excessively on large resource tree size

オープン
  • 何か問題がありますか？
#2,567 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
25/100
issue の種類
リファクタリング
明瞭さ
説明が足りない
活発さ
停滞
技術スタック
java
領域
performance

調査の方向性

AbstractDataTreeNode.indexOfChild() と DeltaDataTree.lookup() から始め、リンクされている heapdump 分析と delta-tree の親ノードの走査を確認します。大規模なリソースツリーで lookup のベンチマークを実施し、提案されている最適化の方向性を比較します。選択したアプローチによって報告された lookup ホットスポットが、lookup の動作を変更せずに縮小されれば完了です。

索引モデルが issue の本文から書いたものです。

説明

enhancement

During analysis of two heapdumps shared here the following issue was discovered as a hotspot that can benefit from optimization:

Performance Data
Metric WITH transitive WITHOUT transitive Ratio
indexOfChild() self time (µs) 70,405,568 35,739,594 2.0×
DeltaDataTree.lookup() (µs) 55,328,734 24,397,133 2.3×
Description

indexOfChild() performs a binary search on a sorted array of child nodes:

protected int indexOfChild(String localName) {
    AbstractDataTreeNode[] nodes = this.children;
    int left = 0, right = nodes.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int compare = localName.compareTo(nodes[mid].name);
        // ...
    }
    return -1;
}

While the binary search itself is O(log n), DeltaDataTree.lookup() calls indexOfChild() at each path segment level:

public DataTreeLookup lookup(IPath key) {
    int keyLength = key.segmentCount();
    for (DeltaDataTree tree = this; tree != null; tree = tree.parent) {
        AbstractDataTreeNode node = tree.rootNode;
        for (int i = 0; i < keyLength; i++) {
            node = node.childAtOrNull(key.segment(i)); // calls indexOfChild
        }
    }
}

The delta tree chain (tree.parent) can be deep, and each delta layer requires re-traversing the path from root.

The combined indexOfChild() time (70.4 seconds) represents the single largest CPU consumer in the entire build.

Suggested Fix
  1. Compact delta chains more aggressively: The parent chain walk is expensive. More frequent immobilization of the delta tree would reduce the number of layers to traverse.
  2. Cache frequent lookups: If the same resource paths are looked up repeatedly (e.g., project roots, source folders), a small LRU cache on DeltaDataTree.lookup() could avoid repeated traversals.
  3. Consider hybrid data structure: For nodes with many children (> 100), consider switching from sorted array + binary search to a HashMap<String, AbstractDataTreeNode> for O(1) child lookup. This is particularly relevant for directories containing many files (e.g., classpath container folders).
  4. Reduce key.segment(i) overhead: Each call to IPath.segment(i) on Path objects does array access. Ensure paths are not being reconstructed or re-parsed in hot loops.
主要言語
Java
スター
165
フォーク
174
平均マージ
3日 6時間
マージ済み PR（30日）
44

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

eclipse-platform/eclipse.platform のほかの issue

eclipse-platform/eclipse.platform の issue をすべて見る

似ている issue

Java の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。