Re: fmatch

[Ludovic Courtès]

Hello!

stefan <address@hidden> writes:

>> > large patterns yield a speedup of 15 times acording to my tests compared
>> > with (ice-9 match).
>> >
>> > I used guile-1.9.10. Does this release have a lot of checks compiled in
>> > so that the comparison is unfair?
>> 
>> All list/pair accessors type-check their arguments (this has always been
>> the case with Guile so that Scheme code cannot yield to segfaults and
>> the like.)
>
> usually the generated match code is somehting like
> (if (pair? x)
>     (if (equal? x data)
>         (let a34 (cdr x) ...)
>       (goto-next))
>     (goto-next))
>
> And the checks are already there. So for this isolated system in should
> be fine to skip the check. But I don't think it explains the speed 
> difference.

Agreed.

> The core of the matcher is a loop with a set of if's arranged so that in the 
> mean it will do 2-3 checks and then find the instruction, so no named labels.

You mean no “labels as values” (info "(gcc) Labels as Values"), right?

> the core of the code look like,
>   #define M_CONTINUE {pat ++; continue;}
>   while(1)
>     {    
>       //printf("match-instruction (*)> %d\n",((int) Ix) >> 2);fflush(stdout);
>       if(SCM_UNLIKELY(Ix == i_cons))
>       {
>         if(SCM_CONSP(x))
>           {
>             PUSH(SCM_CDR(x));
>             x = SCM_CAR(x);
>             M_CONTINUE;
>           }
>         goto return_false;
>       }

Hmmmm.  My first reaction is that I’d rather avoid complex VM
instructions like this and instead focus on native compilation (AOT or
JIT) when we feel like improving performance.

What do you think?

[...]

> I also have similar code for usage in prolog like matching e.g. unfication +
>  backtracking I would expect at least the same speedup here. Note that for 
> this application a pure unwinding of the logic, similar to the match macro 
> will yield very bloated code and going for a targeted virtual machine will 
> make 
> for lean and efficient code.
>
> I hope that in the end a prolog implementation using this approach would be 
> 3-4
> times slower that what you have with a more targeted platform like gnu prolog.

This all sounds like exciting work!

> So in a sense this is a test of what you want. Compare the speed difference 
> of 
> using c-based or scheme based solution. Still I expect the macth construct to 
> be easier to hack and improve uppon and at some point a direct match version 
> will win because you can compile it naitively.

Well, until 1.8, the focus in Guile had been to write the “hot spots” in
C, for performance.  However, that doesn’t scale well and leads to a
hard to maintain code base (we want to write Scheme in the first place,
not C).

For 2.2 and beyond, I really think the focus should be on allowing hot
spots to be written in Scheme, which means compiling Scheme code
natively.  This would be beneficial to all Scheme code, not just this
specific pattern matching construct.

Thanks,
Ludo’.