SkBitmapHasher: use 64-bit-truncated MD5 instead of 64-bit CityHash

SkBitmapHasher: use 64-bit-truncated MD5 instead of 64-bit CityHash
BUG=https://code.google.com/p/skia/issues/detail?id=1257

(if we change our mind within the next few days, we can toggle the
BITMAPHASHER_USES_TRUNCATED_MD5 #ifdef ; at some point, we'll remove that
option so we can delete our CityHash implementation entirely)

R=bungeman@google.com

Committed: https://code.google.com/p/skia/source/detail?r=8992

[epoger, 2013-04-24 17:07:07]

https://codereview.chromium.org/14054012/diff/1/gm/gmmain.cpp
File gm/gmmain.cpp (right):

https://codereview.chromium.org/14054012/diff/1/gm/gmmain.cpp#newcode41
gm/gmmain.cpp:41: #define EPOGER_TEST
patchset 1 adds timing reports, and disables --writePath and --writePicturePath
options (once we switch the bots over to using checksums, we won't write out all
the generated image files anymore)

[epoger, 2013-04-24 17:30:00]

https://codereview.chromium.org/14054012/diff/3001/src/utils/SkBitmapHasher.h
File src/utils/SkBitmapHasher.h (right):

https://codereview.chromium.org/14054012/diff/3001/src/utils/SkBitmapHasher.h...
src/utils/SkBitmapHasher.h:14: #define BITMAPHASHER_USES_TRUNCATED_MD5
patchset 2 changes SkBitmapHasher to use a truncated (64-bit) MD5 instead of
CityHash, guarded by this #define.

https://codereview.chromium.org/14054012/diff/3001/tests/BitmapHasherTest.cpp
File tests/BitmapHasherTest.cpp (right):

https://codereview.chromium.org/14054012/diff/3001/tests/BitmapHasherTest.cpp...
tests/BitmapHasherTest.cpp:45: #ifdef BITMAPHASHER_USES_TRUNCATED_MD5
Unit tests have been updated to succeed whether we use MD5 or not, but the gm
self-tests fail if BITMAPHASHER_USES_TRUNCATED_MD5 is defined.

[epoger, 2013-04-24 17:36:57]

https://codereview.chromium.org/14054012/diff/7001/gm/gmmain.cpp
File gm/gmmain.cpp (right):

https://codereview.chromium.org/14054012/diff/7001/gm/gmmain.cpp#newcode1995
gm/gmmain.cpp:1995: printf("EPOGER_TEST timings with %s algorithm: %d msecs
before summary output, %d msecs total\n",
patchset 3 only adds a report of which hashing algorithm was used.

[epoger, 2013-04-24 17:46:20]

Here are the timing results from running out/Debug/gm on my Ubiquity instance at
patchset 3, with BITMAPHASHER_USES_TRUNCATED_MD5 turned on and off:

EPOGER_TEST timings with MD5 algorithm: 142603 msecs before summary output,
142640 msecs total

EPOGER_TEST timings with CityHash algorithm: 96244 msecs before summary output,
96281 msecs total

In this case, MD5 took 48% longer than CityHash.  (142603 msec = 2 min 22 sec,
vs. 96244 msec = 1 min 36 sec)

[epoger, 2013-04-24 18:13:52]

Hey Ben- I'm not actually looking for a code review here, but I wanted you to
witness this new attempt at assessing performance of MD5 vs CityHash.

Two important distinctions from the tests I ran previously in
https://code.google.com/p/skia/issues/detail?id=1257
('deciding between CityHash, MD5, and SHA1 for image hash algorithm')...

1. In this test, I turned off writing actual images to local disk, because
that's how GM will run once we have switched over to checksums

2. I have built upon your changes in
https://code.google.com/p/skia/source/detail?r=8831 ('ARGB image encoder for
checksums.')

I have sent off trybots with BITMAPHASHER_USES_TRUNCATED_MD5 turned both on and
off ... I will update this codereview once I get results.

[bungeman-skia, 2013-04-24 19:33:17]

Some random thoughts.

1. Is 64 bits enough? We're somewhat avoiding the birthday problem here (I
think) because we're asking (for each existing image) "does this other image
have the same hash as this one?" As a result, we expect to miss a change every
2^bits (instead of every 2^(bits/2) as with the birthday problem) changes. Also,
we don't have someone trying to craft images which collide, so we don't need to
increase the bits simply to increase the search space.

