Consider improving `memcmp`

[ncruces]

Something like:

int memcmp(const void *vl, const void *vr, size_t n) {
  const uint64_t *wl = (const uint64_t *)vl;
  const uint64_t *wr = (const uint64_t *)vr;

  if (n >= 4 * sizeof(uint64_t)) {
    do {
      if (*wl != *wr) break;
      n -= sizeof(uint64_t);
      wl++;
      wr++;
    } while (n >= sizeof(uint64_t));
  }

  const char *b1 = (const char *)wl;
  const char *b2 = (const char *)wr;

  while (n--) {
    if (*b1 != *b2) return *b1 - *b2;
    b1++;
    b2++;
  }

  return 0;
}

[ncruces]

See fac27b8.

[ncruces]

A simple benchmark seems to show an 88% improvement for memcmp. 😳

[ncruces]

These seem to be the musl "worst offenders" (not optimized at all):

• memcmp, strcmp, strncmp
• strcasecmp, strncasecmp
• memrchr, strrchr
• strncat

SQLite uses the first 3 – memory comparisons – fac27b8 optimizes them.

SQLite doesn't use case-less compares: it implements its own to avoid cross platform issues.
Reverse character search is only lightly used.
String concatenation not at all.

If the numbers pan out (~88% boost using 64bit and ~75% for 32bit), it might be worth it to update strlen to use 64-bits also: it's heavily used. Other functions could benefit, but don't seem as heavily used.

I can also improve fac27b8 to handle the case of both pointers are unaligned but share alignment. It shouldn't be as common, but who knows.

[ncruces]

For memset, I looked at the Wasm, and either clang or wasm-opt, are great at replacing it with 128-bit SIMD to zero out “small” fixed size structs, which is a lot of what SQLite uses it for.

I'm not sure it's worth it to have a branch to avoid the memory.fill instruction for the “dynamic and unknown but small” length case, even if memory.fill isn't great.

For memcpy and memmove it's less clear. I need to track down the small usages in the Wasm. I wonder if they always call memory.copy.

What I know for sure is that it's not worth it to carry around these complicated implementations if you'll use the builtins for anything larger than 32 bytes. Reducing their size also helps inlining. Hence those macros.

[ncruces]

I've now checked the assembly and both memset and memcpy are optimized away for "small" constant N, using suitable sequences of i32, i64 or v128 loads/stores.

So I don't think it's worth it to keep the branch inside libc. I mean, if we happen find out that memory.copy and memory.fill are slow, because they "always" call runtime.copy and shouldn't, the fix is to the wazero compiler backend, not libc.

For SQLite, this issue is really about:

1. memcmp, strcmp, strncmp not being optimal at all (known issue), and
2. the better optimized versions of everything else using size_t, which is 32-bit on Wasm.

[daenney]

There's stuff out there like https://github.com/lukego/asmlib which might be informative for how these could be implemented at least.

[ncruces]

The implementation in fac27b8 is pretty reasonable. It's based on how other functions are implemented in musl. I also briefly checked other "simple" libc's, but I don't want to look too deep into GPLed code.

I've just reconfirmed that for large, aligned inputs, using uint64_t makes a memcmp benchmark almost exactly 8x faster, whereas size_t (32-bit) makes them 4x faster; so there's a 2x improvement from using 64-bit (musl uses size_t, which is reasonable as it is 32 or 64-bit depending on hardware, but silly on Wasm that has 32-bit pointers but is often compiled to 64-bit hardware).

It's rare that a benchmark follows the theory this precisely. Check this out:

goos: linux
goarch: amd64
pkg: github.com/ncruces/go-sqlite3
cpu: Intel(R) Xeon(R) W-2135 CPU @ 3.70GHz
           │    before     │                32bit                 │                 64bit                 │               128bit                │
           │    sec/op     │    sec/op     vs base                │    sec/op      vs base                │   sec/op     vs base                │
_memset-12     24.53µ ± 5%    23.84µ ± 8%        ~ (p=0.436 n=10)    24.09µ ± 13%        ~ (p=0.631 n=10)   24.07µ ± 6%        ~ (p=0.353 n=10)
_memcpy-12     70.87µ ± 4%    75.97µ ± 6%   +7.20% (p=0.002 n=10)    71.02µ ±  5%        ~ (p=0.529 n=10)   72.55µ ± 5%        ~ (p=0.315 n=10)
_memcmp-12   1105.46µ ± 2%   262.16µ ± 2%  -76.29% (p=0.000 n=10)   129.51µ ±  1%  -88.28% (p=0.000 n=10)   62.02µ ± 2%  -94.39% (p=0.000 n=10)
geomean        124.3µ         78.01µ       -37.25%                   60.51µ        -51.33%                  47.67µ       -61.66%

