--- title: "High Performance Benchmarks" author: "Joseph Wood" date: "2026-10-16" output: prettydoc::html_pretty: theme: architect toc: true number_sections: false vignette: > %\VignetteIndexEntry{High Performance Benchmarks} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- This document serves as an overview for measuring the performance of `RcppAlgos` against other tools for generating combinations, permutations, and partitions. This stackoverflow post: [How to generate permutations or combinations of object in R?]() has some benchmarks. You will note that the examples in that post are relatively small. The benchmarks below will focus on larger examples where performance really matters and for this reason we only consider the packages [arrangements](), [partitions](), and [RcppAlgos](). ## Setup Information For the benchmarks below, we used a `2025 Macbook Air Apple M4 24 GB` machine. ``` r library(RcppAlgos) library(partitions) library(arrangements) #> #> Attaching package: 'arrangements' #> The following object is masked from 'package:partitions': #> #> compositions library(microbenchmark) options(digits = 4) options(width = 90) pertinent_output <- capture.output(sessionInfo()) cat(paste(pertinent_output[1:3], collapse = "\n")) #> R version 4.6.1 (2026-06-24) #> Platform: aarch64-apple-darwin23 #> Running under: macOS Sequoia 15.7.4 pkgs <- c("RcppAlgos", "arrangements", "partitions", "microbenchmark") sapply(pkgs, packageVersion, simplify = FALSE) #> $RcppAlgos #> [1] '2.10.2' #> #> $arrangements #> [1] '1.1.10' #> #> $partitions #> [1] '1.10.9' #> #> $microbenchmark #> [1] '1.5.0' numThreads <- min(as.integer(RcppAlgos::stdThreadMax() / 2), 6) numThreads #> [1] 5 ``` ## Combinations ### Combinations - Distinct ``` r set.seed(13) v1 <- sort(sample(100, 30)) m <- 21 t1 <- comboGeneral(v1, m, Parallel = T) t2 <- combinations(v1, m) stopifnot(identical(t1, t2)) dim(t1) #> [1] 14307150 21 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = comboGeneral(v1, m, nThreads = numThreads), cbRcppAlgosSer = comboGeneral(v1, m), cbArrangements = combinations(v1, m), times = 15, unit = "relative") #> Warning in microbenchmark(cbRcppAlgosPar = comboGeneral(v1, m, nThreads = numThreads), : #> less accurate nanosecond times to avoid potential integer overflows #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 15 #> cbRcppAlgosSer 3.216 3.051 2.997 3.001 2.988 2.728 15 #> cbArrangements 2.497 2.378 2.347 2.338 2.331 2.246 15 ``` ### Combinations - Repetition ``` r v2 <- v1[1:10] m <- 20 t1 <- comboGeneral(v2, m, repetition = TRUE, nThreads = numThreads) t2 <- combinations(v2, m, replace = TRUE) stopifnot(identical(t1, t2)) dim(t1) #> [1] 10015005 20 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = comboGeneral(v2, m, TRUE, nThreads = numThreads), cbRcppAlgosSer = comboGeneral(v2, m, TRUE), cbArrangements = combinations(v2, m, replace = TRUE), times = 15, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 15 #> cbRcppAlgosSer 3.085 2.998 2.884 2.874 2.809 2.607 15 #> cbArrangements 2.078 2.117 2.036 2.036 1.999 1.838 15 ``` ### Combinations - Multisets ``` r myFreqs <- c(2, 4, 4, 5, 3, 2, 2, 2, 3, 4, 1, 4, 2, 5) v3 <- as.integer(c(1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610)) t1 <- comboGeneral(v3, 20, freqs = myFreqs, nThreads = numThreads) t2 <- combinations(freq = myFreqs, k = 20, x = v3) stopifnot(identical(t1, t2)) dim(t1) #> [1] 14594082 20 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = comboGeneral(v3, 20, freqs = myFreqs, nThreads = numThreads), cbRcppAlgosSer = comboGeneral(v3, 20, freqs = myFreqs), cbArrangements = combinations(freq = myFreqs, k = 20, x = v3), times = 10, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 10 #> cbRcppAlgosSer 3.276 3.191 3.103 3.166 2.977 2.918 10 #> cbArrangements 5.392 5.322 5.176 5.285 4.973 4.899 10 ``` ## Permutations ### Permutations - Distinct ``` r v4 <- as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59)) t1 <- permuteGeneral(v4, 6, nThreads = numThreads) t2 <- permutations(v4, 6) stopifnot(identical(t1, t2)) dim(t1) #> [1] 8910720 6 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = permuteGeneral(v4, 6, nThreads = numThreads), cbRcppAlgosSer = permuteGeneral(v4, 6), cbArrangements = permutations(v4, 6), times = 15, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 15 #> cbRcppAlgosSer 1.516 1.491 1.377 1.460 1.386 1.339 15 #> cbArrangements 2.376 2.357 2.233 2.312 2.361 1.941 15 ## Indexing permutation example with the partitions package t1 <- permuteGeneral(11, nThreads = 4) t2 <- permutations(11) t3 <- perms(11) dim(t1) #> [1] 39916800 11 stopifnot(identical(t1, t2), identical(t1, t(as.matrix(t3)))) rm(t1, t2, t3) invisible(gc()) microbenchmark(cbRcppAlgosPar = permuteGeneral(11, nThreads = 4), cbRcppAlgosSer = permuteGeneral(11), cbArrangements = permutations(11), cbPartitions = perms(11), times = 5, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 5 #> cbRcppAlgosSer 2.334 2.523 2.565 2.593 2.585 2.777 5 #> cbArrangements 4.059 3.925 4.084 4.017 4.192 4.225 5 #> cbPartitions 7.874 7.751 8.370 8.504 8.683 9.009 5 ``` ### Permutations - Repetition ``` r v5 <- v3[1:5] t1 <- permuteGeneral(v5, 10, repetition = TRUE, nThreads = numThreads) t2 <- permutations(v5, 10, replace = TRUE) stopifnot(identical(t1, t2)) dim(t1) #> [1] 9765625 10 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = permuteGeneral(v5, 10, TRUE, nThreads = numThreads), cbRcppAlgosSer = permuteGeneral(v5, 10, TRUE), cbArrangements = permutations(x = v5, k = 10, replace = TRUE), times = 10, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.0000 10 #> cbRcppAlgosSer 2.523 2.527 2.065 2.489 2.480 0.8486 10 #> cbArrangements 2.531 2.521 2.227 2.495 2.493 1.4915 10 ``` ### Permutations - Multisets ``` r v6 <- sort(runif(12)) t1 <- permuteGeneral(v6, 7, freqs = rep(1:3, 4), nThreads = numThreads) t2 <- permutations(freq = rep(1:3, 4), k = 7, x = v6) stopifnot(identical(t1, t2)) dim(t1) #> [1] 19520760 7 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = permuteGeneral(v6, 7, freqs = rep(1:3, 4), nThreads = numThreads), cbRcppAlgosSer = permuteGeneral(v6, 7, freqs = rep(1:3, 4)), cbArrangements = permutations(freq = rep(1:3, 4), k = 7, x = v6), times = 10, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 10 #> cbRcppAlgosSer 3.712 3.711 3.250 3.610 2.559 2.648 10 #> cbArrangements 3.902 3.892 3.516 3.851 2.988 2.880 10 ``` ## Partitions ### Partitions - Distinct #### All Distinct Partitions ``` r t1 <- comboGeneral(0:140, freqs=c(140, rep(1, 140)), constraintFun = "sum", comparisonFun = "==", limitConstraints = 140) t2 <- partitions(140, distinct = TRUE) t3 <- diffparts(140) # Each package has different output formats... we only examine dimensions # and that each result is a partition of 140 stopifnot(identical(dim(t1), dim(t2)), identical(dim(t1), dim(t(t3))), all(rowSums(t1) == 140), all(rowSums(t2) == 140), all(colSums(t3) == 140)) dim(t1) #> [1] 9617150 16 rm(t1, t2, t3) invisible(gc()) microbenchmark(cbRcppAlgosPar = partitionsGeneral(0:140, freqs=c(140, rep(1, 140)), nThreads = numThreads), cbRcppAlgosSer = partitionsGeneral(0:140, freqs=c(140, rep(1, 140))), cbArrangements = partitions(140, distinct = TRUE), cbPartitions = diffparts(140), times = 10, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.00 1.000 1.000 1.000 10 #> cbRcppAlgosSer 2.572 2.504 2.33 2.237 2.258 2.188 10 #> cbArrangements 2.374 2.304 2.15 2.025 2.109 2.035 10 #> cbPartitions 13.645 13.541 12.27 11.805 11.711 11.422 10 ``` #### Restricted Distinct Partitions ``` r t1 <- comboGeneral(160, 10, constraintFun = "sum", comparisonFun = "==", limitConstraints = 160) t2 <- partitions(160, 10, distinct = TRUE) stopifnot(identical(t1, t2)) dim(t1) #> [1] 8942920 10 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = partitionsGeneral(160, 10, nThreads = numThreads), cbRcppAlgosSer = partitionsGeneral(160, 10), cbArrangements = partitions(160, 10, distinct = TRUE), times = 10, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 10 #> cbRcppAlgosSer 3.133 3.121 3.180 3.053 3.461 3.271 10 #> cbArrangements 3.883 3.855 3.854 3.783 3.738 3.932 10 ``` ### Partitions - Repetition #### All Partitions ``` r t1 <- comboGeneral(0:65, repetition = TRUE, constraintFun = "sum", comparisonFun = "==", limitConstraints = 65) t2 <- partitions(65) t3 <- parts(65) # Each package has different output formats... we only examine dimensions # and that each result is a partition of 65 stopifnot(identical(dim(t1), dim(t2)), identical(dim(t1), dim(t(t3))), all(rowSums(t1) == 65), all(rowSums(t2) == 65), all(colSums(t3) == 65)) dim(t1) #> [1] 2012558 65 rm(t1, t2, t3) invisible(gc()) microbenchmark(cbRcppAlgosPar = partitionsGeneral(0:65, repetition = TRUE, nThreads = numThreads), cbRcppAlgosSer = partitionsGeneral(0:65, repetition = TRUE), cbArrangements = partitions(65), cbPartitions = parts(65), times = 20, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 20 #> cbRcppAlgosSer 2.840 2.791 2.349 2.668 2.392 1.753 20 #> cbArrangements 2.878 2.853 2.326 2.713 2.437 1.413 20 #> cbPartitions 8.431 8.509 6.849 8.307 6.939 4.175 20 ``` #### Restricted Partitions ``` r t1 <- comboGeneral(100, 15, TRUE, constraintFun = "sum", comparisonFun = "==", limitConstraints = 100) t2 <- partitions(100, 15) stopifnot(identical(t1, t2)) dim(t1) #> [1] 9921212 15 rm(t1, t2) # This takes a really long time... not because of restrictedparts, # but because apply is not that fast. This transformation is # needed for proper comparisons. As a result, we will compare # a smaller example # t3 <- t(apply(as.matrix(restrictedparts(100, 15, include.zero = F)), 2, sort)) t3 <- t(apply(as.matrix(restrictedparts(50, 15, include.zero = F)), 2, sort)) stopifnot(identical(partitions(50, 15), t3)) rm(t3) invisible(gc()) microbenchmark(cbRcppAlgosPar = partitionsGeneral(100, 15, TRUE, nThreads = numThreads), cbRcppAlgosSer = partitionsGeneral(100, 15, TRUE), cbArrangements = partitions(100, 15), cbPartitions = restrictedparts(100, 15, include.zero = FALSE), times = 10, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 10 #> cbRcppAlgosSer 3.394 3.381 3.069 3.141 2.927 2.728 10 #> cbArrangements 3.546 3.491 3.240 3.424 3.035 2.894 10 #> cbPartitions 14.524 14.494 13.038 13.505 12.039 11.504 10 ``` ### Partitions - Multisets Currently, `RcppAlgos` is the only package capable of efficiently generating partitions of multisets. Therefore, we will only time `RcppAlgos` and use this as a reference for future improvements. ``` r t1 <- comboGeneral(120, 10, freqs = rep(1:8, 15), constraintFun = "sum", comparisonFun = "==", limitConstraints = 120) dim(t1) #> [1] 7340225 10 stopifnot(all(rowSums(t1) == 120)) microbenchmark(cbRcppAlgos = partitionsGeneral(120, 10, freqs = rep(1:8, 15)), times = 10) #> Unit: milliseconds #> expr min lq mean median uq max neval #> cbRcppAlgos 88.95 89.59 92.99 89.94 90.19 115.8 10 ``` ## Compositions ### Compositions - Repetition #### All Compositions (Small case) ``` r t1 <- compositionsGeneral(0:15, repetition = TRUE) t2 <- arrangements::compositions(15) t3 <- partitions::compositions(15) # Each package has different output formats... we only examine dimensions # and that each result is a partition of 15 stopifnot(identical(dim(t1), dim(t2)), identical(dim(t1), dim(t(t3))), all(rowSums(t1) == 15), all(rowSums(t2) == 15), all(colSums(t3) == 15)) dim(t1) #> [1] 16384 15 rm(t1, t2, t3) invisible(gc()) microbenchmark(cbRcppAlgosSer = compositionsGeneral(0:15, repetition = TRUE), cbArrangements = arrangements::compositions(15), cbPartitions = partitions::compositions(15), times = 20, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosSer 1.055 1.039 1.04 1.033 1.043 1.08 20 #> cbArrangements 1.000 1.000 1.00 1.000 1.000 1.00 20 #> cbPartitions 115.957 122.639 149.17 146.644 173.131 182.23 20 ``` For the next two examples, we will exclude the `partitions` package for efficiency reasons. #### All Compositions (Larger case) ``` r t1 <- compositionsGeneral(0:23, repetition = TRUE) t2 <- arrangements::compositions(23) # Each package has different output formats... we only examine dimensions # and that each result is a partition of 23 stopifnot(identical(dim(t1), dim(t2)), all(rowSums(t1) == 23), all(rowSums(t2) == 23)) dim(t1) #> [1] 4194304 23 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = compositionsGeneral(0:23, repetition = TRUE, nThreads = numThreads), cbRcppAlgosSer = compositionsGeneral(0:23, repetition = TRUE), cbArrangements = arrangements::compositions(23), times = 20, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 20 #> cbRcppAlgosSer 3.808 3.788 3.783 3.789 3.809 3.600 20 #> cbArrangements 3.700 3.683 3.665 3.671 3.679 3.483 20 ``` #### Compositions of Specific Length ``` r t1 <- compositionsGeneral(30, 10, repetition = TRUE) t2 <- arrangements::compositions(30, 10) stopifnot(identical(t1, t2), all(rowSums(t1) == 30)) dim(t1) #> [1] 10015005 10 rm(t1, t2) invisible(gc()) microbenchmark(cbRcppAlgosPar = compositionsGeneral(30, 10, repetition = TRUE, nThreads = numThreads), cbRcppAlgosSer = compositionsGeneral(30, 10, repetition = TRUE), cbArrangements = arrangements::compositions(30, 10), times = 20, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgosPar 1.000 1.000 1.000 1.000 1.000 1.000 20 #> cbRcppAlgosSer 2.979 2.891 2.670 2.824 2.649 1.533 20 #> cbArrangements 3.316 3.152 2.913 3.081 2.888 1.648 20 ``` ### Specialized Composition Benchmarks Similar to partitions of multisets, several composition variants supported in `RcppAlgos` (e.g., distinct parts, capped cases, etc.) are not currently available in other R packages or combinatorics libraries. In such cases, benchmarks will only report timings for `RcppAlgos`, which can serve as a reference point for future implementations and improvements. #### Compositions with Specific `target` ``` r t1 <- compositionsGeneral(10, 10, repetition = TRUE, target = 30) dim(t1) #> [1] 9091270 10 stopifnot(all(rowSums(t1) == 30)) microbenchmark( cbRcppAlgosSer = compositionsGeneral(10, 10, repetition = TRUE, target = 30), cbRcppAlgosPar = compositionsGeneral(10, 10, repetition = TRUE, target = 30, nThreads = numThreads), times = 10, check = "identical" ) #> Unit: milliseconds #> expr min lq mean median uq max neval #> cbRcppAlgosSer 57.30 57.82 59.90 59.30 62.16 62.90 10 #> cbRcppAlgosPar 17.51 18.48 23.01 22.54 23.53 40.02 10 ``` #### Compositions with Distinct Parts ``` r t1 <- compositionsGeneral(50, 8) dim(t1) #> [1] 4677120 8 stopifnot(all(rowSums(t1) == 50)) microbenchmark( cbRcppAlgosSer = compositionsGeneral(50, 8), cbRcppAlgosPar = compositionsGeneral(50, 8, nThreads = numThreads), times = 10, check = "identical" ) #> Unit: milliseconds #> expr min lq mean median uq max neval #> cbRcppAlgosSer 217.65 218.3 220.13 218.76 219.15 227.79 10 #> cbRcppAlgosPar 56.01 56.9 60.14 60.02 61.91 67.48 10 ``` #### Compositions with Distinct Parts & Specific `target` ``` r t1 <- compositionsGeneral(30, 7, target = 60) dim(t1) #> [1] 11773440 7 stopifnot(all(rowSums(t1) == 60)) microbenchmark( cbRcppAlgosSer = compositionsGeneral(30, 7, target = 60), cbRcppAlgosPar = compositionsGeneral(30, 7, target = 60, nThreads = numThreads), times = 10, check = "identical" ) #> Unit: milliseconds #> expr min lq mean median uq max neval #> cbRcppAlgosSer 360.50 361.2 363.3 362.5 365.5 367.3 10 #> cbRcppAlgosPar 95.76 98.9 109.4 106.7 119.6 125.8 10 ``` ## Iterators We will show one example from each category to demonstrate the efficiency of the iterators in `RcppAlgos`. The results are similar for the rest of the cases not shown. ### Combinations ``` r pkg_arrangements <- function(n, total) { a <- icombinations(n, as.integer(n / 2)) for (i in 1:total) a$getnext() } pkg_RcppAlgos <- function(n, total) { a <- comboIter(n, as.integer(n / 2)) for (i in 1:total) a@nextIter() } total <- comboCount(18, 9) total #> [1] 48620 microbenchmark(cbRcppAlgos = pkg_RcppAlgos(18, total), cbArrangements = pkg_arrangements(18, total), times = 15, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.00 1.00 1.00 1.00 1.00 1.00 15 #> cbArrangements 20.05 19.03 18.92 18.93 18.61 19.04 15 ``` ### Permutations ``` r pkg_arrangements <- function(n, total) { a <- ipermutations(n) for (i in 1:total) a$getnext() } pkg_RcppAlgos <- function(n, total) { a <- permuteIter(n) for (i in 1:total) a@nextIter() } total <- permuteCount(8) total #> [1] 40320 microbenchmark(cbRcppAlgos = pkg_RcppAlgos(8, total), cbArrangements = pkg_arrangements(8, total), times = 15, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.0 1.00 1.00 1.00 1.00 1.00 15 #> cbArrangements 19.5 19.34 18.16 18.52 18.42 12.84 15 ``` ### Partitions ``` r pkg_partitions <- function(n, total) { a <- firstpart(n) for (i in 1:(total - 1)) a <- nextpart(a) } pkg_arrangements <- function(n, total) { a <- ipartitions(n) for (i in 1:total) a$getnext() } pkg_RcppAlgos <- function(n, total) { a <- partitionsIter(0:n, repetition = TRUE) for (i in 1:total) a@nextIter() } total <- partitionsCount(0:40, repetition = TRUE) total #> [1] 37338 microbenchmark(cbRcppAlgos = pkg_RcppAlgos(40, total), cbArrangements = pkg_arrangements(40, total), cbPartitions = pkg_partitions(40, total), times = 15, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.00 1.0 1.00 1.00 1.00 1.00 15 #> cbArrangements 15.47 15.4 14.89 15.36 15.18 13.93 15 #> cbPartitions 25.30 25.2 24.39 25.17 24.92 21.62 15 ``` ### Compositions ``` r pkg_partitions <- function(n, total) { a <- firstcomposition(n) for (i in 1:(total - 1)) a <- nextcomposition(a, FALSE) } pkg_arrangements <- function(n, total) { a <- icompositions(n) for (i in 1:total) a$getnext() } pkg_RcppAlgos <- function(n, total) { a <- compositionsIter(0:n, repetition = TRUE) for (i in 1:total) a@nextIter() } total <- compositionsCount(0:15, repetition = TRUE) total #> [1] 16384 microbenchmark(cbRcppAlgos = pkg_RcppAlgos(15, total), cbArrangements = pkg_arrangements(15, total), cbPartitions = pkg_partitions(15, total), times = 15, unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.00 1.00 1.00 1.00 1.00 1.00 15 #> cbArrangements 14.33 13.95 13.78 13.91 13.89 12.81 15 #> cbPartitions 48.08 46.71 46.12 46.50 46.65 41.06 15 ```