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