Engine: Slow retrieval of components

[joeltio]

Summary

After profiling the engine, it seems that the main bottleneck is in ics::getComponent, due to the use of Composable and its subsidiary functions such as ics::asCompSet.

Observations

I profiled the following code within a test in engineService.test.cpp:

for (int i = 0; i < 80000; i++) {
    StepSimulationReq stepReq;
    StepSimulationResp stepResp;
    grpc::ServerContext stepContext;
    stepReq.set_name(testSim.SIM_NAME);
    engineSvc->StepSimulation(&stepContext, &stepReq, &stepResp);
}

Here is the flame graph:

Notice how ics::getComponent forms the largest chunk in each operation. Zooming in on the function, we can see its subsidiary functions which are slow:

Note that the third function from the left is a lambda produced by filterEntityId from the EntityIndex.

Just as a reminder, the file calling these methods are in sim/src/ics.cpp:

    auto components = util::Composable<ComponentStore&>(compStore) |
                      ics::asCompSet | compTypeIndex.filterCompType(typeName) |
                      entityIndex.filterEntityId(entityId);

Recommended Fix

1. The result of ics::asCompSet can be cached or even stored and maintained by CompStore, effectively removing the cost of constructing an unordered_set.
2. The util::Composable construction and usage is known at compile-time, therefore, it should not incur any cost. It should be implemented as a constexpr or something similar.
3. The main cost incurred in the filterEntityId lambda is actually the set intersection operation. ics::asCompSet should be changed to return an ordered set (this will not incur much cost since the entity IDs and group IDs are already ordered), and the C++ STL set_intersection should be used. See more details below on the reason.
4. compTypeIndex.filterCompType can be converted to return an iterator to reduce costs incurred in creating a new set.

In conclusion, make things doable at compile-time done at compile-time and convert the functions to generators.

More details on recommended fix 3.

The main cost incurred in the filterEntityId lambda is actually the set intersection operation. The set intersection (written by me) creates a new set and inserts intersecting elements into that set. The high cost of insert is the problem:

template <class T>
std::unordered_set<T> setIntersection(const std::unordered_set<T>& a,
                                      const std::unordered_set<T>& b) {
    std::unordered_set<T> newSet;
    for (const T& aElement : a) {
        if (b.contains(aElement)) {
            newSet.insert(aElement);
        }
    }

    return newSet;
}

Hence, we want to remove the construction of newSet and the insert operation.

To do so, we need to convert this function into a generator, i.e. a function that returns an iterator. Due to the nature of this operation, the iterator returned must be a forward iterator (i.e. an iterator that can only be incremented). Assuming that the inputs are also forward iterators (to ensure composability), this is not possible with unordered sets, but possible with ordered sets.

The C++ STL implementation of set intersection does exactly this. It takes in two iterators of ordered sets and returns an iterator of the set intersection.

Therefore, for compatibility, the filterEntityId code should call the STL set intersection and use ordered_sets to store compStoreIds

[mrzzy]

After profiling the engine, it seems that the main bottleneck is in ics::getComponent, due to the use of Composable and its subsidiary functions such as ics::asCompSet.

Agreed. Here's the call graph I sampled using Valgrind's cachegrind running step() on the Mountain Car Simulation,

• according to cachegrind's profiling getComponent() takes 44% of the of total time spent running StepSimulation().

• looking closer at getComponent()'s profiling:

Observations:

• About 22% of the getComponents()'s runtime is spent on constructing/destroying std::unordered_set and std::_Hashtable.
• 19.31% of the time is spent on emplacing new elements into an unordered set.

1. The result of ics::asCompSet can be cached or even stored and maintained by CompStore, effectively removing the cost of constructing an unordered_set.

Caching means having to maintain 2 copies of the same thing which introduces the issue of having to keep the two copies in sync, when to invalidate the cache etc. Just FYI to show that is not as simple as sounds.

• Using emplace() seems to pretty expensive:
  • Even though emplace() avoids the copy, consistently adding new elements is probably expensive. The set's Hashtable probably needs to be recreated to accommodate no. growing elements everytime its filled, meaning more copying.
  • Maybe we try could initializing the set to fixed size, especially since we know the size the set is supposed be from the ComponentStore

2. The util::Composable construction and usage is known at compile-time, therefore, it should not incur any cost. It should be implemented as a constexpr or something similar.

Have to disagree on this one. The constructor for Composable is probably very expensive:

explicit Composable(Data d) : data(d){};

CMIIW, but d will be considered to be l-value and trigger the copy constructor for a expensive deep copy of whatever Data is templated as: I think a deep copy is done for each additional | function composition with Composable:

util::Composable<ComponentStore&>(compStore) |
ics::asCompSet | compTypeIndex.filterCompType(typeName) |
entityIndex.filterEntityId(entityId);

3. The main cost incurred in the filterEntityId lambda is actually the set intersection operation. ics::asCompSet should be changed to return an ordered set (this will not incur much cost since the entity IDs and group IDs are already ordered), and the C++ STL set_intersection should be used. See more details below on the reason.

Agreed.

4. compTypeIndex.filterCompType can be converted to return an iterator to reduce costs incurred in creating a new set.

That could be one way to cut performance costs.

Another way I think of reducing costs is rethinking should be filterCompType() implemented.
CMIIW, purpose of this filter is search for Components with the given name.
The current approach is:
ComponentStore -> ComponentSet -> Linear Search

Maybe we can consider another apporach to cut this at least O(n) operation to O(1):
ComponentTypeIndex -> ComponentStore

1. Use ComponentTypeIndex's typeNameGroupMap to map from name to CompGroup no.
2. Use ComponentStore to map from CompGroup to CompVec<BaseComponent>

In conclusion, make things doable at compile-time done at compile-time and convert the functions to generators.

Do keep in mind that doing things at compile time makes the code more complex and hard to maintain.
Converting functions to generators only improves performance if we don't use exhaust the generator completely (ie don't use all the elements that could be possibly produced by the generator).