William Harold Newman <william.newman@...> writes:
> On Sat, Dec 06, 2003 at 07:27:36PM +0000, Christophe Rhodes wrote:
>> There are TODOs marked, to which I would add "deuglification". Other
>> comments welcome.
> It's neat, and it would be nice for our benchmark scores:-) but I'm
> not convinced that it's an appropriate thing to build into the compiler:
> * I'm hard-pressed to imagine cases (other than FILL-STRINGS) where
> an application would really care deeply about its performance for
> this case of SEARCH. I would guess that almost every application
> which spends a measurable amount of time on this case will spend a
> negligible proportion of time on it, being I/O bound.
As I say (I can't remember if I did, actually), for the benchmark's
purposes the Boyer-Mooreness of it doesn't win very much; what's
important is removing the generic array access to specialized access.
The current implementation of SEARCH does O(MN) _unspecialized_
(i.e. HAIRY-DATA-VECTOR-REF) accesses to its arguments, which
represents most of the improvements. So if this itself doesn't go in,
I'd still recommend doing _something_ about the suboptimal
string-in-string search, because I think searching for strings in
strings is more common than searching for generic vectors in other
generic vectors. Having a specialized transform that either opencodes
the simple search or calls a specialized routine is perfectly
plausible, of course; cmucl does the latter with its search transform.
> * It looks mostly portable (e.g. as a compiler macro unportably added
> to CL:SEARCH, or as an inline function SEARCH-FAST, or something;
> modulo safe-in-SBCL assumptions like 256 characters). Thus, even if
> someone does come up with an app which wants performance here, it's
> not clear that it should be provided by a clever transform embedded
> in a general-purpose compiler.
Yeah, though that 256 character assumption might not be safe for too
much longer... last year, at the UK SBCL AGM Dan and I agreed that
Unicode wasn't going to happen this year barring outside intervention;
this year, I'm more inclined to be aggressive about it.
(Aside: the UK SBCL AGM, otherwise known as "Dan and Christophe have
lunch", will probably happen sometime later this month. If anyone's
in London between Christmas and the New Year, or else in early
January, and would like to have a drink, say so!)
> If it does go into the compiler, it should probably be conditional on
> (> SPEED SPACE), [...]
Oh yes, definitely. A conversion to a call to a specialized search
function for simple-base-strings is less space-hungry, and might make
a good compromise, either for all compilation policies or for
(>= SPEED SPACE).
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)