Re: [PATCH V2 3/3] strbuf: allow to use preallocated memory

Jeff King [off-list ref] writes:

quoted

I think that call should reset line.buf to the original buffer on
the stack, instead of saying "Ok, I'll ignore the original memory
not owned by us and instead keep pointing at the allocated memory",
as the allocation was done as a fallback measure.

I am not sure I agree. Do we think accessing the stack buffer is somehow
cheaper than the heap buffer (perhaps because of cache effects)? If so,
how much cheaper?

This is not about stack vs heap or even "cheaper" (whatever your
definition of cheap is).  The principle applies equally if the
original buffer came from BSS.

Perhaps I made it clearer by using a more exaggerated example e.g. a
typical expected buffer size of 128 bytes, but the third line of
1000 line input file was an anomaly that is 200k bytes long.  I do
not want to keep that 200k bytes after finishing to process that
third line while using its initial 80 bytes for the remaining 977
lines.

By the way, William seemed to be unhappy with die(), but I actually
think having a die() in the API may not be a bad thing if the check
were about something more sensible.  For example, even if a strbuf
that can grow dynamically, capping the maximum size and say "Hey
this is a one-lne-at-a-time text interface; if we need to grow the
buffer to 10MB, there is something wrong and a producer of such an
input does not even deserve a nice error message" could be an
entirely sensible attitude.  But that does not mean an initial
allocation should be 10MB.  If the expected typical workload fits
within a lot lower bound, starting from there and allowing it to
grow up to that maximum would be the more natural thing to do.

And the problem I have with the proposed "fixed" is that it does not
allow us to do that.

On Mon, Jun 06, 2016 at 04:24:53PM -0700, Junio C Hamano wrote:

This is not about stack vs heap or even "cheaper" (whatever your
definition of cheap is).  The principle applies equally if the
original buffer came from BSS.

Perhaps I made it clearer by using a more exaggerated example e.g. a
typical expected buffer size of 128 bytes, but the third line of
1000 line input file was an anomaly that is 200k bytes long.  I do
not want to keep that 200k bytes after finishing to process that
third line while using its initial 80 bytes for the remaining 977
lines.

Ah, I see. Yes, I can see that argument, though I'd counter that since
we _did_ see a 200k entry, perhaps the hint given in the code is not
actually very sensible. Having seen one big line, might we expect to see
more?

I dunno. I still feel like this whole thing is just micro-optimization
that is not even really going to be measurable outside of pathological
cases.

By the way, William seemed to be unhappy with die(), but I actually
think having a die() in the API may not be a bad thing if the check
were about something more sensible.  For example, even if a strbuf
that can grow dynamically, capping the maximum size and say "Hey
this is a one-lne-at-a-time text interface; if we need to grow the
buffer to 10MB, there is something wrong and a producer of such an
input does not even deserve a nice error message" could be an
entirely sensible attitude.  But that does not mean an initial
allocation should be 10MB.  If the expected typical workload fits
within a lot lower bound, starting from there and allowing it to
grow up to that maximum would be the more natural thing to do.

Yes, I very much agree that "sensible limits" should not be the same
thing as "initial allocated sizes". It is easy to conflate the two when
using static buffers (because it lets you skip allocation entirely,
which is much simpler!), but that usually leads to "sensible limits"
being set way too low as a compromise.

-Peff

On Mon, Jun 06, 2016 at 04:24:53PM -0700, Junio C Hamano wrote:

Jeff King [off-list ref] writes:

quoted

quoted

I think that call should reset line.buf to the original buffer on
the stack, instead of saying "Ok, I'll ignore the original memory
not owned by us and instead keep pointing at the allocated memory",
as the allocation was done as a fallback measure.

I am not sure I agree. Do we think accessing the stack buffer is somehow
cheaper than the heap buffer (perhaps because of cache effects)? If so,
how much cheaper?

This is not about stack vs heap or even "cheaper" (whatever your
definition of cheap is).  The principle applies equally if the
original buffer came from BSS.

Perhaps I made it clearer by using a more exaggerated example e.g. a
typical expected buffer size of 128 bytes, but the third line of
1000 line input file was an anomaly that is 200k bytes long.  I do
not want to keep that 200k bytes after finishing to process that
third line while using its initial 80 bytes for the remaining 977
lines.

"its initial 128 bytes", rather than "its initial 80 bytes", no?
Or else I'm lost :)
 

