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
On further reflection, it would make more sense to put this check inside _M_transfer_from_if, rather than in every splice function.
All this reflection looks perfectly fine to me, thanks reporting it. Don't you want to submit a patch then, you're so close. Otherwise I'll take care in the coming week. Thanks
Created attachment 44955 [details] Proposed patch Sure, here's a proposed patch. Tested in the sense that I have compiled and run a program against the changed code, but I have not run the libstdc++ test suite or similar. Should affect list::splice and forward_list::splice_after with _GLIBCXX_DEBUG set.
Author: fdumont Date: Tue Nov 6 20:20:06 2018 New Revision: 265851 URL: https://gcc.gnu.org/viewcvs?rev=265851&root=gcc&view=rev Log: 2018-11-06 John Bytheway <jbytheway@gmail.com> PR libstdc++/87872 * include/debug/safe_sequence.tcc (_Safe_sequence<>::_M_transfer_from_if): Skip transfer to self. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/debug/safe_sequence.tcc
Patch committed, thanks again.