Improve the efficiency of MooseObjectWarehouseBase<MaterialBase>::sort

[fdkong]

Reason

#0  0x00002aaab222dbed in poll () from /lib64/libc.so.6
#1  0x00002aaab0f279b4 in ips_ptl_pollintr () from /lib64/libpsm2.so.2
#2  0x00002aaab116ee65 in start_thread () from /lib64/libpthread.so.0
#3  0x00002aaab223888d in clone () from /lib64/libc.so.6
Thread 1 (Thread 0x2aaab3c7a880 (LWP 112914)):
#0  0x00002aaaacdaf557 in __gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase> const*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > > std::__find_if<__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase> const*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__ops::_Iter_equals_val<std::shared_ptr<MaterialBase> const> >(__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase> const*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase> const*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__ops::_Iter_equals_val<std::shared_ptr<MaterialBase> const>, std::random_access_iterator_tag) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#1  0x00002aaaacd82274 in DependencyResolverComparator<std::shared_ptr<MaterialBase> >::operator()(std::shared_ptr<MaterialBase> const&, std::shared_ptr<MaterialBase> const&) const [clone .isra.1814] () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#2  0x00002aaaacdaf7ee in std::_Rb_tree<std::shared_ptr<MaterialBase>, std::shared_ptr<MaterialBase>, std::_Identity<std::shared_ptr<MaterialBase> >, DependencyResolverComparator<std::shared_ptr<MaterialBase> >, std::allocator<std::shared_ptr<MaterialBase> > >::_M_get_insert_unique_pos(std::shared_ptr<MaterialBase> const&) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#3  0x00002aaaacdafb49 in std::_Rb_tree_iterator<std::shared_ptr<MaterialBase> > std::_Rb_tree<std::shared_ptr<MaterialBase>, std::shared_ptr<MaterialBase>, std::_Identity<std::shared_ptr<MaterialBase> >, DependencyResolverComparator<std::shared_ptr<MaterialBase> >, std::allocator<std::shared_ptr<MaterialBase> > >::_M_insert_unique_<std::shared_ptr<MaterialBase> const&, std::_Rb_tree<std::shared_ptr<MaterialBase>, std::shared_ptr<MaterialBase>, std::_Identity<std::shared_ptr<MaterialBase> >, DependencyResolverComparator<std::shared_ptr<MaterialBase> >, std::allocator<std::shared_ptr<MaterialBase> > >::_Alloc_node>(std::_Rb_tree_const_iterator<std::shared_ptr<MaterialBase> >, std::shared_ptr<MaterialBase> const&, std::_Rb_tree<std::shared_ptr<MaterialBase>, std::shared_ptr<MaterialBase>, std::_Identity<std::shared_ptr<MaterialBase> >, DependencyResolverComparator<std::shared_ptr<MaterialBase> >, std::allocator<std::shared_ptr<MaterialBase> > >::_Alloc_node&) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#4  0x00002aaaacdb06b5 in DependencyResolver<std::shared_ptr<MaterialBase> >::getSortedValuesSets() () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#5  0x00002aaaacdb1366 in DependencyResolver<std::shared_ptr<MaterialBase> >::getSortedValues() () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#6  0x00002aaaacdb17d8 in DependencyResolver<std::shared_ptr<MaterialBase> >::operator()(std::shared_ptr<MaterialBase> const&, std::shared_ptr<MaterialBase> const&) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#7  0x00002aaaacdb1a4a in void std::__insertion_sort<__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__ops::_Iter_comp_iter<DependencyResolver<std::shared_ptr<MaterialBase> > > >(__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__ops::_Iter_comp_iter<DependencyResolver<std::shared_ptr<MaterialBase> > >) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#8  0x00002aaaacdb2562 in void std::__merge_sort_with_buffer<__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, std::shared_ptr<MaterialBase>*, __gnu_cxx::__ops::_Iter_comp_iter<DependencyResolver<std::shared_ptr<MaterialBase> > > >(__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, std::shared_ptr<MaterialBase>*, __gnu_cxx::__ops::_Iter_comp_iter<DependencyResolver<std::shared_ptr<MaterialBase> > >) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#9  0x00002aaaacdb2f46 in void std::__stable_sort_adaptive<__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, std::shared_ptr<MaterialBase>*, long, __gnu_cxx::__ops::_Iter_comp_iter<DependencyResolver<std::shared_ptr<MaterialBase> > > >(__gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, __gnu_cxx::__normal_iterator<std::shared_ptr<MaterialBase>*, std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > > >, std::shared_ptr<MaterialBase>*, long, __gnu_cxx::__ops::_Iter_comp_iter<DependencyResolver<std::shared_ptr<MaterialBase> > >) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#10 0x00002aaaacdb32d9 in void DependencyResolverInterface::sort<std::shared_ptr<MaterialBase> >(std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > >&) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#11 0x00002aaaacdb35c4 in MooseObjectWarehouseBase<MaterialBase>::sortHelper(std::vector<std::shared_ptr<MaterialBase>, std::allocator<std::shared_ptr<MaterialBase> > >&) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#12 0x00002aaaacdb36c4 in MooseObjectWarehouseBase<MaterialBase>::sort(unsigned int) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#13 0x00002aaaacd8229e in MaterialWarehouse::sort(unsigned int) () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#14 0x00002aaaacc694ef in FEProblemBase::initialSetup() () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#15 0x00002aaaacfcf666 in EigenExecutionerBase::init() () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#16 0x00002aaaacfcfc9d in NonlinearEigen::init() () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#17 0x00002aaaad203fa2 in MooseApp::executeExecutioner() () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#18 0x00002aaaab9a576c in RattlesnakeApp::executeExecutioner() () from /home/kongf/workhome/lemhi/rattlesnake/lib/librattlesnake-opt.so.0
#19 0x00002aaaad204028 in MooseApp::run() () from /home/kongf/workhome/lemhi/moose/framework/libmoose-opt.so.0
#20 0x000000000040279a in main ()

This somehow becomes really slow recently. Will add a profiling result soon!

Design

We should explore a better algorithm

Impact

None

[YaqiWang]

@rwcarlsen fixed something really quick but not the ultimate algorithm fix for #11396. I am surprised that this shows up again.

[permcody]

I'd like to see the profiling. I don't think the issue isn't that sorting is slow, I believe the issue is that we are sorting the same, or similar items several times during setup. Anyway, I'll be curious to see what you find out when you get a good profile.