Date: Wed, 30 Mar 2005 10:31:45 -0800 From: Brooks Davis <brooks@one-eyed-alien.net> To: Peter Jeremy <PeterJeremy@optushome.com.au> Cc: Jeremie Le Hen <jeremie@le-hen.org> Subject: Re: strcspn(3) complexity improvement Message-ID: <20050330183145.GB24465@odin.ac.hmc.edu> In-Reply-To: <20050330110613.GB71384@cirb503493.alcatel.com.au> References: <20050330083435.GI75546@obiwan.tataz.chchile.org> <20050330110613.GB71384@cirb503493.alcatel.com.au>
next in thread | previous in thread | raw e-mail | index | archive | help
--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--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20050330183145.GB24465>