← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/benchmarks/bench_dirstate.py

  • Committer: John Arbash Meinel
  • Date: 2007-05-04 18:59:36 UTC
  • mto: This revision was merged to the branch mainline in revision 2643.
  • Revision ID: john@arbash-meinel.com-20070504185936-1mjdoqmtz74xe5mg
A C implementation of _fields_to_entry_0_parents drops the time from 400ms to 330ms for a 21k-entry tree

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/benchmarks/bench_dirstate.py
25
25
    osutils,
26
26
    tests,
27
27
    )
28
 
from bzrlib.tests.test__dirstate_helpers import (
 
28
from bzrlib.tests.compiled.test_dirstate_helpers import (
29
29
    CompiledDirstateHelpersFeature,
30
30
    )
31
31
 
32
32
 
33
33
class BenchmarkDirState(benchmarks.Benchmark):
34
 
    """Benchmarks for DirState functions."""
35
34
 
36
35
    def build_helper(self, layout):
37
36
        """This is a helper with the common build_??_dirstate funcs.
39
38
        :param layout: [(num_dirs, files_per_dir)]
40
39
            The number of directories per level, and the number of files to put
41
40
            in it.
42
 
        :return: A DirState object with the given layout. The blocks will be
43
 
            modified in memory, and the object will be write locked. (Callers
44
 
            must save and unlock the object).
 
41
        :return: A DirState object with the given layout.
45
42
        """
46
43
        self.build_tree(['dir/'])
47
44
        contents = 'x'*10000
51
48
        file_sha1 = osutils.sha_string(contents)
52
49
 
53
50
        state = dirstate.DirState.initialize('state')
54
 
        def create_entries(base, layout):
55
 
            if not layout:
56
 
                return
57
 
            num_dirs, num_files = layout[0]
58
 
            for dnum in xrange(num_dirs):
59
 
                if base:
60
 
                    path = '%s/%02d_directory' % (base, dnum)
61
 
                else:
62
 
                    path = '%02d_directory' % (dnum,)
63
 
                dir_id = generate_ids.gen_file_id(path)
64
 
                state.add(path, dir_id, 'directory', dir_stat, '')
65
 
                for fnum in xrange(num_files):
66
 
                    fname = '%s/%02d_filename' % (path, fnum)
67
 
                    file_id = generate_ids.gen_file_id(fname)
68
 
                    state.add(fname, file_id, 'file', file_stat, file_sha1)
69
 
                create_entries(path, layout[1:])
70
 
        create_entries(None, layout)
 
51
        try:
 
52
            def create_entries(base, layout):
 
53
                if not layout:
 
54
                    return
 
55
                num_dirs, num_files = layout[0]
 
56
                for dnum in xrange(num_dirs):
 
57
                    if base:
 
58
                        path = '%s/%02d_directory' % (base, dnum)
 
59
                    else:
 
60
                        path = '%02d_directory' % (dnum,)
 
61
                    dir_id = generate_ids.gen_file_id(path)
 
62
                    state.add(path, dir_id, 'directory', dir_stat, '')
 
63
                    for fnum in xrange(num_files):
 
64
                        fname = '%s/%02d_filename' % (path, fnum)
 
65
                        file_id = generate_ids.gen_file_id(fname)
 
66
                        state.add(fname, file_id, 'file', file_stat, file_sha1)
 
67
                    create_entries(path, layout[1:])
 
68
            create_entries(None, layout)
 
69
            state.save()
 
70
        finally:
 
71
            state.unlock()
71
72
        return state
72
73
 
73
74
    def build_10k_dirstate_dirs(self):
74
75
        """Build a DirState file with 10k directories"""
75
 
        state = self.build_helper([(10, 0), (10, 0), (10, 0), (10, 1)])
76
 
        state.save()
77
 
        state.unlock()
78
 
        return state
 
76
        return self.build_helper([(10, 0), (10, 0), (10, 0), (10, 1)])
79
77
 
80
78
    def build_20k_dirstate(self):
81
79
        """Build a DirState file with 20k records.
87
85
        We try to have reasonable filename lengths, as well as a reasonable
88
86
        stat value, etc.
89
87
        """
90
 
        state = self.build_helper([(10, 0), (10, 0), (10, 20)])
91
 
        state.save()
92
 
        state.unlock()
93
 
        return state
94
 
 
95
 
    def build_20k_dirstate_with_parents(self, num_parents):
96
 
        """Build a DirState file with 20k records and N parents.
97
 
 
98
 
        With 1 parent, this is equivalent to after a simple commit. With 2 it
99
 
        is equivalent to after a merge.
100
 
        """
101
 
        # All files are marked as changed in the same revision, and this occurs
102
 
        # supposedly in the history of the current trees.
103
 
        last_changed_id = generate_ids.gen_revision_id('joe@foo.com')
104
 
        parent_revision_ids = [generate_ids.gen_revision_id('joe@foo.com')
105
 
                               for i in xrange(num_parents)]
106
 
        # Start with a dirstate file with 0 parents
107
 
        state = self.build_helper([(10, 0), (10, 0), (10, 20)])
108
 
        try:
109
 
            # This invasively updates the internals of DirState to be fast,
110
 
            # since we don't have an api other than passing in Revision Tree
111
 
            # objects, but that requires having a real inventory, etc.
112
 
            if num_parents > 0:
113
 
                for entry in state._iter_entries():
114
 
                    minikind, fingerprint, size, is_exec, packed_stat = entry[1][0]
115
 
                    for parent_id in parent_revision_ids:
116
 
                        # Add a parent record for this record
117
 
                        entry[1].append((minikind, fingerprint, size, is_exec,
118
 
                                         last_changed_id))
119
 
            state._parents = parent_revision_ids
120
 
            state._ghosts = []
121
 
            state.save()
122
 
        finally:
123
 
            state.unlock()
124
 
        return state
125
 
 
126
 
    def test_add_20k_entries(self):
127
 
        """Time how long it takes to add lots of entries."""
128
 
        state = self.time(self.build_helper, [(10, 0), (10, 0), (10, 20)])
129
 
        state.unlock()
130
 
 
131
 
    def test_build_20k_dirstate(self):
 
88
        return self.build_helper([(10, 0), (10, 0), (10, 20)])
 
89
 
 
90
    def test_build_20k_dirblocks(self):
132
91
        state = self.time(self.build_20k_dirstate)
133
92
        state.lock_read()
134
93
        try:
137
96
        finally:
138
97
            state.unlock()
139
98
 
140
 
    def test_build_20k_dirstate_1_parent(self):
141
 
        state = self.time(self.build_20k_dirstate_with_parents, 1)
142
 
        state.lock_read()
143
 
        try:
144
 
            state._validate()
145
 
            entries = list(state._iter_entries())
146
 
            self.assertEqual(21111, len(entries))
147
 
        finally:
148
 
            state.unlock()
149
 
 
150
 
    def test_build_20k_dirstate_2_parents(self):
151
 
        state = self.time(self.build_20k_dirstate_with_parents, 2)
152
 
        state.lock_read()
153
 
        try:
154
 
            state._validate()
155
 
            entries = list(state._iter_entries())
156
 
            self.assertEqual(21111, len(entries))
157
 
        finally:
158
 
            state.unlock()
159
 
 
160
 
    def test_save_20k_tree_0_parents(self):
161
 
        state = self.build_20k_dirstate()
162
 
        state.lock_read()
163
 
        try:
164
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
165
 
                             state._dirblock_state)
