Optimize `presym_find`
Chang to compare string length first.
### Benchmark
#### Code
*
#### Result
```console
Previous: 10.240772M i/s (25M times in 2.441222s)
New: 16.412985M i/s (25M times in 1.523184s)
```
MODIFY
Rakefile
Rakefile
@@ -192,7 +192,7 @@ file presym_file => cfiles+rbfiles+psfiles+[__FILE__] do
src.scan(/[ \(\[\{]:'([^']+)'/)
]
end
- symbols = (symbols+csymbols+rbsymbols+op_table.keys).flatten.compact.uniq.sort.grep_v(/#/).map{|x| x.gsub("\n", '\n')}
+ symbols = (symbols+csymbols+rbsymbols+op_table.keys).flatten.compact.uniq.grep_v(/#/).map{|x| x.gsub("\n", '\n')}.sort_by!{|x| [x.bytesize, x]}
presyms = File.readlines(presym_file) rescue []
presyms.each{|x| x.chomp!}
if presyms != symbols

MODIFY
src/symbol.c
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;
+ mrb_sym start, idx, presym_size = MRB_PRESYM_MAX;
int cmp;
-
- cmp = memcmp(name, presym_table[mid].name, tlen);
+ 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;

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)
```