1
// Copyright 2012 The Closure Library Authors. All Rights Reserved.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS-IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
/**
16
 * @fileoverview Performance test for goog.structs.Map and
17
 * goog.labs.structs.Map. To run this test fairly, you would have to
18
 * compile this via JsCompiler (with --export_test_functions), and
19
 * pull the compiled JS into an empty HTML file.
20
 * @author [email protected] (Chris Henry)
21
 */
22

23
goog.provide('goog.labs.structs.MapPerf');
24
goog.setTestOnly('goog.labs.structs.MapPerf');
25

26
goog.require('goog.asserts');
27
goog.require('goog.dom');
28
goog.require('goog.dom.TagName');
29
goog.require('goog.labs.structs.Map');
30
goog.require('goog.structs.Map');
31
goog.require('goog.testing.PerformanceTable');
32
goog.require('goog.testing.jsunit');
33

34
goog.scope(function() {
35
var MapPerf = goog.labs.structs.MapPerf;
36

37

38
/**
39
 * @typedef {goog.labs.structs.Map|goog.structs.Map}
40
 */
41
MapPerf.MapType;
42

43

44
/**
45
 * @type {goog.testing.PerformanceTable}
46
 */
47
MapPerf.perfTable;
48

49

50
/**
51
 * A key list. This maps loop index to key name to be used during
52
 * benchmark. This ensure that we do not need to pay the cost of
53
 * string concatenation/GC whenever we derive a key from loop index.
54
 *
55
 * This is filled once in setUpPage and then remain unchanged for the
56
 * rest of the test case.
57
 *
58
 * @type {!Array<string>}
59
 */
60
MapPerf.keyList = [];
61

62

63
/**
64
 * Maxium number of keys in keyList (and, by extension, the map under
65
 * test).
66
 * @type {number}
67
 */
68
MapPerf.MAX_NUM_KEY = 10000;
69

70

71
/**
72
 * Fills the given map with generated key-value pair.
73
 * @param {MapPerf.MapType} map The map to fill.
74
 * @param {number} numKeys The number of key-value pair to fill.
75
 */
76
MapPerf.fillMap = function(map, numKeys) {
77
  goog.asserts.assert(numKeys <= MapPerf.MAX_NUM_KEY);
78

79
  for (var i = 0; i < numKeys; ++i) {
80
    map.set(MapPerf.keyList[i], i);
81
  }
82
};
83

84

85
/**
86
 * Primes the given map with deletion of keys.
87
 * @param {MapPerf.MapType} map The map to prime.
88
 * @return {MapPerf.MapType} The primed map (for chaining).
89
 */
90
MapPerf.primeMapWithDeletion = function(map) {
91
  for (var i = 0; i < 1000; ++i) {
92
    map.set(MapPerf.keyList[i], i);
93
  }
94
  for (var i = 0; i < 1000; ++i) {
95
    map.remove(MapPerf.keyList[i]);
96
  }
97
  return map;
98
};
99

100

101
/**
102
 * Runs performance test for Map#get with the given map.
103
 * @param {MapPerf.MapType} map The map to stress.
104
 * @param {string} message Message to be put in performance table.
105
 */
106
MapPerf.runPerformanceTestForMapGet = function(map, message) {
107
  MapPerf.fillMap(map, 10000);
108

109
  MapPerf.perfTable.run(function() {
110
    // Creates local alias for map and keyList.
111
    var localMap = map;
112
    var localKeyList = MapPerf.keyList;
113

114
    for (var i = 0; i < 500; ++i) {
115
      var sum = 0;
116
      for (var j = 0; j < 10000; ++j) {
117
        sum += localMap.get(localKeyList[j]);
118
      }
119
    }
120
  }, message);
121
};
122

123

124
/**
125
 * Runs performance test for Map#set with the given map.
126
 * @param {MapPerf.MapType} map The map to stress.
127
 * @param {string} message Message to be put in performance table.
128
 */
129
MapPerf.runPerformanceTestForMapSet = function(map, message) {
130
  MapPerf.perfTable.run(function() {
131
    // Creates local alias for map and keyList.
132
    var localMap = map;
133
    var localKeyList = MapPerf.keyList;
134

135
    for (var i = 0; i < 500; ++i) {
136
      for (var j = 0; j < 10000; ++j) {
137
        localMap.set(localKeyList[i], i);
138
      }
139
    }
140
  }, message);
141
};
142

143

144
goog.global['setUpPage'] = function() {
145
  var content = goog.dom.createDom(goog.dom.TagName.DIV);
146
  goog.dom.insertChildAt(document.body, content, 0);
147
  goog.dom.append(
148
      content,
149
      goog.dom.createDom(
150
          goog.dom.TagName.H1, null, 'Closure Performance Tests - Map'),
151
      goog.dom.createDom(
152
          goog.dom.TagName.P, null,
153
          goog.dom.createDom(goog.dom.TagName.STRONG, null, 'User-agent: '),
154
          goog.dom.createDom(
155
              goog.dom.TagName.SPAN, {'id': 'ua'}, navigator.userAgent)),
156
      goog.dom.createDom(goog.dom.TagName.DIV, {'id': 'perf-table'}),
157
      goog.dom.createDom(goog.dom.TagName.HR));
158

159
  MapPerf.perfTable =
160
      new goog.testing.PerformanceTable(goog.dom.getElement('perf-table'));
161

162
  // Fills keyList.
163
  for (var i = 0; i < MapPerf.MAX_NUM_KEY; ++i) {
164
    MapPerf.keyList.push('k' + i);
165
  }
166
};
167

168

169
goog.global['testGetFromLabsMap'] = function() {
170
  MapPerf.runPerformanceTestForMapGet(
171
      new goog.labs.structs.Map(), '#get: no previous deletion (Labs)');
172
};
173

174

175
goog.global['testGetFromOriginalMap'] = function() {
176
  MapPerf.runPerformanceTestForMapGet(
177
      new goog.structs.Map(), '#get: no previous deletion (Original)');
178
};
179

180

181
goog.global['testGetWithPreviousDeletionFromLabsMap'] = function() {
182
  MapPerf.runPerformanceTestForMapGet(
183
      MapPerf.primeMapWithDeletion(new goog.labs.structs.Map()),
184
      '#get: with previous deletion (Labs)');
185
};
186

187

188
goog.global['testGetWithPreviousDeletionFromOriginalMap'] = function() {
189
  MapPerf.runPerformanceTestForMapGet(
190
      MapPerf.primeMapWithDeletion(new goog.structs.Map()),
191
      '#get: with previous deletion (Original)');
192
};
193

194

195
goog.global['testSetFromLabsMap'] = function() {
196
  MapPerf.runPerformanceTestForMapSet(
197
      new goog.labs.structs.Map(), '#set: no previous deletion (Labs)');
198
};
199

200

201
goog.global['testSetFromOriginalMap'] = function() {
202
  MapPerf.runPerformanceTestForMapSet(
203
      new goog.structs.Map(), '#set: no previous deletion (Original)');
204
};
205

206
});  // goog.scope
207

208