From: Dimiter "malkia" Stanev
Subject: Re: From the Beautiful Code Book, Chapter 1, A Regular Expression Matcher
Date:
Message-ID: <5irvbgF3pundfU1@mid.individual.net>
> Overall, this looks pretty good. However, my impression is that you
> blindly added a lot of type declarations. It may be worthwhile to try a
> few benchmarks and selectively remove some of the declarations to see
> which ones actually buy you something. In general, declarations should
> be used sparingly.
Thanks, Pascal!
>
>> (declaim (optimize (speed 3) (safety 0) (debug 0)
>> (space 0) (compilation-speed 0)
>> #+lispworks (hcl:fixnum-safety 0)))
>
> These are extreme settings. You shouldn't declaim such settings. Keep in
> mind that a declamation is global, so your whole program will be
> affected by it. Some CL compilers do pretty harsh optimizations if you
> use such extreme settings. For example, it may be that if your programs
> contains a buggy endless loop, that you cannot get out of it again but
> have to reboot your computer. So be a little more careful here.
I'm really pushing it as much as I can, so I can compare the C version
to the lisp one.
Now I understand why CL-PPCRE is so fast :) - As you told me - it
generates code!
I'll see whether I can do it too :)
Cheers,
Dimiter "malkia" Stanev.
From: Razvan Mihai
Subject: Re: From the Beautiful Code Book, Chapter 1, A Regular Expression Matcher
Date:
Message-ID: <5isukcF3rdcvmU1@mid.individual.net>
Hello,
On Sun, 19 Aug 2007 15:42:55 -0700, Dimiter \"malkia\" Stanev wrote:
> [...]
> I'm really pushing it as much as I can, so I can compare the C version
> to the lisp one.
your code doesn't implement the equivalent functionality of the C code.
For example:
[1]> (load 'match.lisp)
;; Loading file match.lisp ...
;; Loaded file match.lisp
T
[2]> (match ".*$" "abc")
NIL
Regards,
Razvan
From: Dimiter "malkia" Stanev
Subject: Re: From the Beautiful Code Book, Chapter 1, A Regular Expression Matcher
Date:
Message-ID: <5ito60F3rpiraU1@mid.individual.net>
Thanks for spotting that one! I didn't do any testing.
Here is the fixed version:
(defun match (regexp text)
(declare (type simple-base-string regexp text))
(let ((text-length (length text))
(regexp-length (length regexp)))
(declare (type fixnum text-length regexp-length))
(labels ((match-star (ro to)
(declare (type fixnum ro to))
(let ((c (char regexp (- ro 2))))
(declare (type base-char c))
(if (char= c #\.)
(dotimes (o (1+ (- text-length to)))
(declare (type fixnum o))
(when (match-here ro (+ o to))
(return-from match-star t)))
(dotimes (o (1+ (- text-length to)))
(declare (type fixnum o))
(when (match-here ro (+ o to))
(return-from match-star t))
(when (char/= (char text (+ o to)) c)
(return-from match-star nil)))))
nil)
(match-here (ro to)
(declare (type fixnum ro to))
(cond ((= ro regexp-length)
t)
((and (/= regexp-length (1+ ro))
(char= (char regexp (1+ ro)) #\*))
(match-star (+ ro 2) to))
((and (= regexp-length (1+ ro))
(char= (char regexp ro) #\$))
(= text-length to))
(t (when (and (/= text-length to)
(or (char= (char regexp ro) #\.)
(char= (char regexp ro)
(char text to))))
(match-here (1+ ro) (1+ to)))))))
(cond ((= regexp-length 0)
(= text-length 0))
((char= (char regexp 0) #\^)
(match-here 1 0))
(t (dotimes (o (1+ text-length))
(declare (type fixnum o))
(when (match-here 0 o)
(return-from match t))))))))
Razvan Mihai wrote:
> Hello,
>
> On Sun, 19 Aug 2007 15:42:55 -0700, Dimiter \"malkia\" Stanev wrote:
>
>> [...]
>> I'm really pushing it as much as I can, so I can compare the C version
>> to the lisp one.
>
> your code doesn't implement the equivalent functionality of the C code.
> For example:
>
> [1]> (load 'match.lisp)
> ;; Loading file match.lisp ...
> ;; Loaded file match.lisp
> T
> [2]> (match ".*$" "abc")
> NIL
>
> Regards,
>
> Razvan