[libc][NFC] Optimize and standardize the C string functions

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

Added \0 so we know what we are searching for

[gAlfonso-bit]

If there are any objections, please let me know.

[sivachandra]

About strchr, it is the way it is because the standard says, "each character interpreted as unsigned char". I see almost no difference before and after wrt codegen.

Before: https://godbolt.org/z/89sqGrYY9
After: https://godbolt.org/z/4h9eWzKKT

The changes comparing with `\0' are good though.

[gAlfonso-bit]

You are confusing strchr and memchr it seems. Str - standard says char. Memchr - standard says unsigned char.

Easy way to remember this is by knowing: strings are char arrays. Mem is by the raw byte.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[sivachandra]

To get this reviewed, you should split this up into multiple small and focused patches. I have also left a few comments inline you can use as a general guidelines for splitting.

In D106511#2900060, @gAlfonso-bit wrote:

You are confusing strchr and memchr it seems. Str - standard says char. Memchr - standard says unsigned char.

I think the original author looked at cppreference.com which has almost the same text for strchr and memchr.

strchr - https://en.cppreference.com/w/c/string/byte/strchr
memchr - https://en.cppreference.com/w/c/string/byte/memchr

But, I also looked up the actual standard document and it indeed follows what you are saying.

libc/src/string/memchr.cpp

21

Using these explicit casts is probably a good thing, but it mostly cosmetic. If there is a reason beyond just the cosmetics, elaborate that.

libc/src/string/memrchr.cpp

19–20

Instead of folding existing code into patterns like this (using an increment and decrement operator along with a another operator like the dereference operator), I would suggest doing the other way round cleanup. For example, the existing code is more readable than this new code.

libc/src/string/strchr.cpp

19

Comparing with an exact value instead of relying on its boolean interpretation is a good change I think. So, please do it in a separate patch just focused on these kind of changes. It makes the intention clear to the reviewers.

libc/src/string/strcpy.cpp

14

The changes in this file have to be a patch by itself explaining why and what clearly.

libc/src/string/string_utils.h

21–22

For me, most of the changes in this file look like cosmetic churn. So, please explain why you want to do these changes.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

libc/src/string/strchr.cpp

19

It actually does what the point of this patch is, which is that it coverts to char, not unsigned char, and because \0 is a char literal for 0, it makes sense here

libc/src/string/strcpy.cpp

14

It’s an exact copy of the one in memcpy except the argument types align with what the functions are supposed to be handling.

libc/src/string/string_utils.h

21–22

It’s actually more efficient this way and closer to the other functions.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

libc/src/string/strcpy.cpp

14

Addressed

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[sivachandra]

In D106511#2905415, @gAlfonso-bit wrote:

Is this good? @sivachandra

A large part of this change is what I would would consider as "churn". So, if you can demonstrate why you want this change, it will be easier to review for people like me (for whom it might not be clear as to why one flavor is better than the other). For example, for code this like:

const char ch = static_cast<char>(c); // c is of type int

The implicit conversion rules make it equivalent to

const char ch = c;

Unless you want the code to work under -Wconversion or something similar, the explicit cast is redundant. Speaking for myself (as a reviewer), if you can let us know the intention of your change, I will be able read it with that in my mind.

Don't get me wrong here; I totally appreciate you taking time to do this. In fact, I have already commented earlier that some of the changes you included in here are good from consistency and readability point of view, but that they should be done separately in order not to mix-up concerns.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

Rebased on LLVM 13 Release branch

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

libc/src/string/memrchr.cpp

19–20

The code is more efficient this way than the last way.

[gAlfonso-bit]

Rebased to current

[gAlfonso-bit]

Remove unneeded check

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[gAlfonso-bit]

This comment was removed by gAlfonso-bit.

[sivachandra]

One way is to fold this entire patch "Under standardize and optimize" but I would rather split this patch to actually see the "standardize" parts and the "optimize" parts separately. In fact, as it stands, this patch is doing cleanups beyond "optimize" and "standardize". So, I would strongly encourage you to separate out all the individual concerns clearly in different patches.

libc/src/string/memmove.cpp

1

Some of the changes in this file have to separated out into a patch of their own.

libc/src/string/memory_utils/elements.h

1

Same here - some of the changes have to be a patch of their own explaining the rationale clearly. You can combine this change with the change to memmove.cpp.

libc/src/string/memrchr.cpp

19–20

Can you please demonstrate that at -O2 or higher, mixing an increment/decrement operator with another operator is more efficient?

libc/src/string/memchr.cpp

 // TODO: Look at performance benefits of comparing words.
 LLVM_LIBC_FUNCTION(void *, memchr, (const void *src, int c, size_t n)) {
   return internal::find_first_character(
-      reinterpret_cast<const unsigned char *>(src), c, n);
+      reinterpret_cast<const unsigned char *>(src),
+      static_cast<unsigned char>(c), n);
 }
 
 } // namespace __llvm_libc

libc/src/string/memcpy.cpp

 //   implementation parameters.
 // - As compilers and processors get better, the generated code is improved
 //   with little change on the code side.
-static void memcpy_impl(char *__restrict dst, const char *__restrict src,
-                        size_t count) {
+static void memcpy_impl(unsigned char *__restrict dst,
+                        const unsigned char *__restrict src, size_t count) {
   // Use scalar strategies (_1, _2, _3 ...)
   using namespace __llvm_libc::scalar;
 

 LLVM_LIBC_FUNCTION(void *, memcpy,
                    (void *__restrict dst, const void *__restrict src,
                     size_t size)) {
-  memcpy_impl(reinterpret_cast<char *>(dst),
-              reinterpret_cast<const char *>(src), size);
+  memcpy_impl(reinterpret_cast<unsigned char *>(dst),
+              reinterpret_cast<const unsigned char *>(src), size);
   return dst;
 }
 

libc/src/string/memmove.cpp

 
 namespace __llvm_libc {
 
-static inline void move_byte_forward(char *dest_m, const char *src_m,
-                                     size_t count) {
+static inline void move_byte_forward(unsigned char *dest_m,
+                                     const unsigned char *src_m, size_t count) {
   for (size_t offset = 0; count; --count, ++offset)
     dest_m[offset] = src_m[offset];
 }
 
-static inline void move_byte_backward(char *dest_m, const char *src_m,
+static inline void move_byte_backward(unsigned char *dest_m,
+                                      const unsigned char *src_m,
                                       size_t count) {
   for (size_t offset = count - 1; count; --count, --offset)
     dest_m[offset] = src_m[offset];

 
 LLVM_LIBC_FUNCTION(void *, memmove,
                    (void *dest, const void *src, size_t count)) {
-  char *dest_c = reinterpret_cast<char *>(dest);
-  const char *src_c = reinterpret_cast<const char *>(src);
+  unsigned char *dest_c = reinterpret_cast<unsigned char *>(dest);
+  const unsigned char *src_c = reinterpret_cast<const unsigned char *>(src);
 
   // If the distance between src_c and dest_c is equal to or greater
   // than count (integerAbs(src_c - dest_c) >= count), they would not overlap.

   // TODO: Optimize `move_byte_xxx(...)` functions.
   if (dest_c < src_c)
     move_byte_forward(dest_c, src_c, count);
-  if (dest_c > src_c)
+  else if (dest_c > src_c)
     move_byte_backward(dest_c, src_c, count);
   return dest;
 }

libc/src/string/memory_utils/elements.h

 void Copy(char *__restrict dst, const char *__restrict src) {
   Element::Copy(dst, src);
 }
+template <typename Element>
+void Copy(unsigned char *__restrict dst, const unsigned char *__restrict src) {
+  Element::Copy(dst, src);
+}
 // Runtime-size copies from 'src' to 'dst'.
 template <typename Element>
 void Copy(char *__restrict dst, const char *__restrict src, size_t size) {
   Element::Copy(dst, src, size);
 }
+template <typename Element>
+void Copy(unsigned char *__restrict dst, const unsigned char *__restrict src, size_t size) {
+  Element::Copy(dst, src, size);
+}
 
 // Fixed-size equality between 'lhs' and 'rhs'.
 template <typename Element> bool Equals(const char *lhs, const char *rhs) {

     __llvm_libc::Copy<Head>(dst, src);
   }
 
+  static void Copy(unsigned char *__restrict dst, const unsigned char *__restrict src) {
+    Chained<Tail...>::Copy(dst + Head::kSize, src + Head::kSize);
+    __llvm_libc::Copy<Head>(dst, src);
+  }
+
   static bool Equals(const char *lhs, const char *rhs) {
     if (!__llvm_libc::Equals<Head>(lhs, rhs))
       return false;

libc/src/string/memrchr.cpp

 
 LLVM_LIBC_FUNCTION(void *, memrchr, (const void *src, int c, size_t n)) {
   const unsigned char *str = reinterpret_cast<const unsigned char *>(src);
-  const unsigned char ch = c;
+  const unsigned char ch = static_cast<unsigned char>(c);
   for (; n != 0; --n) {
-    const unsigned char *s = str + n - 1;
-    if (*s == ch)
-      return const_cast<unsigned char *>(s);
+    if (*(--str) == ch)
+      return const_cast<unsigned char *>(str);
   }
   return nullptr;
 }

libc/src/string/strchr.cpp

 
 // TODO: Look at performance benefits of comparing words.
 LLVM_LIBC_FUNCTION(char *, strchr, (const char *src, int c)) {
-  unsigned char *str =
-      const_cast<unsigned char *>(reinterpret_cast<const unsigned char *>(src));
-  const unsigned char ch = c;
-  for (; *str && *str != ch; ++str)
-    ;
-  return *str == ch ? reinterpret_cast<char *>(str) : nullptr;
+  const char ch = static_cast<char>(c);
+  for (; *src != ch; ++src)
+    if (*src == '\0')
+      return nullptr;
+
+  return const_cast<char *>(src);
 }
 
 } // namespace __llvm_libc

libc/src/string/strcpy.cpp

 //===----------------------------------------------------------------------===//
 
 #include "src/string/strcpy.h"
-#include "src/string/memcpy.h"
-#include "src/string/string_utils.h"
-
 #include "src/__support/common.h"
+#include "src/string/memory_utils/elements.h"
+#include "src/string/string_utils.h"
 
 namespace __llvm_libc {
 
+// Design rationale
+// ================
+//
+// Using a profiler to observe size distributions for calls into libc
+// functions, it was found most operations act on a small number of bytes.
+// This makes it important to favor small sizes.
+//
+// The tests for `count` are in ascending order so the cost of branching is
+// proportional to the cost of copying.
+//
+// The function is written in C++ for several reasons:
+// - The compiler can __see__ the code, this is useful when performing Profile
+//   Guided Optimization as the optimized code can take advantage of branching
+//   probabilities.
+// - It also allows for easier customization and favors testing multiple
+//   implementation parameters.
+// - As compilers and processors get better, the generated code is improved
+//   with little change on the code side.
+static void strcpy_impl(char *__restrict dst, const char *__restrict src,
+                        size_t count) {
+  // Use scalar strategies (_1, _2, _3 ...)
+  using namespace __llvm_libc::scalar;
+
+  if (count == 0)
+    return;
+  if (count == 1)
+    return Copy<_1>(dst, src);
+  if (count == 2)
+    return Copy<_2>(dst, src);
+  if (count == 3)
+    return Copy<_3>(dst, src);
+  if (count == 4)
+    return Copy<_4>(dst, src);
+  if (count < 8)
+    return Copy<HeadTail<_4>>(dst, src, count);
+  if (count < 16)
+    return Copy<HeadTail<_8>>(dst, src, count);
+  if (count < 32)
+    return Copy<HeadTail<_16>>(dst, src, count);
+  if (count < 64)
+    return Copy<HeadTail<_32>>(dst, src, count);
+  if (count < 128)
+    return Copy<HeadTail<_64>>(dst, src, count);
+  return Copy<Align<_32, Arg::Src>::Then<Loop<_32>>>(dst, src, count);
+}
+
 LLVM_LIBC_FUNCTION(char *, strcpy,
                    (char *__restrict dest, const char *__restrict src)) {
-  return reinterpret_cast<char *>(
-      __llvm_libc::memcpy(dest, src, internal::string_length(src) + 1));
+  strcpy_impl(dest, src, internal::string_length(src) + 1);
+  return dest;
 }
 
 } // namespace __llvm_libc

libc/src/string/string_utils.h

 // Returns the length of a string, denoted by the first occurrence
 // of a null terminator.
 static inline size_t string_length(const char *src) {
-  size_t length;
-  for (length = 0; *src; ++src, ++length)
+  const char *const initial = src;
+  for (; *src != '\0'; ++src)
     ;
-  return length;
+  return src - initial;
 }
 
 // Returns the first occurrence of 'ch' within the first 'n' characters of
 // 'src'. If 'ch' is not found, returns nullptr.
 static inline void *find_first_character(const unsigned char *src,
                                          unsigned char ch, size_t n) {
-  for (; n && *src != ch; --n, ++src)
-    ;
-  return n ? const_cast<unsigned char *>(src) : nullptr;
+  for (; n != 0; --n, ++src)
+    if (*src == ch)
+      return const_cast<unsigned char *>(src);
+  return nullptr;
 }
 
 // Returns the maximum length span that contains only characters not found in
 // 'segment'. If no characters are found, returns the length of 'src'.
 static inline size_t complementary_span(const char *src, const char *segment) {
-  const char *initial = src;
+  const char *const initial = src;
   cpp::Bitset<256> bitset;
 
-  for (; *segment; ++segment)
+  for (; *segment != '\0'; ++segment)
     bitset.set(*segment);
-  for (; *src && !bitset.test(*src); ++src)
+  for (; *src != '\0' && !bitset.test(*src); ++src)
     ;
   return src - initial;
 }

                                  const char *__restrict delimiter_string,
                                  char **__restrict saveptr) {
   cpp::Bitset<256> delimiter_set;
-  for (; *delimiter_string; ++delimiter_string)
+  for (; *delimiter_string != '\0'; ++delimiter_string)
     delimiter_set.set(*delimiter_string);
 
   src = src ? src : *saveptr;
-  for (; *src && delimiter_set.test(*src); ++src)
+  for (; *src != '\0' && delimiter_set.test(*src); ++src)
     ;
-  if (!*src) {
+  if (*src == '\0') {
     *saveptr = src;
     return nullptr;
   }
   char *token = src;
-  for (; *src && !delimiter_set.test(*src); ++src)
+  for (; *src != '\0' && !delimiter_set.test(*src); ++src)
     ;
-  if (*src) {
-    *src = '\0';
-    ++src;
+  if (*src != '\0') {
+    *src++ = '\0';
   }
   *saveptr = src;
   return token;

libc/src/string/strrchr.cpp

 namespace __llvm_libc {
 
 LLVM_LIBC_FUNCTION(char *, strrchr, (const char *src, int c)) {
-  const char ch = c;
+  const char ch = static_cast<char>(c);
   char *last_occurrence = nullptr;
   do {
     if (*src == ch)
       last_occurrence = const_cast<char *>(src);
-  } while (*src++);
+  } while (*src++ != '\0');
   return last_occurrence;
 }