Map

[HimanshuWAR]

I converted an array into a map. It was done for issue #3298 opened on Mar 13, 2020, by nbougalis. The name of the map was kept the same as the array "command". As a map requires a pair, I made a key which was of type string_view and the second one was user-defined data. The changes are made from lines 1224 to 1310 in file "rippled/src/ripple/net/impl/RPCCall.cpp" in develop `branch. Before changes: ``` struct Command { const char* name; parseFuncPtr parse; int minParams; int maxParams; };

    // FIXME: replace this with a function-static std::map and the lookup
    // code with std::map::find when the problem with magic statics on
    // Visual Studio is fixed.
    static Command const commands[] = {
        // Request-response methods
        // - Returns an error, or the request.
        // - To modify the method, provide a new method in the request.
        {"account_currencies", &RPCParser::parseAccountCurrencies, 1, 3},
        //multiple fields like //
        };

_After changes:_

       ```
        struct Command
        {
            parseFuncPtr parse;
            int minParams;
            int maxParams;
        };


        // Visual Studio is fixed.
        static const std::map<std::string_view, Command> command =
        {
        {"account_currencies", {  &RPCParser::parseAccountCurrencies, 1, 3 }},
        //multiple fields like above//
        };

This is my very first PR. I hope that if you find any mistakes or errors in my changes, you will help me rectify them. Thank you!

[ckeshava]

Hi,

I measured the time-taken by alternatives discussed in this Pull Request. I considered the following data structures: - linear search over constexpr array, binary_search over sorted array, search in std::map and search operation in std::unordered_map.

The commands array is primarily used for search operation only within the parseCommand function.

Here are the results for these data structures. The ranges refer to bucket-frequency information for ease of understanding. The time is measured in nano-seconds.

Linear Search on constexpr array: avg ns: 2927; longest ns: 793916 ranges -- 0-9ns: 0; 10-99ns: 389; 100-999ns: 44156; 1000-9999ns: 79586; 10000-99999ns: 2827; 100000ns and over: 18

Binary Search on a constexpr sorted array: avg ns: 3949; longest ns: 6460959 ranges -- 0-9ns: 0; 10-99ns: 83; 100-999ns: 26735; 1000-9999ns: 98521; 10000-99999ns: 1810; 100000ns and over: 150

std::map data structure: avg ns: 3998; longest ns: 2221792 ranges -- 0-9ns: 0; 10-99ns: 123; 100-999ns: 21839; 1000-9999ns: 103047; 10000-99999ns: 2119; 100000ns and over: 171

std::unordered_map data structure: avg ns: 2666; longest ns: 2667042 ranges -- 0-9ns: 94; 10-99ns: 1679; 100-999ns: 43767; 1000-9999ns: 81085; 10000-99999ns: 653; 100000ns and over: 21

Both constexpr array and std::unordered_map have similar time performance.

I feel the improvements are marginal so its pragmatic to stick with a constexpr array instead of switching to unordered_map. the map does not have the advantages of compile-time static-assert checks. If the array were to get a lot bigger the unordered_map might be justified.

[These observations are as of July 2022]

Many many thanks for Scott Schurr for providing the profiling code and also helping in debugging and brainstorming these observations.

[greg7mdp]

Just a thought. std::unordered_map is not very efficient, absl::flat_hash_map would much likely be faster.

[scottschurr]

@greg7mdp, good point. However we don't (yet) have abseil as a dependency. If that happens we should revisit a number of the containers used in the code base.

[greg7mdp]

Oh, my bad, thank you @scottschurr , I thought we already did have an abseil dependency!

[scottschurr]

I suggest that this pull request be closed. We've not heard from the contributor for quite a while, and the changes suggested in this pull request have been superseded by https://github.com/XRPLF/rippled/commit/9aaa0dff5fd422e5f6880df8e20a1fd5ad3b4424 which is now in the develop branch.

[nbougalis]

Per @scottschurr's comment, this PR has been superseded and most of the functionality has already been implemented.