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

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

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #1 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-10 11:39:08 UTC ---
Created attachment 25779
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25779
performance test

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #2 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-10 11:40:20 UTC ---
Created attachment 25780
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25780
output of performance test

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #3 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-10 11:41:14 UTC ---
Created attachment 25781
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25781
gnuplot script to plot test data

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #4 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-10 11:42:23 UTC ---
Created attachment 25782
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25782
plot of performance boost against container size

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #5 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-10 11:43:00 UTC ---
Created attachment 25783
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25783
plot of performance boost against container size, logarithmic by size

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

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> 2011-11-10 11:55:44 UTC ---
(In reply to comment #5)
> Created attachment 25783 [details]
> plot of performance boost against container size, logarithmic by size

This is the more useful one - thanks.

Before looking at your patch, do you have a copyright assignment in place for
contributing to GCC?
For details see http://gcc.gnu.org/contribute.html

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #7 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-10 14:06:38 UTC ---
(In reply to comment #6)
> Before looking at your patch, do you have a copyright assignment in place for
> contributing to GCC?

No, but I'm ready to sign it. What should I do now? I've found this
instructions: http://gcc.gnu.org/wiki/CopyrightAssignment

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

[marc.glisse at normalesup dot org]

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

--- Comment #8 from Marc Glisse <marc.glisse at normalesup dot org> 2011-11-10 17:28:46 UTC ---
Hello,

I can't seem to find a mention of the compiler flags you used for your
benchmarks, what are they? -Ofast -funroll-loops?

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #9 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-10 18:08:31 UTC ---
(In reply to comment #8)
> I can't seem to find a mention of the compiler flags you used for your
> benchmarks, what are they? -Ofast -funroll-loops?

-march=native -O2

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

[paolo.carlini at oracle dot com]

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

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-10 18:20:03 UTC ---
As a general observation about this kind of road to performance improvement:
before manually unrolling loops, I think we should **carefully** analyze why
the loop unrolling optimizations in the compiler cannot be simply relied on.
Indeed, I know we have got already few manually unrolled loops in <algorithm>
but those are *very* old, essentially dating back to the HP / Sgi times: I
would not be suprised at all to learn that vs the current Gcc, maybe further
tweaked with the help of the compiler people, they are actually not benefiting
anymore. At minimum, we should reassess how *much* to unroll for today's cpus,
or whether the optimal solution now would be loop optimization supported by
hints in the code.

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #11 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-11 21:53:50 UTC ---
I've tried different optimization options:
1. -march=native -O2,
2. -march=native -O2 -funroll-loops,
3. -march=native -O2 -funroll-all-loops,
4. -march=native -O3,
5. -march=native -O3 -funroll-loops,
6. -march=native -O3 -funroll-all-loops

And got following list of optimizations from faster to slower: 5, 6, 1, 4, 2, 3

You can see that code with automatic loop unrolling sometimes performs worse
than code without one. 2 and 3 optimizations gives 1.5 times worse result
compared to 1 variant.

5 and 6 variant is better then 1, but still manual loop unrolling performs
better(more than 25%).

Also I've tried changing number of unrolled iteration from 2 to 8 and got best
performance for 4 and 5 on core2 cpu.

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

[grygoriy.fuchedzhy at gmail dot com]

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

Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #25779|0                           |1
        is obsolete|                            |

--- Comment #12 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-11 21:57:06 UTC ---
Created attachment 25798
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25798
performance test

Minor fix to implement patch functionality exactly. Doesn't affect performance.

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

[paolo.carlini at oracle dot com]

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

--- Comment #13 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-11 23:03:38 UTC ---
I would say, the next step, is analyzing why: std::count seems a very simple
algorithm, no aliasing issues for example, compiler should be able to unroll,
maybe vectorize too, and everything else, without having to fiddle with the
code in an ad-hoc way.

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

[grygoriy.fuchedzhy at gmail dot com]

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

--- Comment #14 from Grygoriy Fuchedzhy <grygoriy.fuchedzhy at gmail dot com> 2011-11-12 10:09:52 UTC ---
(In reply to comment #13)
> I would say, the next step, is analyzing why: std::count seems a very simple
> algorithm, no aliasing issues for example, compiler should be able to unroll,
> maybe vectorize too, and everything else, without having to fiddle with the
> code in an ad-hoc way.

I completely agree that analizing why is necessary, but this probably should be
done in separate bug?(should I open it?) As regarding current bug: it seems
that automatic loop unrolling is far from being considered "stable" or
"recommended" optimization, so this patch may improve performance until this
optimization become commonly used. By the way, manually unrolled std::find, one
of old algorithms you mentioned also performs significantly better than version
without loop unrolling.

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

[paolo.carlini at oracle dot com]

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

--- Comment #15 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-12 11:12:36 UTC ---
Actually, patches do not belong to Bugzilla at all thus this issue should have
been posted and discussed only on the mailing list. In any case, we are not
going to add to the library manually unrolled loops for such simple algorithms
until we understand why the loops aren't satisfactorily unrolled, and
vectorized, and all it's profitable, by the compiler.

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

[paolo.carlini at oracle dot com]

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

--- Comment #16 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-12 12:11:48 UTC ---
By the way, without having investigated at all what the optimizers are actually
doing, in mainline, on an i7-980X I have here at hand I don't see the manual
unrolling providing any advantage over -funroll-loops: I'm using  g++ -Ofast
-march=native -funroll-loops test.cc. Numbers attached.

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

[paolo.carlini at oracle dot com]

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

--- Comment #17 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-12 12:14:06 UTC ---
Created attachment 25804
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25804
Some numbers: i7-980X, mainline, -Ofast -funroll-loops, -march=native

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

[paolo.carlini at oracle dot com]

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

--- Comment #18 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-12 12:32:22 UTC ---
Created attachment 25805
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25805
Same, without -funroll-loops

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

[paolo.carlini at oracle dot com]

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

--- Comment #19 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-12 12:34:51 UTC ---
All in all - again, without having analyzed in any detail the optimization
passes - I come to the conclusion that -funroll-loops is doing its job pretty
well, and also that manually unrolling the loop make its life quite a bit
harder.

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

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |WORKSFORME

--- Comment #20 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-11-15 10:52:36 UTC ---
I guess we can close this.