From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qv1-xf30.google.com (mail-qv1-xf30.google.com [IPv6:2607:f8b0:4864:20::f30]) by sourceware.org (Postfix) with ESMTPS id 1424A3858D20 for ; Thu, 9 Mar 2023 19:57:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 1424A3858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-qv1-xf30.google.com with SMTP id m4so2229381qvq.3 for ; Thu, 09 Mar 2023 11:57:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; t=1678391878; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=nFWhKsUHikr0MnqTKDu3Jn6u9jODXMOrGgvNDrdwTT8=; b=jkwCiEIvhdmyuq2hJdzExfpKh5eigcMFV/carpdlcCA13EUbo4J7Mq5N/GeNc3Cewa IGxEAWCcGNUon0Xnk5eqUcIZU2tOz8sDY0N/Q+cDlwGj1VNkTeCgbGo2zGkFDwsG1sJr 9QVl7Oy2RFgilytY83uwICySM8WaEwP0ILhbnyK/WPCDHO0obMAc29w1wI3IjkqARXWK QoB2lMZKLBSRWAz0j9COZEExS99OqzarD80g/iSUJ5jrQdBTTGpbN7rk60yu3FrobIO4 M70RDSycdnqJidzC2xrnU+/68WmJakqTHKp3MdQaC2Bz98r9NEbEEjAoRzuEsHhQ8pLn uelg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1678391878; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=nFWhKsUHikr0MnqTKDu3Jn6u9jODXMOrGgvNDrdwTT8=; b=MeH6Q92n4YXWAmLaXY8qhs6J/JaXFDIZL3vORUU5p4O4wOibUH14CmolnmepynPyFf MqksULmUfpL167XWpujHske+zy4RMdkBHC3r4BIJ1JK5y9uBFryIcVE+P6YG9bfXeBjX WTgGJrQO5VA1M81q3V9LTB+A11/epMHDmYuYIdJ76Bod1l6aoPOY35isHy5Wq368awBp zHEWRpI+4A8zqrY8tXDgKvLW0ckMeNiwwDnYSqG7VgJ2LMLjWYpWB/mhNP+oH717mhBD gRyTZS8jra64rcq2Z7PNCju/vE+bXi4VLSFwgz1St5vvhbeF3REWg0nddsvIFN5WS6WI 011Q== X-Gm-Message-State: AO0yUKUhX7aaN77Q39Qwt4lI/9jhjf9nU3ulFf5JQtZIyIzE24hKMTLN qKBXnMMDBhE0zZTLHsD0Xg/nVEyxTYB8NdVGly6sr+rUb9y/R7/n X-Google-Smtp-Source: AK7set9M9wEXiWBMRJN7OItu+xUg46gE6Z8nTYsbihxB3sk5e0IOmfETmzUtz0mdTG7Y2lb5x9FpYlykH45IkKPzX3A= X-Received: by 2002:a05:6214:14e2:b0:56e:ab9d:6534 with SMTP id k2-20020a05621414e200b0056eab9d6534mr5647471qvw.9.1678391878107; Thu, 09 Mar 2023 11:57:58 -0800 (PST) MIME-Version: 1.0 From: =?UTF-8?B?0JDQu9C10LrRgdCw0L3QtNGAINCo0LjRgtC+0LI=?= Date: Thu, 9 Mar 2023 23:57:47 +0400 Message-ID: Subject: __lower_bound improvement for arithmetical types To: libstdc++@gcc.gnu.org Content-Type: multipart/alternative; boundary="000000000000b048d605f67d0fe9" X-Spam-Status: No, score=0.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: --000000000000b048d605f67d0fe9 Content-Type: text/plain; charset="UTF-8" I want to propose an improvement to std::__lower_bound for arithmetic types with the standard comparators. The main idea is to use linear search on a small number of elements to aid the branch predictor and CPU caches, but only when it is not observable by the user. In other words, if a standard comparator (std::less, std::greater) is used for arithmetic types. In benchmarks I achieved twice the increase in speed for small vectors(16 elements) and increase for 10-20% in large vectors(1'000, 100'000 elements). Code: https://gist.github.com/ATGsan/8a1fdec92371d5778a65b01321c43604 PR: https://github.com/ATGsan/gcc/pull/1 --000000000000b048d605f67d0fe9--