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: Christopher Jefferson <chris at bubblescope dot net>
- To: François Dumont <frs dot dumont at gmail dot com>
- 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: Mon, 7 Oct 2013 13:56:12 +0100
- 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>
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:
> On 10/03/2013 10:59 PM, Paolo Carlini wrote:
>>
>> .. or, if I remember correctly, should we maybe see what happens for a
>> smaller or much smaller number of elements to see if there is a measurable
>> (in number of comparisons terms), on sort?
>>
>> Thanks,
>> Paolo.
>>
> I run the sort performance test using only 11 elements and in this case I
> see:
>
> Without patch:
> sort.cc reverse 10 comparisons 0r 0u 0s
> 0mem 0pf
> sort.cc forwards 20 comparisons 0r 0u 0s
> 0mem 0pf
> sort.cc random 30 comparisons 0r 0u 0s
> 0mem 0pf
>
> With patch:
> sort.cc reverse 10 comparisons 0r 0u 0s
> 0mem 0pf
> sort.cc forwards 19 comparisons 0r 0u 0s
> 0mem 0pf
> sort.cc random 29 comparisons 0r 0u 0s
> 0mem 0pf
>
> 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
>