svn commit: r250215 - stable/9/lib/libc/locale

[Sergey Kandaurov]

On 3 May 2013 23:55, Jilles Tjoelker <jilles at stack.nl> wrote:
> On Fri, May 03, 2013 at 09:49:05PM +0400, Sergey Kandaurov wrote:
>> On 3 May 2013 20:40, Andrey Chernov <ache at freebsd.org> wrote:
>> > I don't think this change is optimal (cause slowdown) since you add
>> > unneeded strlen() in the loop for known-sized elements plus one strlen()
>> > for tested property, and wctype_l() itself can be called very often, so
>> > we definitely don't need slowdown here.
>> > Since most of elements have equal sizes, your len1 == len2 condition
>> > gains almost nothing for valid calls.
>
>> Thanks, you are correct. With this change I got 2-6 times slowdown depending
>> on the specified wctype. I will look at how it can be optimized.
>
> As the original author of this change, I mainly considered programs that
> do not use wctype(), which gain a reduced memory footprint and rtld
> load. For programs that do use it, I expect fewer cache misses because
> there is less pointer chasing.
>
> It is certainly right that sh(1) will call wctype() fairly often if a
> pattern contains a [[:ctype:]] after a *.
>
> If the slowness is because of the strlen() calls, the propnames can be
> constructed like "\5alnum\5alpha"...
>
> The slowness could also be because strcmp() is implemented less badly
> than memcmp(). With the current code, memcmp() can be changed to
> strcmp().
>
> Some sort of perfect hashing can also be an option, although it makes it
> harder to add new properties or adds a build dependency on gperf(1) that
> we would like to get rid of.
>
> Sorry, I have not run my own benchmarks yet.

I hacked a bit on wctype. Speaking about speed, it shows about 1-3.5x
improvement over the previous fast version (before r250215).

Time spend for 2097152 wctype() calls for each of wctype property
                current         previous        mine
alnum           0.090554676     0.035821210     0.033270579
alpha           0.172074310     0.052461036     0.044916572
blank           0.261109989     0.055735281     0.036682745
cntrl           0.357318986     0.069249831     0.038292782
digit           0.436381530     0.094194364     0.039249005
graph           0.540954812     0.085580099     0.043331460
lower           0.618306476     0.095665215     0.044070399
print           0.707443135     0.132559305     0.048216097
punct           0.788922052     0.142809109     0.062871432
space           0.888263108     0.150516644     0.054086142
upper           0.966903461     0.173593592     0.054027834
xdigit          0.406611275     0.201614227     0.060695939
ideogram        0.439763499     0.239640723     0.068566486
special         0.523128094     0.249156298     0.099278051
phonogram       0.564975870     0.260972651     0.135751471
rune            0.637392247     0.235195497     0.064093971

Index: locale/wctype.c
===================================================================
--- locale/wctype.c     (revision 250217)
+++ locale/wctype.c     (working copy)
@@ -74,6 +74,9 @@
                "special\0"     /* BSD extension */
                "phonogram\0"   /* BSD extension */
                "rune\0";       /* BSD extension */
+       static const size_t propnamlen[] = {
+               5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 8, 7, 9, 4, 0
+       };
        static const wctype_t propmasks[] = {
                _CTYPE_A|_CTYPE_D,
                _CTYPE_A,
@@ -92,16 +95,17 @@
                _CTYPE_Q,
                0xFFFFFF00L
        };
-       size_t len1, len2;
+       const size_t *len2;
        const char *p;
        const wctype_t *q;

-       len1 = strlen(property);
        q = propmasks;
-       for (p = propnames; (len2 = strlen(p)) != 0; p += len2 + 1) {
-               if (len1 == len2 && memcmp(property, p, len1) == 0)
+       len2 = propnamlen;
+       for (p = propnames; *len2 != 0; ) {
+               if (property[0] == p[0] && strcmp(property, p) == 0)
                        return (*q);
-               q++;
+               p += *len2 + 1;
+               q++; len2++;
        }

        return (0UL);

-- 
wbr,
pluknet