From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qv1-xf33.google.com (mail-qv1-xf33.google.com [IPv6:2607:f8b0:4864:20::f33]) by sourceware.org (Postfix) with ESMTPS id C31C53858D37 for ; Mon, 17 Jul 2023 09:32:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org C31C53858D37 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-xf33.google.com with SMTP id 6a1803df08f44-63759b5983dso18386606d6.0 for ; Mon, 17 Jul 2023 02:32:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1689586369; x=1692178369; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=55dAbbL3OTzVzjgKnUGpGdFVLRXGCLI6qa2QqmdfVbg=; b=TNZV5QFvNW20YNUUCWD+TayjWxHiPhx4qJxM77iSL7IHaCFeL6x86ZKvOkstyZk/MJ Q48dkH4wRnfVNMI9nObqgYqenD/DjTD0Up0vZ0brvCg9DeCS+suR5NPsGS+NTDL/3oDQ x3QN2LiTmAA7yHTyhbUfF0BvI6KP99fhrCt61NpUc1jJ5WQlIh2Hw/o0r5Z5dwgUsFc2 bxIHh3FCuKb3grkKk59vkr1yxntgdl8m2msiOdefqRMIWNeIJjQMw3R/n4tLdopt1f26 UuWsRAW1fN+YBmQX0Y2qMIv2y6wLhUOVi+rdIO64UZyvZsy80JMrzwEG+SZ64xtdiMcC MRxg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1689586369; x=1692178369; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=55dAbbL3OTzVzjgKnUGpGdFVLRXGCLI6qa2QqmdfVbg=; b=Q/Gafnt0S3rkmIeGlDkf7Ry77lpDz6GZauxTVwNXnxZ9RDrHp9922l/kCot2MG2ozM NXr34vBxfWyLRs7qihmCS78hD2x9lv3OU16RlsJL1BjaYemcmHCz3Oxi2DTD+dL9RWPz DmBoestzEgbV/zFvxlRn0qc1SwFJpVfcvYJwj9yijbJAYh93rhepdljZHpcdW4HNGMAZ +1NFSAVIT8FNGz1RiK4TKoOmJiEF5PVlA+b3ADk1FzDhMDcN+pALj2rBSknphKRNuU8I i7c+NPs3WaC5wumiYR0VWSnkQwRocnGSHlkPVOjQzamYCXsDHrDoYKLIXzgwC6/VIOpJ n6Hw== X-Gm-Message-State: ABy/qLYWwe8R/2r0PdS56kemAmk/2YNGnTLKusL9LwzTeEHX568sPp/W jIayXBt8KfELq0XM+Y+M4qkFqgDpOH4DgnwHZ1s07UoqJqU= X-Google-Smtp-Source: APBJJlE9EMtkSCCoeyHhAGfnwun0lCyxx42T3jHslWd273GqTy317S42EHd43Cb907gMcjdvUXNC+kjwZWYHwEfvMyU= X-Received: by 2002:a0c:9e9a:0:b0:637:2eb:6c1f with SMTP id r26-20020a0c9e9a000000b0063702eb6c1fmr9530226qvd.44.1689586368982; Mon, 17 Jul 2023 02:32:48 -0700 (PDT) MIME-Version: 1.0 From: =?UTF-8?B?0JDQu9C10LrRgdCw0L3QtNGAINCo0LjRgtC+0LI=?= Date: Mon, 17 Jul 2023 12:32:38 +0300 Message-ID: Subject: __lower_bound improvement for arithmetical types(2) To: "libstdc++" Content-Type: multipart/alternative; boundary="00000000000057380e0600ab7b43" X-Spam-Status: No, score=-0.9 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,T_SCC_BODY_TEXT_LINE 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: --00000000000057380e0600ab7b43 Content-Type: text/plain; charset="UTF-8" A couple months ago I sent my proposal to add improvement for lower_bound. As a reminder I send it once more 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 --00000000000057380e0600ab7b43--