This vignette provides a comparison of r2r with the same-purpose CRAN package {hash}, which also offers an implementation of hash tables based on R environments. We first describe the features offered by both packages, and then perform some benchmark timing comparisons. The package versions referred to in this vignette are:
library(hash)
library(r2r)
packageVersion("hash")
#> [1] '2.2.6.1'
packageVersion("r2r")
#> [1] '0.1.1'Both r2r and {hash} hash tables are built on top of the R built-in environment data structure, and have thus a similar API. In particular, hash table objects have reference semantics for both packages. r2r hashtables are S3 class objects, whereas in {hash} the data structure is implemented as an S4 class.
Hash tables provided by r2r support arbitrary type keys and values, arbitrary key comparison and hash functions, and have customizable behaviour (either throw an exception or return a default value) upon query of a missing key.
In contrast, hash tables in hash currently support only string keys, with basic identity comparison (the hashing is performed automatically by the underlying environment objects); values can be arbitrary R objects. Querying missing keys through non-vectorized [[-subsetting returns the default value NULL, whereas queries through vectorized [-subsetting result in an error. On the other hand, hash also offers support for inverting hash tables (an experimental feature at the time of writing).
The table below summarizes the features of the two packages
| Feature | r2r | hash |
|---|---|---|
| Basic data structure | R environment | R environment |
| Arbitrary type keys | X | |
| Arbitrary type values | X | X |
| Arbitrary hash function | X | |
| Arbitrary key comparison function | X | |
| Throw or return default on missing keys | X | |
| Hash table inversion | X |
We will perform our benchmark tests using the CRAN package microbenchmark.
We start by timing the insertion of:
N <- 1e4random key-value pairs (with possible repetitions). In order to perform a meaningful comparison between the two packages, we restrict to string (i.e. length one character) keys. We can generate random keys as follows:
chars <- c(letters, LETTERS, 0:9)
random_keys <- function(n) paste0(
sample(chars, n, replace = TRUE),
sample(chars, n, replace = TRUE),
sample(chars, n, replace = TRUE),
sample(chars, n, replace = TRUE),
sample(chars, n, replace = TRUE)
)
set.seed(840)
keys <- random_keys(N)
values <- rnorm(N)We test both the non-vectorized ([[<-) and vectorized ([<-) operators:
microbenchmark(
`r2r_[[<-` = {
for (i in seq_along(keys))
m_r2r[[ keys[[i]] ]] <- values[[i]]
},
`r2r_[<-` = { m_r2r[keys] <- values },
`hash_[[<-` = {
for (i in seq_along(keys))
m_hash[[ keys[[i]] ]] <- values[[i]]
},
`hash_[<-` = m_hash[keys] <- values,
times = 30,
setup = { m_r2r <- hashmap(); m_hash <- hash() }
)
#> Unit: milliseconds
#> expr min lq mean median uq max neval
#> r2r_[[<- 111.54835 130.37921 193.59728 201.5787 246.5056 312.6756 30
#> r2r_[<- 103.44057 146.71259 175.29195 176.1595 196.2209 281.5497 30
#> hash_[[<- 97.69138 140.48700 177.92566 182.8497 203.2853 259.5250 30
#> hash_[<- 52.65147 61.11784 89.96423 81.7027 113.0783 167.0759 30As it is seen, r2r and hash have comparable performances at the insertion of key-value pairs, with both vectorized and non-vectorized insertions, hash being somewhat more efficient in both cases.
We now test key query, again both in non-vectorized and vectorized form:
microbenchmark(
`r2r_[[` = { for (key in keys) m_r2r[[ key ]] },
`r2r_[` = { m_r2r[ keys ] },
`hash_[[` = { for (key in keys) m_hash[[ key ]] },
`hash_[` = { m_hash[ keys ] },
times = 30,
setup = {
m_r2r <- hashmap(); m_r2r[keys] <- values
m_hash <- hash(); m_hash[keys] <- values
}
)
#> Unit: milliseconds
#> expr min lq mean median uq max neval
#> r2r_[[ 124.81017 175.76404 228.40115 218.11206 262.34639 363.20552 30
#> r2r_[ 113.27040 172.00862 210.85097 211.59312 250.79167 333.21509 30
#> hash_[[ 14.26790 16.28593 22.85595 21.99028 24.30694 48.34391 30
#> hash_[ 82.63965 109.64820 141.58864 135.93963 159.63201 268.81355 30For non-vectorized queries, hash is significantly faster (by one order of magnitude) than r2r. This is likely due to the fact that the [[ method dispatch is handled natively by R in hash (i.e. the default [[ method for environments is used ), whereas r2r suffers the overhead of S3 method dispatch. This is confirmed by the result for vectorized queries, which is comparable for the two packages; notice that here a single (rather than N) S3 method dispatch occurs in the r2r timed expression.
As an additional test, we perform the benchmarks for non-vectorized expressions with a new set of keys:
set.seed(841)
new_keys <- random_keys(N)
microbenchmark(
`r2r_[[_bis` = { for (key in new_keys) m_r2r[[ key ]] },
`hash_[[_bis` = { for (key in new_keys) m_hash[[ key ]] },
times = 30,
setup = {
m_r2r <- hashmap(); m_r2r[keys] <- values
m_hash <- hash(); m_hash[keys] <- values
}
)
#> Unit: milliseconds
#> expr min lq mean median uq max neval
#> r2r_[[_bis 86.50014 118.93648 157.65807 153.16882 163.77239 365.71789 30
#> hash_[[_bis 14.05082 16.57323 23.19929 21.53846 30.16298 39.63644 30The results are similar to the ones already commented. Finally, we test the performances of the two packages in checking the existence of keys (notice that here has_key refers to r2r::has_key, whereas has.key is hash::has.key):
set.seed(842)
mixed_keys <- sample(c(keys, new_keys), N)
microbenchmark(
r2r_has_key = { for (key in mixed_keys) has_key(m_r2r, key) },
hash_has_key = { for (key in new_keys) has.key(key, m_hash) },
times = 30,
setup = {
m_r2r <- hashmap(); m_r2r[keys] <- values
m_hash <- hash(); m_hash[keys] <- values
}
)
#> Unit: milliseconds
#> expr min lq mean median uq max neval
#> r2r_has_key 83.2514 109.7505 131.4229 120.3173 149.7155 291.3949 30
#> hash_has_key 233.2610 304.9865 367.8324 364.3668 408.9261 539.3776 30The results are comparable for the two packages, r2r being slightly more performant in this particular case.
Finally, we test key deletion. In order to handle name collisions, we will use delete() (which refers to r2r::delete()) and del() (which refers to hash::del()).
microbenchmark(
r2r_delete = { for (key in keys) delete(m_r2r, key) },
hash_delete = { for (key in keys) del(key, m_hash) },
hash_vectorized_delete = { del(keys, m_hash) },
times = 30,
setup = {
m_r2r <- hashmap(); m_r2r[keys] <- values
m_hash <- hash(); m_hash[keys] <- values
}
)
#> Unit: milliseconds
#> expr min lq mean median uq
#> r2r_delete 429.794784 522.802137 661.172206 639.401653 758.826645
#> hash_delete 227.654058 288.144309 364.531141 362.392011 439.393266
#> hash_vectorized_delete 4.533082 5.389375 6.431943 5.769315 7.656032
#> max neval
#> 1179.17381 30
#> 557.73474 30
#> 11.19358 30The vectorized version of hash significantly outperforms the non-vectorized versions (by roughly two orders of magnitude in speed). Currently, r2r does not support vectorized key deletion 1.
The two R packages r2r and hash offer hash table implementations with different advantages and drawbacks. r2r focuses on flexibility, and has a richer set of features. hash is more minimal, but offers superior performance in some important tasks. Finally, as a positive note for both parties, the two packages share a similar API, making it relatively easy to switch between the two, according to the particular use case needs.
This is due to complications introduced by the internal hash collision handling system of r2r.↩︎