From patchwork Tue Dec 13 13:20:20 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wilco Dijkstra X-Patchwork-Id: 705399 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3tdL1R2QcXz9t10 for ; Wed, 14 Dec 2016 00:20:43 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b="TRXFJHtz"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:cc:subject:date:message-id :content-type:content-transfer-encoding:mime-version; q=dns; s= default; b=mOAls4igazvTE9RIjce3n6utS9WftFcJM3hn1G/i4uxEEnblPVDBZ PjoDtaC7YTSUqIvHpOu8X4qsBRMDHgiSQPASOh8abWSSXDSpBW3DKZ+I2+k2Lpbx 5SflwVLlX6ZcWzxfHo0xQqIyndxzcHw3GBCsW5XrW4gvaulxTAunVk= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:cc:subject:date:message-id :content-type:content-transfer-encoding:mime-version; s=default; bh=5ImSNfLVhnzEJ6TCF4veeKYZEZc=; b=TRXFJHtz4QmGMQBQaL6ucZm9BXj8 WQIbwU5u2tBe6FFimNMoLEHC9ixN+ouGUjfz07cm3vpKn+kytGtRl5wGJVmGn6Nc he1tjrerr04RgtPY3soWbVwXesmYtzrQEM9h8unAQRqpph5xlr8loBQ+dK1Xxax1 TpuMU6tlndanjos= Received: (qmail 23538 invoked by alias); 13 Dec 2016 13:20:34 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 23522 invoked by uid 89); 13 Dec 2016 13:20:33 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL, BAYES_00, KAM_LOTSOFHASH, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=no version=3.3.2 spammy=UD:string-inlines.c, GLIBC_2_24, **__nextp, 20151213 X-HELO: EUR01-HE1-obe.outbound.protection.outlook.com From: Wilco Dijkstra To: "libc-alpha@sourceware.org" CC: nd Subject: [PATCH v3] Improve strtok(_r) performance Date: Tue, 13 Dec 2016 13:20:20 +0000 Message-ID: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Wilco.Dijkstra@arm.com; x-ms-office365-filtering-correlation-id: c1c46ac1-2c9f-4e26-7312-08d4235ac98f x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001); SRVR:AM5PR0802MB2611; x-microsoft-exchange-diagnostics: 1; AM5PR0802MB2611; 7:gmFfhorWzHFa9u72ot3xM5Jqt2Fj1mUMPa3GHJ8fPqVN+CgfFIL2An33S7TOq3oIrgUffbdQE7+EVo70ffNH0dycU95uZrs/dGjbws2VRky9AnWrL279NUE0JrxZcoFTZvZNOCj170tVBdvp8xwLpkkvOQtNDPKqKFZj8C1Faq91NwGQKmmCwvXWci6wYiRHocTrz+2cmrT6GBNmSQx+V6za+SC0FUWjGZ6s851eVLl+1oaALItmrh8tcUKjhDpZ/ukjI0wClkFH4Dhi4B+Xp8kz9g93eFy7+CE7l24kQ34TvCjWxhZz4NX/BYg0+n7GnzSpha9HHKIz21VeQRAXYRJucWweyn5zfY2aSZwrI8pcwxoLQc47ZQenONZQDW2RaZi4ybKJluBVK1/O9NGVrUVJFgsRzq/1zDm12Zue6M9G8RD07UXz2Onsi84xMCHJz0jy2uRt2AYjgj/DaL1HWg== nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6040375)(601004)(2401047)(5005006)(8121501046)(3002001)(10201501046)(6055026)(6041248)(20161123560025)(20161123555025)(20161123562025)(20161123564025)(6072148); SRVR:AM5PR0802MB2611; BCL:0; PCL:0; RULEID:; SRVR:AM5PR0802MB2611; x-forefront-prvs: 01559F388D x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(7916002)(39850400002)(39840400002)(39450400003)(39410400002)(39860400002)(377424004)(189002)(54534003)(199003)(6916009)(5660300001)(2351001)(105586002)(7736002)(76576001)(77096006)(5640700002)(6506006)(33656002)(110136003)(81166006)(2501003)(81156014)(8676002)(6436002)(106116001)(7696004)(305945005)(106356001)(66066001)(74316002)(38730400001)(86362001)(575784001)(189998001)(68736007)(4001150100001)(97736004)(2900100001)(50986999)(8936002)(6116002)(3846002)(102836003)(122556002)(4326007)(9686002)(101416001)(2906002)(450100001)(54356999)(92566002)(3660700001)(3280700002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM5PR0802MB2611; H:AM5PR0802MB2610.eurprd08.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 13 Dec 2016 13:20:20.0311 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM5PR0802MB2611 Version 3 fixes a minor style issue in bench-strtok.c. Improve strtok and strtok_r performance. Instead of calling strpbrk which calls strcspn, call strcspn directly so we get the end of the token without an extra call to rawmemchr. Also avoid an unnecessary call to strcspn after the last token by adding an early exit for an empty string. Change strtok to tailcall strtok_r to avoid unnecessary code duplication. Remove the special header optimization for strtok_r of a 1-character constant string - both strspn and strcspn contain optimizations for this case. Benchmarking this showed similar performance in the worst case, but up to 5.5x better performance in the "found" case for large inputs. Passes regression tests, OK for commit? ChangeLog: 2015-12-13 Wilco Dijkstra * benchtests/bench-strtok.c (oldstrtok): Add old implementation. * string/strtok.c (strtok): Change to tailcall __strtok_r. * string/strtok_r.c (__strtok_r): Optimize for performance. * string/string-inlines.c (__old_strtok_r_1c): New function. * string/bits/string2.h (__strtok_r): Move to string-inlines.c diff --git a/benchtests/bench-strtok.c b/benchtests/bench-strtok.c index eeb798f01575c712b958ad1b7d5f88f91e158202..41e0e45db818428a3f3a940fa1a70ca3850e84b3 100644 --- a/benchtests/bench-strtok.c +++ b/benchtests/bench-strtok.c @@ -20,13 +20,41 @@ #define TEST_NAME "strtok" #include "bench-string.h" -#define STRTOK strtok_string -#include +char * +oldstrtok (char *s, const char *delim) +{ + static char *olds; + char *token; + + if (s == NULL) + s = olds; + + /* Scan leading delimiters. */ + s += strspn (s, delim); + if (*s == '\0') + { + olds = s; + return NULL; + } + /* Find the end of the token. */ + token = s; + s = strpbrk (token, delim); + if (s == NULL) + /* This token finishes the string. */ + olds = __rawmemchr (token, '\0'); + else + { + /* Terminate the token and make OLDS point past it. */ + *s = '\0'; + olds = s + 1; + } + return token; +} typedef char *(*proto_t) (const char *, const char *); -IMPL (strtok_string, 0) +IMPL (oldstrtok, 0) IMPL (strtok, 1) static void diff --git a/string/bits/string2.h b/string/bits/string2.h index ca1eda9bd127aadb01ab5c929d16621357ddc6e6..e39d4f1a85c25a4f47418e6a5613b27177ca6cbb 100644 --- a/string/bits/string2.h +++ b/string/bits/string2.h @@ -180,45 +180,6 @@ extern void *__rawmemchr (const void *__s, int __c); #endif -#if !defined _HAVE_STRING_ARCH_strtok_r || defined _FORCE_INLINES -# ifndef _HAVE_STRING_ARCH_strtok_r -# define __strtok_r(s, sep, nextp) \ - (__extension__ (__builtin_constant_p (sep) && __string2_1bptr_p (sep) \ - && ((const char *) (sep))[0] != '\0' \ - && ((const char *) (sep))[1] == '\0' \ - ? __strtok_r_1c (s, ((const char *) (sep))[0], nextp) \ - : __strtok_r (s, sep, nextp))) -# endif - -__STRING_INLINE char *__strtok_r_1c (char *__s, char __sep, char **__nextp); -__STRING_INLINE char * -__strtok_r_1c (char *__s, char __sep, char **__nextp) -{ - char *__result; - if (__s == NULL) - __s = *__nextp; - while (*__s == __sep) - ++__s; - __result = NULL; - if (*__s != '\0') - { - __result = __s++; - while (*__s != '\0') - if (*__s++ == __sep) - { - __s[-1] = '\0'; - break; - } - } - *__nextp = __s; - return __result; -} -# ifdef __USE_POSIX -# define strtok_r(s, sep, nextp) __strtok_r (s, sep, nextp) -# endif -#endif - - #if !defined _HAVE_STRING_ARCH_strsep || defined _FORCE_INLINES # ifndef _HAVE_STRING_ARCH_strsep diff --git a/string/string-inlines.c b/string/string-inlines.c index 1091468519e1561ac2a4e9c3ed6eb75ee9fdf43f..d43e5897c37430e5f97940469d65e7ddbdcbd09c 100644 --- a/string/string-inlines.c +++ b/string/string-inlines.c @@ -35,6 +35,36 @@ #include "shlib-compat.h" +#if SHLIB_COMPAT (libc, GLIBC_2_1_1, GLIBC_2_25) +/* The inline functions are not used from GLIBC 2.25 and forward, however + they are required to provide the symbols through string-inlines.c + (if inlining is not possible for compatibility reasons). */ + +char * +__old_strtok_r_1c (char *__s, char __sep, char **__nextp) +{ + char *__result; + if (__s == NULL) + __s = *__nextp; + while (*__s == __sep) + ++__s; + __result = NULL; + if (*__s != '\0') + { + __result = __s++; + while (*__s != '\0') + if (*__s++ == __sep) + { + __s[-1] = '\0'; + break; + } + } + *__nextp = __s; + return __result; +} +compat_symbol (libc, __old_strtok_r_1c, __strtok_r_1c, GLIBC_2_1_1); +#endif + #if SHLIB_COMPAT (libc, GLIBC_2_1_1, GLIBC_2_24) /* The inline functions are not used from GLIBC 2.24 and forward, however they are required to provide the symbols through string-inlines.c diff --git a/string/strtok.c b/string/strtok.c index 7a4574db5c80501e47d045ad4347e8a287b32191..482cdc1da45a71173080b6eff3857e863b5977ea 100644 --- a/string/strtok.c +++ b/string/strtok.c @@ -18,14 +18,6 @@ #include -static char *olds; - -#undef strtok - -#ifndef STRTOK -# define STRTOK strtok -#endif - /* Parse S into tokens separated by characters in DELIM. If S is NULL, the last string strtok() was called with is used. For example: @@ -36,32 +28,8 @@ static char *olds; // s = "abc\0=-def\0" */ char * -STRTOK (char *s, const char *delim) +strtok (char *s, const char *delim) { - char *token; - - if (s == NULL) - s = olds; - - /* Scan leading delimiters. */ - s += strspn (s, delim); - if (*s == '\0') - { - olds = s; - return NULL; - } - - /* Find the end of the token. */ - token = s; - s = strpbrk (token, delim); - if (s == NULL) - /* This token finishes the string. */ - olds = __rawmemchr (token, '\0'); - else - { - /* Terminate the token and make OLDS point past it. */ - *s = '\0'; - olds = s + 1; - } - return token; + static char *olds; + return __strtok_r (s, delim, &olds); } diff --git a/string/strtok_r.c b/string/strtok_r.c index f351304766108dad2c1cff881ad3bebae821b2a0..2d251f90d79b6c546e80e1d25c03955ea8dad92b 100644 --- a/string/strtok_r.c +++ b/string/strtok_r.c @@ -22,14 +22,10 @@ #include -#undef strtok_r -#undef __strtok_r - #ifndef _LIBC /* Get specification. */ # include "strtok_r.h" # define __strtok_r strtok_r -# define __rawmemchr strchr #endif /* Parse S into tokens separated by characters in DELIM. @@ -45,11 +41,17 @@ char * __strtok_r (char *s, const char *delim, char **save_ptr) { - char *token; + char *end; if (s == NULL) s = *save_ptr; + if (*s == '\0') + { + *save_ptr = s; + return NULL; + } + /* Scan leading delimiters. */ s += strspn (s, delim); if (*s == '\0') @@ -59,18 +61,17 @@ __strtok_r (char *s, const char *delim, char **save_ptr) } /* Find the end of the token. */ - token = s; - s = strpbrk (token, delim); - if (s == NULL) - /* This token finishes the string. */ - *save_ptr = __rawmemchr (token, '\0'); - else + end = s + strcspn (s, delim); + if (*end == '\0') { - /* Terminate the token and make *SAVE_PTR point past it. */ - *s = '\0'; - *save_ptr = s + 1; + *save_ptr = end; + return s; } - return token; + + /* Terminate the token and make *SAVE_PTR point past it. */ + *end = '\0'; + *save_ptr = end + 1; + return s; } #ifdef weak_alias libc_hidden_def (__strtok_r)