Nguyễn Thái Ngọc Duy [off-list ref] writes:
Revert the order of delta applying so that by the time a delta is
applied, its base is either non-delta or already inflated.
get_delta_base() is still recursive, but because base's data is always
ready, the inner get_delta_base() call never has any chance to call
itself again.
I suspect s/Revert/Reverse/ here, but I have a feeling that the structure
of the resulting code is a bit too complex and subtle.
In parse_pack_objects(), we have two passes. The first pass scans to
enumerate the objects that appear in the pack and sift them into base and
delta objects, and the second one starts from a base object, resolves its
immediate children with find_unresolved_daltas(), but that function recurses
many times, bound only by the number of objects in the pack, which is the
issue you are trying to address with this series.
I wonder if a cleaner approach is to change the loop in the second pass in
such a way that (1) the function it calls resolves _only_ the immediate
children of the object we know its final shape (either because the object
was recorded in the deflated form in the pack, or we have already resolved
it in earlier iteration), and (2) the loop goes over the objects[] array
not just once, but until we stopped making progress.
It would require us to be able to tell, by looking at objects[i], if the
object itself has already been handled (perhaps you can look at its
idx.sha1 field for this purpose) and if we have already handled its
immediate delta children (you may need to add a bit to struct object_entry
for this).
2012/1/10 Junio C Hamano [off-list ref]:
In parse_pack_objects(), we have two passes. The first pass scans to
enumerate the objects that appear in the pack and sift them into base and
delta objects, and the second one starts from a base object, resolves its
immediate children with find_unresolved_daltas(), but that function recurses
many times, bound only by the number of objects in the pack, which is the
issue you are trying to address with this series.
I wonder if a cleaner approach is to change the loop in the second pass in
such a way that (1) the function it calls resolves _only_ the immediate
children of the object we know its final shape (either because the object
was recorded in the deflated form in the pack, or we have already resolved
it in earlier iteration), and (2) the loop goes over the objects[] array
not just once, but until we stopped making progress.
So basically:
- remove the recursion code from get_base_data()
- update find_unresolved_deltas() to mark resolved objects handled
- put find_unresolve_deltas() call into a loop to go through all
unhandled objects
correct? Yeah I think it's simpler than current code.
It would require us to be able to tell, by looking at objects[i], if the
object itself has already been handled (perhaps you can look at its
idx.sha1 field for this purpose) and if we have already handled its
immediate delta children (you may need to add a bit to struct object_entry
for this).
--
Duy
On Tue, Jan 10, 2012 at 8:03 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
correct? Yeah I think it's simpler than current code.
I wrote about core.deltabasecachelimit, then deleted it, thinking it
should be ok, but how do handle the case when you use up cache limit?
Some handled objects may be freed when we're short on cache and need
to be resolved again before we could resolve an unhandled object.
Assume we're at the limit, have resolved A, which has two children B
and C. When we resolve B we need to free A to keep it fit in cache. By
the time we look at C, A needs to be resolved again. Without tracing
back (i.e. what get_base_data() does), we don't know what we need to
re-resolve among all handled objects.
--
Duy