From owner-freebsd-current@FreeBSD.ORG Wed Mar 30 18:31:47 2005 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 1FF6B16A4CE for ; Wed, 30 Mar 2005 18:31:47 +0000 (GMT) Received: from odin.ac.hmc.edu (Odin.AC.HMC.Edu [134.173.32.75]) by mx1.FreeBSD.org (Postfix) with ESMTP id AD8EF43D54 for ; Wed, 30 Mar 2005 18:31:46 +0000 (GMT) (envelope-from brdavis@odin.ac.hmc.edu) Received: from odin.ac.hmc.edu (localhost.localdomain [127.0.0.1]) by odin.ac.hmc.edu (8.13.0/8.13.0) with ESMTP id j2UIVkMa031611; Wed, 30 Mar 2005 10:31:46 -0800 Received: (from brdavis@localhost) by odin.ac.hmc.edu (8.13.0/8.13.0/Submit) id j2UIVjgg031610; Wed, 30 Mar 2005 10:31:45 -0800 Date: Wed, 30 Mar 2005 10:31:45 -0800 From: Brooks Davis To: Peter Jeremy Message-ID: <20050330183145.GB24465@odin.ac.hmc.edu> References: <20050330083435.GI75546@obiwan.tataz.chchile.org> <20050330110613.GB71384@cirb503493.alcatel.com.au> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="eAbsdosE1cNLO4uF" Content-Disposition: inline In-Reply-To: <20050330110613.GB71384@cirb503493.alcatel.com.au> User-Agent: Mutt/1.4.1i X-Virus-Scanned: by amavisd-new X-Spam-Status: No, hits=0.0 required=8.0 tests=none autolearn=no version=2.63 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on odin.ac.hmc.edu cc: freebsd-current@freebsd.org cc: Jeremie Le Hen Subject: Re: strcspn(3) complexity improvement X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 30 Mar 2005 18:31:47 -0000 --eAbsdosE1cNLO4uF Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Mar 30, 2005 at 09:06:13PM +1000, Peter Jeremy wrote: > On Wed, 2005-Mar-30 10:34:35 +0200, Jeremie Le Hen wrote: > >Andreas Hauser made a patch to strcspn(3) for the DragonFly project > >which makes it faster when dealing with long strings [1] (rev 1.4). > >It basically changes the complexity of the function from > > O(strlen(str) * strlen(chars)) > >to > > O(strlen(str) + strlen(chars)) > >by using a charset. >=20 > It has a significantly higher overhead due to the need to zero the charse= t. >=20 > >I have two questions. First, is this change worth enough to be merged > >in FreeBSD (this function is currently used in 42 binaries from > >/{,usr/}{s,}bin) ? I mean does the performance gain on large strings > >compensates the use of a large 256-bytes buffer ? >=20 > You are proposing this change so I think it's up to you to demonstrate > an improvement. I don't think the space is an issue in userland (it > would be in the kernel) so it's just a matter of which is faster. Did > Joerg or Andreas provide any performance test results? My gut feeling > is that strcspn() isn't heavily used enough or with long enough > "chars" arguments for the change to be noticable in the base system. The real question I have is, how long does the string need to be before this is a win and how much does it hurt for typical string lengths? I've written code with strcspn that needed to perform well, but it was parsing 80-column punch card derived formats. -- Brooks --=20 Any statement of the form "X is the one, true Y" is FALSE. PGP fingerprint 655D 519C 26A7 82E7 2529 9BF0 5D8E 8BE9 F238 1AD4 --eAbsdosE1cNLO4uF Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.1 (GNU/Linux) iD8DBQFCSvCRXY6L6fI4GtQRAnlBAKCFBCvUQoUsj7bWev2ax450CogZTgCgrYDA QwAotIIhueHf9XfERt8Q1hc= =nZjB -----END PGP SIGNATURE----- --eAbsdosE1cNLO4uF--