7 ms·

Yes, it's hard to take the benchmark results seriously in light of the failure to use anything other than a single size at a time.

stephencanon 5y ago
There's a bunch of things that make benchmarking memset and similar functions really hard: 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.
- jeffbee 5y ago
  As far as real-world performance goes, this paper claims (and shows) that code size is the relevant aspect of mem* functions, and concludes that `rep stosb` is optimal in practice, even though it obviously loses to exotic hand-rolled memset and memcmp in microbenchmarks. https://storage.googleapis.com/pub-tools-public-publication-data/pdf/e52f61fd2c51e8962305120548581efacbc06ffc.pdf https://storage.googleapis.com/pub-tools-public-publication-...
  - stephencanon 5y ago
    rep stos _is_ worth using, but that paper makes no mention of it (it does show that in their use rep cmps beat a more complicated memcmp implementation).
  - ckennelly 5y ago
    https://research.google/pubs/pub50338.pdf https://research.google/pubs/pub50338.pdf goes into more depth on the mem* libc functions and principles for the implementations in llvm libc.

stephencanon 5y ago

There's a bunch of things that make benchmarking memset and similar functions really hard: 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.

jeffbee 5y ago
As far as real-world performance goes, this paper claims (and shows) that code size is the relevant aspect of mem* functions, and concludes that `rep stosb` is optimal in practice, even though it obviously loses to exotic hand-rolled memset and memcmp in microbenchmarks. https://storage.googleapis.com/pub-tools-public-publication-data/pdf/e52f61fd2c51e8962305120548581efacbc06ffc.pdf https://storage.googleapis.com/pub-tools-public-publication-...
- stephencanon 5y ago
  rep stos _is_ worth using, but that paper makes no mention of it (it does show that in their use rep cmps beat a more complicated memcmp implementation).
- ckennelly 5y ago
  https://research.google/pubs/pub50338.pdf https://research.google/pubs/pub50338.pdf goes into more depth on the mem* libc functions and principles for the implementations in llvm libc.