jmillikin

  > The mathematician and the blog author are not the same person
  > (as you seem to understand). Nathanson (the mathematician) is
  > the one who is the expert verifier. He is the person who has
  > the higher value and won't be fired in some hypothetical.

  > It seems that JPEG can be decoded on the GPU [1] [2]

  > According to smhasher tests [3] CRC32 is not limited by memory bandwidth.
  > Even if we multiply CRC32 scores x4 (to estimate 512 bit wide SIMD from 128
  > bit wide results), we still don't get close to memory bandwidth.

  > The 32 bit hash of CRC32 is too low for file checksums. xxhash is definitely
  > an improvement over CRC32.

  > Why would you need to use a cryptographic hash function to check integrity
  > of archived files? Quality a non-cryptographic hash function will detect
  > corruptions due to things like bit-rot, bad RAM, etc. just the same.

  > And why is 256 bits needed here? Kopia developers, for example, think 128
  > bit hashes are big enough for backup archives [4].

  > Don't worry about 4-KiB alignment restrictions
  > * Win32 has a restriction that asynchronous requests be aligned on a
  >   4-KiB boundary and be a multiple of 4-KiB in size.
  > * DirectStorage does not have a 4-KiB alignment or size restriction. This
  >   means you don't need to pad your data which just adds extra size to your
  >   package and internal buffers.

  > ZIP/RAR use CRC32, which is aging, collision-prone, and significantly slower
  > to verify than XXH3 for large archival collections.  
  > [...]  
  > On multi-core systems, the verifier splits the asset table into chunks and
  > validates multiple pages simultaneously. This makes BBF verification up to
  > 10x faster than ZIP/RAR CRC checks.

  > While JSON numbers are grammatically simple, they're almost always distinct
  > from how you'd implement numbers in any language that has JSON parsers,
  > syntactically, exactness and precision-wise.

  > use SECCOMP_SET_MODE_STRICT to isolate the child process. But at that
  > point, what are you even doing? Probably nothing useful.

  $ gcc --version
  gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
  $ gcc -O2 -static -o bench-c-gcc benchmark.c
  $ clang --version
  Ubuntu clang version 14.0.0-1ubuntu1.1
  $ clang -O2 -static -o bench-c-clang benchmark.c
  $ rustc --version
  rustc 1.81.0 (eeb90cda1 2024-09-04)
  $ rustc -C opt-level=2 --target x86_64-unknown-linux-musl -o bench-rs benchmark.rs

  $ taskset -c 1 hyperfine --warmup 1000 ./bench-c-gcc
  Benchmark 1: ./bench-c-gcc
    Time (mean ± σ):       3.2 ms ±   0.1 ms    [User: 2.7 ms, System: 0.6 ms]
    Range (min … max):     3.2 ms …   4.1 ms    770 runs

  $ taskset -c 1 hyperfine --warmup 1000 ./bench-c-clang
  Benchmark 1: ./bench-c-clang
    Time (mean ± σ):       3.5 ms ±   0.1 ms    [User: 3.0 ms, System: 0.6 ms]
    Range (min … max):     3.4 ms …   4.8 ms    721 runs

  $ taskset -c 1 hyperfine --warmup 1000 ./bench-rs
  Benchmark 1: ./bench-rs
    Time (mean ± σ):       5.1 ms ±   0.1 ms    [User: 2.9 ms, System: 2.2 ms]
    Range (min … max):     5.0 ms …   7.1 ms    507 runs

  --- benchmark.rs
  +++ benchmark.rs
  @@ -38,22 +38,22 @@
   }
 
   // Generates a random 8-character string
  -fn generate_random_string(rng: &mut Xorshift) -> String {
  +fn generate_random_string(rng: &mut Xorshift) -> [u8; 8] {
       const CHARSET: &[u8] = b"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  -    let mut result = String::with_capacity(8);
  +    let mut result = [0u8; 8];
   
  -    for _ in 0..8 {
  +    for ii in 0..8 {
           let rand_index = (rng.next() % 62) as usize;
  -        result.push(CHARSET[rand_index] as char);
  +        result[ii] = CHARSET[rand_index];
       }
   
       result
   }
   
   // Generates `count` random strings and tracks their occurrences
  -fn generate_random_strings(count: usize) -> HashMap<String, u32> {
  +fn generate_random_strings(count: usize) -> HashMap<[u8; 8], u32> {
       let mut rng = Xorshift::new();
  -    let mut string_counts: HashMap<String, u32> = HashMap::new();
  +    let mut string_counts: HashMap<[u8; 8], u32> = HashMap::with_capacity(count);
   
       for _ in 0..count {
           let random_string = generate_random_string(&mut rng);

  $ taskset -c 1 hyperfine --warmup 1000 ./bench-rs
  Benchmark 1: ./bench-rs
    Time (mean ± σ):       1.5 ms ±   0.1 ms    [User: 1.3 ms, System: 0.2 ms]
    Range (min … max):     1.4 ms …   3.2 ms    1426 runs
 

  // Xorshift+ state variables (64-bit)
  uint64_t state0, state1;

  // Xorshift+ function for generating pseudo-random 64-bit numbers
  uint64_t xorshift_plus() {
      uint64_t s1 = state0;
      uint64_t s0 = state1;
      state0 = s0; 
      s1 ^= s1 << 23; 
      s1 ^= s1 >> 18; 
      s1 ^= s0; 
      s1 ^= s0 >> 5;
      state1 = s1; 
      return state1 + s0; 
  }

  --- benchmark.c
  +++ benchmark.c
  @@ -18,25 +18,35 @@
   StringNode *hashTable[HASH_TABLE_SIZE]; // Hash table for storing unique strings
   
   // Xorshift+ state variables (64-bit)
  -uint64_t state0, state1;
  +struct xorshift_state {
  +       uint64_t state0, state1;
  +};
   
   // Xorshift+ function for generating pseudo-random 64-bit numbers
  -uint64_t xorshift_plus() {
  -    uint64_t s1 = state0;
  -    uint64_t s0 = state1;
  -    state0 = s0;
  +uint64_t xorshift_plus(struct xorshift_state *st) {
  +    uint64_t s1 = st->state0;
  +    uint64_t s0 = st->state1;
  +    st->state0 = s0;
       s1 ^= s1 << 23;
       s1 ^= s1 >> 18;
       s1 ^= s0;
       s1 ^= s0 >> 5;
  -    state1 = s1;
  -    return state1 + s0;
  +    st->state1 = s1;
  +    return s1 + s0;
   }
   
   // Function to generate an 8-character random string
   void generate_random_string(char *buffer) {
  +    uint64_t timestamp = (uint64_t)time(NULL) * 1000;
  +    uint64_t state0 = timestamp ^ 0xDEADBEEF;
  +    uint64_t state1 = (timestamp << 21) ^ 0x95419C24A637B12F;
  +    struct xorshift_state st = {
  +        .state0 = state0,
  +        .state1 = state1,
  +    };
  +
       for (int i = 0; i < STRING_LENGTH; i++) {
  -        uint64_t rand_value = xorshift_plus() % 62;
  +        uint64_t rand_value = xorshift_plus(&st) % 62;
   
           if (rand_value < 10) { // 0-9
               buffer[i] = '0' + rand_value;
  @@ -113,11 +123,6 @@
   }
   
   int main() {
  -    // Initialize random seed
  -    uint64_t timestamp = (uint64_t)time(NULL) * 1000;
  -    state0 = timestamp ^ 0xDEADBEEF; // Arbitrary constant
  -    state1 = (timestamp << 21) ^ 0x95419C24A637B12F; // Arbitrary constant
  -
       double total_time = 0.0;
   
       // Run 3 times and measure execution time
  

  $ taskset -c 1 hyperfine --warmup 1000 ./bench-c-gcc
  Benchmark 1: ./bench-c-gcc
    Time (mean ± σ):       1.1 ms ±   0.1 ms    [User: 1.1 ms, System: 0.1 ms]
    Range (min … max):     1.0 ms …   1.8 ms    1725 runs
  
  $ taskset -c 1 hyperfine --warmup 1000 ./bench-c-clang
  Benchmark 1: ./bench-c-clang
    Time (mean ± σ):       1.0 ms ±   0.1 ms    [User: 0.9 ms, System: 0.1 ms]
    Range (min … max):     0.9 ms …   1.4 ms    1863 runs

  > Yes, I absolutely used ChatGPT to polish my code. If you’re judging me for this,
  > I’m going to assume you still churn butter by hand and refuse to use calculators.
  > [...]
  > I then embarked on the linguistic equivalent of “Google Translate for code,”