On Mon, Jul 17, 2017 at 11:10:01AM +0300, Alexander Monakov wrote: > On Sun, 16 Jul 2017, Segher Boessenkool wrote: > > > How? There's no stable sort in libc and switching over to std::stable_sort > > > would be problematic. > > > > Why? > > - you'd need to decide if the build time cost of extra 8000+ lines > lines brought in by <algorithm> (per each TU) is acceptable; > > - you'd need to decide if the code size cost of multiple instantiations > of template stable_sort is acceptable (or take measures to unify them);
OTOH it should be faster than calling callbacks all the time. > - you'd need to adapt comparators, as STL uses a different interface > that C qsort; > > - you'd need to ensure it doesn't lead to a noticeable slowdown. Okay, so the slowness of compiling STL stuff is a very real issue. > > Sure. Some of our sorts in fact require stable sort though > > At moment only bb-reorder appears to use std::stable_sort, is that what > you meant, or are there more places? For example all_saved_regs (in caller-save.c) ensures a stable sort (I don't know if it actually needs it, or this is just to ensure only identical objects compare equal). I know the one in bb-reorder very much does need it (I added it myself). Sure, you can avoid it by essentially doing it manually (with a last-resort comparison). Segher
