Issue 4916044: W array optimization algorithm with wildcards. (Closed)
|
Created:
13 years, 5 months ago by arthurhsu Modified:
13 years, 2 months ago Reviewers:
Steve VanDeBogart CC:
skia-review_googlegroups.com Base URL:
http://skia.googlecode.com/svn/trunk Visibility:
Public. |
DescriptionW array optimization algorithm with wildcards.
Patch Set 1 #
Total comments: 10
Patch Set 2 : Update per code review #
Total comments: 18
Patch Set 3 : Update per code review #
Total comments: 9
Patch Set 4 : Update per code review #Patch Set 5 : Update per code review #
Total comments: 6
Patch Set 6 : Update per code review #
MessagesTotal messages: 12
A couple high level comments. http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:65: void clearRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range) { A better name for this might be zeroWildcardsInRange. Or should this just be part of finishRange? http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:80: // Assuming that an ASCII representation of a width or a glyph id is, Update the comment to describe how wildcards are used. http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:109: for (int gId = firstIndex; gId <= lastIndex; gId++) { Instead of looping through all the gID's, would it be easier to loop through just the Id's in the subset? Then all the don't care's would be implicit. http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:132: curRange->fAdvance[0] == SK_MinS16)) { It seems like this logic could be promoted out of the if... i.e. to line 120.. if a range is of length one and starts with a wildcard, update the range to start at the current gId, then continue. http://codereview.appspot.com/4916044/diff/1/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/1/tests/WArrayTest.cpp#newcode13 tests/WArrayTest.cpp:13: Maybe you could put the data in an array of structs, with each entry being a data set, then you could templetize the getAdvance method with an int...
Sign in to reply to this message.
http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:65: void clearRange(SkAdvancedTypefaceMetrics::AdvanceMetric<Data>* range) { On 2011/08/18 21:06:10, Steve VanDeBogart wrote: > A better name for this might be zeroWildcardsInRange. Or should this just be > part of finishRange? Done. http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:80: // Assuming that an ASCII representation of a width or a glyph id is, On 2011/08/18 21:06:10, Steve VanDeBogart wrote: > Update the comment to describe how wildcards are used. Done. http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:109: for (int gId = firstIndex; gId <= lastIndex; gId++) { On 2011/08/18 21:06:10, Steve VanDeBogart wrote: > Instead of looping through all the gID's, would it be easier to loop through > just the Id's in the subset? Then all the don't care's would be implicit. In order to keep existing algorithm, this is a minor cost to pay for. http://codereview.appspot.com/4916044/diff/1/src/core/SkAdvancedTypefaceMetri... src/core/SkAdvancedTypefaceMetrics.cpp:132: curRange->fAdvance[0] == SK_MinS16)) { On 2011/08/18 21:06:10, Steve VanDeBogart wrote: > It seems like this logic could be promoted out of the if... i.e. to line 120.. > if a range is of length one and starts with a wildcard, update the range to > start at the current gId, then continue. Doing so we need to repeat logic in line 181 to 185. http://codereview.appspot.com/4916044/diff/1/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/1/tests/WArrayTest.cpp#newcode13 tests/WArrayTest.cpp:13: On 2011/08/18 21:06:10, Steve VanDeBogart wrote: > Maybe you could put the data in an array of structs, with each entry being a > data set, then you could templetize the getAdvance method with an int... Done.
Sign in to reply to this message.
http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:66: void zeroWildcardsInRange( Does this all need to come before finishRange. I think it can be static as well (meaning different naming format). http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:68: } maybe add an SkASSERT(false) here, as we don't expect it to be called. http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:74: if (range->fAdvance[i] == SK_MinS16) { Make this a constant, kDontCareAdvance ? http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:142: if (advance == lastAdvance && advance != SK_MinS16) { The test: advance data = 42 ... 42 subset = 0, 2, 3, 6, 7, 11, 16, 17 does not return 0 17 42 I think either this needs to be an else if, or this case needs to be hit so the rest of the cases aren't when you get a don't care. Haven't look at it further... http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:213: // Remove trailing wildcards. This may need to be done generally in finish range, not sure. http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode15 tests/WArrayTest.cpp:15: const int16_t data1Len = sizeof(data1) / sizeof(int16_t); Probably don't need these vars, can just do it in the |testSet| init. http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode28 tests/WArrayTest.cpp:28: const uint32_t glyphs4[] = {1, 6, 9, 10, 11}; maybe call these subsetX http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode122 tests/WArrayTest.cpp:122: for (size_t i = 0; i < sizeof(testSet) / sizeof(WDataSet); ++i) { SK_ARRAY_COUNT, here and elsewhere.
Sign in to reply to this message.
http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:66: void zeroWildcardsInRange( On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > Does this all need to come before finishRange. I think it can be static as well > (meaning different naming format). GCC said "error: explicit template specialization cannot have a storage class". So we can't make it static. http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:68: } On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > maybe add an SkASSERT(false) here, as we don't expect it to be called. Done. http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:74: if (range->fAdvance[i] == SK_MinS16) { On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > Make this a constant, kDontCareAdvance ? Done. http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:142: if (advance == lastAdvance && advance != SK_MinS16) { On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > The test: > advance data = 42 ... 42 > subset = 0, 2, 3, 6, 7, 11, 16, 17 > does not return 0 17 42 > > I think either this needs to be an else if, or this case needs to be hit so the > rest of the cases aren't when you get a don't care. Haven't look at it > further... Done. Added this case to WArrayTest.cpp, too. http://codereview.appspot.com/4916044/diff/4001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:213: // Remove trailing wildcards. On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > This may need to be done generally in finish range, not sure. Done. http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode15 tests/WArrayTest.cpp:15: const int16_t data1Len = sizeof(data1) / sizeof(int16_t); On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > Probably don't need these vars, can just do it in the |testSet| init. Attempted, SK_ARRAY_COUNT() returns invalid count. However, if SK_ARRAY_COUNT() is called for data*Len, it returns correct value. http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode28 tests/WArrayTest.cpp:28: const uint32_t glyphs4[] = {1, 6, 9, 10, 11}; On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > maybe call these subsetX Done. http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode122 tests/WArrayTest.cpp:122: for (size_t i = 0; i < sizeof(testSet) / sizeof(WDataSet); ++i) { On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > SK_ARRAY_COUNT, here and elsewhere. Done.
Sign in to reply to this message.
http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode15 tests/WArrayTest.cpp:15: const int16_t data1Len = sizeof(data1) / sizeof(int16_t); On 2011/08/22 23:21:01, arthurhsu wrote: > On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > > Probably don't need these vars, can just do it in the |testSet| init. > > Attempted, SK_ARRAY_COUNT() returns invalid count. However, if SK_ARRAY_COUNT() > is called for data*Len, it returns correct value. explain? Sk_ARRAY_COUNT(data1) should return the same thing in this context and the context of |testSet| creation. http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:162: if (advance == lastAdvance) { Does this also need || (repeats > 0 && advance == kDontCareAdvance) ? Or maybe the previous if should become part of the if-else http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:167: } else if (curRange->fAdvance.count() == repeats + 1) { You only advance repeats for real advances, so within this block, there will never be don't cares in the range. Should this check against repeatsWithWildcards instead? http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:192: } else if (wildcards >= 3 && advance != kDontCareAdvance) { Why 3? seems like we should strip all trailing wildcards if they break a range or run. http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:219: } What about C X C D? Looks like that'd fall into the else, which doesn't exist.
Sign in to reply to this message.
http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/4001/tests/WArrayTest.cpp#newcode15 tests/WArrayTest.cpp:15: const int16_t data1Len = sizeof(data1) / sizeof(int16_t); On 2011/08/23 19:14:58, Steve VanDeBogart wrote: > On 2011/08/22 23:21:01, arthurhsu wrote: > > On 2011/08/19 20:55:38, Steve VanDeBogart wrote: > > > Probably don't need these vars, can just do it in the |testSet| init. > > > > Attempted, SK_ARRAY_COUNT() returns invalid count. However, if > SK_ARRAY_COUNT() > > is called for data*Len, it returns correct value. > > explain? Sk_ARRAY_COUNT(data1) should return the same thing in this context and > the context of |testSet| creation. Done. http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:162: if (advance == lastAdvance) { On 2011/08/23 19:14:58, Steve VanDeBogart wrote: > Does this also need || (repeats > 0 && advance == kDontCareAdvance) ? Or maybe > the previous if should become part of the if-else This block is to handle real advances only. If not, the don't care will be inserted and continue the loop. http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:167: } else if (curRange->fAdvance.count() == repeats + 1) { On 2011/08/23 19:14:58, Steve VanDeBogart wrote: > You only advance repeats for real advances, so within this block, there will > never be don't cares in the range. Should this check against > repeatsWithWildcards instead? It shall not. This block is used to knock out leading zeros/wildcards, also make judgement about good continuous runs. C X C X C cases are handled below. http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:192: } else if (wildcards >= 3 && advance != kDontCareAdvance) { On 2011/08/23 19:14:58, Steve VanDeBogart wrote: > Why 3? seems like we should strip all trailing wildcards if they break a range > or run. Done. http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:219: } On 2011/08/23 19:14:58, Steve VanDeBogart wrote: > What about C X C D? Looks like that'd fall into the else, which doesn't exist. Done.
Sign in to reply to this message.
Enumerated and documented cases. All cases shall be covered in unit tests.
Sign in to reply to this message.
http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/9001/src/core/SkAdvancedTypefaceMe... src/core/SkAdvancedTypefaceMetrics.cpp:167: } else if (curRange->fAdvance.count() == repeats + 1) { On 2011/08/23 21:00:46, arthurhsu wrote: > On 2011/08/23 19:14:58, Steve VanDeBogart wrote: > > You only advance repeats for real advances, so within this block, there will > > never be don't cares in the range. Should this check against > > repeatsWithWildcards instead? > > It shall not. This block is used to knock out leading zeros/wildcards, also > make judgement about good continuous runs. C X C X C cases are handled below. C X C X C won't fall into this block. I maintain my claim that as is, ranges with don't cares will never enter this block. http://codereview.appspot.com/4916044/diff/16001/src/core/SkAdvancedTypefaceM... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/16001/src/core/SkAdvancedTypefaceM... src/core/SkAdvancedTypefaceMetrics.cpp:128: // A X 0 X X B does not win anything: 0[A 0 0 0 0 B] Why should this case be any different? http://codereview.appspot.com/4916044/diff/16001/src/core/SkAdvancedTypefaceM... src/core/SkAdvancedTypefaceMetrics.cpp:177: if (advance != kDontCareAdvance) { This is always true: We're only here if advice == lastAdvance, lastAdvance is only kDontCareAdvance for the first iteration, on the first iteration advance will never be kDontCareAdvance because we start with the first glyph in the subset. http://codereview.appspot.com/4916044/diff/16001/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/16001/tests/WArrayTest.cpp#newcode39 tests/WArrayTest.cpp:39: const uint32_t subset4[] = {1, 6, 9, 10, 11}; Don't include the 1 to get the test case you claim.
Sign in to reply to this message.
http://codereview.appspot.com/4916044/diff/16001/src/core/SkAdvancedTypefaceM... File src/core/SkAdvancedTypefaceMetrics.cpp (right): http://codereview.appspot.com/4916044/diff/16001/src/core/SkAdvancedTypefaceM... src/core/SkAdvancedTypefaceMetrics.cpp:128: // A X 0 X X B does not win anything: 0[A 0 0 0 0 B] On 2011/08/30 20:11:25, Steve VanDeBogart wrote: > Why should this case be any different? This is the same as A X X C X C B This is a greedy algorithm so it remembers last non-X value and make a decision when walked to an non-X value A X 0 => decision made, A 0 0 0 X X B => decision made, 0 0 0 B http://codereview.appspot.com/4916044/diff/16001/src/core/SkAdvancedTypefaceM... src/core/SkAdvancedTypefaceMetrics.cpp:177: if (advance != kDontCareAdvance) { On 2011/08/30 20:11:25, Steve VanDeBogart wrote: > This is always true: We're only here if advice == lastAdvance, lastAdvance is > only kDontCareAdvance for the first iteration, on the first iteration advance > will never be kDontCareAdvance because we start with the first glyph in the > subset. Done. http://codereview.appspot.com/4916044/diff/16001/tests/WArrayTest.cpp File tests/WArrayTest.cpp (right): http://codereview.appspot.com/4916044/diff/16001/tests/WArrayTest.cpp#newcode39 tests/WArrayTest.cpp:39: const uint32_t subset4[] = {1, 6, 9, 10, 11}; On 2011/08/30 20:11:25, Steve VanDeBogart wrote: > Don't include the 1 to get the test case you claim. Done.
Sign in to reply to this message.
ping?
Sign in to reply to this message.
On 2011/09/28 23:12:19, arthurhsu wrote: > ping? I think this can be done with much less code. It's been on my todo list to give it a try to confirm/refute that hypothesis. I will try to do that within a week.
Sign in to reply to this message.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
