On Thu, 10 May 2018, Jakub Jelinek wrote: > Have you gathered some statistics on the element sizes and how often they > appear in qsort calls (perhaps weighted by n*log(n) of the element count) > across bootstrap+regtest?
No, but Adhemerval Zanella collected stats on bootstrap, and they are similar to my observations: https://sourceware.org/ml/libc-alpha/2018-01/msg00629.html > glibc uses indirect sorting (sorts pointers to the elements or indexes and > just reshuffles at the end) and has special case for the most commonly used > small element size (4/8). With C++ templates you could achieve that even > without macros, just by instantiating the mergesort and its helpers for the > few common cases. Or is that not worth it (as in, we never sort really > large (say > 32 bytes) element sizes and the 4 or 8 bytes long element sizes > aren't common enough to see benefit by using constant size memcpy for those > cases? I think it's not worth it as branches by element size are not too frequent, off the critical path, and easy for predictors. So doing it via templates would cause significant code growth for no speed gain. As for indirect sorting, we rarely sort elements of size other than 4/8, so I believe that's not worth it either. Alexander
