This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Limit std::sort comparisons on small list
- From: Paolo Carlini <paolo dot carlini at oracle dot com>
- To: FranÃois Dumont <frs dot dumont at gmail dot com>
- Cc: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, "chris at bubblescope dot net" <chris at bubblescope dot net>, Marc Glisse <marc dot glisse at inria dot fr>
- Date: Thu, 03 Oct 2013 22:53:14 +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>
Hi,
On 10/03/2013 10:04 PM, FranÃois Dumont wrote:
So no impact on sort because the number of elements involved is too
important. Good, even if limited, impact on stable_sort because it
reduces the number of comparison by about 0.5% in the random case. I
have added a test to check that on small number of elements it has the
expected impact, only 1 comparison when 2 elements in the array.
Thanks for your help on this. While we wait for comments from Chris,
Marc and other interested people, I have a rather simple-minded question
for you: how would you explain that the number of comparisons for the
sort performance tests remains *exactly* the same, while we know that
the change helps for 2 elements, avoiding a comparison? Isn't navely
weird that a similar situation *never* happens for the performance
tests? Surely it does happen if we change the random seed of the random
variant, at least an handful of times?!?
Thanks again,
Paolo.