Performance regression in future/globals when finding globals in a list of data frames

[DavisVaughan]

CC @HenrikBengtsson

We've gotten a few reports of performance issues appearing in furrr over the years (#267, #268).

Nothing has changed in furrr, so I suspected future or globals has had changes.

Here's a furrr example of a suspected regression:

With CRAN future

library(future)
library(furrr)

# 50,000 instances of `mtcars`
xs <- rep(list(mtcars), 50000)

# Two workers
plan(multisession, workers = 2)

# Should send 25,000 to each worker

# CRAN future 1.69.0
system.time({
  future_map(xs, identity)
})
#>    user  system elapsed 
#>   5.420   0.336   5.985

# Old future 1.33.2
system.time({
  future_map(xs, identity)
})
#>    user  system elapsed 
#>   2.153   0.237   2.739

Yes there's a lot of data shuffling going on here, but users do this quite a bit anyways (despite our warnings against it) and it's generally much faster than this.

It also gets much worse if you add tibbles into the mix.

library(future)
library(furrr)
library(tibble)

# 50,000 instances of `mtcars` but as a tibble
xs <- rep(list(as_tibble(mtcars)), 50000)

# Two workers
plan(multisession, workers = 2)

# Should send 25,000 to each worker

# CRAN future 1.69.0
system.time({
  future_map(xs, identity)
})
#>    user  system elapsed 
#>  10.451   0.523  11.175

# Old future 1.33.2
system.time({
  future_map(xs, identity)
})
#>    user  system elapsed 
#>   3.761   0.302   4.297

---

Ironically, if we naively try and strip out furrr, then CRAN future is actually faster.

So this is probably going to require some investigation to see if we can create a pure future call that shows the slowdown

library(future)

x1 <- rep(list(mtcars), 25000)
x2 <- rep(list(mtcars), 25000)

# Two workers
plan(multisession, workers = 2)

# CRAN future 1.69.0
system.time({
  f1 <- future(
    lapply(x, FUN = identity),
    globals = as.FutureGlobals(list(x = x1))
  )
  f2 <- future(
    lapply(x, FUN = identity),
    globals = as.FutureGlobals(list(x = x2))
  )
  value(list(f1, f2))
})
#>    user  system elapsed 
#>   0.547   0.216   0.999

# Old future 1.33.2
system.time({
  f1 <- future(
    lapply(x, FUN = identity),
    globals = as.FutureGlobals(list(x = x1))
  )
  f2 <- future(
    lapply(x, FUN = identity),
    globals = as.FutureGlobals(list(x = x2))
  )
  value(list(f1, f2))
})
#>    user  system elapsed 
#>   2.485   0.245   3.009

[DavisVaughan]

Even if I try and "exactly" reproduce most of the future::future() call that furrr sets up, then a raw future::future() call is still fast, and is faster in CRAN future.

I'm now convinced that the difference is in the globals somehow, because that is the only thing that isn't exactly the same between this example and furrr itself. I'll investigate that next.

library(future)

x1 <- rep(list(mtcars), 25000)
x2 <- rep(list(mtcars), 25000)

# Two workers
plan(multisession, workers = 2)

# CRAN future 1.69.0
system.time({
  f1 <- future(
    quote(lapply(x, FUN = identity)),
    substitute = FALSE,
    envir = globalenv(),
    stdout = structure(TRUE, drop = TRUE),
    conditions = structure("condition", drop = TRUE),
    globals = as.FutureGlobals(list(x = x1)),
    packages = "purrr",
    seed = FALSE
  )
  f2 <- future(
    quote(lapply(x, FUN = identity)),
    substitute = FALSE,
    envir = globalenv(),
    stdout = structure(TRUE, drop = TRUE),
    conditions = structure("condition", drop = TRUE),
    globals = as.FutureGlobals(list(x = x2)),
    packages = "purrr",
    seed = FALSE
  )
  out <- value(list(f1, f2))
})
#>    user  system elapsed 
#>   0.571   0.235   1.068

