Faster ll2string() implementation.

Based on ideas documented in this blog post:

https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

The original code was modified to handle signed integers, reformetted to
fit inside the Redis code base, and was stress-tested with a program
in order to validate the implementation against snprintf().

Redis was measured to be measurably faster from the point of view of
clients in real-world operations because of this change, since sometimes
number to string conversion is used extensively (for example every time
a GET results into an integer encoded object to be returned to the
user).

1 files changed, 80 insertions, 21 deletions

diff --git a/src/util.c b/src/util.c
index 664c82b80..74ed8a043 100644
--- a/src/util.c
+++ b/src/util.c
@@ -214,28 +214,87 @@ long long memtoll(const char *p, int *err) {
     return val*mul;
 }
 
+/* Return the number of digits of 'v' when converted to string in radix 10.
+ * See ll2string() for more information. */
+uint32_t digits10(uint64_t v) {
+    if (v < 10) return 1;
+    if (v < 100) return 2;
+    if (v < 1000) return 3;
+    if (v < 1000000000000UL) {
+        if (v < 100000000UL) {
+            if (v < 1000000) {
+                if (v < 10000) return 4;
+                return 5 + (v >= 100000);
+            }
+            return 7 + (v >= 10000000UL);
+        }
+        if (v < 10000000000UL) {
+            return 9 + (v >= 1000000000UL);
+        }
+        return 11 + (v >= 100000000000UL);
+    }
+    return 12 + digits10(v / 1000000000000UL);
+}
+
 /* Convert a long long into a string. Returns the number of
- * characters needed to represent the number, that can be shorter if passed
- * buffer length is not enough to store the whole number. */
-int ll2string(char *s, size_t len, long long value) {
-    char buf[32], *p;
-    unsigned long long v;
-    size_t l;
-
-    if (len == 0) return 0;
-    v = (value < 0) ? -value : value;
-    p = buf+31; /* point to the last character */
-    do {
-        *p-- = '0'+(v%10);
-        v /= 10;
-    } while(v);
-    if (value < 0) *p-- = '-';
-    p++;
-    l = 32-(p-buf);
-    if (l+1 > len) l = len-1; /* Make sure it fits, including the nul term */
-    memcpy(s,p,l);
-    s[l] = '\0';
-    return l;
+ * characters needed to represent the number.
+ * If the buffer is not big enough to store the string, 0 is returned.
+ *
+ * Based on the following article (that apparently does not provide a
+ * novel approach but only publicizes an already used technique):
+ *
+ * https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920
+ *
+ * Modified in order to handle signed integers since the original code was
+ * designed for unsigned integers. */
+int ll2string(char* dst, size_t dstlen, long long svalue) {
+    static const char digits[201] =
+        "0001020304050607080910111213141516171819"
+        "2021222324252627282930313233343536373839"
+        "4041424344454647484950515253545556575859"
+        "6061626364656667686970717273747576777879"
+        "8081828384858687888990919293949596979899";
+    int negative;
+    unsigned long long value;
+
+    /* The main loop works with 64bit unsigned integers for simplicity, so
+     * we convert the number here and remember if it is negative. */
+    if (svalue < 0) {
+        value = -svalue;
+        negative = 1;
+    } else {
+        value = svalue;
+        negative = 0;
+    }
+
+    /* Check length. */
+    uint32_t const length = digits10(value)+negative;
+    if (length >= dstlen) return 0;
+
+    /* Null term. */
+    uint32_t next = length;
+    dst[next] = '\0';
+    next--;
+    while (value >= 100) {
+        int const i = (value % 100) * 2;
+        value /= 100;
+        dst[next] = digits[i + 1];
+        dst[next - 1] = digits[i];
+        next -= 2;
+    }
+
+    /* Handle last 1-2 digits. */
+    if (value < 10) {
+        dst[next] = '0' + (uint32_t) value;
+    } else {
+        int i = (uint32_t) value * 2;
+        dst[next] = digits[i + 1];
+        dst[next - 1] = digits[i];
+    }
+
+    /* Add sign. */
+    if (negative) dst[0] = '-';
+    return length;
 }
 
 /* Convert a string into a long long. Returns 1 if the string could be parsed