From owner-freebsd-hackers@FreeBSD.ORG Wed Feb 15 12:47:29 2012 Return-Path: Delivered-To: hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id DACAC1065673 for ; Wed, 15 Feb 2012 12:47:29 +0000 (UTC) (envelope-from simon@comsys.ntu-kpi.kiev.ua) Received: from comsys.kpi.ua (comsys.kpi.ua [77.47.192.42]) by mx1.freebsd.org (Postfix) with ESMTP id 8AC1F8FC18 for ; Wed, 15 Feb 2012 12:47:29 +0000 (UTC) Received: from pm513-1.comsys.kpi.ua ([10.18.52.101] helo=pm513-1.comsys.ntu-kpi.kiev.ua) by comsys.kpi.ua with esmtpsa (TLSv1:AES256-SHA:256) (Exim 4.63) (envelope-from ) id 1RxdsP-0007h5-Ml; Wed, 15 Feb 2012 14:22:25 +0200 Received: by pm513-1.comsys.ntu-kpi.kiev.ua (Postfix, from userid 1001) id 00CF01CC36; Wed, 15 Feb 2012 14:22:25 +0200 (EET) Date: Wed, 15 Feb 2012 14:22:25 +0200 From: Andrey Simonenko To: Bernard van Gastel Message-ID: <20120215122225.GA34935@pm513-1.comsys.ntu-kpi.kiev.ua> References: <1BDAF8C6-66A5-4F4F-A2CD-3928A0B10D48@bitpowder.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1BDAF8C6-66A5-4F4F-A2CD-3928A0B10D48@bitpowder.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-Authenticated-User: simon@comsys.ntu-kpi.kiev.ua X-Authenticator: plain X-Sender-Verify: SUCCEEDED (sender exists & accepts mail) X-Exim-Version: 4.63 (build at 28-Apr-2011 07:11:12) X-Date: 2012-02-15 14:22:25 X-Connected-IP: 10.18.52.101:15930 X-Message-Linecount: 44 X-Body-Linecount: 29 X-Message-Size: 2055 X-Body-Size: 1398 Cc: hackers@freebsd.org Subject: Re: memmem small optimalisation X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 Feb 2012 12:47:29 -0000 On Tue, Feb 14, 2012 at 07:25:14PM +0100, Bernard van Gastel wrote: > Hi all, > > I was looking through the sources of memmove at [1], and saw a (very) > small optimization opportunity. The 'memcmp' also compares the current > character, but the current character is already checked (first part of > the condition). As we already know the size of the string is greater as > 1 (it is checked before the loop), it is possible to replace the memcmp > with (possible doing the decrease of s_len once outside the loop): > memcpy(&cur[1], &cs[1], s_len-1) You are right, also second argument for memcpy() also can be calculated outside of the loop (remembering first character from this buffer is required). One can find similar optimization in other simple memmem() implementations. (search memmem on http://code.google.com/ for example). > Am I missing something? E.g. is readability more important as speed? > This made me wonder what generally the tradeoff is that has to be taken > into account in these cases? Looks like it will give a little improvement. If one want to use such function for huge data, then more advanced string searching algorithms are required. > [1] http://www.freebsd.org/cgi/cvsweb.cgi/src/lib/libc/string/memmem.c?rev=1.2 , excerpt below: > for (cur = (char *)cl; cur <= last; cur++) > if (cur[0] == cs[0] && memcmp(cur, cs, s_len) == 0) > return cur;