On the other hand, if we want to use the hash of the image as its name (without
an intervening look-up) for storage, we do have a birthday problem and will need
more than 64 bits to be comfortable.

2. The above assumes a perfect distribution. MD5 has good distribution, but I
know nothing of CityHash's distribution. MurmurHash2 (on which CityHash is
based) has pretty ok distribution, but I haven't seen anything on CityHash.

Most of the reticence toward CityHash is that we need very low expectation of
false negatives (when an image changes but ends up with the same hash). Also if
we want to store images based on hash we're going to need more bits.

We already know that CityHash is ~10x faster than MD5. If CityHash cannot
fulfill our needs then we can't really use it. If it can, then use it. If the
answer is that we don't know if it can or not, I'd say go with MD5 for now (as
just going with any hash based system is going to speed things up), and set
things up so we can switch later (should only be difficult if we're using the
hash to name images in storage).

[epoger, 2013-04-24 23:32:49]

On 2013/04/24 19:33:17, bungeman1 wrote:
> Some random thoughts.

Thanks for writing down those thoughts, Ben; they're quite useful!  I really
appreciate your help in looking out for potential problems down the road.

> 1. Is 64 bits enough? We're somewhat avoiding the birthday problem here (I
> think) because we're asking (for each existing image) "does this other image
> have the same hash as this one?" As a result, we expect to miss a change every
> 2^bits (instead of every 2^(bits/2) as with the birthday problem) changes.
Also,
> we don't have someone trying to craft images which collide, so we don't need
to
> increase the bits simply to increase the search space.

