[Bug libstdc++/51078] New: [PATCH] performance improvement of std::count algorithm

[grygoriy.fuchedzhy at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51078

             Bug #: 51078
           Summary: [PATCH] performance improvement of std::count
                    algorithm
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: grygoriy.fuchedzhy@gmail.com


Created attachment 25778
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25778
patch itself

This patch improves performance of std::count algorithm in case of random
access iterators by loop unrolling. It doesn't affect std::count algorithm for
usual input iterators. This is done by choosing different versions of function
for different iterator types at compile time, similar technique is used for
std::find algorithm.

Besides the patch itself I've attached performance test which can be used to
test this changes without even applying them. Test program has count_local
function which implements improvements of this patch. Test program generates
test bunch of test containers of different types and performs count_local and
original count algorithm on them. It outputs table with following columns:
container_size, type1_local_time, type1_orig_time, type1_performance_boost,
type2_local_time, type2_orig_time, type2_performance_boost, ...

container_size is length of data passed to each call to count algorithm.
typeX_local_time is time elapsed counting bunch of containers of type X using
count_local function.
typeX_orig_time is time elapsed counting bunch of containers of type X using
original count implementation.
typeX_performance_boost is (typeX_orig_time -
typeX_local_time)/typeX_orig_time.
Number of containers for testing decreases with increasing of container_size to
keep testing time relatively constant.

There is also data file containing test results and gnuplot script to plot
them. Results were obtained on my machine with i7 cpu. Also tried another
machine with core2 processor, got similar results. Also tried changing range of
generated random data from [1-128] to [1-2]. Got similar results.

I also attached plots of performance boost against container size, first one is
linear by size, second one is logarithmic.

As you can see there is performance decrease for very small containers with
length less then 10 elements. And around 30% performance boost for larger
containers with fundamental types. Containers of complex data
vector<vector<int> > have small performace boost around 1%.

There is also list<int> to demonstrate that this patch doesn't affect non
random access iterators.