This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]
Other format:	[Raw text]

Re: Limit std::sort comparisons on small list

From: François Dumont <frs dot dumont at gmail dot com>
To: Christopher Jefferson <chris at bubblescope dot net>
Cc: Paolo Carlini <paolo dot carlini at oracle dot com>, "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, Marc Glisse <marc dot glisse at inria dot fr>
Date: Tue, 08 Oct 2013 21:54:59 +0200
Subject: Re: Limit std::sort comparisons on small list
Authentication-results: sourceware.org; auth=none
References: <52409F6F dot 7040609 at gmail dot com> <alpine dot DEB dot 2 dot 10 dot 1309232317070 dot 4088 at laptop-mg dot saclay dot inria dot fr> <alpine dot DEB dot 2 dot 10 dot 1309290031480 dot 4104 at laptop-mg dot saclay dot inria dot fr> <CA+jCFLvhxsbAu+3Ti07pL0hg7UJfDgBzzbAV5EMwvMUtaa1ZYQ at mail dot gmail dot com> <5249A299 dot 3060103 at oracle dot com> <CA+jCFLu-r8SCWhSv-h+vrcSbWXWAXEiFxVhfNTUpworkXMJsRw at mail dot gmail dot com> <524B322A dot 1090703 at gmail dot com> <C62520F9-5A70-406F-AAE8-0F7900034CC3 at oracle dot com> <524DCDC7 dot 1000801 at gmail dot com> <524DD93A dot 30100 at oracle dot com> <524DDACB dot 7010207 at oracle dot com> <524F2892 dot 3040204 at gmail dot com> <CA+jCFLu-9cj544=u+cKub_RPQ4hbxDWofV6focJTNhd0cKXuCw at mail dot gmail dot com>

On 10/07/2013 02:56 PM, Christopher Jefferson wrote:

I'm unconvinced by this optimisation. I have already heard the
occasional complaint that libstdc++ is quite large, so even in this
tiny case I would be unsure about producing a very small code size
increase for a very small performance improvement.

On 4 October 2013 21:44, François Dumont <frs.dumont@gmail.com> wrote:

so with a limited number of elements we can see the gain even if it looks
like for the sort algo it is limited to 1 comparison. For stable_sort it is
better.

François

I am surprised, code bloat is indeed the only drawback of this patch,but isn't sometimes the compiler unrolling loop itself ? You can evensee in __find_if implementation that we sometimes unroll loops manuallyso I guess that in general it is rather good for performance. Especiallyin this case with the first iteration that is better taken care separately.

Of course it is a small optimization but also a rather trivial one. I amsorry that I can't check the result on the generated code but I am quitesure that the "code bloat" will be even smaller than the optimization.


François

Follow-Ups:
- Re: Limit std::sort comparisons on small list
  - From: David Kastrup

References:
- Limit std::sort comparisons on small list
  - From: François Dumont
- Re: Limit std::sort comparisons on small list
  - From: Paolo Carlini
- Re: Limit std::sort comparisons on small list
  - From: FranÃois Dumont
- Re: Limit std::sort comparisons on small list
  - From: Paolo Carlini
- Re: Limit std::sort comparisons on small list
  - From: Paolo Carlini
- Re: Limit std::sort comparisons on small list
  - From: FranÃois Dumont
- Re: Limit std::sort comparisons on small list
  - From: Christopher Jefferson

Index Nav:	[Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav:	[Date Prev] [Date Next]	[Thread Prev] [Thread Next]