Use performant and safe data structure for active objects

[sfan5]

@Desour this was the idea I described

Note to bystanders: This won't make entities any faster than they were before (e.g. in 5.4.0), it will only walk back some recent performance regressions.

To do

This PR is a Work in Progress.

• make container work with std::unique_ptr (and resolve merge conflict)
• find remaining bugs

How to test

• Use entities and check that nothing blows up.
• try the test code from ActiveObjectMgr fixes #13560
• ???

[ExeVirus]

Interesting, Questions:

1. garbage collected deletion is the most performant method - nvm this is about safety if they get deleted during iteration
2. Why std::map and not at least unordered_map? nvm, apparently it's a fix for attached entities, what a hack solution, but sure.

No questions, except this looks hand-coded, isn't there an existing ultra-performant, battle tested version of this concept somewhere?

meh, looks like we are already running a bunch of hand-coded crap haha. Probably should revisit with more modern stuff if we have time.

[sfan5]

No questions, except this looks hand-coded, isn't there an existing ultra-performant, battle tested version of this concept somewhere?

Dunno, I didn't attempt to search. Feel free to post here if you find one.

[Desour]

Instead of the garbage collection thing, you could add a std::vector<map::iterator> in which you store the iterators to the elements to delete.

---

It would be nice to have some micro benchmark to see the effect of this PR.

[ExeVirus]

Bard.google.com provided this answer, I know about robin_map, and can vouch for it among other flat maps (abseil::flat_map is also a solid choice here I suspect).

What's a performant, C++ structure in an open source library that provides something like std::map, that can insert or remove from the map, while iterating, and the iterator is not invalidated

A performant, C++ structure in an open source library that provides something like std::map, that can insert or remove from the map while iterating, and the iterator is not invalidated is robin_map. It is a header-only library that implements a hash table-based associative container with some unique features, including:

Fast insertion and removal while iterating: robin_map uses a technique called "copy-on-write" to allow for safe and efficient insertion and removal of elements while iterating over the map. This means that the iterator is never invalidated, even if elements are added or removed from the map.
Excellent performance: robin_map is highly optimized for performance, and it often outperforms std::map on a variety of benchmarks.
Open source: robin_map is licensed under the MIT License, which makes it free to use and distribute.
Here is an example of how to use robin_map to insert and remove elements while iterating:

#include <robin_map.h>

using namespace robin_map;

int main() {
  robin_map<int, int> map;

  // Insert some elements into the map.
  for (int i = 0; i < 10; i++) {
    map[i] = i;
  }

  // Iterate over the map and remove any even elements.
  auto it = map.begin();
  while (it != map.end()) {
    if (it->first % 2 == 0) {
      it = map.erase(it);
    } else {
      it++;
    }
  }

  // Print the remaining elements in the map.
  for (auto& pair : map) {
    std::cout << pair.first << " -> " << pair.second << std::endl;
  }

  return 0;
}

This code will print the following output:

1 -> 1
3 -> 3
5 -> 5
7 -> 7
9 -> 9

As you can see, the iterator it is never invalidated, even though we are removing elements from the map while iterating over it. This is because robin_map uses copy-on-write to ensure that the iterator always points to a valid element.

robin_map is a powerful and efficient associative container that is well-suited for a variety of applications. It is especially useful for applications where it is necessary to insert or remove elements from a map while iterating over it.

Keep in mind this is a flat_map, they can shine when working with pointers, which I believe we are right here, so it shouldn't be an issue. Also, MIT so compatible with us. This is the best one I can find that supports C++11, maybe someday we could move to C++14 or something, but that's not this task.

[ExeVirus]

Of course, this assumes we can assign that iterator whenever the map is erased from, which is not probably the case. I guess we could pass in a pointer to that iterator to the activeObject Manager class that deals with insertion and deletion, that could work well, just a bit convoluted. Still probably more performant.

[sfan5]

That's not bad but it missed exactly this detail:

> Of course, this assumes we can assign that iterator whenever the map is erased from, which is not probably the case.

even std::map can guarantee this
This requirement was not explicitly specified but a human could infer that "erase returns a new iterator" is probably not what was meant.

Anyway: ActiveObjectMgr::step will call Lua code and that calls engine code and ... somewhere inside we want to remove the entity from the active. At that point connecting the initially used iterator with the call to erase is not feasible.

Instead of the garbage collection thing, you could add a std::vector<map::iterator> in which you store the iterators to the elements to delete.

good idea, I'll try that.
edit: This doesn't work, erasing the first iterator would invalidate all others.

This is the best one I can find that supports C++11, maybe someday we could move to C++14 or something, but that's not this task.

we're currently already at c++17

[ExeVirus]

Anyway: ActiveObjectMgr::step will call Lua code and that calls engine code and ... somewhere inside we want to remove the entity from the active.

Right, at that point, the remove returns back up to c++ to remove from the activeObjectMgr, at that point the manager would have an internal pointer to the iterator and assign it.

Something like:

iter = map.begin();
manager.set_iter(&iter);
for(iter) {
        iterate, lua eventually calls remove or insert entity
}
manager.set_iter(nullptr);


//Later in ActiveObjectManager remove
{
     if(iter != nullptr) {
         *iter = map.erase(id);
     } else{
         map.erase(id);
     }
}

[sfan5]

