Improve performance of `case_when()` and `case_match()` by DavisVaughan · Pull Request #6711 · tidyverse/dplyr

DavisVaughan · 2023-02-10T17:29:53Z

Three improvements to make these decently fast again:

Minor: Calls to current_env() and caller_env() are now lazy (only evaluated when needed) (needs Can as_function() avoid materializing call ? r-lib/rlang#1558)
Major: We no longer call as_label() to turn the expressions into labels which were being used as informative names that showed up in error messages. This stinks, but as_label() is just too slow to be used eagerly like this. We can revisit this again in the future if we add a lazy ALTREP character vector which could materialize the as_label() calls on demand (i.e. at error time). In the meantime, we now use positional names that also include LHS/RHS information, like ..2 (RHS), which ends up being decent.
Major: I was previously wrapping the evaluation of the lhs/rhs of the formulas in with_case_errors() to give an informative indexed error about which formula failed to evaluate. This got slow as you increased the number of expressions in case_when() (2 * N expressions = number of with_case_errors() calls) because it uses try_fetch(), which is built on tryCatch(), which is in R not C (probably a good Luke project!). I've changed it up so 1 call to with_case_errors() now wraps the entire evaluation loop, and we track some index information to use in the error if one occurs.

Sadly the private option added in rlang (r-lib/rlang@33db700) wasn't enough to make as_label() fast enough to be used eagerly like this. But the infix_overflows() call there is a big part of the performance degradation we see in my benchmarks below.

When I work on #6678 that will end up also knocking off another 50us or so from switching away from vec_assert() in vec_case_when() and if_else().

After that, any other improvements will come from moving vec_case_when() to C in vctrs.

Right now we are in the 2-4x slower range. After #6678 I expect to be 2x slower most of the time. I think we can do a release with that. Then the C implementation in vctrs should fix the rest.

library(dplyr)

# Size 1
x <- 1L

bench::mark(
  one = case_when(x == 1L ~ TRUE), 
  two = case_when(x == 1L ~ TRUE, x == 2L ~ NA),
  three = case_when(x == 1L ~ TRUE, x == 2L ~ NA, TRUE ~ FALSE),
  iterations = 50000,
  check = FALSE
)

# dplyr 1.0.10
#> # A tibble: 3 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 one          56.8µs   74.7µs    12802.     168KB     18.2
#> 2 two          75.5µs   95.4µs    10514.        0B     22.5
#> 3 three        97.4µs  120.2µs     8390.        0B     23.9

# This PR
#> # A tibble: 3 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 one           209µs    278µs     3388.   503.8KB     11.3
#> 2 two           242µs    326µs     2879.     1.3KB     12.2
#> 3 three         272µs    350µs     2787.     1.3KB     14.3

# dplyr 1.1.0 (smacked by the infix-overflow `as_label()` performance issue)
# (note that i had to go down to only 5,000 iterations here)
#> # A tibble: 3 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 one          1.67ms   2.12ms      477.    1.01MB     16.6
#> 2 two          3.14ms   3.86ms      261.    3.36KB     18.2
#> 3 three        3.27ms   4.32ms      228.    3.36KB     16.5

library(dplyr)

# Size 1000
x <- 1:1000

bench::mark(
  one = case_when(x < 200 ~ TRUE), 
  two = case_when(x < 200 ~ TRUE, x < 500 ~ NA),
  three = case_when(x < 200 ~ TRUE, x < 500 ~ NA, TRUE ~ FALSE),
  iterations = 50000,
  check = FALSE
)

# dplyr 1.0.10
#> # A tibble: 3 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 one          73.2µs   92.2µs    10873.    60.1KB     17.0
#> 2 two         108.6µs  136.9µs     7383.   100.9KB     17.3
#> 3 three       136.1µs  171.2µs     5914.   130.6KB     18.3

# This PR
#> # A tibble: 3 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 one           222µs    271µs     3720.    44.1KB     14.4
#> 2 two           279µs    334µs     3011.    60.1KB     15.4
#> 3 three         318µs    382µs     2649.      70KB     16.5

# dplyr 1.1.0
#> # A tibble: 3 × 6
#>   expression      min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 one          2.03ms   2.39ms      400.      45KB     15.0
#> 2 two          3.98ms   4.45ms      222.    62.2KB     16.6
#> 3 three         4.1ms   4.64ms      211.      72KB     16.6

DavisVaughan · 2023-02-10T17:59:19Z

-  .size <- vec_size_common(!!!conditions, !!!values, .size = .size, .call = error_call)
+  .size <- vec_size_common(!!!conditions, !!!values, .size = .size)

-  conditions <- vec_recycle_common(!!!conditions, .size = .size, .call = error_call)
-  values <- vec_recycle_common(!!!values, .size = .size, .call = error_call)


These were superfluous

DavisVaughan · 2023-02-10T17:59:52Z

-    dots_env = dots_env,
-    error_call = error_call
-  )
+  env_error_info <- new_environment()


An environment to track information used by with_case_errors()

DavisVaughan · 2023-02-10T18:00:40Z