166
 
            state._read_dirblocks_if_needed()
167
 
            state._dirblock_state = dirstate.DirState.IN_MEMORY_MODIFIED
168
 
            self.time(state.save)
169
 
        finally:
170
 
            state.unlock()
171
 
 
172
 
    def test_save_20k_tree_1_parent(self):
173
 
        state = self.build_20k_dirstate_with_parents(1)
174
 
        state.lock_read()
175
 
        try:
176
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
177
 
                             state._dirblock_state)
178
 
            state._read_dirblocks_if_needed()
179
 
            state._dirblock_state = dirstate.DirState.IN_MEMORY_MODIFIED
180
 
            self.time(state.save)
181
 
        finally:
182
 
            state.unlock()
183
 
 
184
 
    def test_save_20k_tree_2_parents(self):
185
 
        state = self.build_20k_dirstate_with_parents(2)
186
 
        state.lock_read()
187
 
        try:
188
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
189
 
                             state._dirblock_state)
190
 
            state._read_dirblocks_if_needed()
191
 
            state._dirblock_state = dirstate.DirState.IN_MEMORY_MODIFIED
192
 
            self.time(state.save)
193
 
        finally:
194
 
            state.unlock()
195
 
 
196
 
    def test__read_dirblocks_20k_tree_0_parents_py(self):
197
 
        from bzrlib._dirstate_helpers_py import _read_dirblocks_py
198
 
        state = self.build_20k_dirstate()
199
 
        state.lock_read()
200
 
        try:
201
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
202
 
                             state._dirblock_state)
203
 
            state._read_header_if_needed()
204
 
            self.time(_read_dirblocks_py, state)
205
 
        finally:
