You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@kudu.apache.org by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org> on 2019/12/19 23:47:39 UTC
[kudu-CR] [util] Import FastHash hash function to util
Bankim Bhavsar has uploaded this change for review. ( http://gerrit.cloudera.org:8080/14934
Change subject: [util] Import FastHash hash function to util
......................................................................
[util] Import FastHash hash function to util
FastHash is a simple, robust, and efficient general purpose
hash function from Google.
It's fast, small in size and with least/no quality problems
as per smhasher and hence a good candidate for BlockBloomFilter.
C++ implementation has been ported straight from
https://code.google.com/archive/p/fast-hash/ with minor style
modifications.
Java implementation has been adapted from the C implementation.
Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
---
A java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
A java/kudu-client/src/test/java/org/apache/kudu/util/TestFashHash.java
M src/kudu/util/hash_util-test.cc
M src/kudu/util/hash_util.h
4 files changed, 256 insertions(+), 3 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/34/14934/1
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 1
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 4:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@71
PS3, Line 71: // Implementation is adapted from https://code.google.com/archive/p/fast-hash/
> Nit: add an empty line before to separate the FastHash commentary from the
Done
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@73
PS3, Line 73: ATTRIBUTE_NO_SANITIZE_INTEGER
> Is the inline keyword needed here and below? The function is defined entire
Compiler should inline this function since it's in the header but explicitly mentioning it hints the compiler and also hints the reader why the function is defined in the header and shouldn't be moved to .cc file.
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 4
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Sat, 21 Dec 2019 00:15:02 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 6:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@71
PS3, Line 71: // Implementation is adapted from https://code.google.com/archive/p/fast-hash/
> Not quite what I meant. Here's how I think it should look:
Done
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@73
PS3, Line 73: // Compute 64-bit FastHash.
> I don't feel strongly about this.
Done
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 6
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Thu, 02 Jan 2020 20:45:53 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 3:
(8 comments)
http://gerrit.cloudera.org:8080/#/c/14934/3/java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
File java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java:
http://gerrit.cloudera.org:8080/#/c/14934/3/java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java@37
PS3, Line 37: long
Interesting, what happends when a signed type overflow in Java? Is it the same as in C/C++?
Could you add a small note about that, please?
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util-test.cc
File src/kudu/util/hash_util-test.cc:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util-test.cc@42
PS3, Line 42: // Test FastHash64/32 returns the expected values for inputs. These tests are
Does it make sense to add a small test to make sure this hash implementation runs faster than Google MurmurHash2? Maybe, just to make sure there aren't any regressions. Or it's not possible to have a regression here since the implementation is not going to change after the initial commit? :)
Maybe, they have something like that at https://code.google.com/archive/p/fast-hash/ ?
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@34
PS3, Line 34: static const uint64_t MURMUR_PRIME = 0xc6a4a7935bd1e995;
nit: add UL suffix just for the unification with the way those constants are defined here and in FastHash64() ?
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@73
PS3, Line 73: static inline uint64_t FastHash64(const void* buf, size_t len, uint64_t seed) {
> Is the inline keyword needed here and below? The function is defined entire
+1
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@74
PS3, Line 74: m
style nit: it should be some thing like M or kM, kMultiplier of whatever according to the google style guide
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@74
PS3, Line 74: const
Would constexp do any difference here?
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@75
PS3, Line 75:
nit: drop the extra space?
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@86
PS3, Line 86:
nit: drop the extra space?
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 3
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Sat, 21 Dec 2019 00:19:08 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Andrew Wong (Code Review)" <ge...@cloudera.org>.
Andrew Wong has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
[util] Import FastHash hash function to util
FastHash is a simple, robust, and efficient general purpose
hash function from Google.
It's fast, small in size and with least/no quality problems
as per smhasher and hence a good candidate for BlockBloomFilter.
C++ implementation has been ported straight from
https://code.google.com/archive/p/fast-hash/ with minor style
modifications.
Java implementation has been adapted from the C implementation.
Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Reviewed-on: http://gerrit.cloudera.org:8080/14934
Tested-by: Kudu Jenkins
Reviewed-by: Alexey Serbin <as...@cloudera.com>
---
A java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
A java/kudu-client/src/test/java/org/apache/kudu/util/TestFashHash.java
M src/kudu/util/hash_util-test.cc
M src/kudu/util/hash_util.h
4 files changed, 260 insertions(+), 3 deletions(-)
Approvals:
Kudu Jenkins: Verified
Alexey Serbin: Looks good to me, approved
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 8
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 7: Code-Review+2
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 7
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Tue, 07 Jan 2020 18:33:44 +0000
Gerrit-HasComments: No
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/14934
to look at the new patch set (#2).
Change subject: [util] Import FastHash hash function to util
......................................................................
[util] Import FastHash hash function to util
FastHash is a simple, robust, and efficient general purpose
hash function from Google.
It's fast, small in size and with least/no quality problems
as per smhasher and hence a good candidate for BlockBloomFilter.
C++ implementation has been ported straight from
https://code.google.com/archive/p/fast-hash/ with minor style
modifications.
Java implementation has been adapted from the C implementation.
Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
---
A java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
A java/kudu-client/src/test/java/org/apache/kudu/util/TestFashHash.java
M src/kudu/util/hash_util-test.cc
M src/kudu/util/hash_util.h
4 files changed, 257 insertions(+), 3 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/34/14934/2
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 2
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 3:
(16 comments)
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util-test.cc
File src/kudu/util/hash_util-test.cc:
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util-test.cc@51
PS1, Line 51: hash = HashUtil::FastHash64("abcdefg", 7, 0);
> warning: 7 is a magic number; consider replacing it with a named constant [
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util-test.cc@54
PS1, Line 54: hash = HashUtil::FastHash64("quick brown fox", 15, 42);
> warning: 15 is a magic number; consider replacing it with a named constant
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util-test.cc@64
PS1, Line 64: hash = HashUtil::FastHash32("abcdefg", 7, 0);
> warning: 7 is a magic number; consider replacing it with a named constant [
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util-test.cc@67
PS1, Line 67: hash = HashUtil::FastHash32("quick brown fox", 15, 42);
> warning: 42 is a magic number; consider replacing it with a named constant
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@75
PS1, Line 75: const uint64_t* pos = static_cast<const uint64_t *>(buf);
> warning: 8 is a magic number; consider replacing it with a named constant [
Addressed by fixing the .clang-tidy config file.
https://gerrit.cloudera.org/c/14940/1
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@88
PS1, Line 88:
> warning: 7 is a magic number; consider replacing it with a named constant [
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@89
PS1, Line 89: switch (len & 7) {
> warning: 7 is a magic number; consider replacing it with a named constant [
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@90
PS1, Line 90: case 7: v ^= static_cast<uint64_t>(pos2[6]) << 48;
> warning: 5 is a magic number; consider replacing it with a named constant [
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@91
PS1, Line 91: case 6: v ^= static_cast<uint64_t>(pos2[5]) << 40;
> warning: 32 is a magic number; consider replacing it with a named constant
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@92
PS1, Line 92: case 5: v ^= static_cast<uint64_t>(pos2[4]) << 32;
> warning: 24 is a magic number; consider replacing it with a named constant
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@93
PS1, Line 93: case 4: v ^= static_cast<uint64_t>(pos2[3]) << 24;
> warning: 16 is a magic number; consider replacing it with a named constant
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@94
PS1, Line 94: case 3: v ^= static_cast<uint64_t>(pos2[2]) << 16;
> warning: 8 is a magic number; consider replacing it with a named constant [
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@109
PS1, Line 109: uint64_t h = FastHash64(buf, len, seed);
> warning: 32 is a magic number; consider replacing it with a named constant
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@115
PS1, Line 115: ATTRIBUTE_NO_SANITIZE_INTEGER
> warning: 23 is a magic number; consider replacing it with a named constant
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@116
PS1, Line 116: static inline uint64_t FastHashMix(uint64_t h) {
> warning: 0x2127599bf4325c37UL is a magic number; consider replacing it with
Done
http://gerrit.cloudera.org:8080/#/c/14934/1/src/kudu/util/hash_util.h@117
PS1, Line 117: h ^= h >> 23;
> warning: 47 is a magic number; consider replacing it with a named constant
Done
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 3
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Comment-Date: Fri, 20 Dec 2019 20:05:24 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Bankim Bhavsar has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 5:
(7 comments)
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util-test.cc
File src/kudu/util/hash_util-test.cc:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util-test.cc@42
PS3, Line 42: // Test FastHash64/32 returns the expected values for inputs. These tests are
> Does it make sense to add a small test to make sure this hash implementatio
As per smhasher https://github.com/rurban/smhasher, fasthash is similar in speed as compared to Murmur2Hash(64-bit variant we use) for 64-bit but with fewer quality problems.
fasthash32 4658.24 50.50 181.96 (2) 566
fasthash64 4657.64 47.71 168.22 (3) 509 MomentChi2 5159 !
Murmur2B 4728.94 47.90 192.82 (18) 433 1.8% bias, collisions, 3.4% distrib, BIC
I see fasthash comes with it's own benchmarking tests, so I can try importing those tests and comparing.
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@34
PS3, Line 34: static constexpr uint64_t MURMUR_PRIME = 0xc6a4a7935bd1e995UL;
> nit: add UL suffix just for the unification with the way those constants ar
Done
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@73
PS3, Line 73: ATTRIBUTE_NO_SANITIZE_INTEGER
> +1
Is +1 to Adar's comment or my comment?
If to Adar's comment, explanation is same as above. If you guys feel strongly about dropping the inline keyword then I can do it.
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@74
PS3, Line 74: line
> Would constexp do any difference here?
Done
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@74
PS3, Line 74: a
> style nit: it should be some thing like M or kM, kMultiplier of whatever ac
Done
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@75
PS3, Line 75: f
> nit: drop the extra space?
Done
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@86
PS3, Line 86:
> nit: drop the extra space?
Done
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 5
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Thu, 26 Dec 2019 20:45:06 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/14934
to look at the new patch set (#3).
Change subject: [util] Import FastHash hash function to util
......................................................................
[util] Import FastHash hash function to util
FastHash is a simple, robust, and efficient general purpose
hash function from Google.
It's fast, small in size and with least/no quality problems
as per smhasher and hence a good candidate for BlockBloomFilter.
C++ implementation has been ported straight from
https://code.google.com/archive/p/fast-hash/ with minor style
modifications.
Java implementation has been adapted from the C implementation.
Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
---
A java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
A java/kudu-client/src/test/java/org/apache/kudu/util/TestFashHash.java
M src/kudu/util/hash_util-test.cc
M src/kudu/util/hash_util.h
4 files changed, 258 insertions(+), 3 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/34/14934/3
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 3
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Alexey Serbin, Kudu Jenkins, Adar Dembo, Todd Lipcon,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/14934
to look at the new patch set (#6).
Change subject: [util] Import FastHash hash function to util
......................................................................
[util] Import FastHash hash function to util
FastHash is a simple, robust, and efficient general purpose
hash function from Google.
It's fast, small in size and with least/no quality problems
as per smhasher and hence a good candidate for BlockBloomFilter.
C++ implementation has been ported straight from
https://code.google.com/archive/p/fast-hash/ with minor style
modifications.
Java implementation has been adapted from the C implementation.
Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
---
A java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
A java/kudu-client/src/test/java/org/apache/kudu/util/TestFashHash.java
M src/kudu/util/hash_util-test.cc
M src/kudu/util/hash_util.h
4 files changed, 260 insertions(+), 3 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/34/14934/6
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 6
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Adar Dembo (Code Review)" <ge...@cloudera.org>.
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 3:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@71
PS3, Line 71: // Compute 64-bit FastHash.
Nit: add an empty line before to separate the FastHash commentary from the two implementations.
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@73
PS3, Line 73: static inline uint64_t FastHash64(const void* buf, size_t len, uint64_t seed) {
Is the inline keyword needed here and below? The function is defined entirely in the header; won't it be inlined automatically by the compiler?
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 3
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Fri, 20 Dec 2019 22:40:01 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Adar Dembo (Code Review)" <ge...@cloudera.org>.
Adar Dembo has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 5:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@71
PS3, Line 71: // Implementation is adapted from https://code.google.com/archive/p/fast-hash/
> Done
Not quite what I meant. Here's how I think it should look:
// FastHash is ...
// Implementation is ...
//
// Compute 64-bit FastHash.
// static inline uint64_t FastHash64(...) { ... }
//
// Compute 32-bit FastHash.
// static inline uint32_t FastHash32(...) { ... }
Meaning, the generic FastHash commentary should be separated from the two "function comment + function" blocks, to emphasize that the commentary applies to both blocks.
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@73
PS3, Line 73: ATTRIBUTE_NO_SANITIZE_INTEGER
> That's +1 to Adar's comment. See https://llvm.org/docs/CodingStandards.htm
I don't feel strongly about this.
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 5
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Sun, 29 Dec 2019 18:48:14 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 3:
(1 comment)
http://gerrit.cloudera.org:8080/#/c/14934/3/java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
File java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java:
http://gerrit.cloudera.org:8080/#/c/14934/3/java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java@37
PS3, Line 37: long
> Interesting, what happends when a signed type overflow in Java? Is it the
Ah, it seems all is well there. Sorry for the noise. Probably, this isn't not worth documenting in the code.
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 3
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Sat, 21 Dec 2019 04:17:30 +0000
Gerrit-HasComments: Yes
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Alexey Serbin, Kudu Jenkins, Adar Dembo, Todd Lipcon,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/14934
to look at the new patch set (#5).
Change subject: [util] Import FastHash hash function to util
......................................................................
[util] Import FastHash hash function to util
FastHash is a simple, robust, and efficient general purpose
hash function from Google.
It's fast, small in size and with least/no quality problems
as per smhasher and hence a good candidate for BlockBloomFilter.
C++ implementation has been ported straight from
https://code.google.com/archive/p/fast-hash/ with minor style
modifications.
Java implementation has been adapted from the C implementation.
Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
---
A java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
A java/kudu-client/src/test/java/org/apache/kudu/util/TestFashHash.java
M src/kudu/util/hash_util-test.cc
M src/kudu/util/hash_util.h
4 files changed, 259 insertions(+), 3 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/34/14934/5
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 5
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Bankim Bhavsar (Code Review)" <ge...@cloudera.org>.
Hello Tidy Bot, Kudu Jenkins, Adar Dembo, Todd Lipcon,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/14934
to look at the new patch set (#4).
Change subject: [util] Import FastHash hash function to util
......................................................................
[util] Import FastHash hash function to util
FastHash is a simple, robust, and efficient general purpose
hash function from Google.
It's fast, small in size and with least/no quality problems
as per smhasher and hence a good candidate for BlockBloomFilter.
C++ implementation has been ported straight from
https://code.google.com/archive/p/fast-hash/ with minor style
modifications.
Java implementation has been adapted from the C implementation.
Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
---
A java/kudu-client/src/main/java/org/apache/kudu/util/HashUtil.java
A java/kudu-client/src/test/java/org/apache/kudu/util/TestFashHash.java
M src/kudu/util/hash_util-test.cc
M src/kudu/util/hash_util.h
4 files changed, 259 insertions(+), 3 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/kudu refs/changes/34/14934/4
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 4
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
[kudu-CR] [util] Import FastHash hash function to util
Posted by "Alexey Serbin (Code Review)" <ge...@cloudera.org>.
Alexey Serbin has posted comments on this change. ( http://gerrit.cloudera.org:8080/14934 )
Change subject: [util] Import FastHash hash function to util
......................................................................
Patch Set 3:
(2 comments)
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util-test.cc
File src/kudu/util/hash_util-test.cc:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util-test.cc@42
PS3, Line 42: // Test FastHash64/32 returns the expected values for inputs. These tests are
> As per smhasher https://github.com/rurban/smhasher, fasthash is similar in
Thank you for the information.
I think at this point it's fine to just add the information on the expected speed and other parameters as above into the commit message. For some reason, I was expecting much faster speed compared with murmur2b, but apparently it's not the case.
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h
File src/kudu/util/hash_util.h:
http://gerrit.cloudera.org:8080/#/c/14934/3/src/kudu/util/hash_util.h@73
PS3, Line 73: static inline uint64_t FastHash64(const void* buf, size_t len, uint64_t seed) {
> Is +1 to Adar's comment or my comment?
That's +1 to Adar's comment. See https://llvm.org/docs/CodingStandards.html#don-t-use-inline-when-defining-a-function-in-a-class-definition for details.
--
To view, visit http://gerrit.cloudera.org:8080/14934
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: kudu
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Id0a21d6af10d9ba0dbd9ab46d73552d42976e8d7
Gerrit-Change-Number: 14934
Gerrit-PatchSet: 3
Gerrit-Owner: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Adar Dembo <ad...@cloudera.com>
Gerrit-Reviewer: Alexey Serbin <as...@cloudera.com>
Gerrit-Reviewer: Bankim Bhavsar <ba...@cloudera.com>
Gerrit-Reviewer: Kudu Jenkins (120)
Gerrit-Reviewer: Tidy Bot (241)
Gerrit-Reviewer: Todd Lipcon <to...@apache.org>
Gerrit-Comment-Date: Fri, 27 Dec 2019 01:25:47 +0000
Gerrit-HasComments: Yes