[Openmcl-devel] Re: [cl-ppcre-devel] cl-ppcre speedup

[Gary Byers]

On Wed, 15 Dec 2004, Alan Ruttenberg wrote:

> Actually, closer to a 3x speedup.
>
> (DOTIMES (I 1000000) (CL-PPCRE:SCAN "(\\S+)\\s*(.*)" "DE
> Halobacterium halobium ribosomal proteins, partial and complete")) took
> 14,655 milliseconds (14.655 seconds) to run.
>
> vs.
>
> (DOTIMES (I 1000000) (CL-PPCRE:SCAN "(\\S+)\\s*(.*)" "DE
> Halobacterium halobium ribosomal proteins, partial and complete")) took
> 4,989 milliseconds (4.989 seconds) to run.
>
> -Alan
>
> On Dec 15, 2004, at 1:13 AM, Alan Ruttenberg wrote:
>
> > I was profiling the following expression
> >
> > (cl-ppcre::scan "(\\S+)\\s*(.*)" "DE   Halobacterium halobium
> > ribosomal proteins, partial and complete")
> >
> > and char=, char/= and char<= were coming up highest in the breakdown.

Can you tell whether SPreq_stack_rest_arg (if I'm spelling that right
...) was a significant part of that, or is it spending most of the time
in the functions ?

(If you consider that CHAR<= and friends don't really do much that's
particularly expensive, it's not too surprising that doing that inline
would be faster than going out of line, building a (typically small)
&REST arg on the stack, and then doing a few CHAR-CODEs and fixnum
comparisons.  Of all of those things, stack-consing an &REST arg is
probably the most expensive - and native threads/GC concerns make
it more expensive than it might seem.)


> >
> > One way to conservatively fix (least number of edits to the source)
> > would be the following, which gets about a factor of 2x for the above
> > expression.
> > Arguably, this might be considered for inclusion in openmcl proper.

>From what I saw, your compiler-macro both unrolled the loop and skipped
typechecking.  I'd guess (and this is just a guess) that the first part
of this is more significant and generally worth doing (if you want
the extra speed > safety tradeoff, you should get that independently.)

E.g, if (CHAR<= X Y Z)

macroexpanded into something like:

(let* ((#:code (char-code X)))
  (declare (fixnum #:code))
  (and (<= #:code (setq #:code (char-code y)))
       (<= #:code (char-code z))))

you'd probably be winning pretty significantly already (and whether
you want to ship the typechecking in CHAR-CODE or live even more
dangerously is a separate issue.)

> >
> > Similar could be done for char-equal etc.
>

I wonder if there's a clever way to inline CHAR-UPCASE/CHAR-DOWNCASE ?
(There are obviously straightforward ways to do this; it's sometimes
faster to do this via table lookup, but there may be ways to do this
without conditional branches or memory references.)