From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS3215 2.6.0.0/16 X-Spam-Status: No, score=-5.4 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,MAILING_LIST_MULTI,NICE_REPLY_A, RCVD_IN_DNSWL_MED,SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id D03251F8C6 for ; Mon, 6 Sep 2021 18:44:33 +0000 (UTC) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DEE02385B83A for ; Mon, 6 Sep 2021 18:44:32 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DEE02385B83A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1630953872; bh=jmcKDvGaEttz1HfymWhFYLSQs4h40tCTZZ6rViXpgSc=; h=Subject:To:References:Date:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To:Cc: From; b=v8C27erFfaUcS0pVZOB67YbPrtH6K84a6caJqOUUB28mn6NtCFTcWA8PEDxzT2fxu rxQZbkWojFaF+2CYrHy1NkiJ3ydmJz+RzPh4QkYMYDr0ZDd3sHkyWrmfGXMhuZ9SNB cvK+TjVXPzy8xPnSKS56HR7gYaqRA1iwlD98514A= Received: from mail-qv1-xf35.google.com (mail-qv1-xf35.google.com [IPv6:2607:f8b0:4864:20::f35]) by sourceware.org (Postfix) with ESMTPS id 667303839416 for ; Mon, 6 Sep 2021 18:43:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 667303839416 Received: by mail-qv1-xf35.google.com with SMTP id s16so4404799qvt.13 for ; Mon, 06 Sep 2021 11:43:46 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=jmcKDvGaEttz1HfymWhFYLSQs4h40tCTZZ6rViXpgSc=; b=neBw6r0uykCmpI9CXoI9cdUVJCR3VT4J1sc2vrREZQ+KYCaPhCJ6rRWOipb5UtHXKb PxNF/46+K4RkdQ26W0EGYTWobkeE/v4VT9CnzH+9rjgqV6E/BvBZAmYyriSyKlc7m6gH 02Wuj5MsFZXCC65KjqQYuONMsDjbJHyaTN4R6cN5/1FdzTYvDcl6j43n/U/KKjwqLjZu mABE78cP9HwvkjpD9z2Poazldn6Xk8QU9YbXg9/i80AYZX9SJqW4GFeGPXoSurgivhz4 u/TNuRNBAVPTUeAnqfLKsebqRMS3kOin9r0meVQNg85BOU3zfk2S6gkWDS29J6+jycF7 LBxA== X-Gm-Message-State: AOAM531ngiFS6mgdoHXvxbo1C3H8aUwzJlnuZOtQ2V/CqfJZ7qT8SEL5 LWEDzlIUcKrO4Idf6q8AVIit7lZuEzLFtQ== X-Google-Smtp-Source: ABdhPJyAmuAOmsIW6MWZlPTZrgwXn8uOZShofgrzCQZxVCgApaCwUxXrEzYZgBd3JUlU2ikEJVAo5g== X-Received: by 2002:a0c:8d0f:: with SMTP id r15mr13416115qvb.1.1630953825886; Mon, 06 Sep 2021 11:43:45 -0700 (PDT) Received: from ?IPv6:2804:431:c7cb:733d:210:e147:8627:2d6? ([2804:431:c7cb:733d:210:e147:8627:2d6]) by smtp.gmail.com with ESMTPSA id o23sm5710509qtq.7.2021.09.06.11.43.44 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 06 Sep 2021 11:43:45 -0700 (PDT) Subject: Re: [PATCH v3 6/7] stdlib: Implement introsort with qsort To: Alexander Monakov References: <20210903171144.952737-1-adhemerval.zanella@linaro.org> <20210903171144.952737-7-adhemerval.zanella@linaro.org> Message-ID: Date: Mon, 6 Sep 2021 15:43:43 -0300 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Adhemerval Zanella via Libc-alpha Reply-To: Adhemerval Zanella Cc: libc-alpha@sourceware.org Errors-To: libc-alpha-bounces+e=80x24.org@sourceware.org Sender: "Libc-alpha" On 04/09/2021 06:17, Alexander Monakov wrote: > On Fri, 3 Sep 2021, Adhemerval Zanella via Libc-alpha wrote: > >> @@ -235,6 +305,9 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, >> else >> swap_func = SWAP_BYTES; >> >> + /* Maximum depth before quicksort switches to heapsort. */ >> + size_t depth = 2 * (CHAR_BIT - 1 - __builtin_clzl (total_elems)); >> + > > This doesn't look right, the expression in parenthesis is usually negative, > conversion to size_t wraps around and you make 'depth' a huge positive value. > The first term probably should have been 'CHAR_BIT * sizeof(size_t)'. It is not indeed, it should be: size_t depth = 2 * (sizeof (size_t) * CHAR_BIT - 1 - __builtin_clzl (total_elems)); (I think I did something wrong on some rebase, since I had the above originally). > > Does this mean that heapsort fallback was not exercised in testing? The current tests does not trigger the quadratic behavior on quicksort, that's why I have added the tst-qsort3. The heapsort_r is called on both 'SORTED' and 'BITONIC' array distribution (which should be expected since they tend to be pattern-defeating for quicksort implementations). > > Also, is it certain at that point that total_elems is nonzero? __builtin_clzl > is undefined for a zero argument. Yes, the patch also takes care of that: @@ -222,7 +292,7 @@ _quicksort (void *const pbase, size_t total_elems, size_t size, const size_t max_thresh = MAX_THRESH * size; - if (total_elems == 0) + if (total_elems <= 1) /* Avoid lossage with unsigned arithmetic below. */ return;