# Old future 1.33.2
system.time({
  f1 <- future(
    quote(lapply(x, FUN = identity)),
    substitute = FALSE,
    envir = globalenv(),
    stdout = structure(TRUE, drop = TRUE),
    conditions = structure("condition", drop = TRUE),
    globals = as.FutureGlobals(list(x = x1)),
    packages = "purrr",
    seed = FALSE
  )
  f2 <- future(
    quote(lapply(x, FUN = identity)),
    substitute = FALSE,
    envir = globalenv(),
    stdout = structure(TRUE, drop = TRUE),
    conditions = structure("condition", drop = TRUE),
    globals = as.FutureGlobals(list(x = x2)),
    packages = "purrr",
    seed = FALSE
  )
  out <- value(list(f1, f2))
})
#>    user  system elapsed 
#>   2.696   0.292   3.292

[DavisVaughan]

Ok here's something.

Looks like with CRAN future and CRAN globals, globals collection is very expensive.

Note that we do collect globals on each xs[[i]] element, and I think future.apply does too?

If you downgrade to future 1.33.2, then globals collection gets much faster, even with globals 0.18.0 still being installed, so that's interesting. Note that the globals = FALSE is roughly the same across future versions, so that's helped me isolate the issue to globals = TRUE.

library(future)
library(furrr)

# 50,000 instances of `mtcars`, split across 2 workers
xs <- rep(list(mtcars), 50000)

# CRAN future 1.69.0 / CRAN globals 0.18.0 / globals = TRUE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = TRUE))
})
#>    user  system elapsed 
#>   5.282   0.346   5.893
plan(sequential)

# CRAN future 1.33.2 / CRAN globals 0.18.0 / globals = TRUE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = TRUE))
})
#>    user  system elapsed 
#>   2.059   0.260   2.584
plan(sequential)



# CRAN future 1.69.0 / CRAN globals 0.18.0 / globals = FALSE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = FALSE))
})
#>    user  system elapsed 
#>   0.602   0.205   1.081
plan(sequential)

# CRAN future 1.33.2 / CRAN globals 0.18.0 / globals = FALSE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = FALSE))
})
#>    user  system elapsed 
#>   0.465   0.217   0.947
plan(sequential)

[DavisVaughan]

Okay yea with pak::pak("futureverse/furrr@test/do-nothing-future"), which is a version of furrr that has future::future() calls that effectively "do nothing", we can really see the difference:

# pak::pak("futureverse/furrr@test/do-nothing-future")

library(future)
library(furrr)

# 50,000 instances of `mtcars`, split across 2 workers
xs <- rep(list(mtcars), 50000)

# CRAN future 1.69.0 / CRAN globals 0.18.0 / globals = TRUE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = TRUE))
})
#>    user  system elapsed 
#>   4.684   0.128   4.842
plan(sequential)

# CRAN future 1.33.2 / CRAN globals 0.18.0 / globals = TRUE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = TRUE))
})
#>    user  system elapsed 
#>   1.560   0.045   1.659
plan(sequential)



# CRAN future 1.69.0 / CRAN globals 0.18.0 / globals = FALSE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = FALSE))
})
#>    user  system elapsed 
#>   0.008   0.001   0.045
plan(sequential)

# CRAN future 1.33.2 / CRAN globals 0.18.0 / globals = FALSE
plan(multisession, workers = 2)
system.time({
  future_map(xs, identity, .options = furrr_options(globals = FALSE))
})
#>    user  system elapsed 
#>   0.041   0.001   0.096
plan(sequential)

So now let's focus on what has changed in globals collection, and what's taking so long on the R side as we collect globals over all of the xs.

[DavisVaughan]

Okay @HenrikBengtsson, here's my bisected minimal reprex.

With future 1.40.0:

# devtools::install_version("future", "1.40.0")

library(future)

xs <- rep(list(mtcars), 50000)

system.time({
  gp <- future::getGlobalsAndPackages(xs)
})
#>    user  system elapsed 
#>   1.616   0.056   1.702

With future 1.49.0, the version right after that:

# devtools::install_version("future", "1.49.0")

library(future)

xs <- rep(list(mtcars), 50000)

system.time({
  gp <- future::getGlobalsAndPackages(xs)
})
#>    user  system elapsed 
#>   4.865   0.139   5.022

Here's profvis with 1.40.0

library(future)

xs <- rep(list(mtcars), 50000)

profvis::profvis({
  gp <- future::getGlobalsAndPackages(xs)
})

future 1.40.0, high level

future 1.49.0, high level

future 1.40.0, detailed

future 1.49.0, detailed

Here's my analysis:

