Derrick Stolee [off-list ref] 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.
On 2/15/2018 1:19 PM, Junio C Hamano wrote:
Derrick Stolee [off-list ref] writes:
quoted
+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