Re: strcspn(3) complexity improvement

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