By the way, William seemed to be unhappy with die(), but I actually
think having a die() in the API may not be a bad thing if the check
were about something more sensible.  For example, even if a strbuf
that can grow dynamically, capping the maximum size and say "Hey
this is a one-lne-at-a-timve text interface; if we need to grow the
buffer to 10MB, there is something wrong and a producer of such an
input does not even deserve a nice error message" could be an
entirely sensible attitude.  But that does not mean an initial
allocation should be 10MB.  If the expected typical workload fits
within a lot lower bound, starting from there and allowing it to
grow up to that maximum would be the more natural thing to do.

And the problem I have with the proposed "fixed" is that it does not
allow us to do that.

The "fixed" feature was aimed to allow the users to use strbuf with
strings that they doesn't own themselves (a function parameter for
example). From Michael example in the original mail:

void f(char *path_buf, size_t path_buf_len)
{
    struct strbuf path;
    strbuf_wrap_fixed(&path, path_buf,
    strlen(path_buf),
    path_buf_len);
    ...
    /*
     * no strbuf_release() required here, but if called it
     * is a NOOP
     */
}

I don't have enough knowledge of the codebase to judge if this is
useful, you seem to think it's not.

About this capping, I have troubles to understand if this is something
you'd like to see in this patch (assuming I include your changes)? Or is
this theoretical?


To sum up:
* Rename "wrap" to "attach"
* Forget about this "fixed" feature
* Make the strbuf reuse the preallocated buffer after a reset() (and a
detach() probably?)
* Introduce a more practical macro STRBUF_INIT_ON_STACK() (maybe the
name is too technical?)
* A few code corrections

William Duclot [off-list ref] writes:

quoted

Perhaps I made it clearer by using a more exaggerated example e.g. a
typical expected buffer size of 128 bytes, but the third line of
1000 line input file was an anomaly that is 200k bytes long.  I do
not want to keep that 200k bytes after finishing to process that
third line while using its initial 80 bytes for the remaining 977
lines.

"its initial 128 bytes", rather than "its initial 80 bytes", no?

Either way would work, but 80 is closer to what I had in mind, as
the set-up of the example is "I know 99% of my input will fit within
80, but I'll allocate 128 to avoid realloc cost when there are rare
ones that bust 80.  I do not want to die only because there is an
occasional oddball that needs 200".

The "fixed" feature was aimed to allow the users to use strbuf with
strings that they doesn't own themselves (a function parameter for
example). From Michael example in the original mail:

void f(char *path_buf, size_t path_buf_len)
{
    struct strbuf path;
    strbuf_wrap_fixed(&path, path_buf,
    strlen(path_buf),
    path_buf_len);
    ...
    /*
     * no strbuf_release() required here, but if called it
     * is a NOOP
     */
}

Think what does the "..." part would do using the "path" strbuf.

If 'f()' is meant to take the "dying is perfectly fine if the data
we have to process exceeds the area we were given even by one byte"
attitude, then the "capped to the same length as allocated" is
perfectly fine, but if 'f()' cannot afford to die() and instead has
to signal an error condition to its caller, then this function has
to check the length currently in use (i.e. path.len) and how much
more memory it can still use, before making each call to strbuf_*()
functions, no?

If we were to add "fixed" feature, we'd want to see it to help a
function like f() that cannot afford to die() and does not want to
malloc()/realloc().  I do not think what was in this series was it.

On 06/07/2016 11:06 AM, William Duclot wrote:

[...]
The "fixed" feature was aimed to allow the users to use strbuf with
strings that they doesn't own themselves (a function parameter for
example). From Michael example in the original mail:

