Swap out item vector for a std::list.

[kevingranade]

While profiling for pre-0.B stuff, I noticed that we're spending a significant amount of time inserting and removing items from the item vector:

-    4.77%     0.52%  cataclysm  cataclysm            [.] item::operator=(item&&)
   - item::operator=(item&&)
      - 50.39% item* std::__copy_move<true, false, std::random_access_iterator_tag>::__copy_m<item*, item*>(item*, item*, item*)
           item* std::__copy_move_a<true, item*, item*>(item*, item*, item*)
           __gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<item> > > std::__copy_move_a2<true, __gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<ite
           __gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<item> > > std::move<__gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<item> > >, __gnu_cx
           std::vector<item, std::allocator<item> >::erase(__gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<item> > >)
           process_item(std::vector<item, std::allocator<item> >&, unsigned int, point, bool)
           map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehicle*, int)#1}::operator()(std::vector<item, std::allocator<item> >&, uns
           void map::process_items_in_submap<map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehicle*, int)#1}>(submap*, int, int, map:
           void map::process_items<map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehicle*, int)#1}>(bool, map::process_active_items()
           map::process_active_items()
           game::do_turn()
           main
           __libc_start_main
      - 48.20% item* std::__copy_move_backward<true, false, std::random_access_iterator_tag>::__copy_move_b<item*, item*>(item*, item*, item*)
           item* std::__copy_move_backward_a<true, item*, item*>(item*, item*, item*)
           item* std::__copy_move_backward_a2<true, item*, item*>(item*, item*, item*)
           item* std::move_backward<item*, item*>(item*, item*, item*)
           void std::vector<item, std::allocator<item> >::_M_insert_aux<item>(__gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<item> > >, item&&)
           std::vector<item, std::allocator<item> >::insert(__gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<item> > >, item const&)
           process_item(std::vector<item, std::allocator<item> >&, unsigned int, point, bool)
           map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehicle*, int)#1}::operator()(std::vector<item, std::allocator<item> >&, uns
           void map::process_items_in_submap<map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehicle*, int)#1}>(submap*, int, int, map:
           void map::process_items<map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehicle*, int)#1}>(bool, map::process_active_items()
           map::process_active_items()
           game::do_turn()
           main
           __libc_start_main
      + 1.25% void std::vector<item, std::allocator<item> >::_M_insert_aux<item>(__gnu_cxx::__normal_iterator<item*, std::vector<item, std::allocator<item> > >, item&&)                    

It's probably going to take quite a bit of doing, but I think switching the items std::vector to a std::map is the right way to go. It has the best insertion/removal performance, and we almost always iterate over the container rather than random access elements.

[kevingranade]

It's even worse when waiting:

+   27.56%     0.00%  cataclysm  cataclysm            [.] map::process_active_items()
+   27.52%     0.06%  cataclysm  cataclysm            [.] void map::process_items<map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehic
+   24.92%     1.07%  cataclysm  cataclysm            [.] void map::process_items_in_submap<map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, po
+   21.69%     0.09%  cataclysm  cataclysm            [.] map::process_active_items()::{lambda(std::vector<item, std::allocator<item> >&, unsigned int, point, vehicle*, int)#1}::operator()
+   20.37%     0.18%  cataclysm  cataclysm            [.] process_item(std::vector<item, std::allocator<item> >&, unsigned int, point, bool)

It looks like the only real candidate for why this is taking so long is vector insertion and removal.

The higher-level solution is to split off some active items to something resembling timer queues, e.g. you'd evenly distribute all the rotting food across n containers, and only process one containers worth per turn. More detail in #9926

[kevingranade]

I'm a dumb, there's no reason for the items to be sorted, just put them in a std::list and either append or prepend. (prepend is better actually, then you can just iterate to the end of the list)

[Robik81]

If std:list is way to go, can you please change the label to 'Swap out item vector for a std::list' ?

[kevingranade]

Yea, I was going to do that but was having terrible connection issues to github last night, so gave up.