[Patch] [BZ 15884] strcoll: improve performance by removing the cache

[Siddhesh Poyarekar]

On Wed, Sep 24, 2014 at 10:37:21AM +0200, Leonhard Holz wrote:
> Hello everybody,
> 
> this is a path that should solve bug 15884. It complains about the
> performance of strcoll(). It was found out that the runtime of strcoll() is
> actually bound to strlen which is needed for calculating the size of a cache
> that was installed to improve the comparison performance.
> 
> The idea for this patch was that the cache is only useful in rare cases
> (strings of same length and same first-level-chars) and that it would be
> better to avoid memory allocation at all. To prove this I wrote a
> performance test that is found in benchtests-strcoll.tar.bz2. Also
> modifications in benchtests/Makefile and localedata/Makefile are necessary
> to make it work.
> 
> After removing the cache the strcoll method showed the predicted behavior
> (getting slightly faster) in all but the test case for hindi word sorting.
> This was due the hindi text having much more equal words than the other
> ones. For equal strings the performance was worse since all comparison
> levels were run through and from the second level on the cache improved the
> comparison performance of the original version.
> 
> Therefore I added a bytewise test via strcmp iff the first level comparison
> found that both strings did match because in this case it is very likely
> that equal strings are compared. This solved the problem with the hindi test
> case and improved the performance of the others.

Thanks for working on this and also writing a benchmark for it.  The
general approach seems sound to me (I haven't done a deep review yet),
but there are quite a few nits that will need to be worked out, most
of them covered in the contributor checklist[1].

- There are a lot of unrelated whitespace and formatting changes in
  the patch.  Most of them seem to have been made using the GNU indent
  program, which is mostly accurate, but not completely.  Please
  review and fix them up.

- The change needs a changelog which mentions all your changes,
  including all the new files.

- Please include bench-strcoll.c in the patch as well.  It's OK if you
  post the input files in the tarball but the source needs to be
  reviewed.

- bench-strcoll.c has some code formatting issues, especially
  unnecessary braces around single line for/if blocks.

> Another improvement was achieved by inlineing both static subroutines.

- Please post the inlining change separately with separate numbers for
  it.  In general we stay away from inlining functions and just let
  the compiler do its job.  However if there is a case where such
  inlining is especially useful, it needs to be accompanied with
  numbers.  So a separate patch with separate numbers for the change
  would be helpful.

- Finally, I don't know if you have signed a copyright assignment with
  the FSF for your changes.  Carlos seems to have mentioned that in
  your previous email thread, but I don't know if you've followed
  through on it since I am not an FSF maintainer.  Maybe one of the
  FSF maintainers can confirm that.

Siddhesh

[1] https://sourceware.org/glibc/wiki/Contribution%20checklist
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 473 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20140924/33a87ea9/attachment.sig>