From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 119831 invoked by alias); 10 May 2018 17:45:56 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 119820 invoked by uid 89); 10 May 2018 17:45:56 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00,SPF_PASS autolearn=ham version=3.3.2 spammy=rarely, Hx-languages-length:1297 X-HELO: smtp.ispras.ru Received: from bran.ispras.ru (HELO smtp.ispras.ru) (83.149.199.196) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 10 May 2018 17:45:54 +0000 Received: from monopod.intra.ispras.ru (monopod.intra.ispras.ru [10.10.3.121]) by smtp.ispras.ru (Postfix) with ESMTP id DA3FA203C6; Thu, 10 May 2018 20:45:52 +0300 (MSK) Date: Thu, 10 May 2018 17:48:00 -0000 From: Alexander Monakov To: Jakub Jelinek cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH 0/2] Introduce gcc_qsort In-Reply-To: <20180510172420.GK8577@tucnak> Message-ID: References: <20180510155641.2950-1-amonakov@ispras.ru> <20180510172420.GK8577@tucnak> User-Agent: Alpine 2.20.13 (LNX 116 2015-12-14) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-SW-Source: 2018-05/txt/msg00490.txt.bz2 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