Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1216983003:
Move the GlyphCache to use a hash table instead of doing its own ad-hoc (Closed)
DescriptionChange the GlyphCache to use a hash table instead of doing its own ad-hoc
hashing. This change appears to be performance neutral.
BUG=skia:
Committed: https://skia.googlesource.com/skia/+/c71239b9ff7d8c19dc03cb6c9081e7dc4e0947d2
Patch Set 1 #
Total comments: 10
Patch Set 2 : updates for comments #Patch Set 3 : Fix one last type #
Total comments: 2
Patch Set 4 : Use SkTHashTable in SkGlyphCache #Patch Set 5 : address reeds comments #
Total comments: 9
Patch Set 6 : Address mtklein's comments #
Messages
Total messages: 27 (8 generated)
herb@google.com changed reviewers: + mtklein@google.com
The CQ bit was checked by herb@google.com to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1216983003/1
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
reed@google.com changed reviewers: + reed@google.com
clean looking? slightly surprised that we're pref neutral. Do we have useful micro benches here? what is ram diff? https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h File src/core/SkGlyphCache.h (right): https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:26: static int32_t GetKey(const SkGlyph& glyph) { nit: do we really need signed -vs- unsigned 32 ints?
sorry, "clean looking" was an affirmative, not a question.
https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h File src/core/SkGlyphCache.h (right): https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:24: class GlyphTrait { Might want to call this SkGlyphHashTraits, or nest it in SkGlyphCache as SkGlyphCache::GlyphHashTraits? https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:26: static int32_t GetKey(const SkGlyph& glyph) { On 2015/06/29 20:59:48, reed1 wrote: > nit: do we really need signed -vs- unsigned 32 ints? +1, particularly because fID is an uint32_t (and is always passed as one). I'd be pretty pro SkGlyphID typedef. https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:197: uint32_t fCombinedID; Boy this is getting confusing. Can we name these something like fUnicharAndSubpixel fGlyphID ? Is the first an ID? Is the second any more combined than GlyphIDs are normally? https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:246: //SkTDArray<SkGlyph> fGlyphArray; Let's kill off the dead code and update the comments everywhere (e.g. the comments below at 251-252 too) ?
def tdarray_alloc(n):
count = 0
alloc = 0
for i in range(n):
count += 1
if count >= alloc:
alloc = count + 4
alloc += alloc / 4
return alloc
def thashtable_alloc(n):
count = 0
alloc = 0
for i in range(n):
if 4*count >= 3*alloc:
alloc = 4 if alloc == 0 else alloc*2
count += 1
return alloc
def old_memory(n):
return 2*(256) + tdarray_alloc(n)*40 + 16
def new_memory(n):
return thashtable_alloc(n)*40 + 24
for i in range(40):
print i, old_memory(i), new_memory(i)
-->
hash is more memory-efficient for strikes with 0-24 glyphs, after which the
existing array is more efficient.
I tried making a separate opaque type for the combined glyphID and Position using enum class. This made a much bigger change that kind of flowed everywhere. I think I should do make the specific type in a separate CL. https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h File src/core/SkGlyphCache.h (right): https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:24: class GlyphTrait { On 2015/06/30 16:20:47, mtklein wrote: > Might want to call this SkGlyphHashTraits, or nest it in SkGlyphCache as > SkGlyphCache::GlyphHashTraits? Done. https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:26: static int32_t GetKey(const SkGlyph& glyph) { On 2015/06/29 20:59:48, reed1 wrote: > nit: do we really need signed -vs- unsigned 32 ints? Done. https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:26: static int32_t GetKey(const SkGlyph& glyph) { On 2015/06/29 20:59:48, reed1 wrote: > nit: do we really need signed -vs- unsigned 32 ints? Done. https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:197: uint32_t fCombinedID; On 2015/06/30 16:20:47, mtklein wrote: > Boy this is getting confusing. Can we name these something like > > fUnicharAndSubpixel > fGlyphID > > ? > > Is the first an ID? Is the second any more combined than GlyphIDs are normally? This is really a glyphID and subpixel positioning. Done. https://codereview.chromium.org/1216983003/diff/1/src/core/SkGlyphCache.h#new... src/core/SkGlyphCache.h:246: //SkTDArray<SkGlyph> fGlyphArray; On 2015/06/30 16:20:47, mtklein wrote: > Let's kill off the dead code and update the comments everywhere (e.g. the > comments below at 251-252 too) ? Done.
Slightly hard to follow the CL, as we it doing a bit more than just using hashtable (and that only for glyphID case). I wonder if we created some typedefs... typedef uint32_t PackedGlyphID; // glyph-index + subpixel-pos typedef uint32_t PackedUnicharID; // unichar + subpixel-pos Maybe using those in places would help document things better. https://codereview.chromium.org/1216983003/diff/40001/src/core/SkGlyphCache.cpp File src/core/SkGlyphCache.cpp (right): https://codereview.chromium.org/1216983003/diff/40001/src/core/SkGlyphCache.c... src/core/SkGlyphCache.cpp:65: fGlyphMap.foreach([](SkGlyph* g) { if (g->fPath != NULL) { SkDELETE(g->fPath); } } ); perhaps we can add a LF or two, for readability?
Added typedefs, and addressed other comments. There is a two pixel difference in the dm: gpu/gm/dstreadshuffle Is this a problematic dm? The performance seems to be within the noise envelope, but that envelope is pretty big. The discussion of performance is on a separate thread. PTAL https://codereview.chromium.org/1216983003/diff/40001/src/core/SkGlyphCache.cpp File src/core/SkGlyphCache.cpp (right): https://codereview.chromium.org/1216983003/diff/40001/src/core/SkGlyphCache.c... src/core/SkGlyphCache.cpp:65: fGlyphMap.foreach([](SkGlyph* g) { if (g->fPath != NULL) { SkDELETE(g->fPath); } } ); On 2015/07/06 17:29:35, reed1 wrote: > perhaps we can add a LF or two, for readability? Done.
> There is a two pixel difference in the dm: > gpu/gm/dstreadshuffle > > Is this a problematic dm? Yes.
The CQ bit was checked by herb@google.com
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1216983003/80001
Note for Reviewers: The CQ is waiting for an approval. If you believe that the CL is not ready yet, or if you would like to L-G-T-M with comments then please uncheck the CQ checkbox. Waiting for LGTM from valid reviewer(s) till 2015-07-21 05:23 UTC
The CQ bit was unchecked by commit-bot@chromium.org
No LGTM from a valid reviewer yet. Please ask for an LGTM from a full Skia committer from https://skia.googlesource.com/skia/+/master/CQ_COMMITTERS
lgtm https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h File src/core/SkGlyph.h (right): https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h#newc... src/core/SkGlyph.h:118: class GlyphHashTraits { Seems fine, but now that you're scoped here, HashTraits is just as clear, maybe clearer. https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h#newc... src/core/SkGlyph.h:124: return SkChecksum::CheapMix(glyphId); If we're seeing a lot of time spent looking through the hash table, that may also indicate we have a poor hash function. I am skeptical of the quality of CheapMix(). Might try Mix(). https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.cpp File src/core/SkGlyphCache.cpp (right): https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.c... src/core/SkGlyphCache.cpp:60: if (g->fPath != NULL) { Just FYI, SkDELETE does a null check, so this should be the same fGlyphMap.foreach([](SkGlyph* g) { SkDELETE(g->fPath); }); https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.h File src/core/SkGlyphCache.h (right): https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.h... src/core/SkGlyphCache.h:220: SkGlyphCache *fNext, *fPrev; I think I'd generally prefer SkGlyphCache* fNext; SkGlyphCache* fPrev; SkDescriptor* fDesc; SkScalerContext* fScalerContext; SkPaint::FontMetrics fFontMetrics; I don't mind Type* const, but it's rarely interesting that the pointer's not going to change, and it's easily confused with the more important const Type*.
https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h File src/core/SkGlyph.h (right): https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h#newc... src/core/SkGlyph.h:118: class GlyphHashTraits { On 2015/07/21 19:35:52, mtklein wrote: > Seems fine, but now that you're scoped here, HashTraits is just as clear, maybe > clearer. Done. https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h#newc... src/core/SkGlyph.h:124: return SkChecksum::CheapMix(glyphId); On 2015/07/21 19:35:52, mtklein wrote: > If we're seeing a lot of time spent looking through the hash table, that may > also indicate we have a poor hash function. I am skeptical of the quality of > CheapMix(). Might try Mix(). I think I'm going to work on tuning the hashing table in another cl. https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.cpp File src/core/SkGlyphCache.cpp (right): https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.c... src/core/SkGlyphCache.cpp:60: if (g->fPath != NULL) { On 2015/07/21 19:35:52, mtklein wrote: > Just FYI, SkDELETE does a null check, so this should be the same > fGlyphMap.foreach([](SkGlyph* g) { > SkDELETE(g->fPath); > }); Done. https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.h File src/core/SkGlyphCache.h (right): https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyphCache.h... src/core/SkGlyphCache.h:220: SkGlyphCache *fNext, *fPrev; On 2015/07/21 19:35:52, mtklein wrote: > I think I'd generally prefer > > SkGlyphCache* fNext; > SkGlyphCache* fPrev; > SkDescriptor* fDesc; > SkScalerContext* fScalerContext; > SkPaint::FontMetrics fFontMetrics; > > I don't mind Type* const, but it's rarely interesting that the pointer's not > going to change, and it's easily confused with the more important const Type*. T * const is nicer in multithreaded cases, and it documents the invariant that this does not change.
The CQ bit was checked by herb@google.com
The patchset sent to the CQ was uploaded after l-g-t-m from mtklein@google.com Link to the patchset: https://codereview.chromium.org/1216983003/#ps100001 (title: "Address mtklein's comments")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1216983003/100001
https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h File src/core/SkGlyph.h (right): https://codereview.chromium.org/1216983003/diff/80001/src/core/SkGlyph.h#newc... src/core/SkGlyph.h:124: return SkChecksum::CheapMix(glyphId); On 2015/07/21 22:27:34, herb_g wrote: > On 2015/07/21 19:35:52, mtklein wrote: > > If we're seeing a lot of time spent looking through the hash table, that may > > also indicate we have a poor hash function. I am skeptical of the quality of > > CheapMix(). Might try Mix(). > > I think I'm going to work on tuning the hashing table in another cl. Oh, yeah, most definitely another CL. SGTM!
Message was sent while issue was closed.
Committed patchset #6 (id:100001) as https://skia.googlesource.com/skia/+/c71239b9ff7d8c19dc03cb6c9081e7dc4e0947d2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
