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