Re: strcspn(3) complexity improvement

From: Brooks Davis (brooks_at_one-eyed-alien.net)
Date: 03/30/05

  • Next message: Don Lewis: "Re: Heads up: gtar gone from base system" 
    Date: Wed, 30 Mar 2005 10:31:45 -0800
To: Peter Jeremy <PeterJeremy@optushome.com.au>

    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.
    >
    > It has a significantly higher overhead due to the need to zero the charset.
    >
    > >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 ?
    >
    > 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 

    -- 
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

  • Next message: Don Lewis: "Re: Heads up: gtar gone from base system"