Re: [PATCH/RFH 0/3] stable priority-queue
On Mon, Jul 14, 2014 at 01:02:56PM +0200, David Kastrup wrote: > Jeff King writes: > > > As Junio and I discussed earlier in [1], this series makes the > > prio_queue struct stable with respect to object insertion (which in turn > > means we can use it to replace commit_list in more places). > > I don't think that this makes sense in general since it assumes the > appropriate fallback behavior to be FIFO. Depending on the use case, it > might be the other way round, or something else (like topology-based) > entirely. Remember that this is just a tie-breaker for the regular comparison function. If you want to represent some other ordering, you are free to do the tie-breaking yourself in your comparison function. The one thing we can easily provide but do not is LIFO ordering for the tie-breaker. That would be trivial to add as a flag on the prio_queue, but I'd wait until there is actually a caller who wants it. Yes, it's a bit hacky to provide it for cases which _don't_ care about order (or implement their own separate tie-breaker). But the worst case there is that we are wasting some memory, and I wasn't able to measure a real slow-down. I think it's a reasonable compromise given the lack of generics in C. But if you have a case that is measurably affected, please let me know, and I can look into implementing it in a type-agnostic way (so that the embedded insertion counter becomes just another type). > I see that struct commit already contains an integer field called > "index", assigned sequentially, which might conceivably be used for > tie-breaking independent from the actual prio_queue use at no extra > cost. I don't think it's a good idea to rely on that index, as it is anything but stable. It represents whatever order commits happened to be first touched in the current program run. So: 1. Performing the same operation in-process versus in a sub-process may produce different results. 2. Arguments to a command may have unexpected effects. E.g., specifying "--tags" to "rev-list" will look up the commit at each tag ref, giving them much lower index numbers than they would if we reached only through the normal traversal. -Peff -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH/RFH 0/3] stable priority-queue
Jeff King writes: > As Junio and I discussed earlier in [1], this series makes the > prio_queue struct stable with respect to object insertion (which in turn > means we can use it to replace commit_list in more places). I don't think that this makes sense in general since it assumes the appropriate fallback behavior to be FIFO. Depending on the use case, it might be the other way round, or something else (like topology-based) entirely. commit_list may be unsuitable as such for intermingled addition of unsorted and extraction of sorted elements (the general use case for priority queues). I see that struct commit already contains an integer field called "index", assigned sequentially, which might conceivably be used for tie-breaking independent from the actual prio_queue use at no extra cost. The resulting order will of course be somewhat arbitrary in a different way, but at least will correspond to the order the commits have been discovered/generated, so they should still exhibit a more topological relation than what prio_queue does without further help. -- David Kastrup -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH/RFH 0/3] stable priority-queue
On Mon, Jul 14, 2014 at 12:40 PM, Jeff King wrote: > As Junio and I discussed earlier in [1], this series makes the > prio_queue struct stable with respect to object insertion (which in turn > means we can use it to replace commit_list in more places). > > I think everything here is correct, but the second commit fails the > final test in t5539. I think the test is just flaky (hence the RFH and > cc to Duy). > > That test creates some unrelated commits in two separate repositories, > and then fetches from one to the other. Since the commit creation > happens in a subshell, the first commit in each ends up with the same > test_tick value. When fetch-pack looks at the two root commits > "unrelated1" and "new-too", the exact sequence of ACKs is different > depending on which one it pulls out of the queue first. > > With the current code, it happens to be "unrelated1" (though this is not > at all guaranteed by the prio_queue data structure, it is deterministic > for this particular sequence of input). We see the ready-ACK, and the > test succeeds. > > With the stable queue, we reliably get "new-too" out (since it is our > local tip, it is added to the queue before we even talk to the remote). > We never see a ready-ACK, and the test fails due to the grep on the > TRACE_PACKET output at the end (the fetch itself succeeds as expected). > > I'm really not quite clear on what's supposed to be going on in the > test. I can make it pass with: > > diff --git a/t/t5539-fetch-http-shallow.sh b/t/t5539-fetch-http-shallow.sh > index 94553e1..b461188 100755 > --- a/t/t5539-fetch-http-shallow.sh > +++ b/t/t5539-fetch-http-shallow.sh > @@ -54,6 +54,7 @@ EOF > test_expect_success 'no shallow lines after receiving ACK ready' ' > ( > cd shallow && > + test_tick && > for i in $(test_seq 15) > do > git checkout --orphan unrelated$i && > > which just bumps the timestamp for the unrelated* commits (so that they > are always more recent than "new-too" and get picked first). I'm not > sure if that is too hacky, or if there's a more robust way to set up the > test. The test needs the right amount of "have"s with pkt-flush inserted at the right place. If test_tick makes it happy, I think we could go with it for now. I'll try to study this code more and see if I can come up with a better test. It'll be low priority in my backlog though. -- Duy -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH/RFH 0/3] stable priority-queue
As Junio and I discussed earlier in [1], this series makes the prio_queue struct stable with respect to object insertion (which in turn means we can use it to replace commit_list in more places). I think everything here is correct, but the second commit fails the final test in t5539. I think the test is just flaky (hence the RFH and cc to Duy). That test creates some unrelated commits in two separate repositories, and then fetches from one to the other. Since the commit creation happens in a subshell, the first commit in each ends up with the same test_tick value. When fetch-pack looks at the two root commits "unrelated1" and "new-too", the exact sequence of ACKs is different depending on which one it pulls out of the queue first. With the current code, it happens to be "unrelated1" (though this is not at all guaranteed by the prio_queue data structure, it is deterministic for this particular sequence of input). We see the ready-ACK, and the test succeeds. With the stable queue, we reliably get "new-too" out (since it is our local tip, it is added to the queue before we even talk to the remote). We never see a ready-ACK, and the test fails due to the grep on the TRACE_PACKET output at the end (the fetch itself succeeds as expected). I'm really not quite clear on what's supposed to be going on in the test. I can make it pass with: diff --git a/t/t5539-fetch-http-shallow.sh b/t/t5539-fetch-http-shallow.sh index 94553e1..b461188 100755 --- a/t/t5539-fetch-http-shallow.sh +++ b/t/t5539-fetch-http-shallow.sh @@ -54,6 +54,7 @@ EOF test_expect_success 'no shallow lines after receiving ACK ready' ' ( cd shallow && + test_tick && for i in $(test_seq 15) do git checkout --orphan unrelated$i && which just bumps the timestamp for the unrelated* commits (so that they are always more recent than "new-too" and get picked first). I'm not sure if that is too hacky, or if there's a more robust way to set up the test. Anyway, here are the patches. [1/3]: prio-queue: factor out compare and swap operations [2/3]: prio-queue: make output stable with respect to insertion [3/3]: paint_down_to_common: use prio_queue -Peff [1] http://thread.gmane.org/gmane.comp.version-control.git/252472/focus=252475 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
