This might be a silly question based on the fact that std::set<> already has perfectly good comparison operators, but I think I might have an optimization for my specific use case and want to make sure I'm not hurting myself somehow.
Essentially, I have a costly operation that takes as input a std::set&. I'm caching the operation's result so I can just return the result if the same inputs have already been passed in. This does require storing copies of the sets (which I'm doing in a
std::map<std::set<std::string>, Result*>
, and then doing a search every time the operation is called. Since it is very likely that the same operation is going to be called thousands of times in a row, I would say that the cached std::set is found >99% of the time. I recently experimented with what I thought might be a small improvement, based on the fact that certain characters are invalid in the passed-in strings: I flattened the std::set into a single string, the component strings being delimited with a ':' character. My std::map then becomes
std::map<std::string, Result*>
and every time the operation is called, the set is flattened and the single string searched for in the cache.
I was actually surprised by the performance improvement. My test run used std::sets containing 5 strings, each 30 characters long, and a run of 10,000,000 searches. On my workstation, the times for each run were
std::map<std::set<std::string>, Result*> : 138.8 seconds
std::map<std::string, Result> : 89.2 seconds
It seems that, even with the overhead of flattening the set every call, the second method is a huge improvement. I guess my question is: why? Am I doing something potentially bad here that the implementors of std::set purposefully avoided (i.e. potentially causing bad heap fragmentation with the bigger string?) Is it simply because the individual strings in the set are in different locations and have to be compared separately? Am I shooting myself in the foot? It just seems like too obvious an improvement in this specific case to give such a performance boost.