1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
|
# Copyright (C) 2007 Canonical Ltd
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
"""Benchmarks for bzr DirState performance."""
import os
from bzrlib import (
benchmarks,
dirstate,
generate_ids,
osutils,
tests,
)
from bzrlib.tests.test__dirstate_helpers import (
CompiledDirstateHelpersFeature,
)
class BenchmarkDirState(benchmarks.Benchmark):
"""Benchmarks for DirState functions."""
def build_helper(self, layout):
"""This is a helper with the common build_??_dirstate funcs.
:param layout: [(num_dirs, files_per_dir)]
The number of directories per level, and the number of files to put
in it.
:return: A DirState object with the given layout. The blocks will be
modified in memory, and the object will be write locked. (Callers
must save and unlock the object).
"""
self.build_tree(['dir/'])
contents = 'x'*10000
self.build_tree_contents([('file', contents)])
file_stat = os.lstat('file')
dir_stat = os.lstat('dir')
file_sha1 = osutils.sha_string(contents)
state = dirstate.DirState.initialize('state')
def create_entries(base, layout):
if not layout:
return
num_dirs, num_files = layout[0]
for dnum in xrange(num_dirs):
if base:
path = '%s/%02d_directory' % (base, dnum)
else:
path = '%02d_directory' % (dnum,)
dir_id = generate_ids.gen_file_id(path)
state.add(path, dir_id, 'directory', dir_stat, '')
for fnum in xrange(num_files):
fname = '%s/%02d_filename' % (path, fnum)
file_id = generate_ids.gen_file_id(fname)
state.add(fname, file_id, 'file', file_stat, file_sha1)
create_entries(path, layout[1:])
create_entries(None, layout)
return state
def build_10k_dirstate_dirs(self):
"""Build a DirState file with 10k directories"""
state = self.build_helper([(10, 0), (10, 0), (10, 0), (10, 1)])
state.save()
state.unlock()
return state
def build_20k_dirstate(self):
"""Build a DirState file with 20k records.
This approximates a kernel tree, based on the number of directories
(1000), and number of files per directory (20) and depth (3).
Because DirState doesn't have to have actual disk records, we just add
random files.
We try to have reasonable filename lengths, as well as a reasonable
stat value, etc.
"""
state = self.build_helper([(10, 0), (10, 0), (10, 20)])
state.save()
state.unlock()
return state
def build_20k_dirstate_with_parents(self, num_parents):
"""Build a DirState file with 20k records and N parents.
With 1 parent, this is equivalent to after a simple commit. With 2 it
is equivalent to after a merge.
"""
# All files are marked as changed in the same revision, and this occurs
# supposedly in the history of the current trees.
last_changed_id = generate_ids.gen_revision_id('joe@foo.com')
parent_revision_ids = [generate_ids.gen_revision_id('joe@foo.com')
for i in xrange(num_parents)]
# Start with a dirstate file with 0 parents
state = self.build_helper([(10, 0), (10, 0), (10, 20)])
try:
# This invasively updates the internals of DirState to be fast,
# since we don't have an api other than passing in Revision Tree
# objects, but that requires having a real inventory, etc.
if num_parents > 0:
for entry in state._iter_entries():
minikind, fingerprint, size, is_exec, packed_stat = entry[1][0]
for parent_id in parent_revision_ids:
# Add a parent record for this record
entry[1].append((minikind, fingerprint, size, is_exec,
last_changed_id))
state._parents = parent_revision_ids
state._ghosts = []
state.save()
finally:
state.unlock()
return state
def test_add_20k_entries(self):
"""Time how long it takes to add lots of entries."""
state = self.time(self.build_helper, [(10, 0), (10, 0), (10, 20)])
state.unlock()
def test_build_20k_dirstate(self):
state = self.time(self.build_20k_dirstate)
state.lock_read()
try:
entries = list(state._iter_entries())
self.assertEqual(21111, len(entries))
finally:
state.unlock()
def test_build_20k_dirstate_1_parent(self):
state = self.time(self.build_20k_dirstate_with_parents, 1)
state.lock_read()
try:
state._validate()
entries = list(state._iter_entries())
self.assertEqual(21111, len(entries))
finally:
state.unlock()
def test_build_20k_dirstate_2_parents(self):
state = self.time(self.build_20k_dirstate_with_parents, 2)
state.lock_read()
try:
state._validate()
entries = list(state._iter_entries())
self.assertEqual(21111, len(entries))
finally:
state.unlock()
def test_save_20k_tree_0_parents(self):
state = self.build_20k_dirstate()
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_dirblocks_if_needed()
state._dirblock_state = dirstate.DirState.IN_MEMORY_MODIFIED
self.time(state.save)
finally:
state.unlock()
def test_save_20k_tree_1_parent(self):
state = self.build_20k_dirstate_with_parents(1)
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_dirblocks_if_needed()
state._dirblock_state = dirstate.DirState.IN_MEMORY_MODIFIED
self.time(state.save)
finally:
state.unlock()
def test_save_20k_tree_2_parents(self):
state = self.build_20k_dirstate_with_parents(2)
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_dirblocks_if_needed()
state._dirblock_state = dirstate.DirState.IN_MEMORY_MODIFIED
self.time(state.save)
finally:
state.unlock()
def test__read_dirblocks_20k_tree_0_parents_py(self):
from bzrlib._dirstate_helpers_py import _read_dirblocks_py
state = self.build_20k_dirstate()
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_header_if_needed()
self.time(_read_dirblocks_py, state)
finally:
state.unlock()
def test__read_dirblocks_20k_tree_0_parents_c(self):
self.requireFeature(CompiledDirstateHelpersFeature)
from bzrlib._dirstate_helpers_c import _read_dirblocks_c
state = self.build_20k_dirstate()
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_header_if_needed()
self.time(_read_dirblocks_c, state)
finally:
state.unlock()
def test__read_dirblocks_20k_tree_1_parent_py(self):
from bzrlib._dirstate_helpers_py import _read_dirblocks_py
state = self.build_20k_dirstate_with_parents(1)
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_header_if_needed()
self.time(_read_dirblocks_py, state)
finally:
state.unlock()
def test__read_dirblocks_20k_tree_1_parent_c(self):
self.requireFeature(CompiledDirstateHelpersFeature)
from bzrlib._dirstate_helpers_c import _read_dirblocks_c
state = self.build_20k_dirstate_with_parents(1)
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_header_if_needed()
self.time(_read_dirblocks_c, state)
finally:
state.unlock()
def test__read_dirblocks_20k_tree_2_parents_py(self):
from bzrlib._dirstate_helpers_py import _read_dirblocks_py
state = self.build_20k_dirstate_with_parents(2)
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_header_if_needed()
self.time(_read_dirblocks_py, state)
finally:
state.unlock()
def test__read_dirblocks_20k_tree_2_parents_c(self):
self.requireFeature(CompiledDirstateHelpersFeature)
from bzrlib._dirstate_helpers_c import _read_dirblocks_c
state = self.build_20k_dirstate_with_parents(2)
state.lock_read()
try:
self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
state._dirblock_state)
state._read_header_if_needed()
self.time(_read_dirblocks_c, state)
finally:
state.unlock()
def do_bisect_list(self, bisect_func):
"""Call bisect_dirblock for each path."""
# We use self._paths and self._blocks because we expect it to be a very
# long list. And the interface for 'self.time()' causes the parameters
# to be printed when run with --lsprof-timed. Which is *really* ugly
# when the list is thousands of entries.
blocks = self._blocks
return [bisect_func(blocks, path) for path in self._paths]
def do_bisect_list_cached(self, bisect_func):
"""Same as do_bisect_list, but cache the split paths"""
cache = {}
blocks = self._blocks
return [bisect_func(blocks, path, cache=cache) for path in self._paths]
def setup_paths_and_offsets(self, state):
"""Get a list of paths and expected offsets.
This will be used to check do_bisect_list*
"""
state._read_dirblocks_if_needed()
paths = ['']
expected_offsets = [0]
for offset, info in enumerate(state._dirblocks):
dirname = info[0]
# We already handled the empty path
if dirname == '':
continue
# all paths are of the form ##_directory
# so search for ##_director, ##_directory
paths.extend([dirname[:-1], dirname])
expected_offsets.extend([offset, offset])
self._paths = paths
self._expected_offsets = expected_offsets
self._blocks = state._dirblocks
def checkOffsets(self, offsets):
"""Make sure offsets matches self._expected_offsets"""
# These are really long lists, so it is easier to compare them with
# assertEqualDiff. So turn them into strings.
expected_str = '\n'.join(str(x) for x in self._expected_offsets)
offset_str = '\n'.join(str(x) for x in offsets)
self.assertEqualDiff(expected_str, offset_str)
def test_bisect_dirblock_py(self):
from bzrlib._dirstate_helpers_py import bisect_dirblock_py
state = self.build_10k_dirstate_dirs()
state.lock_read()
try:
self.setup_paths_and_offsets(state)
offsets = self.time(self.do_bisect_list,
bisect_dirblock_py)
self.checkOffsets(offsets)
finally:
state.unlock()
def test_bisect_dirblock_cached_py(self):
from bzrlib._dirstate_helpers_py import bisect_dirblock_py
state = self.build_10k_dirstate_dirs()
state.lock_read()
try:
self.setup_paths_and_offsets(state)
offsets = self.time(self.do_bisect_list_cached,
bisect_dirblock_py)
self.checkOffsets(offsets)
finally:
state.unlock()
def test_bisect_dirblock_c(self):
self.requireFeature(CompiledDirstateHelpersFeature)
from bzrlib._dirstate_helpers_c import bisect_dirblock_c
state = self.build_10k_dirstate_dirs()
state.lock_read()
try:
self.setup_paths_and_offsets(state)
offsets = self.time(self.do_bisect_list, bisect_dirblock_c)
self.checkOffsets(offsets)
finally:
state.unlock()
def create_path_names(self, layout, base=''):
"""Create a list of paths with auto-generated names.
:param layout: A list of [(num_dirs, num_files)] tuples. For each
level, the given number of directories will be created, each
containing that many files.
So [(2, 5), (3, 4)] will create 2 top level directories, containing
5 files, and each top level directory will contain 3 subdirs with 4
files.
:param base: The base path to prepend to all entries, most callers will
pass ''
:return: A list of path names.
"""
if not layout:
return []
paths = []
num_dirs, num_files = layout[0]
for dnum in xrange(num_dirs):
if base:
path = '%s/%02d_directory' % (base, dnum)
else:
path = '%02d_directory' % (dnum,)
paths.append(path)
for fnum in xrange(num_files):
fname = '%s/%02d_filename' % (path, fnum)
paths.append(fname)
paths.extend(self.create_path_names(layout[1:], base=path))
return paths
def test_create_path_names(self):
names = self.create_path_names([(2, 3), (1, 2)])
self.assertEqual(['00_directory',
'00_directory/00_filename',
'00_directory/01_filename',
'00_directory/02_filename',
'00_directory/00_directory',
'00_directory/00_directory/00_filename',
'00_directory/00_directory/01_filename',
'01_directory',
'01_directory/00_filename',
'01_directory/01_filename',
'01_directory/02_filename',
'01_directory/00_directory',
'01_directory/00_directory/00_filename',
'01_directory/00_directory/01_filename',
], names)
names = self.time(self.create_path_names, [(10, 2), (10, 2), (10, 20)])
# 20 files + 1 directory name, 10 times, plus 2 filenames and 1 dir, 10
# times, and another 2 files + 1 dir, 10 times
self.assertEqual(21330, 10*(3 + 10*(3 + 10*(1 + 20))))
self.assertEqual(21330, len(names))
def compareAllPaths(self, cmp_func, layout):
"""Compare N^2 paths.
Basically, compare every path in the list against every other path.
"""
paths = self.create_path_names(layout)
def compare_all():
for path1 in paths:
for path2 in paths:
cmp_func(path1, path2)
self.time(compare_all)
def test_cmp_by_dirs_py(self):
"""Benchmark 103041 comparisons."""
from bzrlib._dirstate_helpers_py import cmp_by_dirs_py
self.compareAllPaths(cmp_by_dirs_py,
[(3, 1), (3, 1), (3, 1), (3, 2)])
def test_cmp_by_dirs_c(self):
self.requireFeature(CompiledDirstateHelpersFeature)
from bzrlib._dirstate_helpers_c import cmp_by_dirs_c
self.compareAllPaths(cmp_by_dirs_c,
[(3, 1), (3, 1), (3, 1), (3, 2)])
|