First of all: my intent had been to compare and store images named *exclusively*
by their hash digest.  ("Oh, a test resulted in an image with digest 0x1234 ? 
Then I will assume it is identical to any other image I have ever seen with
digest 0x1234 , which will be stored at http://$ROOT/gm/0x1234.png .")

But maybe we can sort of avoid the "birthday problem" by indexing by a
combination of test name and hash digest.  ("Oh, the blurrect test resulted in
an image with digest 0x1234 ?  Then I will assume it is identical to any other
blurrect test result I have ever seen with digest 0x1234 , which will be stored
at http://$ROOT/gm/blurrect/0x1234.png.")  Adding the test name to the index is
cheap, so this seems like a good win.

I don't know how to prove this mathematically, but I believe 2^64 hash values
per test should be more than adequate to avoid collisions (assuming a reasonable
hash distribution).  And in the event of collision, it would be a bit painful
but not catastrophic.  Maybe an hour of work to resolve it, manually replacing
the image at http://root/blurrect/0x1234.png.

> We already know that CityHash is ~10x faster than MD5. If CityHash cannot
> fulfill our needs then we can't really use it. If it can, then use it. If the
> answer is that we don't know if it can or not, I'd say go with MD5 for now (as
> just going with any hash based system is going to speed things up), and set
> things up so we can switch later (should only be difficult if we're using the
> hash to name images in storage).

Indeed I am planning to use the hash to name images in storage.  What's the
alternative?  I guess a lookup table that says, "hash digest 0x1234 refers to
image http://$ROOT/gm/RanDomSTring.png"?  I'm not sure how that would help,
though, because modifying the paths in that table would be equivalent to
renaming the images in storage.

Anyway, as noted above, I believe image paths like
http://$ROOT/gm/blurrect/0x1234.png should be "unique enough" in practice. 
Please let me know what you think.

[epoger, 2013-04-24 23:47:54]

Here are the timing results of truncated-MD5 vs CityHash from the bots.  On our
slowest platform, truncated-MD5 was 30% slower than CityHash: 18 minutes to run
GenerateGMs, instead of 14 minutes.



As of ~r8839 in the waterfall bots (using CityHash, writing out actual images,
no timing printfs):

http://108.170.217.252:10117/builders/Skia_Linux_NoGPU_Debug_32/builds/1426
GenerateGMs took 1:22 to run

http://108.170.217.252:10117/builders/Skia_NexusS_4-1_Float_Debug_32/builds/1146
GenerateGMs took 18:39 to run



Trying patchset 3 with BITMAPHASHER_USES_TRUNCATED_MD5 turned off (same as
above, but not writing out actual images):

http://108.170.217.252:10117/builders/Skia_Linux_NoGPU_Debug_32_Trybot/builds...
GenerateGMs took 1:07 to run
EPOGER_TEST timings with CityHash algorithm: 65603 msecs before summary output,
65619 msecs total

http://108.170.217.252:10117/builders/Skia_NexusS_4-1_Float_Debug_32_Trybot/b...
GenerateGMs took 14:12 to run
EPOGER_TEST timings with CityHash algorithm: 840711 msecs before summary output,
841923 msecs total



Trying patchset 3 with BITMAPHASHER_USES_TRUNCATED_MD5 turned on (same as above,
but using MD5 instead of CityHash):

http://108.170.217.252:10117/builders/Skia_Linux_NoGPU_Debug_32_Trybot/builds...
GenerateGMs took 1:42 to run  (35 seconds longer = 52% longer than CityHash)
EPOGER_TEST timings with MD5 algorithm: 101350 msecs before summary output,
101367 msecs total

http://108.170.217.252:10117/builders/Skia_NexusS_4-1_Float_Debug_32_Trybot/b...
GenerateGMs took 18:32 to run  (4:20 longer = 30% longer than CityHash)
EPOGER_TEST timings with MD5 algorithm: 1101867 msecs before summary output,
1103081 msecs total

[bungeman-skia, 2013-04-25 15:39:54]

On 2013/04/24 23:32:49, epoger wrote:
> On 2013/04/24 19:33:17, bungeman1 wrote:
> > Some random thoughts.
> 
> Thanks for writing down those thoughts, Ben; they're quite useful!  I really
> appreciate your help in looking out for potential problems down the road.
> 
> > 1. Is 64 bits enough? We're somewhat avoiding the birthday problem here (I
> > think) because we're asking (for each existing image) "does this other image
> > have the same hash as this one?" As a result, we expect to miss a change
every
> > 2^bits (instead of every 2^(bits/2) as with the birthday problem) changes.
> Also,
> > we don't have someone trying to craft images which collide, so we don't need
> to
> > increase the bits simply to increase the search space.
> 
> First of all: my intent had been to compare and store images named
*exclusively*
> by their hash digest.  ("Oh, a test resulted in an image with digest 0x1234 ? 
> Then I will assume it is identical to any other image I have ever seen with
> digest 0x1234 , which will be stored at http://%24ROOT/gm/0x1234.png .")
> 
> But maybe we can sort of avoid the "birthday problem" by indexing by a
> combination of test name and hash digest.  ("Oh, the blurrect test resulted in
> an image with digest 0x1234 ?  Then I will assume it is identical to any other
> blurrect test result I have ever seen with digest 0x1234 , which will be
stored
> at http://%24ROOT/gm/blurrect/0x1234.png.%22)  Adding the test name to the
index is
> cheap, so this seems like a good win.
> 
> I don't know how to prove this mathematically, but I believe 2^64 hash values
> per test should be more than adequate to avoid collisions (assuming a
reasonable
> hash distribution).  And in the event of collision, it would be a bit painful
> but not catastrophic.  Maybe an hour of work to resolve it, manually replacing
> the image at http://root/blurrect/0x1234.png.
> 

First a rough idea of the worst case number of images. Let's say Blink/WebKit
scale and we have 10^4 image tests, 10^1 configs (assume they don't overlap for
the moment), and 10^2 back revisions of each. This adds up to 10^7 total images
(admittedly worst case). Assume some sharing to bring this down to ~10^6. (At
50KB each this is ~50GB worth of pngs.)

There are (at least) three ways of looking at this. In the following 'N' is the
number of buckets and 'n' is the number of items.

First, the probability of a having seen a collision reaches 50% at approximately
n = (1/2) + sqrt((1/4) - 2*N*ln(0.5)) . For N=2^64 this is n=~5*10^9 so we'd
have a 50% probability of seeing a collision at around five billion. This at
least gives a rough sense of scale.

Second, the expected number of collisions (see
http://math.stackexchange.com/questions/35791/birthday-problem-expected-numbe...
) is n * (1 - (1 - (1/N))^(n-1)) . This means that for N=2^64 and n=10^6 we
expect ~5*10^-8 collisions. Note that if we change n=10^9 we expect 0.05
collisions. At n=5*10^9 we expect ~1.4 collisions.

Third, the probability of having some collision is approximately p = 1 -
e^((-n^2)/(2*N)) . For N=2^64 and n=10^9 this gives p~=0.000002%. For n=10^9
this goes to p~=2.6%. At n=5*10^9 this rises to the expected 50%.

So if we expect to have up to a million total images 64 bits may be enough, if
the hash is perfect. As you get toward the billion mark 64 bits isn't enough to
expect uniqueness. So 64 bits may be good enough for what we're doing
(especially if we use prefixed names and age out old images). I'm more concerned
about the 'perfect' part with CityHash, as I know little of its distribution.
The nice thing about 128 bits is that all of these probabilities get really,
really small. (The analysis goes from "can we get away with this" to "it ain't
gonna happen".)

> > We already know that CityHash is ~10x faster than MD5. If CityHash cannot
> > fulfill our needs then we can't really use it. If it can, then use it. If
the
> > answer is that we don't know if it can or not, I'd say go with MD5 for now
(as
> > just going with any hash based system is going to speed things up), and set
> > things up so we can switch later (should only be difficult if we're using
the
> > hash to name images in storage).
> 
> Indeed I am planning to use the hash to name images in storage.  What's the
> alternative?  I guess a lookup table that says, "hash digest 0x1234 refers to
> image http://%24ROOT/gm/RanDomSTring.png%22?  I'm not sure how that would
help,
> though, because modifying the paths in that table would be equivalent to
> renaming the images in storage.
> 
> Anyway, as noted above, I believe image paths like
> http://%24ROOT/gm/blurrect/0x1234.png should be "unique enough" in practice. 
> Please let me know what you think.

[bungeman-skia, 2013-04-25 15:42:47]

> e^((-n^2)/(2*N)) . For N=2^64 and n=10^9 this gives p~=0.000002%. For n=10^9

The 'n=10^9' here should read 'n=10^6'.

[epoger, 2013-04-25 16:11:37]

Wow, thanks for the math.

On 2013/04/25 15:39:54, bungeman1 wrote:
> Third, the probability of having some collision is approximately p = 1 -
> e^((-n^2)/(2*N)) . For N=2^64 and n=10^6 this gives p~=0.000002%. For n=10^9
> this goes to p~=2.6%. At n=5*10^9 this rises to the expected 50%.

If we index our results by test name + hash digest, then for each test, n = 10^3
(10^1 configs and 10^2 back revisions of each).  Assuming a perfect hash
(assuming!), that gives p~=0.000000000002% *for each test*.

If we ran 10^4 different tests, the chances of ANY of them colliding would be
0.000000000002% * 10^4 = 0.00000002% 

My conclusion from this: *assuming* a perfect hash, 64 bits is more than
adequate, especially given the relatively low cost of collision (one
spectacularly pathological image error might go unnoticed).

At that point, we are left to wonder, is our trust in MD5 sufficiently greater
than that of CityHash to warrant spending the extra time to run MD5?  My
conclusion is no, but I'll leave it to the discussion in
https://code.google.com/p/skia/issues/detail?id=1257 ('deciding between
CityHash, MD5, and SHA1 for image hash algorithm').  Basically, Mike's the
boss... if he wants the builds to run slower to allow for MD5, that's his call!

[epoger, 2013-05-03 14:49:25]

Ben- it's ready for review at patchset 6.

https://codereview.chromium.org/14054012/diff/25001/gm/tests/outputs/compared...
File
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt
(right):

https://codereview.chromium.org/14054012/diff/25001/gm/tests/outputs/compared...
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt:5:
"bitmap-cityhash" : 12927999507540085554
Patchset 6 updates the gm self-test expected results to use the new algorithm.

[bungeman-skia, 2013-05-03 15:21:00]

https://codereview.chromium.org/14054012/diff/25001/src/utils/SkBitmapHasher.cpp
File src/utils/SkBitmapHasher.cpp (right):

https://codereview.chromium.org/14054012/diff/25001/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:57: *result = *((SkHashDigest *)&digest);
While I did write this, I wrote it more as an easy means of testing timings, not
really thinking about correctness. I'm somewhat uncomfortable with the fact that
the value of result will be endian dependent like this. If we know that
SkHashDigest is uint64_t then I would prefer something like

*result = (digest.data[0] << (0*8)) +
          (digest.data[1] << (1*8)) +
          (digest.data[2] << (2*8)) +
          (digest.data[3] << (3*8)) +
          (digest.data[4] << (4*8)) +
          (digest.data[5] << (5*8)) +
          (digest.data[6] << (6*8)) +
          (digest.data[7] << (7*8));

So that we're always looking at digest.data as if it were little endian. This
way the same image will have the same 'result' on big, little, and middle-endian
machines.

[epoger, 2013-05-03 16:28:00]

https://codereview.chromium.org/14054012/diff/25001/src/utils/SkBitmapHasher.cpp
File src/utils/SkBitmapHasher.cpp (right):

https://codereview.chromium.org/14054012/diff/25001/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:57: *result = *((SkHashDigest *)&digest);
On 2013/05/03 15:21:00, bungeman1 wrote:
> While I did write this, I wrote it more as an easy means of testing timings,
not
> really thinking about correctness. I'm somewhat uncomfortable with the fact
that
> the value of result will be endian dependent like this. If we know that
> SkHashDigest is uint64_t then I would prefer something like
> 
> *result = (digest.data[0] << (0*8)) +
>           (digest.data[1] << (1*8)) +
>           (digest.data[2] << (2*8)) +
>           (digest.data[3] << (3*8)) +
>           (digest.data[4] << (4*8)) +
>           (digest.data[5] << (5*8)) +
>           (digest.data[6] << (6*8)) +
>           (digest.data[7] << (7*8));
> 
> So that we're always looking at digest.data as if it were little endian. This
> way the same image will have the same 'result' on big, little, and
middle-endian
> machines.

Good idea, thanks for the catch.  I implemented it a bit differently, in the
hopes of code reuse later. Tell me what you think.

https://codereview.chromium.org/14054012/diff/23005/include/core/SkEndian.h
File include/core/SkEndian.h (right):

https://codereview.chromium.org/14054012/diff/23005/include/core/SkEndian.h#n...
include/core/SkEndian.h:83: static inline uint64_t SkEndianSwap64(uint64_t
value) {
Added 64-bit versions of the various converters...

[bungeman-skia, 2013-05-03 17:16:22]

The hash changes lgtm, adding reed to review the endian change.

[reed1, 2013-05-03 17:22:18]

seems good. can we write a unittest for the endian swappers? Perhaps
outside/after this CL...

[epoger, 2013-05-03 17:35:45]

Committed patchset #7 manually as r8992 (presubmit successful).

[epoger, 2013-05-03 17:36:39]

On 2013/05/03 17:22:18, reed1 wrote:
> seems good. can we write a unittest for the endian swappers? Perhaps
> outside/after this CL...

Filed https://code.google.com/p/skia/issues/detail?id=1280 ('create unittests
for SkEndian.h')... we don't even have unittests for any of the (existing)
endian swappers.