https://gitlab.com/nbdkit/nbdkit/-/blob/b31859402d1404ba0433...

  static inline bool __attribute__((__nonnull__ (1)))
  is_zero (const char *buffer, size_t size)
  {
    size_t i;
    const size_t limit = size < 16 ? size : 16;

    for (i = 0; i < limit; ++i)
      if (buffer[i])
        return false;
    if (size != limit)
      return ! memcmp (buffer, buffer + 16, size - 16);

    return true;
  }

(Might or might not still be true on more modern aarch64 hardware...)

This would eliminate split loads and provide a decent speedup.

https://lemire.me/blog/2012/05/31/data-alignment-for-speed-m...

Memory alignment is innocuous (others than often compromise code legibility).

Loop unrolling, on the other hand, can slow down the code. Specially in small loops.

See Agner uarch PDF.

We can't easily use a larger size because we mustn't read beyond the end of the buffer if it's shorter than 16 bytes and not a multiple of 2, 4, etc.

https://listman.redhat.com/archives/libguestfs/2017-April/ms...

https://rusty.ozlabs.org/?p=560

Hope that helps!

(And yes, the CCAN memeqzero routine is the same as yours above in form).

It counts how many bits are set to 1, you’re looking for 0.

You can also cast it into a uint64_t integer and do an equality test. There might be a way to use fused multiply add.

Also are you mmaping the file so you can just read it directly as a single buffer? You should be able to madvise to free pages after they’ve been checked.

PUSHFB can also be used. http://0x80.pl/articles/sse-popcount.html

Essentially you want to vectorize this tho memcmp may already be vectorized and do the cpu detection.

Edit: also… You should be able to load 15 x 256 bits and then test them. Try VPTEST https://www.intel.com/content/www/us/en/develop/documentatio...

I haven't looked at the implementation, but you could test it against yours.

    strchr(str, 0) == NULL
    memchr(str, 0, len) == NULL

Huh. OP is right, there is no good function for this in the standard library.

One of the big things about C is that there is no standard library function for anything remotely nontrivial. So successfully coding in C relies on "tricks", and snippets and lore that have been passed on over the years.

Rust, meanwhile, has a check_for_all_zeroes crate or something.

Turned out it was quite slow.

I replaced it with an Intel hand optimized version made for the StrongARM, and replaced the prefetch opcode by a simple load because this opcode was not supported by the arch of the CPU of this console.

50% faster, this is quite significant for such a low-level, already optimized routine, used extensively in many stages of a game engine.

I think that we should never assume that standard implementations are optimal, trust but verify.

I wonder though: it seems to me that memory bandwidth should far and away be the limiting factor for a memcpy, so I would think even a straight-forward translation of the "trivial" implementation wouldn't be that far off from an "optimal" one. I guess memory prefetching would make a difference, but would minimizing the number of loads/stores (or unrolling the loop) really matter that much?

[1]: https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy....

Only on recent x86, and with a long list of caveats. Look up discussion about erms online.

> I wonder though: it seems to me that memory bandwidth should far and away be the limiting factor for a memcpy, so I would think even a straight-forward translation of the "trivial" implementation wouldn't be that far off from an "optimal" one. I guess memory prefetching would make a difference, but would minimizing the number of loads/stores (or unrolling the loop) really matter that much?

Memory bandwidth is often the limiting factor, but not always. But your simple byte-by-byte loop is not going to get anywhere near saturating that; you'll need to unroll and use vector instructions, which might dispatch slower but copy several orders of magnitude more data.

In practice everything is memory bound because of course the CPU is faster than memory, but you'd be surprised by how difficult it can be to reach the full CPU capacity.

"Memory bound" or "Network bound" are way too frequently used as poor excuses by lazy coders.

Sadly I don't have a link, but as far as I remember rep movsb was always hilariously slow. So memcpy implementations tried to optimize copies using half a page of vector instructions with size and alignment tests, which of course killed the CPUs instruction cache.

Compiler optimized memcpy are good for small copies that will be inlined, but copying big chunks is an other story and I've seen non-marginal differences depending on implementation.

The most difficult problem is that each implementation is usually tuned for a specific CPU and might be sub-optimal with a different brand or revision...

For background: https://faculty-web.msoe.edu/johnsontimoj/EE4980/files4980/m... Since 1993 ram chips have integrated state machines receiving and interpreting higher level commands. They also have wide sense amplifier banks being loaded/stored all at once.

Likewise for doing copies from external RAM to internal SRAM, it was slow enough compared to the 1 cycle latency accessing SRAM, and CPU cycles were precious enough, that code copying lots of memory from external memory was designed to stop execution and let other code run and resume once the copy was finished.

We were able to get some serious speed out of the 96mhz CPU because we optimized everything around our memory bus.

I feel like there's also something in this topic that relates to things like "going to" getting reduced to "gonna".

Zen has CLZERO which can clear a cacheline in one go, but not sure how good it is.

There is a definite need to do hundreds of MB - the Linux kernel has a background thread that does nothing but zero out pages. What do you think happens to the GBs of RAM freed by closing Chrome? Once it’s made available in one spot, no reason others could use it (eg a hardened malloc implementation, etc).

Additionally, CLZERO ends up doing very similar work since the resulting cache flush os seen by the RAM controller as a block write.

On a similar note part of ATI 2000 https://en.wikipedia.org/wiki/HyperZ was fast Z clear, today a norm on every GPU.

Not hundreds but in one of my apps I do have 10th MB of continuous cache that has to be zeroed before use / reuse.

It returns the memory to the OS, and will pagefault on later accesses remapping them as zero-filled. It works in pages. Sizes smaller than a page result in whatever else is in the same page getting nuked.

If you don't immediately reuse the whole cache, it might spread out the zeroing/remapping over time, rather than in a single large go. Imagine some testing would be in order to see if a syscall + mapping changes ( require reloading with TLB for the process ? ) would be smaller than a straight run of writing zeros at some point.

IIRC, the zeroing is not something you can expect from non-linux madvise implementations.

  pi@rasppi400:~/memset_benchmark $ uname -a
  Linux rasppi400 5.10.63-v8+ #1459 SMP PREEMPT Wed Oct 6 16:42:49 BST 2021 aarch64 GNU/Linux
  
  pi@rasppi400:~/memset_benchmark $ ./bench_memset
  size, alignment, offset, libc, local
  0, 16, 0, 1237452, 834116, 1.483549,
  1, 16, 0, 1612697, 945325, 1.705971,
  2, 16, 0, 1779538, 945320, 1.882472,
  3, 16, 0, 1557081, 945324, 1.647140,
  4, 16, 0, 1779527, 889736, 2.000062,
  5, 16, 0, 1557103, 1000940, 1.555641,
  6, 16, 0, 1779551, 1000944, 1.777873,
  7, 16, 0, 1557111, 1000945, 1.555641,
  8, 16, 0, 1334654, 889723, 1.500078,
  Bus error
  
  pi@rasppi400:~/memset_benchmark $ gdb ./bench_memset
  [...]
  (gdb) run
  Starting program: /home/pi/memset_benchmark/bench_memset
  size, alignment, offset, libc, local
  0, 16, 0, 1557105, 722928, 2.153887,
  1, 16, 0, 1557103, 889797, 1.749953,
  2, 16, 0, 1557107, 889849, 1.749855,
  3, 16, 0, 1557108, 889759, 1.750033,
  4, 16, 0, 1557117, 889789, 1.749985,
  5, 16, 0, 1557110, 889745, 1.750063,
  6, 16, 0, 1557116, 889754, 1.750052,
  7, 16, 0, 1557110, 889758, 1.750038,
  8, 16, 0, 1557109, 889803, 1.749948,
  
  Program received signal SIGBUS, Bus error.
  
  small_memset (n=<optimized out>, c=<optimized out>, s=0x29690)
      at /home/pi/memset_benchmark/src/lib.c:33
  33          *((uint64_t *)last) = val8;