void f(char *path_buf, size_t path_buf_len)
{
    struct strbuf path;
    strbuf_wrap_fixed(&path, path_buf,
    strlen(path_buf),
    path_buf_len);
    ...

I also thought that "fixed" strbufs would be useful in cases where you
*know* what size string you need and only want a strbuf wrapper because
it offers a lot of convenience functions. Nowadays we would do that
using something like

static int feed_object(const unsigned char *sha1, int fd, int negative)
{
	char buf[42];

	if (negative && !has_sha1_file(sha1))
		return 1;

	memcpy(buf + negative, sha1_to_hex(sha1), 40);
	if (negative)
		buf[0] = '^';
	buf[40 + negative] = '\n';
	return write_or_whine(fd, buf, 41 + negative, "send-pack: send refs");
}

Instead, one could write

static int feed_object(const unsigned char *sha1, int fd, int negative)
{
	char buf[GIT_SHA1_HEXSZ + 2];
	struct strbuf line = WRAPPED_FIXED_STRBUF(buf);

	if (negative && !has_sha1_file(sha1))
		return 1;

	if (negative)
		strbuf_addch(&line, '^');
	strbuf_add(&line, sha1_to_hex(sha1), GIT_SHA1_HEXSZ);
	strbuf_addch(&line, '\n');
	return write_or_whine(fd, line.buf, line.len, "send-pack: send refs");
}

* It's a little less manual bookkeeping, and thus less error-prone,
  than the current code.

* If somebody decides to add another character to the line but
  forgets to increase the allocation size, the code dies in testing
  rather than (a) overflowing the buffer, like the current
  code, or (b) silently becoming less performant, as if it used a
  preallocated but non-fixed strbuf.

* There's no need to strbuf_release() (which can be convenient in
  a function with multiple exit paths).

I don't know whether this particular function should be rewritten; I'm
just giving an example of the type of scenario where I think it could be
useful.

In a world without fixed strbufs, what would one use in this situation?

Michael

On Wed, Jun 08, 2016 at 06:20:41PM +0200, Michael Haggerty wrote:

Instead, one could write

quoted

static int feed_object(const unsigned char *sha1, int fd, int negative)
{
	char buf[GIT_SHA1_HEXSZ + 2];
	struct strbuf line = WRAPPED_FIXED_STRBUF(buf);

	if (negative && !has_sha1_file(sha1))
		return 1;

	if (negative)
		strbuf_addch(&line, '^');
	strbuf_add(&line, sha1_to_hex(sha1), GIT_SHA1_HEXSZ);
	strbuf_addch(&line, '\n');
	return write_or_whine(fd, line.buf, line.len, "send-pack: send refs");
}

Hmm. I'm not sure that just replacing that with a regular heap-allocated
strbuf is so bad. It additionally gets rid of the SHA1_HEXSZ math in the
allocation.

So from your list of advantages:

* It's a little less manual bookkeeping, and thus less error-prone,
  than the current code.

We have this, but better.

* If somebody decides to add another character to the line but
  forgets to increase the allocation size, the code dies in testing
  rather than (a) overflowing the buffer, like the current
  code, or (b) silently becoming less performant, as if it used a
  preallocated but non-fixed strbuf.

Instead of overflowing, it just silently works.

* There's no need to strbuf_release() (which can be convenient in
  a function with multiple exit paths).

Same.

The downside, obviously, is the cost of malloc/free. It may even be
noticeable here here because this really is a tight loop of strbuf
allocation (OTOH, we immediately make a syscall; how expensive is
write() compared to malloc()?).

We can hack around that by reusing the same strbuf.

Unfortunately the usual trick of:

  struct strbuf buf = STRBUF_INIT;
  for (...) {
	strbuf_reset(&buf);
	...
  }
  strbuf_release(&buf);

does not work, because we are in a sub-function. We can pass in the
buffer as scratch space, but that makes the function interface a little
uglier than it needs to be.

Likewise, we could make the strbuf static inside feed_object().  It's
not so bad here, where we know there aren't re-entrancy issues, but it's
not a very safe pattern in general (and it leaks the memory when we're
done with the function).

That made me wonder if we could repeatedly reuse a buffer attached to
the file descriptor. And indeed, isn't that what stdio is? The whole
reason this buffer exists is because we are using a direct descriptor
write. If we switched this function to use fprintf(), we'd avoid the
whole buffer question, have a fixed cap on our memory use (since we just
flush anytime the buffer is full) _and_ we'd reduce the number of
write syscalls we're making by almost a factor of 100.

I don't know whether this particular function should be rewritten; I'm
just giving an example of the type of scenario where I think it could be
useful.

In a world without fixed strbufs, what would one use in this situation?

I know I've done the exact opposite of what you wanted here and talked
about this specific function. But I _do_ think this is a pattern I've
seen several times, where we format into a buffer only to write() it
out. I think they may comprise a reasonable number of our buffer-using
loops.

-Peff

On Wed, Jun 08, 2016 at 03:19:18PM -0400, Jeff King wrote:

That made me wonder if we could repeatedly reuse a buffer attached to
the file descriptor. And indeed, isn't that what stdio is? The whole
reason this buffer exists is because we are using a direct descriptor
write. If we switched this function to use fprintf(), we'd avoid the
whole buffer question, have a fixed cap on our memory use (since we just
flush anytime the buffer is full) _and_ we'd reduce the number of
write syscalls we're making by almost a factor of 100.

So all of this strbuf discussion aside, I think it is worth doing
something like this for this particular case.

-- >8 --
Subject: send-pack: use buffered I/O to talk to pack-objects

We start a pack-objects process and then write all of the
positive and negative sha1s to it over a pipe. We do so by
formatting each item into a fixed-size buffer and then
writing each individually. This has two drawbacks:

  1. There's some manual computation of the buffer size,
     which is not immediately obvious is correct (though it
     is).

  2. We write() once per sha1, which means a lot more system
     calls than are necessary.

We can solve both by wrapping the pipe descriptor in a stdio
handle; this is the same technique used by upload-pack when
serving fetches.

Note that we can also simplify and improve the error
handling here. The original detected a single write error
and broke out of the loop (presumably to avoid writing the
error message over and over), but never actually acted on
seeing an error; we just fed truncated input and took
whatever pack-objects returned.

In practice, this probably didn't matter, as the likely
errors would be caused by pack-objects dying (and we'd
probably just die with SIGPIPE anyway). But we can easily
make this simpler and more robust; the stdio handle keeps an
error flag, which we can check at the end.

Signed-off-by: Jeff King <redacted>
---
 send-pack.c | 33 ++++++++++++++++-----------------
 1 file changed, 16 insertions(+), 17 deletions(-)

diff --git a/send-pack.c b/send-pack.c
index 37ee04e..299d303 100644
--- a/send-pack.c
+++ b/send-pack.c

@@ -36,18 +36,15 @@ int option_parse_push_signed(const struct option *opt,
 	die("bad %s argument: %s", opt->long_name, arg);
 }
 
-static int feed_object(const unsigned char *sha1, int fd, int negative)
+static void feed_object(const unsigned char *sha1, FILE *fh, int negative)
 {
-	char buf[42];
-
 	if (negative && !has_sha1_file(sha1))
-		return 1;
+		return;
 
-	memcpy(buf + negative, sha1_to_hex(sha1), 40);
 	if (negative)
-		buf[0] = '^';
-	buf[40 + negative] = '\n';
-	return write_or_whine(fd, buf, 41 + negative, "send-pack: send refs");
+		putc('^', fh);
+	fputs(sha1_to_hex(sha1), fh);
+	putc('\n', fh);
 }
 
 /*

@@ -73,6 +70,7 @@ static int pack_objects(int fd, struct ref *refs, struct sha1_array *extra, stru
 		NULL,
 	};
 	struct child_process po = CHILD_PROCESS_INIT;
+	FILE *po_in;
 	int i;
 
 	i = 4;

@@ -97,21 +95,22 @@ static int pack_objects(int fd, struct ref *refs, struct sha1_array *extra, stru
 	 * We feed the pack-objects we just spawned with revision
 	 * parameters by writing to the pipe.
 	 */
+	po_in = xfdopen(po.in, "w");
 	for (i = 0; i < extra->nr; i++)
-		if (!feed_object(extra->sha1[i], po.in, 1))
-			break;
+		feed_object(extra->sha1[i], po_in, 1);
 
 	while (refs) {
-		if (!is_null_oid(&refs->old_oid) &&
-		    !feed_object(refs->old_oid.hash, po.in, 1))
-			break;
-		if (!is_null_oid(&refs->new_oid) &&
-		    !feed_object(refs->new_oid.hash, po.in, 0))
-			break;
+		if (!is_null_oid(&refs->old_oid))
+			feed_object(refs->old_oid.hash, po_in, 1);
+		if (!is_null_oid(&refs->new_oid))
+			feed_object(refs->new_oid.hash, po_in, 0);
 		refs = refs->next;
 	}
 
-	close(po.in);
+	fflush(po_in);
+	if (ferror(po_in))
+		die_errno("error writing to pack-objects");
+	fclose(po_in);
 
 	if (args->stateless_rpc) {
 		char *buf = xmalloc(LARGE_PACKET_MAX);

-- 
2.9.0.rc2.138.geb72a36