1

I have an array that contains over 150,000+ object pointers of over 300+ different classes, but they all inherit from the same base class. Obviously that's very inefficient when we need to search for an object.

I've thought about splitting this array per-object-type, which got some better performance, but not as much as I would have hoped:

std::unordered_map<std::type_index, std::vector<A*>> instances;

Also, the search criteria is often based on name, but it can also be just variadic template parameters, further complicating the issue. So I'm not sure about how I should be sorting this array. Here's a simplified version of one of the search function:

template <class TYPE, class... ARGS> A* search(ARGS... args) {
    auto object_template = TYPE(args...);
    for (auto const& object : objects) {
        auto typed_object = as<TYPE>(object);
        if (typed_object && *typed_object == object_template)
            return object;
    }
    return nullptr;
}

Is there any nice programming pattern that can be used to solve this kind of search performance issue? Has anyone faced this problem before and have a good solution?

Thank you!

  • 1
    Observations: (1) you are mixing templates with polymorphism, which (in C++) usually leads to difficulties. If feasible, can your class hierarchy be redesigned to use either but not both? (2) How is the array used? If the array owns the contained objects you could perhaps use multiple arrays to store them by value, leading to better memory access patterns. (3) A search can be optimized if the data can be structured in a convenient way, e.g. indexed. Indexing by type was a first good step. Will TYPE always be a leaf type, or might it be a base class? Can your objects be ordered or hashed? – amon Sep 12 '17 at 13:56
  • (1) no way around that unfortunately, that would mean too much code refactoring. (2) the array does not own the object, its basically an array of weak pointers. (3) TYPE is always a leaf type (the array never contains A pointers). – Deathicon Sep 12 '17 at 14:01
  • (1) You are comparing objects by equality. What kind of equality is this? Is this a value equality where you compare member by member? If so, is this equality immutable, or can an object in the list change so that it's no longer equal to some other object? (Perhaps we could define an artificial total order for the objects.) (2) You said there are different kinds of searches. Do all searches take the shown form where you compare array entries against fully initialized objects of the same type? Are there searches where the TYPE is not known? – amon Sep 12 '17 at 15:36
  • 1
    In the question, you use a static_cast to perform an (unchecked!) downcast, and only assert that the static decltype() of your objects is a base of the TYPE. Shouldn't this actually be a dynamic_cast which will return nullptr if the object isn't actually an instance of your TYPE? – amon Sep 12 '17 at 16:28
  • 1
    I doubt micro-optimizing will bring you some benefit, and based on the information given in the question, its virtually impossible to do more than that (besides partioning by type, which you already do). So your best shot is IMHO to utilize the details you did not tell us, like other partioning criterias based on the details of the classes. Moreover, are the 150K objects evenly distributed among the 300 classes? What about optimizing the "search by name" cases separately? Do all kinds of searches occur with the same probability, or can you optimize for certain kinds of searches? – Doc Brown Sep 12 '17 at 19:55
2

It seems to me that you have a lot of already implemented code, and you want to just optimize your search.

Also, it seems to me that your search cannot be entirely refactored (by changing the filter criteria).

Since you already tried a improvement of searching only within the set of the specific Type of your object, I would add the parallel approach to the search.

