-
Notifications
You must be signed in to change notification settings - Fork 249
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Removing unordered_maps may give big performance improvements #483
Comments
This PR performs some light optimizations discovered through profiling. First, it improves memory access during the relabeling procedure: - Use `vector` instead of `unordered_map` for relabeled responses. - Re-use a single vector to hold relabeled responses. It also updates the vector allocation and access strategy for code on the hot path: - When populating vectors, use `resize` and `operator[]` instead of `reserve` and `push_back`. - Prefer `operator[]` instead of `at` for vector element access. Addresses #483.
On this and #359 : did you want to switch out all unordered_maps? Aside for future reference: easy way to set up profiling from R: On Mac you can get the above output without starting from the C++ side. Build the package from source as usual, debug symbols are included by default (the -g in $ R CMD config CXXFLAGS). a) Start R or RStudio. To get source annotations (Mac specific dSYM file is not automatically generated) run Another aside: stepping through grf C++ from R with lldb: https://gist.github.com/erikcs/5e1f0994f8c4d274926e50a2ba1901de |
This was already fixed in #514 but the issue remained open. Closing now |
This PR performs some light optimizations discovered through profiling. First, it improves memory access during the relabeling procedure: - Use `vector` instead of `unordered_map` for relabeled responses. - Re-use a single vector to hold relabeled responses. It also updates the vector allocation and access strategy for code on the hot path: - When populating vectors, use `resize` and `operator[]` instead of `reserve` and `push_back`. - Prefer `operator[]` instead of `at` for vector element access. Addresses grf-labs#483.
We noted in our meeting today that our splitting rules seem to be making use of
unordered_map
. As we've seen before (#359), it seems that we should avoid c++ hash tables at all costs.What I have now is far from a full-blown perf analysis, but check this out.
regression_forest
ontest/forest/resources/regression_data.csv
(n=500, p=10). This is the output of CLion's profiler.The total runtime was 3.43 seconds. (Note this branch contains the same code as the current development version of grf, except I added a command-line interface for profiling).
std::unordered_map<size_t, double>
withstd::vector<double>
in folderssplitting
andrelabeling
, and then make sure that the vectors are property initialized.This time, the total runtime was 2.26 seconds, which is 65.8% of the version with unordered_map.
With a larger dataset (n=15000, p=10), the runtime is 61s with grf development version, and about 37s using
std::vector
.The text was updated successfully, but these errors were encountered: