text: ---
  title: "Sorting vs Hashing"
  output: github_document
  editor_options: 
    chunk_output_type: console
  ---
  
  ```{r, include = FALSE}
  knitr::opts_chunk$set(collapse = TRUE, comment = "#> ")
  knitr::opts_chunk$set(fig.width = 10)
  
  # prevent press() noise and autoplot() noise
  knitr::opts_chunk$set(message = FALSE, warning = FALSE)
  ```
  
  Investigates performance of `vec_order()` vs current implementation of `vec_unique()`, which is based on hashing and a dictionary. It might be worth switching to use the sort based approach of `vec_order()`.
  
  ## Setup
  
  ```{r}
  library(vctrs)
  library(rlang)
  library(stringr)
  library(ggplot2)
  library(dplyr)
  ```
  
  ```{r}
  # Generate `size` random words of varying string sizes
  new_dictionary <- function(size, min_length, max_length) {
    lengths <- rlang::seq2(min_length, max_length)
  
    stringi::stri_rand_strings(
      size,
      sample(lengths, size = size, replace = TRUE)
    )
  }
  ```
  
  ```{r}
  # Work around bench_expr bug where vectorized attribute isn't being sliced
  # https://github.com/r-lib/bench/pull/90
  
  filter_bench <- function(.data, ...) {
    out <- dplyr::mutate(.data, rn = row_number()) %>%
      dplyr::filter(...)
    
    # patch up bench_expr
    which <- out$rn
    desc <- attr(.data$expression, "description")
    attr(out$expression, "description") <- desc[which]
    
    out$rn <- NULL
    
    out
  }
  ```
  
  ```{r}
  plot_bench <- function(df, title = waiver()) {
    df %>%
      ggplot(aes(x = n_groups, y = as.numeric(median))) +
      geom_point(aes(color = as.character(expression))) +
      facet_wrap(~ size, labeller = label_both, nrow = 1) +
      scale_x_log10() +
      scale_y_log10() + 
      labs(
        x = "Number of groups (log10)",
        y = "Time (log10 seconds)",
        color = "Type",
        title = title
      )
  }
  ```
  
  ## Compare with `vec_unique_loc()`
  
  It is worth comparing to `vec_unique_loc()`, which is the most bare bones of the uniqueness functions, to test whether or not uniqueness-by-sorting can be faster than uniqueness-by-hashing.
  
  In a branch, I hacked together an implementation of `vec_unique_loc()` based on `vec_order()`. It takes approximately the same amount of time as `vec_order()` itself, so I will just use `vec_order()` as a proxy for the sorting approach.
  
  ## Integers
  
  ### Test 1
  
  - Integers
  - Varying total size (small)
  - Varying group size
  
  ```{r}
  set.seed(123)
  
  size <- 10 ^ (1:4)
  n_groups <- 10 ^ (1:6)
  
  df <- bench::press(
    size = size,
    n_groups = n_groups,
    {
      x <- sample(n_groups, size, replace = TRUE)
      bench::mark(
        vec_order(x), vec_unique_loc(x), 
        iterations = 100, check = FALSE
      )
    }
  )
  ```
  
  Performance is generally the same for small sizes
  
  ```{r, echo=FALSE}
  plot_bench(df, "Integers (small)")
  ```
  
  However, `size = 10000` seems to already show `vec_order()` being faster.
  
  ```{r}
  df[-1] %>%
    filter(size == 10000)
  ```
  
  
  ### Test 2
  
  - Integers
  - Varying total size (large)
  - Varying number of groups
  
  ```{r}
  set.seed(123)
  
  size <- 10 ^ (5:7)
  n_groups <- 10 ^ (1:6)
  
  df <- bench::press(
    size = size,
    n_groups = n_groups,
    {
      x <- sample(n_groups, size, replace = TRUE)
      bench::mark(
        vec_order(x), vec_unique_loc(x), 
        iterations = 20, check = FALSE
      )
    }
  )
  ```
  
  As the total size increases, `vec_order()` starts to do better.
  
  ```{r, echo = FALSE}
  plot_bench(df, "Integers (large)")
  ```
  
  ### Test 3
  
  This benchmark shows how much better `vec_order()` scales for large size and large number of groups. For integers it is always faster, and scales extremely well.
  
  ```{r}
  set.seed(123)
  
  size <- 10 ^ 8
  n_groups <- 10 ^ (1:7)
  
  df <- bench::press(
    size = size,
    n_groups = n_groups,
    {
      x <- sample(n_groups, size, replace = TRUE)
      bench::mark(
        vec_order(x), vec_unique_loc(x), 
        iterations = 20, check = FALSE
      )
    }
  )
  ```
  
  ```{r, echo = FALSE}
  df %>%
    ggplot(aes(x = n_groups, y = as.numeric(median))) +
    geom_point(aes(color = as.character(expression))) +
    geom_line(aes(color = as.character(expression))) +
    scale_x_log10() +
    labs(
      x = "Number of groups (log10)",
      y = "Time (seconds)",
      color = "Type",
      title = "Integers - Size=1e8, Varying n_groups"
    )
  ```
  
  ## Doubles
  
  ### Test 1
  
  - Doubles
  - Varying total size (small)
  - Varying group size
  
  ```{r}
  set.seed(123)
  
  size <- 10 ^ (1:4)
  n_groups <- 10 ^ (1:6)
  
  df <- bench::press(
    size = size,
    n_groups = n_groups,
    {
      x <- sample(n_groups, size, replace = TRUE) + 0
      bench::mark(
        vec_order(x), vec_unique_loc(x), 
        iterations = 100, check = FALSE
      )
    }
  )
  ```
  
  `vec_order()` is generally a bit slower for these smaller sizes, but it scales much better with large sizes and larger number of groups. See the next test.
  
  ```{r, echo=FALSE}
  plot_bench(df, "Doubles (small size)")
  ```
  
  ### Test 2
  
  This benchmark shows how much better `vec_order()` scales for large size and large number of groups. For doubles it is slower up front, but scales much better.
  
  ```{r}
  set.seed(123)
  
  size <- 10 ^ 8
  n_groups <- 10 ^ (1:7)
  
  df <- bench::press(
    size = size,
    n_groups = n_groups,
    {
      x <- sample(n_groups, size, replace = TRUE) + 0
      bench::mark(
        vec_order(x), vec_unique_loc(x), 
        iterations = 20, check = FALSE
      )
    }
  )
  ```
  
  ```{r, echo = FALSE}
  df %>%
    ggplot(aes(x = n_groups, y = as.numeric(median))) +
    geom_point(aes(color = as.character(expression))) +
    geom_line(aes(color = as.character(expression))) +
    scale_x_log10() +
    labs(
      x = "Number of groups (log10)",
      y = "Time (seconds)",
      color = "Type",
      title = "Doubles - Size=1e8, Varying n_groups"
    )
  ```
  
  ## Characters
  
  ### Test 1
  
  Currently string ordering is much slower than `vec_unique_loc()` (especially when most strings are unique) due to all of the allocations that are required + the fact that it does a radix ordering of unique strings and then an integer radix ordering after that.
  
  I am confident that the C level part of `vec_order()` could gain a `sort_character = false` option that would do a much faster counting sort in order-of-first-appearance that utilizes the truelengths in a different way. It wouldn't sort strings at all, so should be very fast. This is what `cgroup()` does in `base::order()`, which is not currently implemented in `vec_order()` because I didn't have a use for it until now. https://github.com/wch/r-source/blob/8d7ac4699fba640d030703fa010b66bf26054cbd/src/main/radixsort.c#L1051
  
  Very large set of strings with 10 groups
  
  - Don't notice much of a difference between the two here, because there aren't many unique strings.
  
  ```{r}
  set.seed(123)
  
  size <- 1e7
  n_groups <- 10
  
  dict <- new_dictionary(n_groups, min_length = 5, max_length = 20)
  x <- sample(dict, size, TRUE)
  
  bench::mark(vec_order(x), vec_unique_loc(x), iterations = 10, check = FALSE)
  ```
  
  Very large set of completely random strings
  
  - Extremely large difference, because `vec_order()` is doing way too much work to actually sort the strings.
  
  ```{r}
  set.seed(123)
  
  n_groups <- 1e7
  
  x <- new_dictionary(n_groups, min_length = 5, max_length = 20)
  
  bench::mark(vec_order(x), vec_unique_loc(x), iterations = 10, check = FALSE)
  ```
  
  ## Multiple columns
  
  ### Test 1
  
  3 integer columns, each with 20 groups. 1e7 total size.
  
  ```{r}
  set.seed(123)
  
  size <- 1e7L
  n_groups <- 20
  n_cols <- 3
  
  cols <- replicate(n_cols, sample(n_groups, size, TRUE), simplify = FALSE)
  names(cols) <- seq_along(cols)
  df <- vctrs::new_data_frame(cols, size)
  
  bench::mark(
    vec_order(df), 
    vec_unique_loc(df), 
    iterations = 10,
    check = FALSE
  )
  ```
  
  ### Test 2
  
  Same as before but with character columns. We do worse here because as mentioned before, we do too much work in `vec_order()` right now with character vectors.
  
  ```{r}
  set.seed(123)
  
  size <- 1e7L
  n_groups <- 20
  n_cols <- 3
  
  cols <- replicate(
    n_cols, 
    {
      dict <- new_dictionary(n_groups, 5, 20)
      sample(dict, size, TRUE)
    }, 
    simplify = FALSE
  )
  
  names(cols) <- seq_along(cols)
  df <- vctrs::new_data_frame(cols, size)
  
  bench::mark(
    vec_order(df), 
    vec_unique_loc(df), 
    iterations = 5,
    check = FALSE
  )
  ```
  
  ### Test 3
  
  20 integer columns, each with 2 groups. 1e7 total size.
  
  ```{r}
  set.seed(123)
  
  size <- 1e7L
  n_groups <- 2
  n_cols <- 20
  
  cols <- replicate(n_cols, sample(n_groups, size, TRUE), simplify = FALSE)
  names(cols) <- seq_along(cols)
  df <- vctrs::new_data_frame(cols, size)
  
  bench::mark(
    vec_order(df), 
    vec_unique_loc(df), 
    iterations = 5,
    check = FALSE
  )
  ```
  