Re: strcspn(3) complexity improvement

From: Peter Jeremy (PeterJeremy_at_optushome.com.au)
Date: 03/30/05

  • Next message: Poul-Henning Kamp: "Re: ciss(4): speed degradation for Compaq Smart Array" 
    Date: Wed, 30 Mar 2005 21:06:13 +1000
To: Jeremie Le Hen <jeremie@le-hen.org>

    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.

    >Second, I would like to know how to deal with the copyright update.
    >ATM, I changed the top of the copyright (up to Andrea's email address),
    >is it acceptable ?

    My reading of the change is that it completely replaces strcspn.c and
    therefore the change should include Andrea's copyright, replacing the
    existing UC copyright. 

    -- 
Peter Jeremy
_______________________________________________
freebsd-current@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscribe@freebsd.org"
  • Next message: Poul-Henning Kamp: "Re: ciss(4): speed degradation for Compaq Smart Array"