public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/103621] New: stable_sort could call std::__merge_sort_with_buffer directly in typical case
@ 2021-12-08 22:45 riad93 at mail dot ru
2022-10-13 17:12 ` [Bug libstdc++/103621] " fdumont at gcc dot gnu.org
0 siblings, 1 reply; 2+ messages in thread
From: riad93 at mail dot ru @ 2021-12-08 22:45 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103621
Bug ID: 103621
Summary: stable_sort could call std::__merge_sort_with_buffer
directly in typical case
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: riad93 at mail dot ru
Target Milestone: ---
So, currently __stable_sort is implemented this way:
if (__buf.begin() == 0)
std::__inplace_stable_sort(__first, __last, __comp);
else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
_DistanceType(__buf.size()), __comp);
which means that on the topmost iteration the merge the split will be done in a
naive way, and the copy+merge will happen even in typical case when there's
enough memory for everything.
Subjectively, it makes sense that in general calling
std::__merge_sort_with_buffer should be faster (otherwise why would it exist),
but I wasn't able to measure any difference yet.
^ permalink raw reply [flat|nested] 2+ messages in thread
* [Bug libstdc++/103621] stable_sort could call std::__merge_sort_with_buffer directly in typical case
2021-12-08 22:45 [Bug libstdc++/103621] New: stable_sort could call std::__merge_sort_with_buffer directly in typical case riad93 at mail dot ru
@ 2022-10-13 17:12 ` fdumont at gcc dot gnu.org
0 siblings, 0 replies; 2+ messages in thread
From: fdumont at gcc dot gnu.org @ 2022-10-13 17:12 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103621
François Dumont <fdumont at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|--- |13.0
Status|UNCONFIRMED |RESOLVED
CC| |fdumont at gcc dot gnu.org
Resolution|--- |FIXED
--- Comment #1 from François Dumont <fdumont at gcc dot gnu.org> ---
I think it has been fixed by:
commit 63d182fb86e47323ac50d9368845d712e1f7da89
Author: François Dumont <fdumont@gcc.gnu.org>
Date: Thu Jan 21 19:30:47 2021 +0100
libstdc++: Enhance branching in std::inplace_merge and std::stable_sort
When we manage to allocate a buffer of the expected size we can simplify
the code to
perform the expected algorithm.
libstdc++-v3/ChangeLog:
* include/bits/stl_algo.h
(__merge_adaptive): Adapt to merge only when buffer is large
enough..
(__merge_adaptive_resize): New, adapt merge when buffer is too
small.
(__inplace_merge): Adapt, use latter.
(__stable_sort_adaptive): Adapt to sort only when buffer is large
enough.
(__stable_sort_adaptive_resize): New, adapt sort when buffer is too
small.
(__stable_sort): Adapt, use latter.
Let us know otherwise.
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2022-10-13 17:12 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-12-08 22:45 [Bug libstdc++/103621] New: stable_sort could call std::__merge_sort_with_buffer directly in typical case riad93 at mail dot ru
2022-10-13 17:12 ` [Bug libstdc++/103621] " fdumont at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).