From: Derrick Stolee <stolee@gmail.com>
Date: Thu, 15 Feb 2018 18:23:12 GMT
Subject: Re: [PATCH v3 04/14] commit-graph: implement write_commit_graph()
Message-ID: <91e19f5b-ac4b-5843-b3b0-8eba37aaee68@gmail.com>
In-Reply-To: <xmqqinay9kv4.fsf@gitster-ct.c.googlers.com>

On 2/15/2018 1:19 PM, Junio C Hamano wrote:
> Derrick Stolee <stolee@gmail.com> writes:
>
>> +struct packed_oid_list {
>> +	struct object_id **list;
>> +	int nr;
>> +	int alloc;
>> +};
> What is the typical access pattern for this data structure?  If it
> is pretty much "allocate and grow as we find more", then a dynamic
> array of struct (rather than a dynamic array of pointers to struct)
> would be a lot more appropriate.  IOW
>
> 	struct packed_oid_list {
> 		struct object_id *list;
> 		int nr, alloc;
> 	};
>
> The version in the posted patch has to pay malloc overhead plus an
> extra pointer for each object id in the list; unless you often
> replace elements in the list randomly and/or you borrow object ID
> field in other existing data structure whose lifetime is longer than
> this list by pointing at it, I do not see how the extra indirection
> is worth it.
>

The pattern used in write_commit_graph() is to append OIDs to the list 
as we discover them and then sort in lexicographic order. The sort then 
only swaps pointers.

I can switch this to sort the 'struct object_id' elements themselves, if 
that is a better pattern.

Thanks,
-Stolee