From: Florian Weimer <fweimer@redhat.com>
To: libc-alpha@sourceware.org
Cc: DJ Delorie <dj@redhat.com>
Subject: [PATCH] malloc: Remove bin scanning from memalign (bug 30723)
Date: Thu, 10 Aug 2023 19:36:56 +0200 [thread overview]
Message-ID: <87pm3uajev.fsf@oldenburg.str.redhat.com> (raw)
On the test workload (mpv --cache=yes with VP9 video decoding), the
bin scanning has a very poor success rate (less than 2%). The tcache
scanning has about 50% success rate, so keep that.
---
DJ, this is on top of my other patch. Given that the chunk scanning
code has such a small hit rate on the workload, I have just removed it.
I think we need better data structures before we can bring this back,
otherwise most workloads with a high number of memalign calls suffer too
much. Typical heaps have hundreds, if not thousands, of free list
entries. I had not considered the impact of that on repeated memalign
calls.
What do you think?
Tested x86_64-linux-gnu.
Thanks,
Florian
malloc/malloc.c | 127 +++-----------------------------------------------------
1 file changed, 5 insertions(+), 122 deletions(-)
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 948f9759af..9c2cab7a59 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -5082,7 +5082,6 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
mchunkptr remainder; /* spare room at end to split off */
unsigned long remainder_size; /* its size */
INTERNAL_SIZE_T size;
- mchunkptr victim;
nb = checked_request2size (bytes);
if (nb == 0)
@@ -5101,129 +5100,13 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
we don't find anything in those bins, the common malloc code will
scan starting at 2x. */
- /* This will be set if we found a candidate chunk. */
- victim = NULL;
+ /* Call malloc with worst case padding to hit alignment. */
+ m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
- /* Fast bins are singly-linked, hard to remove a chunk from the middle
- and unlikely to meet our alignment requirements. We have not done
- any experimentation with searching for aligned fastbins. */
+ if (m == 0)
+ return 0; /* propagate failure */
- if (av != NULL)
- {
- int first_bin_index;
- int first_largebin_index;
- int last_bin_index;
-
- if (in_smallbin_range (nb))
- first_bin_index = smallbin_index (nb);
- else
- first_bin_index = largebin_index (nb);
-
- if (in_smallbin_range (nb * 2))
- last_bin_index = smallbin_index (nb * 2);
- else
- last_bin_index = largebin_index (nb * 2);
-
- first_largebin_index = largebin_index (MIN_LARGE_SIZE);
-
- int victim_index; /* its bin index */
-
- for (victim_index = first_bin_index;
- victim_index < last_bin_index;
- victim_index ++)
- {
- victim = NULL;
-
- if (victim_index < first_largebin_index)
- {
- /* Check small bins. Small bin chunks are doubly-linked despite
- being the same size. */
-
- mchunkptr fwd; /* misc temp for linking */
- mchunkptr bck; /* misc temp for linking */
-
- bck = bin_at (av, victim_index);
- fwd = bck->fd;
- while (fwd != bck)
- {
- if (chunk_ok_for_memalign (fwd, alignment, nb) > 0)
- {
- victim = fwd;
-
- /* Unlink it */
- victim->fd->bk = victim->bk;
- victim->bk->fd = victim->fd;
- break;
- }
-
- fwd = fwd->fd;
- }
- }
- else
- {
- /* Check large bins. */
- mchunkptr fwd; /* misc temp for linking */
- mchunkptr bck; /* misc temp for linking */
- mchunkptr best = NULL;
- size_t best_size = 0;
-
- bck = bin_at (av, victim_index);
- fwd = bck->fd;
-
- while (fwd != bck)
- {
- int extra;
-
- if (chunksize (fwd) < nb)
- break;
- extra = chunk_ok_for_memalign (fwd, alignment, nb);
- if (extra > 0
- && (extra <= best_size || best == NULL))
- {
- best = fwd;
- best_size = extra;
- }
-
- fwd = fwd->fd;
- }
- victim = best;
-
- if (victim != NULL)
- {
- unlink_chunk (av, victim);
- break;
- }
- }
-
- if (victim != NULL)
- break;
- }
- }
-
- /* Strategy: find a spot within that chunk that meets the alignment
- request, and then possibly free the leading and trailing space.
- This strategy is incredibly costly and can lead to external
- fragmentation if header and footer chunks are unused. */
-
- if (victim != NULL)
- {
- p = victim;
- m = chunk2mem (p);
- set_inuse (p);
- if (av != &main_arena)
- set_non_main_arena (p);
- }
- else
- {
- /* Call malloc with worst case padding to hit alignment. */
-
- m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
-
- if (m == 0)
- return 0; /* propagate failure */
-
- p = mem2chunk (m);
- }
+ p = mem2chunk (m);
if ((((unsigned long) (m)) % alignment) != 0) /* misaligned */
{
base-commit: e02ce52fd890d3b5197f78cf25096faa9446fa3d
next reply other threads:[~2023-08-10 17:37 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-08-10 17:36 Florian Weimer [this message]
2023-08-10 18:04 ` DJ Delorie
2023-08-11 7:20 ` Florian Weimer
2023-08-11 23:14 ` DJ Delorie
2023-08-21 14:01 ` Sam James
2023-08-21 14:45 ` Florian Weimer
2023-08-11 8:54 ` Maxim Kuvyrkov
2023-08-11 9:14 ` Florian Weimer
2023-08-11 14:52 ` Florian Weimer
2023-08-12 6:52 ` Andreas Schwab
2023-08-12 13:23 ` Florian Weimer
2023-08-12 13:33 ` Florian Weimer
2023-08-12 14:50 ` Andreas Schwab
2023-08-14 2:14 ` Xi Ruoyao
2023-08-14 9:16 ` Florian Weimer
2023-08-15 11:58 ` Adhemerval Zanella Netto
2023-08-14 9:42 Florian Weimer
2023-08-14 20:49 ` DJ Delorie
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=87pm3uajev.fsf@oldenburg.str.redhat.com \
--to=fweimer@redhat.com \
--cc=dj@redhat.com \
--cc=libc-alpha@sourceware.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).