DT[chr.vec] slower than tibble[chr.vec,] by sub-linear factors

Open
#5,837 7 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Refactor
Clarity
Mostly clear
Activity status
Quiet
Tech stack
r
Domain
data, performance

Research direction

Start with the character-vector lookup entry point shown in the benchmark, N.dt[half.no.match], and reproduce the comparison against data.frame and tibble using the supplied atime code. Profile the data.table path to identify the constant-factor cost, then verify that the benchmark shows faster or comparable timings without changing lookup results.

Written by the indexing model from the issue text.

Description

performance

I recently wrote a blog post which analyzes time complexity of partial matching of [.data.frame (when looking up rows using a character vector, compared to the data frame row names) and compares with alternatives from data.table and tibble: https://tdhock.github.io/blog/2023/df-partial-match/
The important part for these purposes is the second set of figures in the Comparison section, which shows that tibble is actually faster than data.table by constant factors. Now constant factors aren't a big deal, but this does suggest that there is some room for optimization/improvement.
A simplified version of the code from the blog is shown below:

library(data.table)
workaround.result <- atime::atime(
  N=10^seq(1, 7, by=0.5),
  setup={
    N.v <- 1:N
    N.ids <- paste0("cg", sprintf("%06d",N.v-1))
    N.d <- data.frame(row.names=N.ids, N.v)
    N.half <- as.integer(N/2)
    matching.str <- sample(N.ids, N, replace=F)
    half.no.match <- c(matching.str[1:N.half], rep("FOO",N.half) )
    N.dt <- data.table(N.d, name=N.ids, key="name")
    N.tib <- tibble::tibble(N.d)
  },
  base=N.d[match(half.no.match, rownames(N.d)),,drop=F],
  data.table=N.dt[half.no.match],
  tibble=N.tib[half.no.match,],
  seconds.limit=1)
workaround.refs <- atime::references_best(workaround.result)
workaround.pred <- predict(workaround.refs)
plot(workaround.pred)

image
The log-log plot is computation time (seconds) vs data size N. The horizontal line and text labels shows the size N which each method is able to handle in 1 second. Because all the methods have the same asymptotic slope, that indicates they all have the same asymptotic complexity, but differ by constant factors. data.table could reduce these constant factors, ideally to be as fast as, or faster than tibble.

Dominant language
R
Stars
3.9k
Forks
1.1k
Avg merge
14h 4m
Merged PRs (30d)
4

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from Rdatatable/data.table

All issues in Rdatatable/data.table

Similar issues

More R issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.