Fixed performance bug in UIOP:DIRECTORY-FILES

Faré fahree at gmail.com
Sat Jun 11 12:56:47 UTC 2016


>> I bumped ASDF to 3.1.7.1 after I fixed a performance bug in
>> directory-files that made it quadratic instead of linear, due to some
>> remove-duplicates used for logical-pathnames.
>> The fix was to only use this quadratic behavior for LPNs. If you use
>> LPNs, you deserve to lose on large directories. LPNs are for legacy
>> Lisp code with relatively few files, only.
>
> If you mean that REMOVE-DUPLICATES is quadratic, then it's bad in
> itself (we know better algorithms for linear REMOVE-DUPLICATES);
>
It's quadratic when used with a test that isn't one of the few for
which the implementation knows a compatible hash function.

UIOP is the wrong place to implement a new hash-table implementation
based on a new hash-function just for pathname-equal, then reimplement
remove-duplicates on top of that. And for portability reasons, I can't
just replace pathname-equal by normalization then using equal, or by
using namestrings instead of pathnames, etc.


> There's no reason to disparage logical pathnames, they're very nice.
>
In the abstract, the idea sounds vaguely nice, but the specification
is a disaster, and so are its many incompatible implentations. As for
using DIRECTORY with it... ouch ouch ouch.

—♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• http://fare.tunes.org
I have never let my schooling interfere with my education. — Mark Twain



More information about the asdf-devel mailing list