On 2/15/2018 1:19 PM, Junio C Hamano wrote:
Derrick Stolee <sto...@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
