Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

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

Đang mở
  • Có gì không ổn?
#2,567 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tái cấu trúc
Độ rõ ràng
Cần làm rõ
Mức độ hoạt động
Đình trệ
Công nghệ
java
Lĩnh vực
performance

Hướng nghiên cứu

Bắt đầu với AbstractDataTreeNode.indexOfChild() và DeltaDataTree.lookup(), sau đó xem xét phân tích heapdump được liên kết và quá trình duyệt các nút cha của delta-tree. Benchmark các lookup trên những cây tài nguyên lớn và so sánh các hướng tối ưu hóa được đề xuất. Được xem là hoàn tất khi cách tiếp cận được chọn làm giảm hotspot lookup đã báo cáo mà không thay đổi hành vi lookup.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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.
Ngôn ngữ chính
Java
Star
165
Fork
174
Merge trung bình
3 ngày 5 giờ
Pull request đã merge (30 ngày)
44

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của eclipse-platform/eclipse.platform

Tất cả issue của eclipse-platform/eclipse.platform

Issue tương tự

Thêm issue về Java

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.