Re: [PATCH 3/3] ref-filter: factor ref_array pushing into its own function

[Jeff King]

On Mon, Apr 09, 2018 at 08:18:35AM +0900, Junio C Hamano wrote:

> Jeff King  writes:
> 
> > In preparation for callers constructing their own ref_array
> > structs, let's move our own internal push operation into its
> > own function.
> >
> > While we're at it, we can replace REALLOC_ARRAY() with
> > ALLOC_GROW(), which should give the growth operation
> > amortized linear complexity (as opposed to growing by one,
> > which is potentially quadratic, though in-place realloc
> > growth often makes this faster in practice).
> 
> Sorry, but I do not quite get the last part this paragraph.  Up to
> but not including ", though in-place..." I would understand as:
> 
>  - With ALLOC_GROW(), we are explicit in that we are amortizing
>the allocation cost by growing in exponential batches.
> 
>  - With REALLOC_ARRAY(), we are telling the underlying
>realloc(3) that it is OK to pretend that we grow by one, but
>if that permission is literally followed, it could end up
>quadratic.
> 
> So if you have really a bad realloc(3) implementation, switching
> to use ALLOC_GROW() is an improvement.

Yes, that's the gist of what I was saying. Though it is not even
necessarily "a bad realloc". At some point you may hit heap segmentation
and need to copy (though I guess if that happens repeatedly then maybe
your realloc really _is_ bad ;) ).

> But after that I am not sure what you are getting at.  Do you mean
> "In practice, a well-done realloc(3) does the amortizing internally
> anyway, which makes it faster than the grow-by-one quadratic, so
> this change may not make that much of a difference"?  Or do you mean
> "In practice, a well-done realloc(3) internally amortizes better
> than we do manually, so this change may hurt performance"?

The first. I couldn't measure any speedup on glibc, which makes me think
it's mostly doing in-place expansion.

> In either case, I think this splitting into a helper is obviously a
> good move, and using ALLOC_GROW() is conceptually cleaner, as we use
> it everywhere and tend to avoid realloc(3) just to add one item.
> 
> Other than that small confusion (not even a nit), three patches were
> pleasant read.  Thanks.

Thanks. Please feel free to expand or clarify the commit message if that
helps.

-Peff

Re: [PATCH 3/3] ref-filter: factor ref_array pushing into its own function

[Junio C Hamano]

Jeff King  writes:

> In preparation for callers constructing their own ref_array
> structs, let's move our own internal push operation into its
> own function.
>
> While we're at it, we can replace REALLOC_ARRAY() with
> ALLOC_GROW(), which should give the growth operation
> amortized linear complexity (as opposed to growing by one,
> which is potentially quadratic, though in-place realloc
> growth often makes this faster in practice).

Sorry, but I do not quite get the last part this paragraph.  Up to
but not including ", though in-place..." I would understand as:

 - With ALLOC_GROW(), we are explicit in that we are amortizing
   the allocation cost by growing in exponential batches.

 - With REALLOC_ARRAY(), we are telling the underlying
   realloc(3) that it is OK to pretend that we grow by one, but
   if that permission is literally followed, it could end up
   quadratic.

So if you have really a bad realloc(3) implementation, switching
to use ALLOC_GROW() is an improvement.

But after that I am not sure what you are getting at.  Do you mean
"In practice, a well-done realloc(3) does the amortizing internally
anyway, which makes it faster than the grow-by-one quadratic, so
this change may not make that much of a difference"?  Or do you mean
"In practice, a well-done realloc(3) internally amortizes better
than we do manually, so this change may hurt performance"?

In either case, I think this splitting into a helper is obviously a
good move, and using ALLOC_GROW() is conceptually cleaner, as we use
it everywhere and tend to avoid realloc(3) just to add one item.

Other than that small confusion (not even a nit), three patches were
pleasant read.  Thanks.

Re: [PATCH 3/3] ref-filter: factor ref_array pushing into its own function

[Harald Nordgren]

Looks good to me.

Reviewed-by: Harald Nordgren 

On Fri, Apr 6, 2018 at 9:27 PM, Derrick Stolee  wrote:
> On 4/6/2018 2:59 PM, Jeff King wrote:
>>
>> In preparation for callers constructing their own ref_array
>> structs, let's move our own internal push operation into its
>> own function.
>>
>> While we're at it, we can replace REALLOC_ARRAY() with
>> ALLOC_GROW(), which should give the growth operation
>> amortized linear complexity (as opposed to growing by one,
>> which is potentially quadratic, though in-place realloc
>> growth often makes this faster in practice).
>>
>> Signed-off-by: Jeff King 
>> ---
>>   ref-filter.c | 16 +---
>>   ref-filter.h |  8 
>>   2 files changed, 21 insertions(+), 3 deletions(-)
>>
>> diff --git a/ref-filter.c b/ref-filter.c
>> index c1c3cc9480..6e9328b274 100644
>> --- a/ref-filter.c
>> +++ b/ref-filter.c
>> @@ -1840,6 +1840,18 @@ static struct ref_array_item
>> *new_ref_array_item(const char *refname,
>> return ref;
>>   }
>>   +struct ref_array_item *ref_array_push(struct ref_array *array,
>> + const char *refname,
>> + const struct object_id *oid)
>> +{
>> +   struct ref_array_item *ref = new_ref_array_item(refname, oid);
>> +
>> +   ALLOC_GROW(array->items, array->nr + 1, array->alloc);
>> +   array->items[array->nr++] = ref;
>> +
>> +   return ref;
>> +}
>> +
>>   static int ref_kind_from_refname(const char *refname)
>>   {
>> unsigned int i;
>> @@ -1930,13 +1942,11 @@ static int ref_filter_handler(const char *refname,
>> const struct object_id *oid,
>>  * to do its job and the resulting list may yet to be pruned
>>  * by maxcount logic.
>>  */
>> -   ref = new_ref_array_item(refname, oid);
>> +   ref = ref_array_push(ref_cbdata->array, refname, oid);
>> ref->commit = commit;
>> ref->flag = flag;
>> ref->kind = kind;
>>   - REALLOC_ARRAY(ref_cbdata->array->items, ref_cbdata->array->nr +
>> 1);
>> -   ref_cbdata->array->items[ref_cbdata->array->nr++] = ref;
>> return 0;
>>   }
>>   diff --git a/ref-filter.h b/ref-filter.h
>> index 68268f9ebc..76cf87cb6c 100644
>> --- a/ref-filter.h
>> +++ b/ref-filter.h
>> @@ -135,4 +135,12 @@ void setup_ref_filter_porcelain_msg(void);
>>   void pretty_print_ref(const char *name, const struct object_id *oid,
>>   const struct ref_format *format);
>>   +/*
>> + * Push a single ref onto the array; this can be used to construct your
>> own
>> + * ref_array without using filter_refs().
>> + */
>> +struct ref_array_item *ref_array_push(struct ref_array *array,
>> + const char *refname,
>> + const struct object_id *oid);
>> +
>>   #endif /*  REF_FILTER_H  */
>
>
> The three patches in this series look good to me.
>
> Reviewed-by: Derrick Stolee 

Re: [PATCH 3/3] ref-filter: factor ref_array pushing into its own function

[Derrick Stolee]

On 4/6/2018 2:59 PM, Jeff King wrote:

In preparation for callers constructing their own ref_array
structs, let's move our own internal push operation into its
own function.

While we're at it, we can replace REALLOC_ARRAY() with
ALLOC_GROW(), which should give the growth operation
amortized linear complexity (as opposed to growing by one,
which is potentially quadratic, though in-place realloc
growth often makes this faster in practice).

Signed-off-by: Jeff King 
---
  ref-filter.c | 16 +---
  ref-filter.h |  8 
  2 files changed, 21 insertions(+), 3 deletions(-)

diff --git a/ref-filter.c b/ref-filter.c
index c1c3cc9480..6e9328b274 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -1840,6 +1840,18 @@ static struct ref_array_item *new_ref_array_item(const 
char *refname,
return ref;
  }
  
+struct ref_array_item *ref_array_push(struct ref_array *array,

+ const char *refname,
+ const struct object_id *oid)
+{
+   struct ref_array_item *ref = new_ref_array_item(refname, oid);
+
+   ALLOC_GROW(array->items, array->nr + 1, array->alloc);
+   array->items[array->nr++] = ref;
+
+   return ref;
+}
+
  static int ref_kind_from_refname(const char *refname)
  {
unsigned int i;
@@ -1930,13 +1942,11 @@ static int ref_filter_handler(const char *refname, 
const struct object_id *oid,
 * to do its job and the resulting list may yet to be pruned
 * by maxcount logic.
 */
-   ref = new_ref_array_item(refname, oid);
+   ref = ref_array_push(ref_cbdata->array, refname, oid);
ref->commit = commit;
ref->flag = flag;
ref->kind = kind;
  
-	REALLOC_ARRAY(ref_cbdata->array->items, ref_cbdata->array->nr + 1);

-   ref_cbdata->array->items[ref_cbdata->array->nr++] = ref;
return 0;
  }
  
diff --git a/ref-filter.h b/ref-filter.h

index 68268f9ebc..76cf87cb6c 100644
--- a/ref-filter.h
+++ b/ref-filter.h
@@ -135,4 +135,12 @@ void setup_ref_filter_porcelain_msg(void);
  void pretty_print_ref(const char *name, const struct object_id *oid,
  const struct ref_format *format);
  
+/*

+ * Push a single ref onto the array; this can be used to construct your own
+ * ref_array without using filter_refs().
+ */
+struct ref_array_item *ref_array_push(struct ref_array *array,
+ const char *refname,
+ const struct object_id *oid);
+
  #endif /*  REF_FILTER_H  */


The three patches in this series look good to me.

Reviewed-by: Derrick Stolee