From: Jeff King <peff@peff.net>
To: Remi Galan Alfonso <remi.galan-alfonso@ensimag.grenoble-inp.fr>
Cc: William Duclot <william.duclot@ensimag.grenoble-inp.fr>,
git@vger.kernel.org,
simon rabourg <simon.rabourg@ensimag.grenoble-inp.fr>,
francois beutin <francois.beutin@ensimag.grenoble-inp.fr>,
antoine queru <antoine.queru@ensimag.grenoble-inp.fr>,
matthieu moy <matthieu.moy@grenoble-inp.fr>,
mhagger@alum.mit.edu
Subject: Re: [PATCH 0/2] strbuf: improve API
Date: Wed, 1 Jun 2016 17:07:13 -0400 [thread overview]
Message-ID: <20160601210713.GA18118@sigill.intra.peff.net> (raw)
In-Reply-To: <20160601074218.GB14096@sigill.intra.peff.net>
On Wed, Jun 01, 2016 at 03:42:18AM -0400, Jeff King wrote:
> I have no idea if those ideas would work. But I wouldn't want to start
> looking into either of them without some idea of how much time we're
> actually spending on strbuf mallocs (or how much time we would spend if
> strbufs were used in some proposed sites).
So I tried to come up with some numbers.
Here's an utterly silly use of strbufs, but one that I think should
over-emphasize the effect of any improvements we make:
diff --git a/Makefile b/Makefile
index 7a0551a..72b968a 100644
--- a/Makefile
+++ b/Makefile
@@ -579,6 +579,7 @@ PROGRAM_OBJS += shell.o
PROGRAM_OBJS += show-index.o
PROGRAM_OBJS += upload-pack.o
PROGRAM_OBJS += remote-testsvn.o
+PROGRAM_OBJS += foo.o
# Binary suffix, set to .exe for Windows builds
X =
diff --git a/foo.c b/foo.c
index e69de29..b62dd97 100644
--- a/foo.c
+++ b/foo.c
@@ -0,0 +1,18 @@
+#include "git-compat-util.h"
+#include "strbuf.h"
+
+int main(void)
+{
+ const char *str = "this is a string that we'll repeatedly insert";
+ size_t len = strlen(str);
+
+ int i;
+ for (i = 0; i < 1000000; i++) {
+ struct strbuf buf = STRBUF_INIT;
+ int j;
+ for (j = 0; j < 500; j++)
+ strbuf_add(&buf, str, len);
+ strbuf_release(&buf);
+ }
+ return 0;
+}
That takes about 3.5 seconds to run git-foo on my machine. Here's where
perf says the time goes:
# Children Self Command Shared Object Symbol
# ........ ........ ....... ................. ..........................
#
35.62% 34.58% git-foo git-foo [.] strbuf_add
22.70% 22.14% git-foo git-foo [.] strbuf_grow
19.85% 19.04% git-foo libc-2.22.so [.] __memcpy_avx_unaligned
9.47% 9.17% git-foo git-foo [.] main
4.88% 4.68% git-foo git-foo [.] memcpy@plt
3.21% 3.12% git-foo libc-2.22.so [.] realloc
1.75% 1.71% git-foo libc-2.22.so [.] _int_realloc
1.42% 0.00% git-foo [unknown] [.] 0x676e697274732061
0.82% 0.79% git-foo git-foo [.] xrealloc
0.61% 0.59% git-foo git-foo [.] memory_limit_check
0.45% 0.00% git-foo [unknown] [.] 0000000000000000
0.32% 0.00% git-foo [unknown] [.] 0x0000000000000fff
0.32% 0.32% git-foo [unknown] [k] 0x00007f591b44a2f0
0.31% 0.31% git-foo [unknown] [k] 0x0000000000404719
0.30% 0.00% git-foo [unknown] [.] 0x0000000000001ffe
0.30% 0.30% git-foo libc-2.22.so [.] _int_free
0.30% 0.28% git-foo libc-2.22.so [.] _int_malloc
So malloc and free are pretty low. It looks like realloc is more,
probably because of the memcpys it has to do. I don't think that would
be much better in a stack-based system (because we'd realloc there,
too). What would help is simply using a larger initial size (for _this_
made-up benchmark; I'm not convinced it would be all that good in the
real world).
But either way, most of the time is actually spent in the strbuf
functions themselves (interesting, if you replace strbuf_add with
strbuf_addf, we spend much more time dealing with the formatted input).
We can probably micro-optimize them some.
Here's a short and hacky patch to inline strbuf_grow, and to use
compiler intrinsics to do the overflow checks (which obviously isn't
portable, but we can easily hide it behind a macro and fall back to the
existing scheme):
diff --git a/strbuf.c b/strbuf.c
index 1ba600b..4f163cb 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -55,19 +55,25 @@ void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)
sb->buf[sb->len] = '\0';
}
-void strbuf_grow(struct strbuf *sb, size_t extra)
+static inline void strbuf_grow_inline(struct strbuf *sb, size_t extra)
{
int new_buf = !sb->alloc;
- if (unsigned_add_overflows(extra, 1) ||
- unsigned_add_overflows(sb->len, extra + 1))
+ if (__builtin_add_overflow(extra, sb->len, &extra) ||
+ __builtin_add_overflow(extra, 1, &extra))
die("you want to use way too much memory");
if (new_buf)
sb->buf = NULL;
- ALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);
+ ALLOC_GROW(sb->buf, extra, sb->alloc);
if (new_buf)
sb->buf[0] = '\0';
}
+void strbuf_grow(struct strbuf *sb, size_t extra)
+{
+ strbuf_grow_inline(sb, extra);
+}
+#define strbuf_grow strbuf_grow_inline
+
void strbuf_trim(struct strbuf *sb)
{
strbuf_rtrim(sb);
That drops my best-of-five for git-foo from:
real 0m3.377s
user 0m3.376s
sys 0m0.000s
to:
real 0m3.107s
user 0m3.104s
sys 0m0.000s
So that's at least measurable. Again, though, I'm not convinced it
actually matters much in the real world. But from what I see here, I'd
be surprised if the stack-buffer thing actually generates measurable
improvements here _or_ in the real world.
-Peff
next prev parent reply other threads:[~2016-06-01 21:07 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-05-30 10:36 [PATCH 0/2] strbuf: improve API William Duclot
2016-05-30 10:36 ` [PATCH 1/2] strbuf: add tests William Duclot
2016-05-30 11:26 ` Johannes Schindelin
2016-05-30 13:42 ` Simon Rabourg
2016-05-30 11:56 ` Matthieu Moy
2016-05-31 2:04 ` Michael Haggerty
2016-05-31 9:48 ` Simon Rabourg
2016-05-30 10:36 ` [PATCH 2/2] strbuf: allow to use preallocated memory William Duclot
2016-05-30 12:13 ` Johannes Schindelin
2016-05-30 13:20 ` William Duclot
2016-05-31 6:21 ` Johannes Schindelin
2016-05-31 3:05 ` Michael Haggerty
2016-05-31 6:41 ` Johannes Schindelin
2016-05-31 8:25 ` Michael Haggerty
2016-05-30 12:52 ` Matthieu Moy
2016-05-30 14:15 ` William Duclot
2016-05-30 14:34 ` Matthieu Moy
2016-05-30 15:16 ` William Duclot
2016-05-31 4:05 ` Michael Haggerty
2016-05-31 15:59 ` William Duclot
2016-06-03 14:04 ` William Duclot
2016-05-30 21:56 ` Mike Hommey
2016-05-30 22:46 ` William Duclot
2016-05-30 22:50 ` Mike Hommey
2016-05-31 6:34 ` Junio C Hamano
2016-05-31 15:45 ` William
2016-05-31 15:54 ` Matthieu Moy
2016-05-31 16:08 ` William Duclot
2016-05-30 11:32 ` [PATCH 0/2] strbuf: improve API Remi Galan Alfonso
2016-06-01 7:42 ` Jeff King
2016-06-01 19:50 ` David Turner
2016-06-01 20:09 ` Jeff King
2016-06-01 20:22 ` David Turner
2016-06-01 21:07 ` Jeff King [this message]
2016-06-02 11:11 ` Michael Haggerty
2016-06-02 12:58 ` Matthieu Moy
2016-06-02 14:22 ` William Duclot
2016-06-24 17:20 ` Jeff King
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
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20160601210713.GA18118@sigill.intra.peff.net \
--to=peff@peff.net \
--cc=antoine.queru@ensimag.grenoble-inp.fr \
--cc=francois.beutin@ensimag.grenoble-inp.fr \
--cc=git@vger.kernel.org \
--cc=matthieu.moy@grenoble-inp.fr \
--cc=mhagger@alum.mit.edu \
--cc=remi.galan-alfonso@ensimag.grenoble-inp.fr \
--cc=simon.rabourg@ensimag.grenoble-inp.fr \
--cc=william.duclot@ensimag.grenoble-inp.fr \
/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.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
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).