Doing some profiling I found a good portion of time and memory was being spent in rune-in-range-p among others. Investigating the source I found a comment in german that google translates into something like "that can be done nevertheless better". So I did.
We now use a binary search instead of a linear search. Type declarations (simple-vector) helped a bit on sbcl. As well as rune-name-char-p had been calling rune-in-range-p with each of a bunch of different lists. So I combined these lists at compile time, and search through the sorted list once.
Some tests I did (each one twice):
;;ORGINAL seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.075 | 1,266,472 | 43,752 | 0.000002 | RUNE-IN-RANGE-P 0.010 | 804,632 | 34,574 | 0.0000003 | RUNE-NAME-CHAR-P 0.000 | 1,018,912 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.085 | 3,090,016 | 82,996 | | Total seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.067 | 1,222,936 | 43,752 | 0.000002 | RUNE-IN-RANGE-P 0.003 | 1,078,888 | 34,574 | 0.0000001 | RUNE-NAME-CHAR-P 0.000 | 1,036,544 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.070 | 3,338,368 | 82,996 | | Total
;;NEW seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.043 | 0 | 37,001 | 0.000001 | RUNE-IN-RANGE-P 0.000 | 833,704 | 34,574 | 0.000000 | RUNE-NAME-CHAR-P 0.000 | 1,056,296 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.043 | 1,890,000 | 76,245 | | Total seconds | consed | calls | sec/call | name -------------------------------------------------------- 0.028 | 0 | 37,001 | 0.000001 | RUNE-IN-RANGE-P 0.000 | 808,528 | 34,574 | 0.000000 | RUNE-NAME-CHAR-P 0.000 | 1,116,776 | 4,670 | 0.000000 | VALID-NAME-P -------------------------------------------------------- 0.028 | 1,925,304 | 76,245 | | Total
Nathan Bird
Hi,
Quoting Nathan Bird (nathan@acceleration.net):
Doing some profiling I found a good portion of time and memory was being spent in rune-in-range-p among others. Investigating the source I found a comment in german that google translates into something like "that can be done nevertheless better". So I did.
first of all, thank you very much for working on speed issues.
However, I have to admit that my characters.lisp duplicates work already done by Gilbert. Gilbert's functions are in xml-name-rune-p.lisp and are using inline functions accessing bitvectors. Embarrassingly, I didn't notice the latter file before writing characters.lisp and then just stuck a comment into the file instead of fixing it right away. My apologies for that -- and sorry for writing that comment in german. :-(
We now use a binary search instead of a linear search. Type declarations (simple-vector) helped a bit on sbcl. As well as rune-name-char-p had been calling rune-in-range-p with each of a bunch of different lists. So I combined these lists at compile time, and search through the sorted list once.
That seems cool, but it would really be good to see how fast the bit vector implementation is compared to binary search, and then to unify the two files, probably by dropping one of them.
It would be great if you have the time to do this, otherwise I will eventually look at it myself.
Thank you, David
-
David Lichteblau -
Nathan Bird