diff options
author | mtklein <mtklein@google.com> | 2015-11-13 07:07:47 -0800 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2015-11-13 07:07:47 -0800 |
commit | 0274efbd3d2c3b2fba2b4212347159a20050038d (patch) | |
tree | 938361c44fba7b2f2b2f8bde112833df571258b0 | |
parent | 64c4728c70001ed074fecf5c4e083781987b12e9 (diff) |
Revert of Switch uses of SkChecksum::Compute to Murmur3. (patchset #2 id:20001 of https://codereview.chromium.org/1436973003/ )
Reason for revert:
I would not have expected this to change any images.
Looks like it's changed both MSAA and non-MSAA GMs:
1d024a3c909ae5cefa5e8b339e2b52dc73ee85ac&unt=true&head=true&query=source_type%3Dgm">https://gold.skia.org/search2?blame=1d024a3c909ae5cefa5e8b339e2b52dc73ee85ac&unt=true&head=true&query=source_type%3Dgm
Original issue's description:
> Switch uses of SkChecksum::Compute to Murmur3.
>
> SkChecksum::Compute is a very, very poorly distributed hash function.
> This replaces all remaining uses with Murmur3.
>
> The only interesting stuff is in src/gpu.
>
> BUG=skia:
>
> Committed: https://skia.googlesource.com/skia/+/1d024a3c909ae5cefa5e8b339e2b52dc73ee85ac
TBR=bsalomon@google.com,mtklein@chromium.org
NOPRESUBMIT=true
NOTREECHECKS=true
NOTRY=true
BUG=skia:
Review URL: https://codereview.chromium.org/1445523003
-rw-r--r-- | bench/ChecksumBench.cpp | 9 | ||||
-rw-r--r-- | include/private/SkChecksum.h | 89 | ||||
-rw-r--r-- | src/core/SkPictureFlat.h | 4 | ||||
-rw-r--r-- | src/gpu/GrProgramDesc.h | 3 | ||||
-rw-r--r-- | src/gpu/GrResourceCache.cpp | 8 | ||||
-rw-r--r-- | tests/ChecksumTest.cpp | 2 |
6 files changed, 107 insertions, 8 deletions
diff --git a/bench/ChecksumBench.cpp b/bench/ChecksumBench.cpp index 92e7da662f..a2c282435e 100644 --- a/bench/ChecksumBench.cpp +++ b/bench/ChecksumBench.cpp @@ -13,6 +13,7 @@ #include "SkTemplates.h" enum ChecksumType { + kChecksum_ChecksumType, kMD5_ChecksumType, kSHA1_ChecksumType, kMurmur3_ChecksumType, @@ -41,6 +42,7 @@ public: protected: const char* onGetName() override { switch (fType) { + case kChecksum_ChecksumType: return "compute_checksum"; case kMD5_ChecksumType: return "compute_md5"; case kSHA1_ChecksumType: return "compute_sha1"; case kMurmur3_ChecksumType: return "compute_murmur3"; @@ -51,6 +53,12 @@ protected: void onDraw(int loops, SkCanvas*) override { switch (fType) { + case kChecksum_ChecksumType: { + for (int i = 0; i < loops; i++) { + volatile uint32_t result = SkChecksum::Compute(fData, sizeof(fData)); + sk_ignore_unused_variable(result); + } + } break; case kMD5_ChecksumType: { for (int i = 0; i < loops; i++) { SkMD5 md5; @@ -83,6 +91,7 @@ private: /////////////////////////////////////////////////////////////////////////////// +DEF_BENCH( return new ComputeChecksumBench(kChecksum_ChecksumType); ) DEF_BENCH( return new ComputeChecksumBench(kMD5_ChecksumType); ) DEF_BENCH( return new ComputeChecksumBench(kSHA1_ChecksumType); ) DEF_BENCH( return new ComputeChecksumBench(kMurmur3_ChecksumType); ) diff --git a/include/private/SkChecksum.h b/include/private/SkChecksum.h index 6289a444ae..4526416fc1 100644 --- a/include/private/SkChecksum.h +++ b/include/private/SkChecksum.h @@ -12,7 +12,31 @@ #include "SkTLogic.h" #include "SkTypes.h" +/** + * Computes a 32bit checksum from a blob of 32bit aligned data. This is meant + * to be very very fast, as it is used internally by the font cache, in + * conjuction with the entire raw key. This algorithm does not generate + * unique values as well as others (e.g. MD5) but it performs much faster. + * Skia's use cases can survive non-unique values (since the entire key is + * always available). Clients should only be used in circumstances where speed + * over uniqueness is at a premium. + */ class SkChecksum : SkNoncopyable { +private: + /* + * Our Rotate and Mash helpers are meant to automatically do the right + * thing depending if sizeof(uintptr_t) is 4 or 8. + */ + enum { + ROTR = 17, + ROTL = sizeof(uintptr_t) * 8 - ROTR, + HALFBITS = sizeof(uintptr_t) * 4 + }; + + static inline uintptr_t Mash(uintptr_t total, uintptr_t value) { + return ((total >> ROTR) | (total << ROTL)) ^ value; + } + public: /** * uint32_t -> uint32_t hash, useful for when you're about to trucate this hash but you @@ -44,6 +68,7 @@ public: /** * Calculate 32-bit Murmur hash (murmur3). + * This should take 2-3x longer than SkChecksum::Compute, but is a considerably better hash. * See en.wikipedia.org/wiki/MurmurHash. * * @param data Memory address of the data block to be processed. @@ -52,6 +77,70 @@ public: * @return hash result */ static uint32_t Murmur3(const void* data, size_t bytes, uint32_t seed=0); + + /** + * Compute a 32-bit checksum for a given data block + * + * WARNING: this algorithm is tuned for efficiency, not backward/forward + * compatibility. It may change at any time, so a checksum generated with + * one version of the Skia code may not match a checksum generated with + * a different version of the Skia code. + * + * @param data Memory address of the data block to be processed. Must be + * 32-bit aligned. + * @param size Size of the data block in bytes. Must be a multiple of 4. + * @return checksum result + */ + static uint32_t Compute(const uint32_t* data, size_t size) { + // Use may_alias to remind the compiler we're intentionally violating strict aliasing, + // and so not to apply strict-aliasing-based optimizations. + typedef uint32_t SK_ATTRIBUTE(may_alias) aliased_uint32_t; + const aliased_uint32_t* safe_data = (const aliased_uint32_t*)data; + + SkASSERT(SkIsAlign4(size)); + + /* + * We want to let the compiler use 32bit or 64bit addressing and math + * so we use uintptr_t as our magic type. This makes the code a little + * more obscure (we can't hard-code 32 or 64 anywhere, but have to use + * sizeof()). + */ + uintptr_t result = 0; + const uintptr_t* ptr = reinterpret_cast<const uintptr_t*>(safe_data); + + /* + * count the number of quad element chunks. This takes into account + * if we're on a 32bit or 64bit arch, since we use sizeof(uintptr_t) + * to compute how much to shift-down the size. + */ + size_t n4 = size / (sizeof(uintptr_t) << 2); + for (size_t i = 0; i < n4; ++i) { + result = Mash(result, *ptr++); + result = Mash(result, *ptr++); + result = Mash(result, *ptr++); + result = Mash(result, *ptr++); + } + size &= ((sizeof(uintptr_t) << 2) - 1); + + safe_data = reinterpret_cast<const aliased_uint32_t*>(ptr); + const aliased_uint32_t* stop = safe_data + (size >> 2); + while (safe_data < stop) { + result = Mash(result, *safe_data++); + } + + /* + * smash us down to 32bits if we were 64. Note that when uintptr_t is + * 32bits, this code-path should go away, but I still got a warning + * when I wrote + * result ^= result >> 32; + * since >>32 is undefined for 32bit ints, hence the wacky HALFBITS + * define. + */ + if (8 == sizeof(result)) { + result ^= result >> HALFBITS; + } + return static_cast<uint32_t>(result); + } }; // SkGoodHash should usually be your first choice in hashing data. diff --git a/src/core/SkPictureFlat.h b/src/core/SkPictureFlat.h index 8befca0538..98a43ecb57 100644 --- a/src/core/SkPictureFlat.h +++ b/src/core/SkPictureFlat.h @@ -179,7 +179,7 @@ class SkFlatData; class SkFlatController : public SkRefCnt { public: - + SkFlatController(uint32_t writeBufferFlags = 0); virtual ~SkFlatController(); @@ -357,7 +357,7 @@ private: fIndex = index; fFlatSize = size; fTopBot[0] = SK_ScalarNaN; // Mark as unwritten. - fChecksum = SkChecksum::Murmur3(this->data(), size); + fChecksum = SkChecksum::Compute((uint32_t*)this->data(), size); } int fIndex; diff --git a/src/gpu/GrProgramDesc.h b/src/gpu/GrProgramDesc.h index 9641195354..05b52cc7cd 100644 --- a/src/gpu/GrProgramDesc.h +++ b/src/gpu/GrProgramDesc.h @@ -107,7 +107,8 @@ protected: *(this->atOffset<uint32_t, GrProgramDesc::kLengthOffset>()) = SkToU32(keyLength); uint32_t* checksum = this->atOffset<uint32_t, GrProgramDesc::kChecksumOffset>(); - *checksum = SkChecksum::Murmur3(fKey.begin(), keyLength); + *checksum = 0; + *checksum = SkChecksum::Compute(reinterpret_cast<uint32_t*>(fKey.begin()), keyLength); } // The key, stored in fKey, is composed of four parts: diff --git a/src/gpu/GrResourceCache.cpp b/src/gpu/GrResourceCache.cpp index 4a0c9b2b36..cb6bcf75fd 100644 --- a/src/gpu/GrResourceCache.cpp +++ b/src/gpu/GrResourceCache.cpp @@ -42,7 +42,7 @@ GrUniqueKey::Domain GrUniqueKey::GenerateDomain() { } uint32_t GrResourceKeyHash(const uint32_t* data, size_t size) { - return SkChecksum::Murmur3(data, size); + return SkChecksum::Compute(data, size); } ////////////////////////////////////////////////////////////////////////////// @@ -564,7 +564,7 @@ uint32_t GrResourceCache::getNextTimestamp() { int currP = 0; int currNP = 0; while (currP < sortedPurgeableResources.count() && - currNP < fNonpurgeableResources.count()) { + currNP < fNonpurgeableResources.count()) { uint32_t tsP = sortedPurgeableResources[currP]->cacheAccess().timestamp(); uint32_t tsNP = fNonpurgeableResources[currNP]->cacheAccess().timestamp(); SkASSERT(tsP != tsNP); @@ -596,10 +596,10 @@ uint32_t GrResourceCache::getNextTimestamp() { // count should be the next timestamp we return. SkASSERT(fTimestamp == SkToU32(count)); - + // The historical timestamps of flushes are now invalid. this->resetFlushTimestamps(); - } + } } return fTimestamp++; } diff --git a/tests/ChecksumTest.cpp b/tests/ChecksumTest.cpp index cf9d65c59e..c095a5ac11 100644 --- a/tests/ChecksumTest.cpp +++ b/tests/ChecksumTest.cpp @@ -18,7 +18,7 @@ static uint32_t murmur_noseed(const uint32_t* d, size_t l) { return SkChecksum:: DEF_TEST(Checksum, r) { // Algorithms to test. They're currently all uint32_t(const uint32_t*, size_t). typedef uint32_t(*algorithmProc)(const uint32_t*, size_t); - const algorithmProc kAlgorithms[] = { &murmur_noseed }; + const algorithmProc kAlgorithms[] = { &SkChecksum::Compute, &murmur_noseed }; // Put 128 random bytes into two identical buffers. Any multiple of 4 will do. const size_t kBytes = SkAlign4(128); |