206
 
            state.unlock()
207
 
 
208
 
    def test__read_dirblocks_20k_tree_0_parents_c(self):
209
 
        self.requireFeature(CompiledDirstateHelpersFeature)
210
 
        from bzrlib._dirstate_helpers_c import _read_dirblocks_c
211
 
        state = self.build_20k_dirstate()
212
 
        state.lock_read()
213
 
        try:
214
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
215
 
                             state._dirblock_state)
216
 
            state._read_header_if_needed()
217
 
            self.time(_read_dirblocks_c, state)
218
 
        finally:
219
 
            state.unlock()
220
 
 
221
 
    def test__read_dirblocks_20k_tree_1_parent_py(self):
222
 
        from bzrlib._dirstate_helpers_py import _read_dirblocks_py
223
 
        state = self.build_20k_dirstate_with_parents(1)
224
 
        state.lock_read()
225
 
        try:
226
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
227
 
                             state._dirblock_state)
228
 
            state._read_header_if_needed()
229
 
            self.time(_read_dirblocks_py, state)
230
 
        finally:
231
 
            state.unlock()
232
 
 
233
 
    def test__read_dirblocks_20k_tree_1_parent_c(self):
234
 
        self.requireFeature(CompiledDirstateHelpersFeature)
235
 
        from bzrlib._dirstate_helpers_c import _read_dirblocks_c
236
 
        state = self.build_20k_dirstate_with_parents(1)
237
 
        state.lock_read()
238
 
        try:
239
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
240
 
                             state._dirblock_state)
241
 
            state._read_header_if_needed()
242
 
            self.time(_read_dirblocks_c, state)
243
 
        finally:
244
 
            state.unlock()
245
 
 
246
 
    def test__read_dirblocks_20k_tree_2_parents_py(self):
247
 
        from bzrlib._dirstate_helpers_py import _read_dirblocks_py
248
 
        state = self.build_20k_dirstate_with_parents(2)
249
 
        state.lock_read()
250
 
        try:
251
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
252
 
                             state._dirblock_state)
253
 
            state._read_header_if_needed()
254
 
            self.time(_read_dirblocks_py, state)
255
 
        finally:
256
 
            state.unlock()
257
 
 
258
 
    def test__read_dirblocks_20k_tree_2_parents_c(self):
259
 
        self.requireFeature(CompiledDirstateHelpersFeature)
260
 
        from bzrlib._dirstate_helpers_c import _read_dirblocks_c
261
 
        state = self.build_20k_dirstate_with_parents(2)
262
 
        state.lock_read()
263
 
        try:
264
 
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
265
 
                             state._dirblock_state)
266
 
            state._read_header_if_needed()
267
 
            self.time(_read_dirblocks_c, state)
 
99
    def test__read_dirblocks_20k_tree_no_parents(self):
 
100
        state = self.build_20k_dirstate()
 
101
        state.lock_read()
 
102
        try:
 
103
            self.assertEqual(dirstate.DirState.NOT_IN_MEMORY,
 
104
                             state._dirblock_state)
 
105
            self.time(state._read_dirblocks_if_needed)
268
106
        finally:
269
107
            state.unlock()
270
108
 
312
150
        offset_str = '\n'.join(str(x) for x in offsets)
313
151
        self.assertEqualDiff(expected_str, offset_str)
314
152
 
315
 
    def test_bisect_dirblock_py(self):
316
 
        from bzrlib._dirstate_helpers_py import bisect_dirblock_py
 
153
    def test_py_bisect_dirblock(self):
317
154
        state = self.build_10k_dirstate_dirs()
318
155
        state.lock_read()
319
156
        try:
320
157
            self.setup_paths_and_offsets(state)
321
 
            offsets = self.time(self.do_bisect_list,
322
 
                                bisect_dirblock_py)
 
158
            offsets = self.time(self.do_bisect_list, dirstate.py_bisect_dirblock)
323
159
            self.checkOffsets(offsets)
324
160
        finally:
325
161
            state.unlock()
326
162
 
327
 
    def test_bisect_dirblock_cached_py(self):
328
 
        from bzrlib._dirstate_helpers_py import bisect_dirblock_py
 
163
    def test_py_bisect_dirblock_cached(self):
329
164
        state = self.build_10k_dirstate_dirs()
330
165
        state.lock_read()
331
166
        try:
332
167
            self.setup_paths_and_offsets(state)
333
168
            offsets = self.time(self.do_bisect_list_cached,
334
 
                                bisect_dirblock_py)
 
169
                                dirstate.py_bisect_dirblock)
335
170
            self.checkOffsets(offsets)
