From db00fb238be221f58414d5b5763321706e262f24 Mon Sep 17 00:00:00 2001
From: KOBAYASHI Shuji <shuujii@gmail.com>
Date: Tue, 24 Nov 2020 16:30:52 +0900
Subject: Optimize `presym_find`

Chang to compare string length first.

### Benchmark

#### Code

* https://github.com/shuujii/mruby-presym_find-benchmark

#### Result

```console
Previous: 10.240772M i/s (25M times in 2.441222s)
     New: 16.412985M i/s (25M times in 1.523184s)
```
---
 src/symbol.c | 30 ++++++++++--------------------
 1 file changed, 10 insertions(+), 20 deletions(-)

(limited to 'src')

diff --git a/src/symbol.c b/src/symbol.c
index daff23c36..c94f6f239 100644
--- a/src/symbol.c
+++ b/src/symbol.c
@@ -21,33 +21,23 @@ static const struct {
   uint16_t len;
 } presym_table[] = {
 #include <../build/presym.inc>
-  {0,0}
 };
 
 static mrb_sym
 presym_find(const char *name, size_t len)
 {
-  int start = 0;
-  int end = MRB_PRESYM_MAX-1;
-
-  while (start<=end) {
-    int mid = (start+end)/2;
-    size_t plen = presym_table[mid].len;
-    size_t tlen = (plen > len) ? len : plen;
-    int cmp;
-
-    cmp = memcmp(name, presym_table[mid].name, tlen);
+  mrb_sym start, idx, presym_size = MRB_PRESYM_MAX;
+  int cmp;
+  for (start = 0; presym_size != 0; presym_size/=2) {
+    idx = start+presym_size/2;
+    cmp = len-presym_table[idx].len;
     if (cmp == 0) {
-      if (len > plen) cmp = 1;
-      else if (len < plen) cmp = -1;
+      cmp = memcmp(name, presym_table[idx].name, len);
+      if (cmp == 0) return idx+1;
     }
-
-    if (cmp == 0) {
-      return mid+1;
-    } else if (cmp > 0) {
-      start = mid+1;
-    } else {
-      end = mid-1;
+    if (0 < cmp) {
+      start = ++idx;
+      --presym_size;
     }
   }
   return 0;
-- 
cgit v1.2.3