DT[by] performance test improvement

[tdhock]

I see HEAD and base are much faster than others (right bottom panel).
But it seems to take more memory. (upper right panel)

#7686 (comment)

Did somebody improve join max/min/aggregation speed recently? Which PR? We should add a commit from that PR, or from current master, to that atime test case, so we can maintain this speed improvement, going forward.

The code for the test case which uses more memory and is faster:

"DT[by] fixed in #4558" = atime::atime_test(
    setup = {
      N9 <- as.integer(N * 0.9)
      d <- data.table(
        id = sample(c(seq.int(N9), sample(N9, N-N9, TRUE))),
        v1 = sample(5L, N, TRUE),
        v2 = sample(5L, N, TRUE)
      )
    },
    expr = data.table:::`[.data.table`(d, , max(v1) - min(v2), by = id),

[tdhock]

doing manual bisect…
after Oct 3 #7315
after Dec 23 #7502
after Jan 12 #7517
after Jan 14 #7589 #7596
before Jan 19 #7598
before Jan 21 #7615
before Jan 20 #7606

found it in #7401 by @ben-schwen , reviewed by @MichaelChirico and @jangorecki

[tdhock]

do you think this increase in memory usage and speed is expected?
If so, I could add the merge commit from #7401 as a historical reference for this test case.
If not, maybe Ben could do a follow-up PR to reduce memory usage?

[MichaelChirico]

Speed is definitely expected I'd say -- max(v1) - min(v2) was explicitly targeted as something that was not GForce before but is now. Glad it was picked up by an existing test!

On the memory side... it's more interesting. I didn't have a prior so I asked Gemini. It says it's a major win for memory efficiency!!! Unless you remind it that actually we see memory usage go up, then it backtracks and points out that maybe memory could go up after all 🙃

---

Evaluate the memory efficiency implications of this merged pull request: #7401

✦ Based on a thorough evaluation of the changes in merged pull request #7401, here is an analysis of its memory efficiency implications.

1. Significant Expansion of GForce Optimization
   The most impactful change for memory efficiency is the dramatic expansion of GForce (data.table's fast C-level grouping optimization). Previously, GForce was limited to very simple expressions (e.g., sum(col) or mean(col)). This PR introduces an AST (Abstract Syntax Tree) walker that allows GForce to handle much more complex j expressions:

• Arithmetic in j: Expressions like sum(x) + sum(y), (sum(x) - mean(y)) / .N, or sum(x) * 1.05 are now GForce-able. Instead of executing these in R for every group (creating millions of small R objects), data.table now transforms them into a single call (e.g., gsum(x) + gsum(y)) that is evaluated efficiently in C once for all groups.
• Type Conversion Support: GForce now supports type conversions like as.numeric(col), as.integer(col), etc., as arguments to grouping functions (e.g., sum(as.numeric(x))). This avoids the "million little pieces" problem where R would otherwise create a tiny numeric vector for every single group.

2. Modularization of Optimization Internals
   The PR refactors the core optimization logic into a cleaner, modular structure (using helper functions like .optimize_gforce, .optimize_lapply, and .optimize_sd_subset).

• Reduced R Overhead: The new .massageSD implementation is designed to minimize R-level overhead (like symbol lookups and as.list copies) which previously caused significant memory pressure during the optimization of thousands of groups.
• Better .SD Handling: Subsetting .SD (e.g., .SD[1], head(.SD)) is now transformed into per-column subsets (e.g., list(col1[1], col2[1], ...)) that are themselves GForce-optimized. This completely avoids materializing the .SD data.table for each group, a common cause of memory exhaustion in grouped operations.

3. Optimization of New lapply Patterns
   The PR adds optimization for the lapply(list(col1, col2, ...), fun) pattern.

• Previously, only lapply(.SD, fun) was optimized. Users who manually specified a list of columns missed out on GForce.
• By optimizing this pattern, data.table avoids the R-level lapply loop for each group, further reducing the allocation of intermediate R lists and names.

4. Memory-Performance Trade-offs

• Peak Memory vs. Object Count: For expressions like sum(as.numeric(x)), the optimizer may create a single full-length numeric copy of the column before grouping. While this uses a predictable amount of memory, it is far more efficient than the "fragmented" memory usage caused by creating thousands/millions of small vectors, which stresses the R Garbage Collector (GC) and leads to high memory overhead per object.
• Vectorized Results: By staying in GForce, the intermediate results (like the sums for each group) are stored in contiguous C arrays until the final result is assembled, minimizing memory fragmentation.

Summary
Pull request #7401 is a major win for memory efficiency. By moving complex arithmetic and type-converted grouping operations from R into the C-level GForce engine, it drastically reduces the number of R object allocations. This leads to lower memory pressure, fewer GC cycles, and significantly faster execution for data.tables with a high number of groups.

We found, however, that this {atime} test shows some increase in memory usage. Explain.

"DT[by] fixed in #4558" = atime::atime_test(                                                                                                                                                                                                                                                                                                                                                                                         
    setup = {                                                                                                                                                                                                                                                                                                                                                                                                                        
      N9 <- as.integer(N * 0.9)                                                                                                                                                                                                                                                                                                                                                                                                      
      d <- data.table(                                                                                                                                                                                                                                                                                                                                                                                                               
        id = sample(c(seq.int(N9), sample(N9, N-N9, TRUE))),                                                                                                                                                                                                                                                                                                                                                                         
        v1 = sample(5L, N, TRUE),                                                                                                                                                                                                                                                                                                                                                                                                    
        v2 = sample(5L, N, TRUE)                                                                                                                                                                                                                                                                                                                                                                                                     
      )                                                                                                                                                                                                                                                                                                                                                                                                                              
    },                                                                                                                                                                                                                                                                                                                                                                                                                               
    expr = data.table:::`[.data.table`(d, , max(v1) - min(v2), by = id),                                                                                                                                                                                                                                                                                                                                                             

✦ The increase in memory usage observed in the {atime} test is a direct consequence of how the new AST (Abstract Syntax Tree) walker handles arithmetic expressions in GForce.

The Mechanism of the Increase

Before PR #7401, the expression max(v1) - min(v2) was not GForce-optimized as a whole. Because it involved a subtraction operator (-), data.table would fall back to its standard grouping mechanism (dogroups). In that mode, for each of the N9 groups (which is 90% of N), R would:

1. Calculate a scalar max(v1) for the group.
2. Calculate a scalar min(v2) for the group.
3. Subtract them to get a single scalar result.
4. Store that scalar in the final result vector.
   In this "row-by-row" (or group-by-group) approach, only one result vector of length ngrp is ever fully materialized in memory.

After PR #7401, this expression is now fully GForce-optimized. The AST walker transforms it into a vectorized calculation:

1. gmax(v1) is called, producing a full numeric vector of length ngrp.
2. gmin(v2) is called, producing a second full numeric vector of length ngrp.
3. The subtraction is performed on these two vectors, producing a third full numeric vector of length ngrp.

Why this impacts your specific test
In your setup, the number of groups (ngrp) is extremely high (90% of N).

• If N = 1,000,000, then ngrp = 900,000.
• During the subtraction step, GForce holds three vectors of length 900,000 in memory simultaneously (the two intermediate results and the final result).
• At 8 bytes per double, this is roughly 3 * 900,000 * 8 bytes ≈ 21.6 MB of peak memory for the vectors alone, plus the overhead of the GForce indexing structures (high and low vectors, which add another 4 * N bytes).

Summary
The memory increase is a trade-off for speed. While the new vectorized GForce approach uses more peak memory (because it materializes intermediate vectors for the entire set of groups), it is significantly faster than the previous R-loop approach because it avoids the overhead of millions of small R function calls and environment management. For cases where ngrp is nearly equal to N, the intermediate vector overhead
becomes visible in tools like {atime}.

[ben-schwen]

Yeah I also think the memory could go slightly up for high number of groups since we do nit doGroups calculation for each group separate.

With the new GeForce interface we could calculate x-y inplace on x instead of allocating a new object automatically saving one allocation but I'm pretty sure thats not really worth it.

[MichaelChirico]

Two feedbacks on {atime} reporting here:

• It's hard to tell the units -- there are too many facets. Ideally we could add a y-axis every 4-6 plots. At a minimum it should be at the leftmost part and rightmost part of the plot.
• Why wasn't this surfaced in the report? If I click in on modularize optimization internals #7401, I would have expected this to show up as the # 1 left-most / salient plot, instead it's all the way to the right

[ben-schwen]

@MichaelChirico AFAIU, we order by speed increase in atime 😅

[tdhock]

Thanks guys, in that case I will send a PR adding a new sha to this test case, and we will keep this memory increase, which seems reasonable (1.8x more memory for 4–5x speedup).

• Ben is right, atime only emphasizes speed problems (not improvements)
• to see the units in each panel we could switch to facet_wrap instead of grid atime_pkg option for facet_wrap tdhock/atime#106

[tdhock]

even bigger speedups (8–11x) at larger data sizes (seconds.limit=1).

test code https://github.com/Rdatatable/data.table/pull/7691/files#diff-702730b30ceeb15d25326120b1d1b5ff82c987842a38986d9e3d892942419b27

[MichaelChirico]

atime only emphasizes speed problems (not improvements)

Is there a downside to sorting by abs(change)? It seems like in any single PR, with very high likelihood, we'll only see change in one direction.

[ben-schwen]

I guess the problem with abs(change) is to find a good unit, currently seconds vs KB? I maybe abs(relative_change)?