From owner-svn-src-all@FreeBSD.ORG Fri May 3 20:48:40 2013 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by hub.freebsd.org (Postfix) with ESMTP id 859B4ED0; Fri, 3 May 2013 20:48:40 +0000 (UTC) (envelope-from pluknet@gmail.com) Received: from mail-wi0-x22a.google.com (mail-wi0-x22a.google.com [IPv6:2a00:1450:400c:c05::22a]) by mx1.freebsd.org (Postfix) with ESMTP id 7926F136D; Fri, 3 May 2013 20:48:39 +0000 (UTC) Received: by mail-wi0-f170.google.com with SMTP id hq12so1121157wib.5 for ; Fri, 03 May 2013 13:48:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type; bh=3XogMX/q2KUQF44N3E9Auwt27FvBpe6T6vwz4sRgrQE=; b=cwZsTPiDBjG3eydxRKrBU/W/vzhs9DFINMGL0gUIgOX47Xi9ccjOro5y13pjI2I5ZW sgX0NuORjvppOCX3WJd3V8C8obTVVkubiyHFilZ/rE9FVAB0XBs0dzB/ZhsY3hdQjbLz x2M55f7crLJ1G4fdxROL2IZgibezYXL/DkFXFWlTgeUDr34cIc93QNAHOcnUkXXA4l+I LE58lt8lbF2boex/FxgM3hXesJOnquaPAq5u25BsEOtultdW8yikxVbEDdIKm2gCHkqV L3wFBRUD5yWlzKnBXr4tJdG5bhZ3ygjtOzH3VvyawNjt+W+HhW5qFFMf+A4XnTbJMhhN IS8Q== MIME-Version: 1.0 X-Received: by 10.194.92.231 with SMTP id cp7mr16030959wjb.3.1367614118676; Fri, 03 May 2013 13:48:38 -0700 (PDT) Sender: pluknet@gmail.com Received: by 10.194.29.199 with HTTP; Fri, 3 May 2013 13:48:38 -0700 (PDT) In-Reply-To: <20130503195540.GA52657@stack.nl> References: <201305031552.r43FqiPN024580@svn.freebsd.org> <5183E899.4000503@freebsd.org> <20130503195540.GA52657@stack.nl> Date: Sat, 4 May 2013 00:48:38 +0400 X-Google-Sender-Auth: StXQvw9ial6WGk3GnWKPyi32r_A Message-ID: Subject: Re: svn commit: r250215 - stable/9/lib/libc/locale From: Sergey Kandaurov To: Jilles Tjoelker Content-Type: text/plain; charset=ISO-8859-1 Cc: svn-src-stable@freebsd.org, svn-src-all@freebsd.org, src-committers@freebsd.org, Andrey Chernov , svn-src-stable-9@freebsd.org X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 May 2013 20:48:40 -0000 On 3 May 2013 23:55, Jilles Tjoelker wrote: > On Fri, May 03, 2013 at 09:49:05PM +0400, Sergey Kandaurov wrote: >> On 3 May 2013 20:40, Andrey Chernov 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