336
171
        finally:
337
172
            state.unlock()
338
173
 
339
 
    def test_bisect_dirblock_c(self):
 
174
    def test_c_bisect_dirblock(self):
340
175
        self.requireFeature(CompiledDirstateHelpersFeature)
341
 
        from bzrlib._dirstate_helpers_c import bisect_dirblock_c
 
176
        from bzrlib.compiled.dirstate_helpers import c_bisect_dirblock
342
177
        state = self.build_10k_dirstate_dirs()
343
178
        state.lock_read()
344
179
        try:
345
180
            self.setup_paths_and_offsets(state)
346
 
            offsets = self.time(self.do_bisect_list, bisect_dirblock_c)
 
181
            offsets = self.time(self.do_bisect_list, c_bisect_dirblock)
347
182
            self.checkOffsets(offsets)
348
183
        finally:
349
184
            state.unlock()
350
 
 
351
 
    def create_path_names(self, layout, base=''):
352
 
        """Create a list of paths with auto-generated names.
353
 
 
354
 
        :param layout: A list of [(num_dirs, num_files)] tuples. For each
355
 
            level, the given number of directories will be created, each
356
 
            containing that many files.
357
 
            So [(2, 5), (3, 4)] will create 2 top level directories, containing
358
 
            5 files, and each top level directory will contain 3 subdirs with 4
359
 
            files.
360
 
        :param base: The base path to prepend to all entries, most callers will
361
 
            pass ''
362
 
        :return: A list of path names.
363
 
        """
364
 
        if not layout:
365
 
            return []
366
 
 
367
 
        paths = []
368
 
        num_dirs, num_files = layout[0]
369
 
        for dnum in xrange(num_dirs):
370
 
            if base:
371
 
                path = '%s/%02d_directory' % (base, dnum)
372
 
            else:
373
 
                path = '%02d_directory' % (dnum,)
374
 
            paths.append(path)
375
 
            for fnum in xrange(num_files):
376
 
                fname = '%s/%02d_filename' % (path, fnum)
377
 
                paths.append(fname)
378
 
            paths.extend(self.create_path_names(layout[1:], base=path))
379
 
        return paths
380
 
 
381
 
    def test_create_path_names(self):
382
 
        names = self.create_path_names([(2, 3), (1, 2)])
383
 
        self.assertEqual(['00_directory',
384
 
                          '00_directory/00_filename',
385
 
                          '00_directory/01_filename',
386
 
                          '00_directory/02_filename',
387
 
                          '00_directory/00_directory',
388
 
                          '00_directory/00_directory/00_filename',
389
 
                          '00_directory/00_directory/01_filename',
390
 
                          '01_directory',
391
 
                          '01_directory/00_filename',
392
 
                          '01_directory/01_filename',
393
 
                          '01_directory/02_filename',
394
 
                          '01_directory/00_directory',
395
 
                          '01_directory/00_directory/00_filename',
396
 
                          '01_directory/00_directory/01_filename',
397
 
                         ], names)
398
 
        names = self.time(self.create_path_names, [(10, 2), (10, 2), (10, 20)])
399
 
        # 20 files + 1 directory name, 10 times, plus 2 filenames and 1 dir, 10
400
 
        # times, and another 2 files + 1 dir, 10 times
401
 
        self.assertEqual(21330, 10*(3 + 10*(3 + 10*(1 + 20))))
402
 
        self.assertEqual(21330, len(names))
403
 
 
404
 
    def compareAllPaths(self, cmp_func, layout):
405
 
        """Compare N^2 paths.
406
 
 
407
 
        Basically, compare every path in the list against every other path.
408
 
        """
409
 
        paths = self.create_path_names(layout)
410
 
        def compare_all():
411
 
            for path1 in paths:
412
 
                for path2 in paths:
413
 
                    cmp_func(path1, path2)
414
 
        self.time(compare_all)
415
 
 
416
 
    def test_cmp_by_dirs_py(self):
417
 
        """Benchmark 103041 comparisons."""
418
 
        from bzrlib._dirstate_helpers_py import cmp_by_dirs_py
419
 
        self.compareAllPaths(cmp_by_dirs_py,
420
 
                             [(3, 1), (3, 1), (3, 1), (3, 2)])
421
 
 
422
 
    def test_cmp_by_dirs_c(self):
423
 
        self.requireFeature(CompiledDirstateHelpersFeature)
424
 
        from bzrlib._dirstate_helpers_c import cmp_by_dirs_c
425
 
        self.compareAllPaths(cmp_by_dirs_c,
426
 
                             [(3, 1), (3, 1), (3, 1), (3, 2)])