Use std::unordered_set (hash set) instead of std::set (tree set) in blockfilter interface, as suggested by @ryanofsky in #12254. This may result in a very minor speedup, but I haven't measured.
This moves CSipHasher to it's own file crypto/siphash.h, so that it can be used in the libbitcoin_util library without including hash.{h,cpp}. I'm open to other suggestions on solving this issue if people would prefer to leave CSipHasher where it is.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
357 | + uint64_t m_k0, m_k1; 358 | + 359 | +public: 360 | + ByteVectorHash(); 361 | + size_t operator()(const std::vector<unsigned char>& input) const; 362 | +};
I don't think util.h is the best place for a generic utility data structure such as this, it's more for assorted operating system functions
or maybe support/bytevectorhash.h ?
unless there's a strong need to group this with other things
0 | @@ -0,0 +1,47 @@ 1 | +// Copyright (c) 2016-2018 The Bitcoin Core developers
ACK on moving siphash to a separate unit
utACK f4608359e4e643c6e197df822e03226146e37a49 verified move-onlyness of extraction commit
0 | @@ -0,0 +1,18 @@ 1 | +// Copyright (c) 2018 The Bitcoin Core developers 2 | +// Distributed under the MIT software license, see the accompanying 3 | +// file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 | + 5 | +#include <crypto/siphash.h> 6 | +#include <support/bytevectorhash.h> 7 | +#include <random.h>
src/support/bytevectorhash.cpp:6:1: warning: #includes are not sorted properly [llvm-include-order]
20 | + v[0] = 0x736f6d6570736575ULL ^ k0; 21 | + v[1] = 0x646f72616e646f6dULL ^ k1; 22 | + v[2] = 0x6c7967656e657261ULL ^ k0; 23 | + v[3] = 0x7465646279746573ULL ^ k1; 24 | + count = 0; 25 | + tmp = 0;
Initialize count and tmp using default member initializers or in the member initializer list of the constructor?
This is a move-only commit. I'd rather not modify the contents of the code here.
Makes sense!
@ryanofsky can you take a look here please? according to @jimpo this was your suggestion
0 | @@ -0,0 +1,23 @@ 1 | +// Copyright (c) 2018 The Bitcoin Core developers 2 | +// Distributed under the MIT software license, see the accompanying 3 | +// file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 | + 5 | +#ifndef BITCOIN_SUPPORT_BYTEVECTORHASH_H 6 | +#define BITCOIN_SUPPORT_BYTEVECTORHASH_H 7 | + 8 | +/** 9 | + * Implementation of Hash named requirement for a byte vector. This may be used the hash function in
This may be used as the hash.. ?
10 | + * std::unordered_set or std::unordered_map over std::vector<unsigned char>. Internally, a random 11 | + * instance of SipHash-2-4 is used. 12 | + */ 13 | +class ByteVectorHash 14 | +{ 15 | +private:
Drop private.
I think it's more clear to leave it explicit even if the default for class is private.
14 | @@ -15,6 +15,7 @@ 15 | 16 | #include <amount.h> 17 | #include <coins.h> 18 | +#include <crypto/siphash.h>
Can be removed?
It's used in SaltedTxidHasher
5 | @@ -6,6 +6,7 @@ 6 | #include <util.h> 7 | 8 | #include <chainparamsbase.h> 9 | +#include <crypto/siphash.h>
Can be removed?
0 | @@ -0,0 +1,23 @@ 1 | +// Copyright (c) 2018 The Bitcoin Core developers 2 | +// Distributed under the MIT software license, see the accompanying 3 | +// file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 | + 5 | +#ifndef BITCOIN_SUPPORT_BYTEVECTORHASH_H 6 | +#define BITCOIN_SUPPORT_BYTEVECTORHASH_H 7 | + 8 | +/**
Missing includes <stdint.h> and <vector>.
8 | +/** 9 | + * Implementation of Hash named requirement for a byte vector. This may be used the hash function in 10 | + * std::unordered_set or std::unordered_map over std::vector<unsigned char>. Internally, a random 11 | + * instance of SipHash-2-4 is used. 12 | + */ 13 | +class ByteVectorHash
nit, final.
@jimpo can you improve PR description of the advantages of this change (beside linking @ryanofsky suggestion)?
Do you have numbers to support this change?
Left some nits.
5 | +#ifndef BITCOIN_SUPPORT_BYTEVECTORHASH_H 6 | +#define BITCOIN_SUPPORT_BYTEVECTORHASH_H 7 | + 8 | +/** 9 | + * Implementation of Hash named requirement for a byte vector. This may be used the hash function in 10 | + * std::unordered_set or std::unordered_map over std::vector<unsigned char>. Internally, a random
In commit "blockfilter: Use unordered_set instead of set in blockfilter." (f4608359e4e643c6e197df822e03226146e37a49)
The way this is written makes it seem like this whole class is tied to std::vector<unsigned char>, when actually only the call operator is. I guess my concern that if someone wants to reuse this hash function on a similar type like Span<char>, prevector, or std::string, the naming and comments here will lead them to copy/paste/rename this whole class instead of doing something simpler like overloading the call operator or adding a Span conversion.
I'd suggest:
operator() overloads for new types could be added here in the future.ByteVectorHash to something like RandomizedSipHash to avoid tying it to std::vector.std::vector with Span.
I updated the comment to say that it works for any types that internally store (or reference) a byte array, but decided not to change the class name.
utACK f4608359e4e643c6e197df822e03226146e37a49. Sorry for missing this previously. I confirmed the first commit is move-only, and I think the changes in the second commit should make it easier to use hash maps more places in the future. I left a suggestion below, but also think this change looks good as it is.
utACK cfabca8749a132220e649d4563fb876afc21ceec
Just one not comment: I always imagined the things in 'support' as low level features that are independently usable, and find it a bit strange to put something there that depends on random and crypto/siphash. Perhaps others have a different understanding, as I don't think it was ever written down somewhere what it was for, but I would just put it in src/.
utACK cfabca8749a132220e649d4563fb876afc21ceec. Only changes are updating ByteVectorHash comment, adding final specifier, and tweaking includes.
This is a move-only commit with the exception of changes to includes.
utACK fef5adcc331c4d7b92b71e03fc8a73343a865599