public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
From: "François Dumont" <frs.dumont@gmail.com>
To: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>,
	gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH] PR 83938 Reduce memory consumption in stable_sort/inplace_merge
Date: Mon, 22 Jun 2020 08:27:16 +0200	[thread overview]
Message-ID: <6974d337-971f-a512-8e46-45201a4f8146@gmail.com> (raw)
In-Reply-To: <db2a8694-0d25-e9a6-bfd5-5a633e4ea119@gmail.com>

Gentle remider.



On 11/06/20 8:32 am, François Dumont wrote:
> As we are on patching algos we still have this old one.
>
>     From the original patch I only kept the memory optimization part 
> as the new performance test was not showing good result for the other 
> part to change pivot value. I also kept the small change in 
> get_temporary_buffer even if I don't have strong feeling about it, it 
> just make sure that we'll try to allocate 1 element as a last chance 
> allocation.
>
>     Note that there is still place for an improvement. If we miss 
> memory on the heap we then use a recursive implementation which then 
> rely on stack memory. I would be surprise that a system which miss 
> heap memory would have no problem to allocate about the same on the 
> stack so we will surely end up in a stack overflow. I still have this 
> on my todo even if I already made several tries with no satisfying 
> result in terms of performance.
>
>     Tested under Linux x86_64.
>
> Commit message:
>
>     libstdc++: Limit memory allocation in stable_sort/inplace_merge 
> (PR 83938)
>
>     Reduce memory consumption in stable_sort/inplace_merge to what is 
> used.
>
>     Co-authored-by: François Dumont  <fdumont@gcc.gnu.org>
>
>     libstdc++-v3/ChangeLog:
>
>     2020-06-11  John Chang  <john.chang@samba.tv>
>                 François Dumont  <fdumont@gcc.gnu.org>
>
>             PR libstdc++/83938
>             * include/bits/stl_tempbuf.h (get_temporary_buffer): 
> Change __len
>             computation in the loop.
>             * include/bits/stl_algo.h:
>             (__inplace_merge): Take temporary buffer length from 
> smallest range.
>             (__stable_sort): Limit temporary buffer length.
>             * testsuite/25_algorithms/inplace_merge/1.cc (test03): 
> Test different
>             pivot positions.
>             * testsuite/performance/25_algorithms/stable_sort.cc: Test 
> stable_sort
>             under different heap memory conditions.
>             * testsuite/performance/25_algorithms/inplace_merge.cc: New.
>
> Ok to commit ?
>
> François
>


  reply	other threads:[~2020-06-22  6:27 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-06-11  6:32 François Dumont
2020-06-22  6:27 ` François Dumont [this message]
2020-06-24 17:39 ` Jonathan Wakely
2020-06-24 20:12   ` François Dumont
2020-11-18 20:43   ` François Dumont
2020-11-19 12:26 ` Jonathan Wakely

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=6974d337-971f-a512-8e46-45201a4f8146@gmail.com \
    --to=frs.dumont@gmail.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=libstdc++@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).