New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

TTreeCache scale (very) poorly with number of baskets/clusters. #12649

Closed

pcanal opened this issue Apr 12, 2023 · 24 comments · Fixed by #12650

Assignees

Labels

affects:master affects:6.18 affects:6.20 affects:6.22 affects:6.24 affects:6.26 affects:6.28 bug priority:critical

Projects

Fixed in 6.24/10 Fixed in 6.26/12 Fixed in 6.30/00 Fixed in 6.28/06

Milestone

Member

pcanal commented Apr 12, 2023

As described in https://root-forum.cern.ch/t/interactively-working-with-large-ntuple-tree-files-discovered-big-difference-between-old-and-new-root-versions-in-speed-7s-vs-1-hour-response-time/54312, when a file/TTree is created such that the cluster is actually pretty small (in bytes) and thus the number of cluster in the file is very larges (100,000+ clusters), the TTreeCache scale poorly (since v6.14/00).

In particular in the described case, the run-time increase from a few second (7s) to more than one hour.

The text was updated successfully, but these errors were encountered:

pcanal added bug affects:master affects:6.22 affects:6.20 affects:6.18 priority:critical affects:6.24 affects:6.26 affects:6.28 labels

pcanal added this to the 6.28/04 milestone

pcanal self-assigned this

pcanal added a commit to pcanal/root that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

59355ee

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes root-project#12649

pcanal added a commit to pcanal/root that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

d0b72c9

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes root-project#12649

pcanal added a commit to pcanal/root that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

e56e19f

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes root-project#12649

jalopezg-git mentioned this issue

Fix TTreeCache Scaling with the number of clusters/baskets. #12650

Merged

pcanal closed this as completed in #12650

pcanal added a commit that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

fc4880d

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes #12649

github-actions bot commented Apr 20, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

1 similar comment

github-actions bot commented Apr 21, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

pcanal added a commit to pcanal/root that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

97fb4a7

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes root-project#12649

github-actions bot commented Apr 24, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

1 similar comment

github-actions bot commented Apr 25, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

pcanal added a commit that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

5e81da6

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes #12649

github-actions bot commented Apr 26, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

6 similar comments

github-actions bot commented Apr 27, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented Apr 28, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 1, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 2, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 3, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 4, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 5, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

12 similar comments

github-actions bot commented May 8, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 9, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 10, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 11, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 12, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 15, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 16, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 17, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 18, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 19, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 22, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

github-actions bot commented May 23, 2023

It appears this issue is closed, but wasn't yet added to a project. Please add upcoming versions that will include the fix, or 'not applicable' otherwise.

Sincerely,
🤖

pcanal added a commit that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

bff7aa1

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes #12649

pcanal added a commit that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

d279821

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes #12649

pcanal added this to Issues in Fixed in 6.24/10 via automation

pcanal added this to Issues in Fixed in 6.26/12 via automation

pcanal added this to Issues in Fixed in 6.30/00 via automation

pcanal added this to Issues in Fixed in 6.28/06 via automation

enirolf pushed a commit to enirolf/root that referenced this issue


          TTreeCache correct place cache (avoid O(N^2) behavior

7f6cbef

Prior to this change, the cache of which basket to start the search
on would restart from the first basket at each cluster iteration
(i.e. for filling the cache with with clusters)

On an extreme example:
        15,272,928 entries
           152,739 baskets (and as many clusters)
            10,000 Actual TTreeCache buffer size (minimum allowed)
             8,442 estimated buffer size of TTreeCache (1.5 times compressed buffer size)
               400 bytes per baskets
               100 entries per baskets (i.e. per clusters)
                25 number of cluster per TTreeCache buffer for single branch with default size.
                 1 float per entry (reading a single branch).

This ends up repairing the performance of a simple `TTree::Draw` of a single branch
from 1 hour back down to 7s (performance seem in v6.12).

This correct an issue introduced by commit 73f6223 first since in v6.14/00

This fixes root-project#12649

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment