git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 09/17] gc_boundary(): move the check "alloc <= nr" to caller

From
Michael Haggerty <mhagger@alum.mit.edu>
Date
May 23, 2013, 07:09 UTC
Message-ID
<519DC0B7.7080401@alum.mit.edu>
In-Reply-To
<7vobc4nrz8.fsf@alter.siamese.dyndns.org>
On 05/21/2013 07:49 PM, Junio C Hamano wrote:
Show 15 quoted lines
> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> There is no logical reason for this test to be here.  At the caller we
>> might be able to figure out its meaning.
>>
>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
>> ---
> 
> I do not think this change is justified, *unless* the caller later
> in the series gains a better heuristics than what can be done with
> information in the object_array (namely, alloc and nr) to decide
> when to trigger gc.
> 
> And I was hoping to see such a cleverness added to the caller, but I
> do not think I saw any.
Correct.
Show 13 quoted lines
> I would have to say gc_boundary() knows better when it needs to gc
> with the code at this point in the series, and that is true also in
> the final code after all the patches in this series.
> 
> If we keep the "when to gc" logic inside "gc", in 11/17 this caller
> can no longer call directly to object_array_filter().  It should
> call gc_boundary(), but I see it as a merit, not a downside.  The
> "gc function can later be taught the high/low watermark logic you
> alluded to in 10/17, and the growth/shrinkage characteristic you
> would take advantage of while doing "gc" is specific to this
> codepath.  And the logic still does not have to have access to
> anything only the caller has access to; "gc" can work on what can be
> read from the object_array->{alloc,nr} that is given to it.

I don't feel strongly about this patch and if you prefer to have it dropped I will do so. But let me explain my reasoning:

1. The function name gc_boundary() suggests that it will do a garbage
collection unconditionally.  In fact, it might or might not depending on
this test.  At the caller, this made it look like a gc was happening
each time through the loop, which made me nervous about the performance.
 The new version makes it clear at the caller that the gc is only
happening occasionally.
2. Even assuming that gc_boundary() were renamed to maybe_gc_boundary(),
the function has hopelessly little information on which to base its
decision whether or not to gc, and the choice of policy can only be
justified based on some implicit knowledge about how the array is grown
and shrunk.  But the growing/shrinking is done at the layer of the
caller, and therefore the choice of gc policy also belongs at the layer
of the caller.
3. As you point out, if the gc policy is ever to be made more
intelligent, then gc_boundary() is unlikely to have enough information
to implement the new policy (e.g., it would have no place to record
low/high water marks).  Separating concerns at the correct level would
make a change like that easier.

At the moment I am not interested in improving the gc policy of this code. The only reason that I am mucking about here is to change it to use object_array_filter(), which is needed to centralize where object_array_entries are created and destroyed so that the "name" memory can be copied and freed consistently. That can be done with or without patches 09 and 10. Please let me know what you prefer.

Michael
Show 51 quoted lines
>   revision.c | 27 ++++++++++++---------------
> 
>>  1 file changed, 12 insertions(+), 15 deletions(-)
>>
>> diff --git a/revision.c b/revision.c
>> index 8ac88d6..2e0992b 100644
>> --- a/revision.c
>> +++ b/revision.c
>> @@ -2437,23 +2437,19 @@ static struct commit *get_revision_1(struct rev_info *revs)
>>  
>>  static void gc_boundary(struct object_array *array)
>>  {
>> -	unsigned nr = array->nr;
>> -	unsigned alloc = array->alloc;
>> +	unsigned nr = array->nr, i, j;
>>  	struct object_array_entry *objects = array->objects;
>>  
>> -	if (alloc <= nr) {
>> -		unsigned i, j;
>> -		for (i = j = 0; i < nr; i++) {
>> -			if (objects[i].item->flags & SHOWN)
>> -				continue;
>> -			if (i != j)
>> -				objects[j] = objects[i];
>> -			j++;
>> -		}
>> -		for (i = j; i < nr; i++)
>> -			objects[i].item = NULL;
>> -		array->nr = j;
>> +	for (i = j = 0; i < nr; i++) {
>> +		if (objects[i].item->flags & SHOWN)
>> +			continue;
>> +		if (i != j)
>> +			objects[j] = objects[i];
>> +		j++;
>>  	}
>> +	for (i = j; i < nr; i++)
>> +		objects[i].item = NULL;
>> +	array->nr = j;
>>  }
>>  
>>  static void create_boundary_commit_list(struct rev_info *revs)
>> @@ -2577,7 +2573,8 @@ static struct commit *get_revision_internal(struct rev_info *revs)
>>  		if (p->flags & (CHILD_SHOWN | SHOWN))
>>  			continue;
>>  		p->flags |= CHILD_SHOWN;
>> -		gc_boundary(&revs->boundary_commits);
>> +		if (revs->boundary_commits.alloc <= revs->boundary_commits.nr)
>> +			gc_boundary(&revs->boundary_commits);
>>  		add_object_array(p, NULL, &revs->boundary_commits);
>>  	}
-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/
Previous: Junio C HamanoNext: Junio C Hamano
Message 19 of 42 in “Remove assumptions about refname lifetimes”
  1. 00/17 Remove assumptions about refname lifetimesMichael Haggerty, May 19, 2013
  2. 01/17 describe: make own copy of refnameMichael Haggerty, May 19, 2013
  3. 02/17 fetch: make own copies of refnamesMichael Haggerty, May 19, 2013
  4. 03/17 add_rev_cmdline(): make a copy of the name argumentMichael Haggerty, May 19, 2013
  5. 04/17 builtin_diff_tree(): make it obvious that function wants two entriesMichael Haggerty, May 19, 2013
  6. Junio C HamanoMay 21, 2013
  7. Michael HaggertyMay 23, 2013
  8. 05/17 cmd_diff(): use an object_array for holding treesMichael Haggerty, May 19, 2013
  9. Junio C HamanoMay 21, 2013
  10. Michael HaggertyMay 23, 2013
  11. 06/17 cmd_diff(): rename local variable "list" -> "entry"Michael Haggerty, May 19, 2013
  12. 07/17 cmd_diff(): make it obvious which cases are exclusive of each otherMichael Haggerty, May 19, 2013
  13. 08/17 revision: split some overly-long linesMichael Haggerty, May 19, 2013
  14. Junio C HamanoMay 21, 2013
  15. Michael HaggertyMay 23, 2013
  16. Junio C HamanoMay 23, 2013
  17. 09/17 gc_boundary(): move the check "alloc <= nr" to callerMichael Haggerty, May 19, 2013
  18. Junio C HamanoMay 21, 2013
  19. Michael HaggertyMay 23, 2013
  20. Junio C HamanoMay 23, 2013
  21. 10/17 get_revision_internal(): make check less mysteriousMichael Haggerty, May 19, 2013
  22. Junio C HamanoMay 21, 2013
  23. Michael HaggertyMay 23, 2013
  24. 11/17 object_array: add function object_array_filter()Michael Haggerty, May 19, 2013
  25. 12/17 object_array_remove_duplicates(): rewrite to reduce copyingMichael Haggerty, May 19, 2013
  26. 13/17 fsck: don't put a void*-shaped peg in a char*-shaped holeMichael Haggerty, May 19, 2013
  27. 14/17 find_first_merges(): initialize merges variable using initializerMichael Haggerty, May 19, 2013
  28. 15/17 find_first_merges(): remove unnecessary codeMichael Haggerty, May 19, 2013
  29. 16/17 object_array_entry: copy name before storing in name fieldMichael Haggerty, May 19, 2013
  30. Johan HerlandMay 20, 2013
  31. Michael HaggertyMay 20, 2013
  32. Jeff KingMay 20, 2013
  33. Michael HaggertyMay 20, 2013
  34. 17/17 refs: document the lifetime of the refname passed to each_ref_fnMichael Haggerty, May 19, 2013
  35. Johan HerlandMay 20, 2013
  36. Michael HaggertyMay 20, 2013
  37. Junio C HamanoMay 20, 2013
  38. Jeff KingMay 20, 2013
  39. Johan HerlandMay 20, 2013
  40. Junio C HamanoMay 20, 2013
  41. Johan HerlandMay 20, 2013
  42. Junio C HamanoMay 21, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.