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)

* svn del WC/dir/file
   because STMT_HAS_SERVER_EXCLUDED_NODES
   STMT_INSERT_DELETE_LIST
   STMT_DELETE_NODES_RECURSIVE
   STMT_INSERT_DELETE_FROM_NODE_RECURSIVE
   are O(entries in dir).

* 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
   is O(files in dir) in both calls of from
   svn_wc__db_base_get_lock_tokens_recursive()
   and STMT_DELETE_NODES_RECURSIVE is
   O(files in dir) as well.

It would be nice if these queries could be fixed for 1.8.

-- Stefan^2.
Received on 2012-05-19 22:35:10 CEST