Basically, in your search (regardless if it's done by variadic parameters or by name):

  • Querying for an object of type T;
  • From original array A1 (with 300+ different types), select only the subset containing objects of type T;
  • Now you have another array A2;
  • Separate N chunks of same size of the array A2, and create a thread that will perform a linear search in each of these chunks;
  • wait for all N threads to be completed;
  • one of the threads might find the queried Object.

Thus, the overall time will be optimized according to the number of threads you define.

  • I suppose using threads could speed up the search in "A2", which then becomes more dependent of the number of core the CPU has than really solving the search algorithm itself. This is not what I am looking for yet. Threading optimizations will be used at the end when the algorithm is as efficient as possible using the right structure. – Deathicon Sep 12 '17 at 18:35
  • 3
    @Deathicon yes I just gave this answer based on the fact that you current data structure cannot be ordered, and that you current algorithm is basically a linear search. I avoided giving specific language details in here; I just suggested a quick way of improving your current search feature in general. Ideally, if you could somehow manage to be able to set your data so you could perform a binary search would be the best way to do, but from you scenario I cannot figure how to do this. – Emerson Cardoso Sep 12 '17 at 18:39
  • This is a very good idea since the search problem is “embarrassingly parallel”. However, it will only help as long as the problem is CPU-limited, not if the limit is set by memory bandwidth. – amon Sep 13 '17 at 9:13
  • After trying a lot of different things, I ended up splitting per std::type_index along with threading the searches through these vectors. Profiling showed this resulted in the best results. Got about ~6x speed up. – Deathicon Sep 14 '17 at 20:39
1

Performance has two parts:

  • Do as little work as possible.
  • What work you do, do as quickly as possible.

Here the second part can be addressed fairly quickly: don't use dynamic_cast, we'll look at ways to avoid that in a minute. Don't construct the same object over and over again. At the very least, we want something like this:

template <class TYPE>
A* search(TYPE const& expected) {
  static_assert( TYPE is subclass of A );
  for (TYPE* obj : magically_get_eligible_objects<TYPE>()) {
    if (obj && (*obj == expected))
      return obj;
  }
  return nullptr;
}

In C++, templates and polymorphism don't mesh well at all. There is not going to be an elegant, type-safe solution to magically_get_eligible_objects(). But if we write correct code we can take shortcuts and violate the C++ type system somewhat safely. For the rest of this answer, only the leaf TYPEs are relevant. The A* type might as well be void*.

Because you always know the TYPE for a query, you can partition your objects by type. There is no need to store them in a single data structure. This will help to reduce the search space if the population of objects is well distributed over multiple types: if at most 30% of objects have the same type, your worst-case time for a search also dropped to 30% (plus overhead).

For this partitioning you can use a map<type_index, vector<A*>> or multimap<type_index, A*> under the condition that you use an object's type_index(typeid(obj)) as key for inserting, deleting, and looking up objects or ranges of objects. When you get iterators or collections to a number of objects which are nominally of type A but you know their actual TYPE, then you can *cough* reinterpret_cast the collections. Since you're only storing pointers this ought to be safe in practice. For individual pointers you can use a static_cast safely.

Note: if all your objects have a constant name or other data that is known by all searches, then the key can be a tuple<type_index, NameType> instead which should lead to a sufficiently good partitioning. I'll continue assuming this is not the case.

Possibly, you could use a tuple<vector<TYPE1*>, vector<TYPE2*>, ..., vector<TYPEn*>> data structure instead and look up partitions by type. This avoids some casts but is (aside from that type safety and potentially a bit of runtime performance) not fundamentally superior to a map<type_index, vector<void*>>. This does make polymorphic operations (like inserting an element where the TYPE is not known) a lot more difficult.

Within a partition, the objects would still be unordered, requiring you to scan them linearly. If specific TYPEs have stronger properties we would need to introduce a custom Partition type that can be specialized for individual TYPEs.

We would need an abstract base partition for the partition container to compile, something like:

class BasePartition {
public:
  virtual void insert(void*) = 0;
  virtual void* search_by_name(NameType const&) = 0;
  virtual void* search_by_expected(void*) = 0;
};

Then a template class that defaults to an unsorted vector, but could be specialized for better data structures:

template<class TYPE>
class Partition : BasePartition {
  vector<TYPE*> objects;
public:
  void insert(void* obj) override {
    objects.push_back(static_cast<TYPE*>(obj));
  }

  void* search_by_name(NameType const& name) override { ... }

  void* search_by_expected(void* untyped_expected) override {
    // may prefer dynamic_cast for more defensive code
    TYPE* untyped_expected = static_cast<TYPE*>(untyped_expected);
    ...
  }
};

We might then have a map<type_index, unique_ptr<BasePartition>> partitions container. Given a BasePartition* partition for the correct TYPE, the search() function might then be simplified to

// partition casts internally
return static_cast<TYPE*>(partition->search_by_expected(&expected));

We can then specialize the Partition template for types where a more efficient search is possible. E.g. if one type can be ordered, we could use a set instead of a vector. You could also maintain additional unordered_maps to index the objects by some property, e.g. by name. Whether the additional memory usage is a valid tradeoff depends on your application.

  • when you mention "don't construct the same object over and over again" you mean avoid doing TYPE(args...)? I thought that was pretty neat instead of implementing a virtual compare function that essentially uses the same parameters as the constructor. I should profile creating that temporary object to see how much it weights in the total time elapsed. As for your partitioning, it seems to all boil down to created specialized containers per type, but we'd still have to figure out a way to differentiate objects from each other of the same TYPE so we can sort things out. – Deathicon Sep 12 '17 at 18:40
  • @Deathicon Avoiding the TYPE constructor is a very minor thing, but it turns out that passing a TYPE object by value is more or less the same as constructing the object internally. The compiler may not be able to remove the repeated instantiation if the TYPE isn't trivially constructible and destructible: minute but avoidable overhead. Your shown search() function also doesn't use perfect forwarding for the args which leads to unnecessary copies, but that's bordering on nitpicking. – amon Sep 13 '17 at 8:59
  • This answer doesn't provide clear directions how your search could get faster. But it does discuss mechanisms how you can structure your data to optimize and specialize the search for those types where optimizations are possible. There's not enough info for more detailed advice and discussing 300+ classes here would be far too broad. You know best what these classes represent and how they are used. – amon Sep 13 '17 at 9:01
0

Just a pragmatic idea for improved indexing/hashing:

  1. Create a numeric hash value (uint) not only taking into account TYPE (as you already did in your example), but also ARGS - these are the two properties I can identify to define a distinct object group from your example.
  2. Store the pointers in a multi-value hash container (std::unordered_multimap), using the hash value as key.
  3. Extract all objects of a group with std::unordered_multimap::equal_range().

With this you've moved part of the calculations necessary to compare the objects into creation of the hash, and the lookup of all pointers of a specific "type"/object group should be as fast as it can get.

  • TYPE does form distinct groups, but not ARGS which is just the values of the object. So the key cannot be a combination of both TYPE and ARGS in my case. – Deathicon Sep 13 '17 at 17:18
  • 1
    In this case your original example was misleading; I see you already fixed that. Now, before thinking about optimization you should profile the code first and see where the processing time is spent; further measures will depend on that. – Murphy Sep 13 '17 at 17:51
0

To me your search function has too little information. Even though you've now parallelized it and it's 6x faster, you're still doing things like linearly searching through every single object of a given type just to see if two name string fields match. That's still kind of gross even if the linear-time search algorithm is distributed across threads. It's like multithreading a bubble sort when you could have been using quicksort.

Your callers obviously have more information about what they're searching for when they call the search function for it to be able to do something much, much smarter than linearly search through all objects of the same type checking for equality. Otherwise the search function would not be able to narrow down its result to a single object.

So to me it's worth identifying the type of searches you do most often and not use this generalized search function in those critical paths. If you do name string comparisons often to find objects with a matching name, then it would likely shave off way more time than it costs to build and update the structure when you add/remove objects if you built an associative container like a binary tree (map), trie, or a hash table (unordered_map) mapping string keys to object pointers. You can then use a search_by_name function to retrieve objects with a matching name using this data structure to accelerate searches.

Now you've improved the search algorithm from linear time to logarithmic or even constant time and your searches will potentially be way faster single-threaded in constant time than even multithreaded in linear time on top of being able to scale better, and now you can parallelize the much cheaper searches if you still want to multithread instead of devoting all your hardware to performing a single expensive linear search just to find an object with a matching name, e.g.

Your now multithreaded search function might still be useful as a fallback for rare cases, but for the common cases I'd degeneralize a bit and start building appopriate associative structures and corresponding search functions to vastly speed up these searches for the most common case types of searches you perform.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.