In both future 1.40.0 and 1.49.0, with this particular example (which is a list of many data frames), the slowest part of globals collection is this globals:::.length() function.

But in future 1.49.0, it seems like you started calling this many more times. IIUC, this corresponds to a switch to a DFS global collection strategy.

But it actually seems like you use both an "ordered" and "dfs" strategy?
futureverse/future@4292c31

And it seems like both are still being used in CRAN future
https://github.com/futureverse/future/blob/57e8a9ddba3422efd2bfd23b13bb24e7e4d5f264/R/utils-options.R#L463

So that may explain why we see both findGlobals() and globalsOf() calls in future 1.49.0 above, both of which use .length(), so we are calling it a lot more!

If we go over here and look at .length():

https://github.com/futureverse/globals/blob/00bbb3402a03ee74b08e1e163fdb6a567312cacb/R/utils.R#L186-L219

The problem is that we have many data frames coming through here, which all must go through the more expensive path of checking getS3method(). And if you have a tibble, then that has even more classes that you must loop through! So that explains why tibble is weirdly more expensive.

I think you could greatly simplify this to just

.length <- function(x) {
  if (is.object(x)) {
    length(unclass(x))
  } else {
    length(x)
  }
}

In any recent version of R (anything with ALTREP support), unclass() doesn't create a copy. It creates an ALTREP wrapper around the object, where the ALTREP wrapper R object is allowed to have different attributes than the underlying object (like dropping the class attribute) without actually modifying the underlying object. It creates a copy if an actual modification is made, but you don't need that here!

x <- structure(as.list(1:500000), class = "foolist")

profmem::profmem(unclass(x))
#> Rprofmem memory profiling of:
#> unclass(x)
#> 
#> Memory allocations:
#>       what bytes calls
#> total        0

bench::mark(unclass(x))
#> # A tibble: 1 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 unclass(x)        0   82.1ns 10691125.        0B        0

# See the `"wrapper"`? That's the free ALTREP wrapper
.Internal(inspect(unclass(x)))
#> @12f9e09f0 19 VECSXP g0c0 []  wrapper [srt=-2147483648,no_na=0]
#>   @120318000 19 VECSXP g1c7 [MARK,REF(10004)] (len=500000, tl=0)
#>     @12f850b70 13 INTSXP g1c1 [MARK,REF(65535)] (len=1, tl=0) 1
#>     @12f850b38 13 INTSXP g1c1 [MARK,REF(65535)] (len=1, tl=0) 2
#>     @12f850b00 13 INTSXP g1c1 [MARK,REF(65535)] (len=1, tl=0) 3
#>     @12f850ac8 13 INTSXP g1c1 [MARK,REF(65535)] (len=1, tl=0) 4
#>     @12f850a90 13 INTSXP g1c1 [MARK,REF(65535)] (len=1, tl=0) 5
#>     ...

So I think you should have no fear of an unclass() being expensive here.

And now with CRAN future and a patched version of globals with this fix:

library(future)

xs <- rep(list(mtcars), 50000)

system.time({
  gp <- future::getGlobalsAndPackages(xs)
})
#>    user  system elapsed 
#>   2.033   0.026   2.078

That looks pretty good!

And if we rerun the original examples in the opening comment, it also looks good now:

(these are even faster than future 1.33.2 actually)

library(future)
library(furrr)

# 50,000 instances of `mtcars`
xs <- rep(list(mtcars), 50000)

# Two workers
plan(multisession, workers = 2)

# Should send 25,000 to each worker

# CRAN future 1.69.0, and patched globals
system.time({
  future_map(xs, identity)
})
#>    user  system elapsed 
#>   2.159   0.030   2.258

library(future)
library(furrr)
library(tibble)

# 50,000 instances of `mtcars` but as a tibble
xs <- rep(list(as_tibble(mtcars)), 50000)

# Two workers
plan(multisession, workers = 2)

# Should send 25,000 to each worker

# CRAN future 1.69.0, and patched globals
system.time({
  future_map(xs, identity)
})
#>    user  system elapsed 
#>   2.170   0.029   2.247

This fix should also help future.apply, because it suffers from the exact same issue because you also call getGlobalsAndPackages() on each chunk
https://github.com/futureverse/future.apply/blob/0e15b00784aa29c56c3c175c41148b89bca7bde6/R/future_xapply.R#L163C17-L163C38