[PATCH] Improve performance of list::reverse

[Jonathan Wakely]

On 09/10/16 16:23 +0100, Elliot Goodrich wrote:
>Hi,
>
>If we unroll the loop so that we iterate both forwards and backwards,
>we can take advantage of memory-level parallelism when chasing
>pointers. This means that reverse takes 35% less time when nodes are
>randomly scattered in memory and about the same time if nodes are
>contiguous.
>
>Further, as our node pointers will never alias, we can interleave the
>swaps of the next and previous pointers to remove further data
>dependencies. This takes another 5% off the time when nodes are
>scattered in memory and takes 20% off when nodes are contiguous.
>
>All in all we save 20%-40% depending on the memory layout.

Nice, thanks for the patch.

Do you have (or are you willing to sign) a copyright assignment for
GCC?

See https://gcc.gnu.org/contribute.html#legal for details.

>For future improvement, by passing whether there is an odd or even
>number of nodes in the list we can hoist one of the ifs out of the
>loop and gain another 5-10% but most likely this is only possible when
>_GLIBCXX_USE_CXX11_ABI is defined and size() is O(1). This would bring
>the saving to 30%-45%. Is it worth writing a new overload of
>_M_reverse which takes the size of the list?

That certainly seems worthwhile. Do we need an overload or can it just
be done with #if? It seems to me we'd either want to use the size, or
not use it, we wouldn't want both versions defined at once. That
suggests #if to me.