+      ! Can't recycle `..1 (LHS)` (size 2) to match `..1 (RHS)` (size 3).
    Code
      (expect_error(case_when(c(TRUE, FALSE) ~ 1, c(FALSE, TRUE, FALSE) ~ 2, c(FALSE,
        TRUE, FALSE, NA) ~ 3)))
    Output
      <error/vctrs_error_incompatible_size>
      Error in `case_when()`:
-      ! Can't recycle `c(TRUE, FALSE)` (size 2) to match `c(FALSE, TRUE, FALSE)` (size 3).
+      ! Can't recycle `..1 (LHS)` (size 2) to match `..2 (LHS)` (size 3).


Particularly important to show LHS vs RHS in these errors, otherwise it can be very confusing

hadley · 2023-02-11T15:04:08Z

-    default_env = default_env,
-    dots_env = dots_env,
-    error_call = error_call
+    default_env = caller_env(),


It's interesting that this is expensive enough to care about.

It is super minor honestly, but we've worked hard in vctrs to make env evaluation lazy and it seems a waste to throw that away

hadley · 2023-02-11T15:05:17Z

 }

-with_case_errors <- function(expr, side, i, error_call) {
+with_case_errors <- function(expr, error_call, env_error_info) {


Are you taking advantage of try_fetch() features here? Is it worth changing to a bare withCallingHandlers()?

Good point, withCallingHandlers() is as fast as it gets. Probably still better to wrap from the outside though.

Is it still worth having this as a separate function? It's kind of hard to follow now that the lexical envs are intertwined.

hadley · 2023-02-11T15:06:04Z

+    names(lhs) <- paste0("..", seq_args, " (LHS)")
+    names(rhs) <- paste0("..", seq_args, " (RHS)")


Given that people don't seem to general understand LHS/RHS might be better to just use left/right.

lionel- · 2023-02-13T14:58:15Z

 }

-with_case_errors <- function(expr, side, i, error_call) {
+with_case_errors <- function(expr, error_call, env_error_info) {


Good point, withCallingHandlers() is as fast as it gets. Probably still better to wrap from the outside though.

lionel- · 2023-02-13T15:00:33Z

 }

-with_case_errors <- function(expr, side, i, error_call) {
+with_case_errors <- function(expr, error_call, env_error_info) {


Is it still worth having this as a separate function? It's kind of hard to follow now that the lexical envs are intertwined.

Rather than wrapping `eval_tidy()`, we now wrap the whole for loop, assuming that the only errors that can happen in the loop are related to expression evaluation. This avoids repeated calls to `try_fetch()`, which can be expensive due to `tryCatch()` being implemented in R rather than C. This is particularly important when there are many conditions, as the repeated `try_fetch()` calls have a noticeable performance impact

DavisVaughan marked this pull request as ready for review February 10, 2023 17:54

DavisVaughan requested a review from lionel- February 10, 2023 17:58

DavisVaughan commented Feb 10, 2023

View reviewed changes

DavisVaughan requested a review from hadley February 10, 2023 18:00

DavisVaughan mentioned this pull request Feb 10, 2023

Use check_logical() rather than vec_assert() in if_else() and vec_case_when() #6715

Merged

hadley approved these changes Feb 11, 2023

View reviewed changes

lionel- approved these changes Feb 13, 2023

View reviewed changes

DavisVaughan added 8 commits February 13, 2023 15:08

Allow environments to be lazy if possible

e7bc40e

Use positional naming in case_when()

e51045e

Minor style cleanup

391891a

NEWS bullet

cf5cc74

NEWS bullet tweak

c93e6d8

Inline with_case_errors() and switch to withCallingHandlers()

a592903

Use left and right

1d18013

DavisVaughan force-pushed the feature/positional-names-case-when branch from 6b92b11 to 1d18013 Compare February 13, 2023 20:09

DavisVaughan merged commit 688bcde into tidyverse:main Feb 13, 2023

DavisVaughan deleted the feature/positional-names-case-when branch February 13, 2023 20:24

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve performance of `case_when()` and `case_match()`#6711

Improve performance of `case_when()` and `case_match()`#6711
DavisVaughan merged 8 commits intotidyverse:mainfrom
DavisVaughan:feature/positional-names-case-when

DavisVaughan commented Feb 10, 2023 •

edited

Loading

Uh oh!

DavisVaughan Feb 10, 2023

Uh oh!

DavisVaughan Feb 10, 2023

Uh oh!

DavisVaughan Feb 10, 2023

Uh oh!

Uh oh!

hadley Feb 11, 2023

Uh oh!

DavisVaughan Feb 13, 2023

Uh oh!

hadley Feb 11, 2023

Uh oh!

lionel- Feb 13, 2023

Uh oh!

lionel- Feb 13, 2023

Uh oh!

hadley Feb 11, 2023

Uh oh!

lionel- Feb 13, 2023

Uh oh!

lionel- Feb 13, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

		names(lhs) <- paste0("..", seq_args, " (LHS)")
		names(rhs) <- paste0("..", seq_args, " (RHS)")

Conversation

DavisVaughan commented Feb 10, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

DavisVaughan commented Feb 10, 2023 •

edited

Loading