frollmax is slow on descending sequences

Start by running the supplied benchmark and tracing the data.table::frollmax entry point for the descending-sequence case. The issue names no source file or test; establish a regression check for the reported slowdown and verify that results remain correct across the benchmark inputs.

# Minimal reproducible example; please be sure to set verbose=TRUE where possible!

if (!require("devtools")) install.packages("devtools")
if (!require("RCRoll")) devtools::install_github("davidcsterratt/RCRoll")
if (!require("roll")) install.packages("roll")
if (!require("data.table")) devtools::install_github("Rdatatable/data.table", branch="frollmax")

benchmark <- function(n, k, func) {
  x = func(n)
  start_time = Sys.time(); y.RCRoll = RCRoll::rollmin(x, k) ; print(paste("RCRoll:", Sys.time() - start_time))
  start_time = Sys.time(); y.roll = roll::roll_min(x, k) ; print(paste("roll:", Sys.time() - start_time))
  start_time = Sys.time(); y.data.table = data.table::frollmax(x, k) ; print(paste("data.table:", Sys.time() - start_time))
   return(list("RCRoll"=y.RCRoll, "roll"=y.roll, "data.table"=y.data.table))
}

n <- 1E7
k <- 1E3

# Random normal
out1 <- benchmark(n, k, rnorm)
# All equal to 0
out2 <- benchmark(n, k, function(n) {rep(0, n)})
# Ascending
out3 <- benchmark(n, k, function(n) {seq(0, length.out=n)})
# Descending
out4 <- benchmark(n, k, function(n) {seq(0, by=-1, length.out=n)})

Output of the benchmarking code:

[1] "RCRoll: 0.169624805450439"
[1] "roll: 0.153290987014771"
[1] "data.table: 0.0348567962646484"
[1] "RCRoll: 0.0276196002960205"
[1] "roll: 0.0650320053100586"
[1] "data.table: 0.034125804901123"
[1] "RCRoll: 0.0440917015075684"
[1] "roll: 0.0651366710662842"
[1] "data.table: 0.0270349979400635"
[1] "RCRoll: 0.0287351608276367"
[1] "roll: 0.0672793388366699"
[1] "data.table: 3.9090781211853"

data.table::frollmax() is considerably slower for descending sequences.

Note that RCRoll is an unpublished package I wrote based on the late Richard Harter's ascending minimum algorithm before I realised that the roll package seemed to be about as efficient (at least on one core). Note also that I've not compared the results and I've used the rolling min function from roll.

# Output of sessionInfo()

> sessionInfo()
R Under development (unstable) (2023-12-29 r85751)
Platform: x86_64-pc-linux-gnu
Running under: Ubuntu 22.04.3 LTS

Matrix products: default
BLAS:   /usr/local/lib/R/lib/libRblas.so 
LAPACK: /usr/lib/x86_64-linux-gnu/lapack/liblapack.so.3.10.0

locale:
 [1] LC_CTYPE=en_GB.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=en_GB.UTF-8        LC_COLLATE=en_GB.UTF-8    
 [5] LC_MONETARY=en_GB.UTF-8    LC_MESSAGES=en_GB.UTF-8   
 [7] LC_PAPER=en_GB.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_GB.UTF-8 LC_IDENTIFICATION=C       

time zone: Europe/London
tzcode source: system (glibc)

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] data.table_1.14.99 RcppRoll_0.3.0     zoo_1.8-12         roll_1.1.6        
[5] RCRoll_0.1         devtools_2.4.5     usethis_2.2.2     

loaded via a namespace (and not attached):
 [1] miniUI_0.1.1.1     compiler_4.4.0     promises_1.2.1     Rcpp_1.0.12       
 [5] stringr_1.5.1      later_1.3.2        fastmap_1.1.1      lattice_0.20-45   
 [9] mime_0.12          R6_2.5.1           htmlwidgets_1.6.4  profvis_0.3.8     
[13] shiny_1.8.0        rlang_1.1.3        cachem_1.0.8       stringi_1.8.3     
[17] httpuv_1.6.13      fs_1.6.3           RcppParallel_5.1.7 pkgload_1.3.3     
[21] memoise_2.0.1      cli_3.6.2          magrittr_2.0.3     grid_4.4.0        
[25] digest_0.6.34      xtable_1.8-4       remotes_2.4.2.1    lifecycle_1.0.4   
[29] vctrs_0.6.5        glue_1.7.0         urlchecker_1.0.1   sessioninfo_1.2.2 
[33] pkgbuild_1.4.3     purrr_1.0.2        tools_4.4.0        ellipsis_0.3.2    
[37] htmltools_0.5.7   

P.S. @jangorecki This issue was prompted by your nice talk at EdinbR on Friday - I was the person who said I'd follow up after the meeting.