3 ms·

I don't know enough about the ARM / aarch64 instruction set to know how optimal memcmp()/strcmp() is implemented on ARM / aarch64. However, in the general case

by KMag 6y ago

I don't know enough about the ARM / aarch64 instruction set to know how optimal memcmp()/strcmp() is implemented on ARM / aarch64. However, in the general case, since these comparisons treat earlier bytes as more significant, fast implementation either needs dedicated instructions or wide big-endian unsigned integer comparisons. A related use case is that if you have structures full of unsigned big-endian integer types, memcmp() will give you the same ordering as numeric comparison of the integers. It's a pretty corner case, but it might be useful for b-tree key comparisons where you have compound keys, say in a database table with a compound primary key.

zeusk 6y ago
above 128 bytes, ARM implementations tend to use the NEON/SIMD for memcmp/strcmp so I doubt the endian-ness would matter.
sgtnoodle 6y ago
Whether or not the endianness is in your favor, an optimized implementation could still use wide integer comparisons to tear through the bulk of the data quickly. On mismatch, simply fall back to byte-wise to determine the correct ordering. On a tangent, strcmp seems like it would be difficult to optimize since the length isn't known until the trailing null is found. Does anyone know how it's typically done?
- zeusk 6y ago
  I know you asked for strcmp, but the strlen is far better documented on how the null-byte detection works for ARM. https://lkml.org/lkml/2020/9/14/871 https://lkml.org/lkml/2020/9/14/871 https://github.com/ARM-software/optimized-routines/blob/master/string/aarch64/strlen-mte.S https://github.com/ARM-software/optimized-routines/blob/mast...
  - sgtnoodle 6y ago
    I see, so the implementations basically read past the end of the string as long as it won't cross a page boundary and cause a memory protection fault. It's technically a buffer overflow, but since the implementations are architecture specific, it's safe to do. I wonder if there are memory sanitizers that would complain about that sort of access?
    - deleted 6y ago
      [deleted]

by KMag 6y ago

zeusk 6y ago

above 128 bytes, ARM implementations tend to use the NEON/SIMD for memcmp/strcmp so I doubt the endian-ness would matter.

sgtnoodle 6y ago

Whether or not the endianness is in your favor, an optimized implementation could still use wide integer comparisons to tear through the bulk of the data quickly. On mismatch, simply fall back to byte-wise to determine the correct ordering. On a tangent, strcmp seems like it would be difficult to optimize since the length isn't known until the trailing null is found. Does anyone know how it's typically done?

zeusk 6y ago
I know you asked for strcmp, but the strlen is far better documented on how the null-byte detection works for ARM. https://lkml.org/lkml/2020/9/14/871 https://lkml.org/lkml/2020/9/14/871 https://github.com/ARM-software/optimized-routines/blob/master/string/aarch64/strlen-mte.S https://github.com/ARM-software/optimized-routines/blob/mast...
- sgtnoodle 6y ago
  I see, so the implementations basically read past the end of the string as long as it won't cross a page boundary and cause a memory protection fault. It's technically a buffer overflow, but since the implementations are architecture specific, it's safe to do. I wonder if there are memory sanitizers that would complain about that sort of access?
  - deleted 6y ago
    [deleted]