__lower_bound improvement for arithmetical types

__lower_bound improvement for arithmetical types

[Александр Шитов]

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

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

Re: __lower_bound improvement for arithmetical types

[Jonathan Wakely]

On Thu, 9 Mar 2023 at 19:58, Александр Шитов via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> 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

This is an interesting idea, thanks.

You limit the linear search to a single cacheline, but you don't
ensure that the range to search doesn't cross two cachelines, right?
Maybe it doesn't matter in practice, but I wonder if limiting the
linear search to a single cacheline would be even better.

Re: __lower_bound improvement for arithmetical types

[Александр Шитов]

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

Benchmark shows that adding an extra check to determine whether two
iterators are in one cache line requires noticeable CPU time. These checks
outweigh the benefits of searching through one cache line.


Given these facts, I 'd rather stick to the previously proposed version. Do
I have to do change the code somehow so that it could be merged to
libstdc++ ?

сб, 25 мар. 2023 г. в 14:16, Александр Шитов <alex.shitov1237@gmail.com>:

> Benchmark shows that adding an extra check to determine whether two
> iterators are in one cache line requires noticeable CPU time. These checks
> outweigh the benefits of searching through one cache line.
>
>
> Given these facts, I 'd rather stick to the previously proposed version.
> Do I have to do change the code somehow so that it could be merged to
> libstdc++ ?
>
> Пт, 10 марта 2023 г. в 14:27, Jonathan Wakely <jwakely.gcc@gmail.com>:
>
>> On Thu, 9 Mar 2023 at 19:58, Александр Шитов via Libstdc++
>> <libstdc++@gcc.gnu.org> wrote:
>> >
>> > 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
>>
>> This is an interesting idea, thanks.
>>
>> You limit the linear search to a single cacheline, but you don't
>> ensure that the range to search doesn't cross two cachelines, right?
>> Maybe it doesn't matter in practice, but I wonder if limiting the
>> linear search to a single cacheline would be even better.
>>
>

Re: __lower_bound improvement for arithmetical types

[Jonathan Wakely]

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

On Wed, 29 Mar 2023, 07:26 Александр Шитов, <alex.shitov1237@gmail.com>
wrote:

> Benchmark shows that adding an extra check to determine whether two
> iterators are in one cache line requires noticeable CPU time. These checks
> outweigh the benefits of searching through one cache line.
>

OK, thanks for checking.



> Given these facts, I 'd rather stick to the previously proposed version.
> Do I have to do change the code somehow so that it could be merged to
> libstdc++ ?
>

It will have to wait until after the GCC 13 release, so I'll review it
properly in a few weeks.

It looks like we can probably get it merged though, thanks for the
contribution.




> сб, 25 мар. 2023 г. в 14:16, Александр Шитов <alex.shitov1237@gmail.com>:
>
>> Benchmark shows that adding an extra check to determine whether two
>> iterators are in one cache line requires noticeable CPU time. These checks
>> outweigh the benefits of searching through one cache line.
>>
>>
>> Given these facts, I 'd rather stick to the previously proposed version.
>> Do I have to do change the code somehow so that it could be merged to
>> libstdc++ ?
>>
>> Пт, 10 марта 2023 г. в 14:27, Jonathan Wakely <jwakely.gcc@gmail.com>:
>>
>>> On Thu, 9 Mar 2023 at 19:58, Александр Шитов via Libstdc++
>>> <libstdc++@gcc.gnu.org> wrote:
>>> >
>>> > 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
>>>
>>> This is an interesting idea, thanks.
>>>
>>> You limit the linear search to a single cacheline, but you don't
>>> ensure that the range to search doesn't cross two cachelines, right?
>>> Maybe it doesn't matter in practice, but I wonder if limiting the
>>> linear search to a single cacheline would be even better.
>>>
>>

Re: __lower_bound improvement for arithmetical types

[Александр Шитов]

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

Hello!

I am reminding about my patch.



Ср, 29 марта 2023 г. в 12:00, Jonathan Wakely <jwakely.gcc@gmail.com>:

>
>
> On Wed, 29 Mar 2023, 07:26 Александр Шитов, <alex.shitov1237@gmail.com>
> wrote:
>
>> Benchmark shows that adding an extra check to determine whether two
>> iterators are in one cache line requires noticeable CPU time. These checks
>> outweigh the benefits of searching through one cache line.
>>
>
> OK, thanks for checking.
>
>
>
>> Given these facts, I 'd rather stick to the previously proposed version.
>> Do I have to do change the code somehow so that it could be merged to
>> libstdc++ ?
>>
>
> It will have to wait until after the GCC 13 release, so I'll review it
> properly in a few weeks.
>
> It looks like we can probably get it merged though, thanks for the
> contribution.
>
>
>
>
>> сб, 25 мар. 2023 г. в 14:16, Александр Шитов <alex.shitov1237@gmail.com>:
>>
>>> Benchmark shows that adding an extra check to determine whether two
>>> iterators are in one cache line requires noticeable CPU time. These checks
>>> outweigh the benefits of searching through one cache line.
>>>
>>>
>>> Given these facts, I 'd rather stick to the previously proposed version.
>>> Do I have to do change the code somehow so that it could be merged to
>>> libstdc++ ?
>>>
>>> Пт, 10 марта 2023 г. в 14:27, Jonathan Wakely <jwakely.gcc@gmail.com>:
>>>
>>>> On Thu, 9 Mar 2023 at 19:58, Александр Шитов via Libstdc++
>>>> <libstdc++@gcc.gnu.org> wrote:
>>>> >
>>>> > 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
>>>>
>>>> This is an interesting idea, thanks.
>>>>
>>>> You limit the linear search to a single cacheline, but you don't
>>>> ensure that the range to search doesn't cross two cachelines, right?
>>>> Maybe it doesn't matter in practice, but I wonder if limiting the
>>>> linear search to a single cacheline would be even better.
>>>>
>>>