public inbox for
 help / color / mirror / Atom feed
* __lower_bound improvement for arithmetical types(2)
@ 2023-07-17  9:32 Александр Шитов
  0 siblings, 0 replies; only message in thread
From: Александр Шитов @ 2023-07-17  9:32 UTC (permalink / raw)
  To: libstdc++

[-- Attachment #1: Type: text/plain, Size: 743 bytes --]

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).



^ permalink raw reply	[flat|nested] only message in thread

only message in thread, other threads:[~2023-07-17  9:32 UTC | newest]

Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-17  9:32 __lower_bound improvement for arithmetical types(2) Александр Шитов

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).