Not a fan of that approach, it requires manual bookkeeping and is easy to mess up. Also it doesn't address the "insert while iterate" problem.
For ModifySafeMap the compiler will ensure you're not using it incorrectly.

[ExeVirus]

Fair, nullptr is a lot easier method of book keeping which ones got removed.

…

On Wed, Oct 11, 2023, 3:46 AM sfan5 ***@***.***> wrote: Not a fan of that approach, it requires manual bookkeeping and is easy to mess up. Also it doesn't address the "insert while iterate" problem. — Reply to this email directly, view it on GitHub <#13880 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AKT7N2QWVXSI36EFS46Y5TTX6ZFDTANCNFSM6AAAAAA5ZEM2RA> . You are receiving this because you commented.Message ID: ***@***.***>

[sfan5]

@Desour I've commited benchmarks, here are the results:

---------------------------------------------------------------------------------------------------
ModifySafeMap
---------------------------------------------------------------------------------------------------
/home/stefan/minetest/src/benchmark/benchmark_mapmodify.cpp:66
...................................................................................................

benchmark name                                           samples       iterations    estimated
                                                         mean          low mean      high mean
                                                         std dev       low std dev   high std dev
---------------------------------------------------------------------------------------------------
iterate_50                                                         100           124 2418.000000 us 
                                                           0.197172 us   0.197038 us   0.197794 us 
                                                           0.001260 us   0.000112 us   0.002993 us 
                                                                                                   
iterate_400                                                        100            16 2484.800000 us 
                                                           1.568054 us   1.566139 us   1.569861 us 
                                                           0.009502 us   0.008342 us   0.011109 us 
                                                                                                   
iterate_1000                                                       100             5 2426.500000 us 
                                                           4.504366 us   4.478356 us   4.538444 us 
                                                           0.150758 us   0.117902 us   0.194182 us 
                                                                                                   
remove_during_iterate_50                                           100           218 2398.000000 us 
                                                           0.116162 us   0.115971 us   0.116524 us 
                                                           0.001291 us   0.000697 us   0.002209 us 
                                                                                                   
remove_during_iterate_400                                          100            23 2444.900000 us 
                                                           1.730517 us   1.711092 us   1.748887 us 
                                                           0.096375 us   0.088150 us   0.114952 us 
                                                                                                   
remove_during_iterate_100                                          100            83 2415.300000 us 
                                                           0.361059 us   0.360667 us   0.361886 us 
                                                           0.002771 us   0.001451 us   0.004571 us 

---------------------------------------------------------------------------------------------------
plain std::map
---------------------------------------------------------------------------------------------------
/home/stefan/minetest/src/benchmark/benchmark_mapmodify.cpp:122
...................................................................................................

benchmark name                                           samples       iterations    estimated
                                                         mean          low mean      high mean
                                                         std dev       low std dev   high std dev
---------------------------------------------------------------------------------------------------
iterate_50                                                         100            47 2444.000000 us 
                                                           0.515102 us   0.514461 us   0.517416 us 
                                                           0.005523 us   0.001499 us   0.012632 us 
                                                                                                   
iterate_400                                                        100             4 2608.400000 us 
                                                           6.562560 us   6.553167 us   6.593690 us 
                                                           0.078484 us   0.027948 us   0.176309 us 
                                                                                                   
iterate_1000                                                       100             2 4438.800000 us 
                                                          22.460560 us  22.429000 us  22.512310 us 
                                                           0.202292 us   0.129612 us   0.330964 us 
                                                                                                   
remove_during_iterate_50                                           100           203 2415.700000 us 
                                                           0.121964 us   0.121800 us   0.122519 us 
                                                           0.001374 us   0.000472 us   0.003080 us 
                                                                                                   
remove_during_iterate_400                                          100            19 2430.100000 us 
                                                           1.633944 us   1.632026 us   1.638154 us 
                                                           0.013739 us   0.006201 us   0.023362 us 
                                                                                                   
remove_during_iterate_100                                          100            91 2429.700000 us 
                                                           0.295833 us   0.295510 us   0.297056 us 
                                                           0.002777 us   0.000276 us   0.006405 us 

The proposed implementation definitely avoids a bunch of extra overhead during iteration, which is the most common operation we do.
It is however quite the micro-optimization. We can revisit this after the next release (also since there's a risk of bugs).

[sfan5]

@Desour I rebased this to current master but std::unique_ptr makes a bit of a mess of the formerly simple code I had.
what are your feelings on going back to bare pointers?

[Desour]

@Desour I rebased this to current master but std::unique_ptr makes a bit of a mess of the formerly simple code I had. what are your feelings on going back to bare pointers?

Are there other things than those where I commented that drastically make life harder?
If you distinguish move and borrow semantics (aka have separate take and get functions), it should be fine, I think.

[sfan5]

Are there other things than those where I commented that drastically make life harder?

No, those were all actually.

[Desour]

Code is fine otherwise.
Haven't tested yet.

[Desour]

Is it an issue that size() and empty() have up to linear time? size() is called in ActiveObjectMgr::registerObject.

[sfan5]

Hmm hopefully not.
I've changed ::step to avoid it at least.

One conceptual problem ist that you pay the cost of uncollected garbage every iteration and call to size/empty but garbage is only collected once you hit a certain limit...

[Desour]

Tested, found no issues.