From patchwork Fri Feb 3 14:34:17 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Akinobu Mita X-Patchwork-Id: 139384 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from merlin.infradead.org (unknown [IPv6:2001:4978:20e::2]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 1F3B8104792 for ; Sat, 4 Feb 2012 01:35:11 +1100 (EST) Received: from localhost ([::1] helo=merlin.infradead.org) by merlin.infradead.org with esmtp (Exim 4.76 #1 (Red Hat Linux)) id 1RtKDF-0007un-P5; Fri, 03 Feb 2012 14:34:05 +0000 Received: from mail-pw0-f49.google.com ([209.85.160.49]) by merlin.infradead.org with esmtps (Exim 4.76 #1 (Red Hat Linux)) id 1RtKDC-0007uZ-GB for linux-mtd@lists.infradead.org; Fri, 03 Feb 2012 14:34:03 +0000 Received: by pbdx9 with SMTP id x9so3510353pbd.36 for ; Fri, 03 Feb 2012 06:34:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer; bh=e/TbCec0xQwG/RFSAvPJ23vpSsFuou1WUsFPiZ5aqvs=; b=cIQCVzVy5pGHIo7xFhN0pLU2vabgfr9fX8mIfvjj/hx9mrE950ewUTLQdKQ94fmjGj T49asQdEVatsmOrdkbRm3fgA5noxjKFgi/GJhLcHeiNr7lKkPUp2pl+8ZWrOxZhQL7Pz 7Q2qQ5y9S4KNQ3B/GG9XTGRZC3nr/EsWDRJVE= Received: by 10.68.216.133 with SMTP id oq5mr17876311pbc.110.1328279640356; Fri, 03 Feb 2012 06:34:00 -0800 (PST) Received: from localhost.localdomain (p2046-adsao01yokonib2-acca.kanagawa.ocn.ne.jp. [61.214.148.46]) by mx.google.com with ESMTPS id z5sm13489410pbc.5.2012.02.03.06.33.55 (version=TLSv1/SSLv3 cipher=OTHER); Fri, 03 Feb 2012 06:33:59 -0800 (PST) From: Akinobu Mita To: linux-kernel@vger.kernel.org, akpm@linux-foundation.org, Eric Dumazet , Brian Norris , joe@perches.com, linux-mtd@lists.infradead.org Subject: [PATCH] string: memchr_inv speed improvements Date: Fri, 3 Feb 2012 23:34:17 +0900 Message-Id: <1328279657-9054-1-git-send-email-akinobu.mita@gmail.com> X-Mailer: git-send-email 1.7.4.4 X-Spam-Note: CRM114 invocation failed X-Spam-Score: -2.7 (--) X-Spam-Report: SpamAssassin version 3.3.2 on merlin.infradead.org summary: Content analysis details: (-2.7 points) pts rule name description ---- ---------------------- -------------------------------------------------- -0.7 RCVD_IN_DNSWL_LOW RBL: Sender listed at http://www.dnswl.org/, low trust [209.85.160.49 listed in list.dnswl.org] 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (akinobu.mita[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature Cc: Akinobu Mita X-BeenThere: linux-mtd@lists.infradead.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Linux MTD discussion mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: linux-mtd-bounces@lists.infradead.org Errors-To: linux-mtd-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org - Generate a 64-bit pattern more efficiently memchr_inv needs to generate a 64-bit pattern filled with a target character. The operation can be done by more efficient way. - Don't call the slow check_bytes() if the memory area is 64-bit aligned memchr_inv compares contiguous 64-bit words with the 64-bit pattern as much as possible. The outside of the region is checked by check_bytes() that scans for each byte. Unfortunately, the first 64-bit word is unexpectedly scanned by check_bytes() even if the memory area is aligned to a 64-bit boundary. Both changes were originally suggested by Eric Dumazet. Signed-off-by: Akinobu Mita Suggested-by: Eric Dumazet --- lib/string.c | 20 ++++++++++++++++---- 1 files changed, 16 insertions(+), 4 deletions(-) diff --git a/lib/string.c b/lib/string.c index dc4a863..3a03782 100644 --- a/lib/string.c +++ b/lib/string.c @@ -785,12 +785,24 @@ void *memchr_inv(const void *start, int c, size_t bytes) if (bytes <= 16) return check_bytes8(start, value, bytes); - value64 = value | value << 8 | value << 16 | value << 24; - value64 = (value64 & 0xffffffff) | value64 << 32; - prefix = 8 - ((unsigned long)start) % 8; + value64 = value; +#if defined(ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64 + value64 *= 0x0101010101010101; +#elif defined(ARCH_HAS_FAST_MULTIPLIER) + value64 *= 0x01010101; + value64 |= value64 << 32; +#else + value64 |= value64 << 8; + value64 |= value64 << 16; + value64 |= value64 << 32; +#endif + prefix = (unsigned long)start % 8; if (prefix) { - u8 *r = check_bytes8(start, value, prefix); + u8 *r; + + prefix = 8 - prefix; + r = check_bytes8(start, value, prefix); if (r) return r; start += prefix;