Updates:
Status: Invalid
Comment #1 on issue 2838 by [email protected]: Patch: Changes less<Grob *> to
Grob::less.
http://code.google.com/p/lilypond/issues/detail?id=2838
I am not sure about that: sometimes you can reduce algorithmic complexity
of some algorithms by putting sets into any old order as long as it is
reproducible in the current session. eq-based hashing works on that
premise: if you do a hash-for-each afterwards, you'll get the elements out
in consistent order, but the order might differ from run to run.
Comparing two sets for common elements can be done O(n lg n) by first
sorting the sets, then using a list-merge algorithm. Sorting on memory
address is quite feasible for that as long as the garbage collector does
not reallocate elements.
Finding a more predictable sorting order will in general be preferable. It
is possibly more expensive, and it is likely to mask decisions which are
actually made arbitrarily when they probably shouldn't.
In the use cases I see, this sorting happens right before calling uniq on
the result. Uniq removes equal successive elements. Since the elements of
the vectors here are indeed pointers, the previous sorting pass should sort
on pointer values in order to make this work reliably. The resulting array
will still be sorted according to pointer values. If that has an influence
on further processing, it might be conceivable to do a post-sort on some
other more reproducible criterion.
But in the given combination with uniq working with actual pointer
equivalence, this patch is wrong. It most certainly violates exactly the
intent of the people writing it and combining it with uniq and makes the
intended behavior less reliable in the case of different grobs comparing
equal, since in that case the following uniq will stop working reliably.
Since the underlying assumption for this patch and issue is clearly wrong,
I am marking the issue as invalid.
