Default less-than comparison of public_key_type is slooooowwwwww

[nathanielhourt]

Updated by @abitmore: duplicate of #1371.

--- Original Message ---

Just caught this... Fwiw:

BOOST_AUTO_TEST_CASE(public_key_type_comparison) {
    flat_set<public_key_type> s1;

    for (int i = 0; i < 5; ++i)
        s1.insert(fc::ecc::private_key::generate().get_public_key());

    flat_set<public_key_type, pubkey_comparator> s2(s1.begin(), s1.end());

    const int rounds = 1'000'000;

    auto start = fc::time_point::now();
    for (int i = 0; i < rounds; ++i)
        BOOST_CHECK(s1.contains(*s1.begin()));
    auto end = fc::time_point::now();

    wlog("public_key_type default comparion: ${rounds} rounds in ${ms} ms",
         ("rounds", rounds)("ms", (end-start).count()/1000));

    start = fc::time_point::now();
    for (int i = 0; i < rounds; ++i)
        BOOST_CHECK(s2.contains(*s2.begin()));
    end = fc::time_point::now();

    wlog("public_key_type proper comparion: ${rounds} rounds in ${ms} ms",
         ("rounds", rounds)("ms", (end-start).count()/1000));
}

Output:

83440ms th_a       performance_tests.cpp:67      test_method          ] public_key_type default comparion: 1000000 rounds in 5637 ms
83772ms th_a       performance_tests.cpp:75      test_method          ] public_key_type proper comparion: 1000000 rounds in 332 ms

In other words, public_key_type has no native operator< defined, but address does and public_key_type converts to address implicitly, so public_key_type() < public_key_type() converts both to address and compares those, which means two unnecessary SHA512 calculations.

Does it matter? See here

[abitmore]

Known issue. Unfortunately simply adding an explicit operator< function changes consensus. See #1151.

For use cases like sign_state, if it does not impact consensus, I think we can just use another comparison function to improve performance. E.G. change

      flat_map<public_key_type,bool>   provided_signatures;

to

      flat_map<public_key_type,bool, pubkey_comparator>   provided_signatures;

Related code:

bitshares-core/libraries/protocol/include/graphene/protocol/types.hpp

Lines 269 to 274 in 349e006

	class pubkey_comparator {
	public:
	inline bool operator()(const public_key_type& a, const public_key_type& b) const {
	return a.key_data < b.key_data;
	}
	};

[abitmore]

Probably a better solution is to add a faster default comparison function, and update the code that impacts consensus to use an explicit "old" comparison function.

[nathanielhourt]

Known issue. Unfortunately simply adding an explicit operator< function changes consensus. See #1151.

I was afraid it might, which is why I didn't propose a fix. I haven't seen what consensus mechanisms are affected yet, but I haven't looked too closely yet either.

[abitmore]

Actually this issue is a duplicate of #1371. We have made efforts to address it and found it was a non-issue (see #1401) so decided that we won't fix it.

Time may have changed though. If new data shows that it became an issue we may try to address it again, otherwise it's better to leave it there.

[abitmore]

FWIW related issues:

• a special public key can't be in key_auths array: Missing Active Authority bitsharesjs#13
• Wrong public key recovered from signature? (missing required active authority even when authority's signature is present.) #607
• Missing Active Authority while adding active authority cryptonomex/graphene-ui#795
• Missing Active Authority while adding active authority cryptonomex/graphene#630

[nathanielhourt]

Alright, well I'd mistakenly assumed it was new information, but since it isn't, feel free to close this issue as duplicate, or not, as you see fit. :)

[abitmore]

Duplicate of #1371. Closing.