• Jeff King's avatar
    prio-queue: make output stable with respect to insertion · e8f91e3d
    Jeff King authored
    If two items are added to a prio_queue and compare equal,
    they currently come out in an apparently random order (this
    order is deterministic for a particular sequence of
    insertions and removals, but does not necessarily match the
    insertion order). This makes it unlike using a date-ordered
    commit_list, which is one of the main types we would like to
    replace with it (because prio_queue does not suffer from
    O(n) insertions).
    
    We can make the priority queue stable by keeping an
    insertion counter for each element, and using it to break
    ties. This does increase the memory usage of the structure
    (one int per element), but in practice it does not seem to
    affect runtime. A best-of-five "git rev-list --topo-order"
    on linux.git showed less than 1% difference (well within the
    run-to-run noise).
    
    In an ideal world, we would offer both stable and unstable
    priority queues (the latter to try to maximize performance).
    However, given the lack of a measurable performance
    difference, it is not worth the extra code.
    Signed-off-by: default avatarJeff King <peff@peff.net>
    Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
    e8f91e3d
prio-queue.h 1.49 KB