On my machine, Wasm SIMD clearly gives another 2x improvement, but requires even stricter 16 bytes alignment:

int memcmp(const void *v1, const void *v2, size_t n) {
  const v128_t *w1 = v1;
  const v128_t *w2 = v2;
  if ((((uintptr_t)v1 | (uintptr_t)v2) & (sizeof(v128_t) - 1)) == 0) {
    while (n >= sizeof(v128_t) && !wasm_v128_any_true(*w1 ^ *w2)) {
      n -= sizeof(v128_t);
      w1++;
      w2++;
    }
  }

  const unsigned char *u1 = (const void *)w1;
  const unsigned char *u2 = (const void *)w2;
  while (n--) {
    if (*u1 != *u2) return *u1 - *u2;
    u1++;
    u2++;
  }
  return 0;
}

I'm not sure, though, if it's worth it to have lots of alternatives complicating inlining. Particularly in functions taking 2 parameters where alignment must agree between them. Functions taking only one parameter can have a prologue that waits until alignment, then speds through the aligned middle, then has an epilogue.

Also, as much as I love hacking, I really don't feel like pivoting this project to a better libc. 🤣

I could upstream the changes to wasi-libc. I wonder how eager they'd be to deviate from musl (on the size_t) and add a SIMD path.

[ncruces]

Added a benchmark in e6c9f18. The quick turnaround at building a module with just libc and dumping the wat should also help me iterate faster.

[ncruces]

Results for the latest commit, using unaligned SIMD:

goos: darwin
goarch: amd64
pkg: github.com/ncruces/go-sqlite3/sqlite3/libc
cpu: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
            │    before     │                after                │
            │    sec/op     │    sec/op     vs base               │
_memset-12     234.2µ ± 15%   232.7µ ±  9%        ~ (p=0.699 n=6)
_memcpy-12     197.5µ ± 16%   194.1µ ± 25%        ~ (p=0.589 n=6)
_memcmp-12    4929.4µ ±  2%   330.7µ ±  7%  -93.29% (p=0.002 n=6)
_strlen-12    1732.8µ ± 15%   562.1µ ±  6%  -67.56% (p=0.002 n=6)
_strcmp-12    6490.9µ ±  1%   526.0µ ±  5%  -91.90% (p=0.002 n=6)
_strncmp-12   6577.6µ ±  3%   379.3µ ±  5%  -94.23% (p=0.002 n=6)
geomean        1.601m         344.6µ        -78.48%

            │    before     │                  after                  │
            │      B/s      │      B/s        vs base                 │
_memset-12    16.68Gi ± 13%    16.79Gi ±  8%          ~ (p=0.699 n=6)
_memcpy-12    19.78Gi ± 19%    20.13Gi ± 20%          ~ (p=0.589 n=6)
_memcmp-12    405.7Mi ±  2%   6047.0Mi ±  7%  +1390.41% (p=0.002 n=6)
_strlen-12    2.256Gi ± 13%    6.950Gi ±  5%   +208.06% (p=0.002 n=6)
_strcmp-12    308.1Mi ±  1%   3803.5Mi ±  5%  +1134.40% (p=0.002 n=6)
_strncmp-12   304.1Mi ±  3%   5273.6Mi ±  6%  +1634.36% (p=0.002 n=6)
geomean       1.725Gi          8.016Gi         +364.69%

I may look at a few other functions, but don't want to get too deep. SQLite also uses these:

• memchr
• strchr (aka. __strchrnul)
• strchrnul (aka. __strchrnul)
• strcspn (uses __strchrnul)
• strspn

[ncruces]

This is done. There's a strong bias in strings.c towards stuff that's relevant to this project; other users might be worse off.

We assume wazero, SQLite, and that small implementations that get inlined are better than optimizing corner cases.

[ncruces]

Damn, my memory is not what it used to be; malloc is 8 byte aligned.

I need to see if strlen can be made better; the version I had that supported misalignment was a bit crap. The stuff you have to do to avoid reading past the end of memory… which basically never happens.