Hi Bert,
In short: excellent work! With your latest changes,
all algorithmic issues have been resolved as already
confirmed on IRC. Two places in the server could
also be improved (r1340874-5).
Note to package builders: Sqlite 3.7.7 will not use
all available indexes while 3.7.12 does (an possibly
earlier ones). Deletion will still be slow with those
old versions.
To illustrate how much performance improved since
April here the original results:
Processing 16384 files in the same folder
Creating files ... real user sys
Adding files ... 10.174 8.317 1.780
Running status ... 0.235 0.196 0.036
Commit files ... 19.434 8.997 6.116
Listing files ... 0.157 0.064 0.012
Updating files ... 0.312 0.292 0.012
Local copy ... 5228.840 4998.244 215.085
Commit copy ... 3.398 2.304 1.012
Delete 1 file ... 0.275 0.260 0.012
Deleting files ... 5025.387 4521.755 455.236
Commit deletions ... 1681.892 1508.402 94.458
Export all ... 1.758 1.012 0.720
Check out all ... 17.582 9.533 7.828
Now look at HEAD results:
Processing 16384 files in the same folder
Creating files ... real user sys
Adding files ... 9.590 7.896 1.620
Running status ... 0.135 0.084 0.048
Commit files ... 14.130 5.676 4.908
Listing files ... 0.105 0.036 0.012
Updating files ... 0.267 0.244 0.016
Local copy ... 10.023 5.344 4.592
Commit copy ... 0.675 0.568 0.064
Delete 1 file ... 0.009 0.004 0.004
Deleting files ... 6.686 4.892 1.744
Commit deletions .. 17.530 4.016 2.320
Export all ... 1.259 0.604 0.632
Check out all ... 14.026 6.640 7.236
(some ra_svn improvements can be seen in list,
export and such).
-- Stefan^2.
Bert Huijben wrote:
>
>> -----Original Message-----
>> From: Stefan Fuhrmann [mailto:stefanfuhrmann_at_alice-dsl.de]
>> Sent: zaterdag 19 mei 2012 20:34
>> To: Subversion Development
>> Subject: Working copy operations that are worse than O(change size)
>>
>> Hi Bert& interested parties,
>>
>> as promised, I ran the create_bigdir.sh benchmark with the
>> latest commit harvester improvements (r1340484). While
>> I do see some speedup, the following operations have runtime
>> that is not proportional to the size of the change, i.e. they
>> exhibit O(n^2) behavior.
>>
>> All statements are run in directories that are directly below
>> the WC root and contain(ed) no sub-directories.
>>
>> * svn cp WC/dir1 WC/dir2
>> because STMT_INSERT_WORKING_NODE_COPY_FROM_BASE
>> is O(entries in dir1)
> This query was O(entries-in-wc). This query is O(n) now.
> (It is evaluated for every node that is copied)
>
>> * svn del WC/dir/file
>> because STMT_HAS_SERVER_EXCLUDED_NODES
> This query is no longer evaluated for files that are deleted; only for BASE
> directories that are deleted.
> And this query properly uses an index now.
>
>> STMT_INSERT_DELETE_LIST
> I have an alternative implementation that should be more efficient if I look
> at the query plan, but my measurements don't show a difference.
>
> /* This matches the selection in STMT_INSERT_DELETE_FROM_NODE_RECURSIVE.
> A subquery is used instead of nodes_current to avoid a table scan */
> -- STMT_INSERT_DELETE_LIST
> INSERT INTO delete_list(local_relpath)
> SELECT local_relpath FROM nodes AS n
> WHERE wc_id = ?1
> AND (local_relpath = ?2
> OR IS_STRICT_DESCENDANT_OF(local_relpath, ?2))
> AND op_depth>= ?3
> AND op_depth = (SELECT MAX(s.op_depth) FROM nodes AS s
> WHERE s.wc_id = ?1
> AND s.local_relpath = n.local_relpath)
> AND presence NOT IN ('base-deleted', 'not-present', 'excluded', 'absent')
>
> This one uses the right index, while the current one doesn't.
>
> It appears that for me most time is spend in the INSERT part; not in the
> SELECT.
> (Even if I change it to a simple INSERT, the profiled result is the same)
>
>> STMT_DELETE_NODES_RECURSIVE
> Split in two queries. Uses the right index now
>
>> STMT_INSERT_DELETE_FROM_NODE_RECURSIVE
>> are O(entries in dir).
> I can't find an O(nodes) behavior on this query. It does use the right
> indexes.
> (And the query plan contains the pristine refcount triggers)
>> * svn ci WC/dir
>> after deleting every single file in dir
>> is O(files in dir ^ 2) because
>> STMT_SELECT_BASE_NODE_LOCK_TOKENS_RECURSIVE
> This query uses an index now (was table scan)
>
>> is O(files in dir) in both calls of from
>> svn_wc__db_base_get_lock_tokens_recursive()
>> and STMT_DELETE_NODES_RECURSIVE is
> Split in two queries. The delete and relpath revert code paths use an index
> now.
> (That leaves the wcroot revert case, which really needs a table scan)
>
>> O(files in dir) as well.
>>
>> It would be nice if these queries could be fixed for 1.8.
> I think most are fixed now :)
>
>
> Most of these show huge performance improvements on large working copies,
> but on the small working copies from our test suite a table scan is often
> slightly faster than an index lookup, followed by looking up the actual
> record.
>
> Bert
>
>
Received on 2012-05-21 02:36:48 CEST