ppsspp
ppsspp copied to clipboard
hrydgard
Optimize SymbolMap::AddModule and UpdateActiveSymbols using reserve, unordered_map, C++17 features
@hrydgard, I think it will be very useful, judging by comment in begin function
Im sorry, I did not check build for linux and android, lower_bound and upper_bound unordered_map methods are supported only MSVC, but they can be replaced with find().
More info: https://stackoverflow.com/a/75705300
Im sorry, I did not check build for linux and android, lower_bound and upper_bound unordered_map methods are supported only MSVC, but they can be replaced with find().
Don't need to be sorry about not checking the build, but I don't see how lower_bound/upper_bound are even meaningful on an unordered_map?
Anyway, how much does this change speed things up? Did you have a very slow use case?
Calling reserve on the vector with the argument size() + 1 should make it slower. Before your change it calls reserve itself (if it needs to) in the push_back function and that's twice the vector's current size to make sure push/pop/emplace_back's complexity is amortized O(1). You deliberately force it to realloc on every call to SymbolMap::AddModule and that's wrong. If you want the details, it'll be O(curr_size) per call => O(modules_count^2) to add all modules (instead of O(modules_count).
I don't know what to say about the change of map to unordered_map, you didn't explain why it should fit better. Also this weird rbegin() to std::make_reverse_iterator(begin())... The std::find_if though looks better than what was before.
I would also like to see your benchmarks, because so far it looks like it makes stuff slower. Unless, of course, you didn't benchmark it, and just thought it may improve something. Without testing it's even hard to tell if the lambda in the std::find_if would add enough overhead to nullify the speedup.
