1 /*
2  * Copyright 2013 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #include "Benchmark.h"
9 #include "SkCanvas.h"
10 #include "SkChecksum.h"
11 #include "SkPaint.h"
12 #include "SkString.h"
13 #include "SkTemplates.h"
14 
15 #include "gUniqueGlyphIDs.h"
16 #define gUniqueGlyphIDs_Sentinel    0xFFFF
17 
18 static int count_glyphs(const uint16_t start[]) {
19     const uint16_t* curr = start;
20     while (*curr != gUniqueGlyphIDs_Sentinel) {
21         curr += 1;
22     }
23     return static_cast<int>(curr - start);
24 }
25 
26 class FontCacheBench : public Benchmark {
27 public:
28     FontCacheBench()  {}
29 
30 protected:
31     const char* onGetName() override {
32         return "fontcache";
33     }
34 
35     void onDraw(int loops, SkCanvas* canvas) override {
36         SkPaint paint;
37         this->setupPaint(&paint);
38         paint.setTextEncoding(SkPaint::kGlyphID_TextEncoding);
39 
40         const uint16_t* array = gUniqueGlyphIDs;
41         while (*array != gUniqueGlyphIDs_Sentinel) {
42             int count = count_glyphs(array);
43             for (int i = 0; i < loops; ++i) {
44                 paint.measureText(array, count * sizeof(uint16_t));
45             }
46             array += count + 1;    // skip the sentinel
47         }
48     }
49 
50 private:
51     typedef Benchmark INHERITED;
52 };
53 
54 ///////////////////////////////////////////////////////////////////////////////
55 
56 static uint32_t rotr(uint32_t value, unsigned bits) {
57     return (value >> bits) | (value << (32 - bits));
58 }
59 
60 typedef uint32_t (*HasherProc)(uint32_t);
61 
62 static uint32_t hasher0(uint32_t value) {
63     value = value ^ (value >> 16);
64     return value ^ (value >> 8);
65 }
66 
67 static const struct {
68     const char* fName;
69     HasherProc  fHasher;
70 } gRec[] = {
71     { "hasher0",  hasher0 },
72     { "hasher2",  SkChecksum::Mix },
73 };
74 
75 #define kMaxHashBits   12
76 #define kMaxHashCount  (1 << kMaxHashBits)
77 
78 static int count_collisions(const uint16_t array[], int count, HasherProc proc,
79                             unsigned hashMask) {
80     char table[kMaxHashCount];
81     sk_bzero(table, sizeof(table));
82 
83     int collisions = 0;
84     for (int i = 0; i < count; ++i) {
85         int index = proc(array[i]) & hashMask;
86         collisions += table[index];
87         table[index] = 1;
88     }
89     return collisions;
90 }
91 
92 static void dump_array(const uint16_t array[], int count) {
93     for (int i = 0; i < count; ++i) {
94         SkDebugf(" %d,", array[i]);
95     }
96     SkDebugf("\n");
97 }
98 
99 class FontCacheEfficiency : public Benchmark {
100 public:
101     FontCacheEfficiency()  {
102         if (false) dump_array(nullptr, 0);
103         if (false) rotr(0, 0);
104     }
105 
106 protected:
107     const char* onGetName() override {
108         return "fontefficiency";
109     }
110 
111     void onDraw(int loops, SkCanvas* canvas) override {
112         static bool gDone;
113         if (gDone) {
114             return;
115         }
116         gDone = true;
117 
118         for (int hashBits = 6; hashBits <= 12; hashBits += 1) {
119             int hashMask = ((1 << hashBits) - 1);
120             for (int limit = 32; limit <= 1024; limit <<= 1) {
121                 for (size_t i = 0; i < SK_ARRAY_COUNT(gRec); ++i) {
122                     int collisions = 0;
123                     int glyphs = 0;
124                     const uint16_t* array = gUniqueGlyphIDs;
125                     while (*array != gUniqueGlyphIDs_Sentinel) {
126                         int count = SkMin32(count_glyphs(array), limit);
127                         collisions += count_collisions(array, count, gRec[i].fHasher, hashMask);
128                         glyphs += count;
129                         array += count + 1;    // skip the sentinel
130                     }
131                     SkDebugf("hashBits [%d] limit [%d] collisions [%d / %d = %1.2g%%] using %s\n", hashBits, limit, collisions, glyphs,
132                              collisions * 100.0 / glyphs, gRec[i].fName);
133                 }
134             }
135         }
136     }
137 
138 private:
139     typedef Benchmark INHERITED;
140 };
141 
142 ///////////////////////////////////////////////////////////////////////////////
143 
144 DEF_BENCH( return new FontCacheBench(); )
145 
146 // undefine this to run the efficiency test
147 //DEF_BENCH( return new FontCacheEfficiency(); )
148