Faster hashing from nanonext?

[wlandau]

Prework

• I understand and agree to help guide.
• I understand and agree to contributing guide.
• New features take time and effort to create, and they take even more effort to maintain. So if the purpose of the feature is to resolve a struggle you are encountering personally, please consider first posting a "trouble" or "other" issue so we can discuss your use case and search for existing solutions first.

Proposal

SHA256 hashes from nanonext appear to be much faster than the analogous ones from digest according to the benchmark below. So I wonder if it is worth considering switching to nanonext to produce hashes for things that targets needs (hashes of R commands and files to check if a target is out of date). @shikokuchuo, are there plans to implement xxhash64 in nanonext? That is what targets currently uses.

Benchmark

library(microbenchmark)
library(digest)
library(nanonext)
library(tibble)
library(purrr)
set.seed(0)

datasets <- replicate(
  1e3,
  tibble(
    a = rnorm(1e3),
    b = rnorm(1e3),
    c = rnorm(1e3),
    d = rnorm(1e3)
  ),
  simplify = FALSE
)

tmp <- digest(datasets[[1]], algo = "sha256")
tmp <- sha256(datasets[[1]])

system.time(lapply(datasets, digest, algo = "sha256"))
#>    user  system elapsed 
#>   0.380   0.016   0.400

system.time(lapply(datasets, sha256))
#>    user  system elapsed 
#>   0.242   0.005   0.248

^{Created on 2023-03-17 with reprex v2.0.2}

[shikokuchuo]

In short, nanonext will never have 'xxhash64' as it simply exposes the hashing capabilities of the mbedTLS library.

These are secure cryptographic functions using what some consider a much cleaner library than openSSL, and very much optimised as mbedTLS (as per the name) is often used on embedded or otherwise constrained devices. If I remember, for digest there is some disclaimer saying that for cryptographic purposes other libraries should be used.

I can replicate the results from your benchmark in terms of the relative speed of sha256 hashing.

If you are considering moving to sha256, which has become somewhat of a standard these days, the implementation in nanonext can definitely be considered.

[wlandau]

Thanks for explaining, the stack definitely makes sense. I will keep it in mind in case I need sha256 and above or cryptographic guarantees. For targets though, I do not need a cryptographically safe hash, and I would like something at least as fast as the current xxhash64 in digest. From benchmarks on the same data as above, it looks like xxhash64 in digest is faster than sha256 from mbedTLS.

[shikokuchuo]

Out of curiosity, I exposed the sha-1 algorithm from mbedTLS and I get closer to the xxHash64 performance but not surpassing it. The performance gain vs sha1 from the digest package is still maintained though.

I think I will leave it in for the next version of nanonext as you will be able to use this instead of sha224() as a slightly more efficient way of creating the unique names for crew.

[wlandau]

Thanks! sha1 sounds great for generating unique names quickly for crew.

[shikokuchuo]

On this, rlang::hash() turns out to be an order of magnitude faster than digest on the above test. It also uses a 128 bit xxHash128.

However see the note above https://github.com/r-lib/rlang/blob/c55f6027928d3104ed449e591e8a225fcaf55e13/src/internal/hash.c#L120C15-L120C15 I am not sure how this behaviour compares to digest. In nanonext I always use XDR for hashing to ensure reproducibility across systems even if it is slower.

[wlandau]

Interesting. rlang has something for everything, doesn't it?

I do need targets to guarantee stable hashes across different platforms, but this is still good for awareness. Thanks for the pointer.

[shikokuchuo]

I'm posting here as the more appropriate place to continue the conversation from #1139 (comment).

Very rough-and-ready testing with 'xxhash64' within secretbase shows that it could halve the runtime of the above benchmark. I can't promise anything yet as I'm not sure it makes sense to add that particular hash (there seem to be newer versions XXH3?), and I've also not inspected the code for things like portability.

[wlandau]

Wow, that would be an incredible boon! Please keep me posted if this works out!

I'm not committed to xxhash64, I'm just looking for something with the right balance of speed, memory usage, and avoidance of collisions. (But for short suffixes for dynamic branch names, a separate 32-bit hash would be nice to have as well.)

[shikokuchuo]

I see so potentially 2 hashes. It may be a while before I get back to this so I'll let you know when I do. In the meantime I've put in a file hashing interface for secretbase so at least it's ready.

[shikokuchuo]

There is now a PR implementing xxHash64. I'll invite you to try it out over an extended period of time, but should allow you to replace in a non-breaking manner.

Given how much it's been cleaned up (from a code dump of over 6,000 lines to just c. 400) and given 32-bit is mostly separate code, I don't think there will be a XXH32 implementation.

[njtierney]

Would this be of interest, @wlandau ? https://github.com/coolbutuseless/xxhashlite

[wlandau]

Looks like a cool package, but I still need secretbase for XOF for parallel-safe RNG seeds (https://github.com/shikokuchuo/secretbase?tab=readme-ov-file#sha-3-and-xof-usage, #1139), and at this point I am trying to slim targets back down to just one hashing package.

[wlandau]

targets moved to secretbase::siphash13() in #1262.