[Bug libstdc++/87872] New: debug list::splice should not call _M_transfer_from_if on self-splices

["jbytheway at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87872

            Bug ID: 87872
           Summary: debug list::splice should not call _M_transfer_from_if
                    on self-splices
           Product: gcc
           Version: 7.3.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jbytheway at gmail dot com
  Target Milestone: ---

I encountered this issue when trying to understand the performance of a
_GLIBCXX_DEBUG build of a least-recently-used cache.

The cache is simply a std::list of items, with a std::unordered_map of keys to
list iterators.  So, in this case an iterator exists for every element of the
list (of which there are ~thousands).

Debug iterator operations require checking every iterator, which in this case
means they are O(n).

For the common case of moving an element to the end of the list, a previous
version of the code used erase+insert.  This was O(n) due to the debug iterator
invalidation check on erase, which is understandable and probably unavoidable.

I changed the code to use splice instead of erase+insert, and was surprised to
discover that the performance was still poor.  splice is also currently O(n) in
this case.

That's because the debug list::splice functions call _M_transfer_from_if to
transfer some iterators from the spliced-from list to the spliced-to list.

However, in the common case of self-splicing, there is no need to do this.  No
iterators are invalidated and none change their associated container.  If the
calls from list::splice to _M_transfer_from_if are guarded by "if (this !=
&__x)" then self-splicing becomes O(1).

I think it is relatively common when using lists to hold iterators to most or
all of the items, so this change would be a simple and very useful improvement
to the debug containers.  I've made the change locally and it's working well
for me.

I'm using gcc 7.3.1 but I've checked trunk and as far as I can tell the
relevant code is identical.

For reference, the code for the LRU cache can be found here:
https://github.com/jbytheway/Cataclysm-DDA/blob/12fbc8eb3e586f5ad65058fb5e452b4d30de41b7/src/map_memory.h#L20-L35
https://github.com/jbytheway/Cataclysm-DDA/blob/12fbc8eb3e586f5ad65058fb5e452b4d30de41b7/src/map_memory.cpp#L15-L33