Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:110144 Return-Path: Delivered-To: mailing list internals@lists.php.net Received: (qmail 89884 invoked from network); 12 May 2020 15:52:33 -0000 Received: from unknown (HELO php-smtp4.php.net) (45.112.84.5) by pb1.pair.com with SMTP; 12 May 2020 15:52:33 -0000 Received: from php-smtp4.php.net (localhost [127.0.0.1]) by php-smtp4.php.net (Postfix) with ESMTP id A321B1804D3 for ; Tue, 12 May 2020 07:29:14 -0700 (PDT) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on php-smtp4.php.net X-Spam-Level: X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,HTML_MESSAGE, RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE, SPF_PASS autolearn=no autolearn_force=no version=3.4.2 X-Spam-ASN: AS15169 209.85.128.0/17 X-Spam-Virus: No X-Envelope-From: Received: from mail-ot1-f50.google.com (mail-ot1-f50.google.com [209.85.210.50]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-256) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by php-smtp4.php.net (Postfix) with ESMTPS for ; Tue, 12 May 2020 07:29:14 -0700 (PDT) Received: by mail-ot1-f50.google.com with SMTP id 72so10658768otu.1 for ; Tue, 12 May 2020 07:29:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=c+TjkNOqV4F2K1SfV2bulSPtTmxIvgU1uSz6VCUWObo=; b=IdlEchgmR2Xt3UY3uLu11OCsLwwIQY0HS0C7y+xjX2su7PqyTC701uMuBp6t2xLt5p eils0YVHb1AxY2GnC0Fx6/Eeu140JAeze77uQJrKdbVMOdyc++6czhPA2V12wJdqHC+l mUfYQ9miGbpyIZSwVdZRlYyBAapq9oDFKe7sd2AbByrhRAnu7DYJiWxzl4ZQIVsN1oQS GacaE8tR1wXt3QAMvtF3sMYyTqX//RvajiKnbeSvf3FvvPLQjck/3aqtqMU4TVnzubuB HBtHhjaJCzh/UJCy2UKkL9SuNAFLnMP9OV+JXMcnEe/VcRulM9uc9/jPSrmebW9/bPrx Bf6Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=c+TjkNOqV4F2K1SfV2bulSPtTmxIvgU1uSz6VCUWObo=; b=iozGdqac1kKEQdbz/qnKFUDpx12V7aJS5bkrfKUn2PcL6A1CgUlyL+MbIfsnv9Oujv 16FtEY/3TCXdisYLPyAVmbVNZxl9DMmCNdPosv5LZOy/CQtDbpd8zjQCaalAudkribcE 8LDVZJwvwn6saaJbSsIxtkyAfX0SFlAImbW4xK4aiR7TpRfN4z3LFoZgVKjxoU3PBXj1 Q+KzDmFaW3mW9FYCZmY964O1nUTlPx9OIKyYWFItf8AJuF7jd0LHj3KGnKb7hr7iQbGg M+44TZaCY1SmpY6MajsFP8DvRdQ7il2rxqCTNzBhLDAOHj5vhY2U8+acJkGrJ1LoAwjC 6mrw== X-Gm-Message-State: AGi0Pua+Yej9528NyR3juuD4PQQ2JZONkZtspjQYThH4TnzmJjAX8zXa 4kYGM/SRT+X1Udg39eJ0OTEzMx8VgD1fLrHc1p4= X-Google-Smtp-Source: APiQypKBVMkn/9gECZ7obW6y47EJqG6YeO2b4eNnyztSzhd8Nlkf2C6uN1fyTchiq7RcVhS1hB9p1hUEVFVNvczW2PM= X-Received: by 2002:a9d:68d3:: with SMTP id i19mr13250569oto.83.1589293745965; Tue, 12 May 2020 07:29:05 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: Date: Tue, 12 May 2020 16:28:53 +0200 Message-ID: To: Nikita Popov Cc: PHP internals Content-Type: multipart/alternative; boundary="0000000000002c11a905a57449a9" Subject: Re: [PHP-DEV] [RFC] Make sorting stable From: nicolas.grekas+php@gmail.com (Nicolas Grekas) --0000000000002c11a905a57449a9 Content-Type: text/plain; charset="UTF-8" Hi Nikita, Thanks for another nice RFC. This was previously discussed in https://externals.io/message/108841, but I > figured it would make sense to create an RFC for this change: > https://wiki.php.net/rfc/stable_sorting > > As before, the implementation approach is to stick with the existing qsort > and use a fallback comparison criterion, which is cheap to implement > internally. The obvious alternative is to use a stable base sort like > Timsort. I gave this a quick try in > https://github.com/php/php-src/pull/5559, > and it does better in some cases (already sorted data) and worse in others > (random data). I don't plan to pursue this direction personally. (It may > also be interesting to use pdqsort as the unstable base, which should make > the "already sorted" case faster.) > IIRC, in PHP 5 sorting was stable. Then PHP 7 made it unstable. That was something to account for when migrating - BC break inside. Do you know why did this happen at the time? On my side, I would very much prefer a new sorting flag, to be 200% sure of the behavior: sort($array, SORT_STABLE) That would allow ppl that don't care about stability to let the engine go with the fastest algorithm. WDYT? Nicolas --0000000000002c11a905a57449a9--