better addInt (#16160)

* better addint
* Update lib/system/strmantle.nim

Co-authored-by: Juan Carlos <juancarlospaco@gmail.com>

1 files changed, 81 insertions, 15 deletions

diff --git a/lib/system/strmantle.nim b/lib/system/strmantle.nim
index fa6ff411b..b5d275e25 100644
--- a/lib/system/strmantle.nim
+++ b/lib/system/strmantle.nim
@@ -9,6 +9,72 @@
 
 # Compilerprocs for strings that do not depend on the string implementation.
 
+const digitsTable = "0001020304050607080910111213141516171819" &
+    "2021222324252627282930313233343536373839" &
+    "4041424344454647484950515253545556575859" &
+    "6061626364656667686970717273747576777879" &
+    "8081828384858687888990919293949596979899"
+  # Inspired by https://engineering.fb.com/2013/03/15/developer-tools/three-optimization-tips-for-c
+  # Generates:
+  # .. code-block:: nim
+  #   var res = ""
+  #   for i in 0 .. 99:
+  #     if i < 10:
+  #       res.add "0" & $i
+  #     else:
+  #       res.add $i
+  #   doAssert res == digitsTable
+  
+
+func digits10(num: uint64): int {.noinline.} =
+  if num < 10:
+    result = 1
+  elif num < 100:
+    result = 2
+  elif num < 1_000:
+    result = 3
+  elif num < 10_000:
+    result = 4
+  elif num < 100_000:
+    result = 5
+  elif num < 1_000_000:
+    result = 6
+  elif num < 10_000_000:
+    result = 7
+  elif num < 100_000_000:
+    result = 8
+  elif num < 1_000_000_000:
+    result = 9
+  elif num < 10_000_000_000'u64:
+    result = 10
+  elif num < 100_000_000_000'u64:
+    result = 11
+  elif num < 1_000_000_000_000'u64:
+    result = 12
+  else:
+    result = 12 + digits10(num div 1_000_000_000_000'u64)
+
+template numToString(result: var string, origin: uint64, length: int) =
+  var num = origin
+  var next = length - 1
+  const nbatch = 100
+
+  while num >= nbatch:
+    let originNum = num
+    num = num div nbatch
+    let index = (originNum - num * nbatch) shl 1
+    result[next] = digitsTable[index + 1]
+    result[next - 1] = digitsTable[index]
+    dec(next, 2)
+
+  # process last 1-2 digits
+  if num < 10:
+    result[next] = chr(ord('0') + num)
+  else:
+    let index = num * 2
+    result[next] = digitsTable[index + 1]
+    result[next - 1] = digitsTable[index]
+
 proc cmpStrings(a, b: string): int {.inline, compilerproc.} =
   let alen = a.len
   let blen = b.len
@@ -49,22 +115,22 @@ proc addInt*(result: var string; x: int64) =
   ##     b = 45
   ##   a.addInt(b) # a <- "12345"
   let base = result.len
-  setLen(result, base + sizeof(x)*4)
-  var i = 0
-  var y = x
-  while true:
-    var d = y div 10
-    result[base+i] = chr(abs(int(y - d*10)) + ord('0'))
-    inc(i)
-    y = d
-    if y == 0: break
+  var length: int
+  var num: uint64
+
   if x < 0:
-    result[base+i] = '-'
-    inc(i)
-  setLen(result, base+i)
-  # mirror the string:
-  for j in 0..i div 2 - 1:
-    swap(result[base+j], result[base+i-j-1])
+    if x == low(int64):
+      num = uint64(x)
+    else:
+      num = uint64(-x)
+    length = base + digits10(num) + 1
+    setLen(result, length)
+    result[base] = '-'
+  else:
+    num = uint64(x)
+    length = base + digits10(num)
+    setLen(result, length)
+  numToString(result, num, length)
 
 proc nimIntToStr(x: int): string {.compilerRtl.} =
   result = newStringOfCap(sizeof(x)*4)