On SPARC you have no choice, align or die!

  pi@rasppi400:~/memset_benchmark $ uname -a
  Linux rasppi400 5.10.63-v8+ #1459 SMP PREEMPT Wed Oct 6 16:42:49 BST 2021 aarch64 GNU/Linux
  pi@rasppi400:~/memset_benchmark $
  pi@rasppi400:~/memset_benchmark $ file ./bench_memset
  ./bench_memset: ELF 32-bit LSB executable, ARM, EABI5 version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux-armhf.so.3, for GNU/Linux 3.2.0, BuildID[sha1]=ebeb69b6cb9664d78c1256a2c862f3d28f11e15e, with debug_info, not stripped

  Program received signal SIGBUS, Bus error.
  small_memset (n=<optimized out>, c=<optimized out>, s=0x29690)
      at /home/pi/memset_benchmark/src/lib.c:33
  33          *((uint64_t *)last) = val8;
  1: x/i $pc
  => 0x11c8c <local_memset+1560>: strd    r0, [r7, #-8]
  (gdb) info registers
  r0             0x0                 0
  r1             0x0                 0
  r2             0x0                 0
  r3             0x1475              5237
  r4             0x5f5e100           100000000
  r5             0x11674             71284
  r6             0x29690             169616
  r7             0x29699             169625

https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aar...

There's also the "ifunc" mechanism which can be used to make the choice at runtime, eg:

https://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/aar...

I'm not saying it would go either way, just a big flaw to consider with the benchmarking method where it is doing only repeated calls of the same size only.

It is suprising the GCC version does an integer multiply, if I am reading right (several cycles, unless it is cheaper for uint32 * char).

Measuring the time _repeated_ small calls to memset usually doesn't make any sense, even when the lengths are heterogeneous; this results in an instruction stream that's almost all memset, but for small memsets you almost always have lots of "other stuff" mixed in in real use. This can lead you to a suboptimal implementation.

You have to factor in what distribution of sizes actually occurs in a live system. I haven't looked at this for a decade or so, but the last time I checked the majority of system-wide time in memset (on macOS running diverse applications) was spent in length-4096 calls, and the next highest spike was (perversely) length-zero. A system implementation has to balance the whole system's needs; a memset for just your program can certainly do better. Dtrace or similar tooling is invaluable to gather this information.

As with any benchmarking, the only way to actually know is to swap out the implementation and measure real app / system performance. All that said, Nadav's implementation looks pretty plausible. It's branchier than I would like, and doesn't take advantage of specialized instructions for large buffers, but for some input distributions that's a very reasonable tradeoff, and I don't doubt that it's competitive with system memsets.

https://storage.googleapis.com/pub-tools-public-publication-...

Spot regressions early (locally) but make the decisions based on the big the picture.

On x86 the situation is in some ways worse. Quite a few x86 CPUs have had atrociously bad implementation of the string instructions. As a result, some high performance systems rolled their own memset/memcpy implementations. That results in feedback to the CPU designers failing to prioritize further optimize those string instructions. Thankfully, string instructions have kept getting better, so the general recommendation today is to just use the string instructions.

They assumed aligned writes were safe and the compiler optimized it incorrectly, resulting in memory corruption.

Given it's comparatively huge impl. it probably massively messes with the instruction cache of the rest of your program or am I overlooking something?

explicit_bzero and it's numerous variants are not only insecure, but also slow. (byte wise!)

Only safelibc has a secure memset_s. https://github.com/rurban/safeclib/blob/master/tests/perf_me...

That being said, preliminary instrumentation indicates the tradeoffs made were correct.

My main point, however, is that for such low-level, essential subroutines, assembly remains the correct implementation language; c is still inadequate.)

That branch is not needed because memset() is UD if length is 0, but it's nice that it's safer.

That used to be stable stakes for this kind of thing, but maybe it doesn’t matter much anymore?

This is undefined behavior under C99 §6.3.2.3 Paragraph 7. "If the resulting pointer is not correctly aligned for the pointed-to type, the behavior is undefined."

The musl code referenced has handling for this.

I’m curious about what the referenced code compiles down to, actually, because not only could GCC be auto-vectorizing it, it could be replacing it with a REP STOSQ or indeed a call to memset.

gcc: https://godbolt.org/z/6xG5dKjj9

clang: https://godbolt.org/z/Mh9zozjvK

I'm no asm expert, but it doesn't look like a lot of vector instructions in the gcc compilation of this, while the clang compilation seems to have more calls with the 128-bit xmm registers (at least on x86_64.) You can also just see visibly how many more instructions the gcc version outputs.