[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

[PATCH] Fix O(n) runtime in cache lookup, part 2/2

From: Stefan Fuhrman <stefanfuhrmann_at_alice-dsl.de>
Date: Tue, 06 Apr 2010 19:56:12 +0200

Hi devs,

this is a follow-up to the previous patch.
It uses the extended cache interface to
bring directory traversal times down from
O(N^2) to amortized O(N).

dir_entry_id_from_node now calls the new
svn_fs_fs__dag_dir_entry function that
duplicates only one entry instead of all
under the given node.

[[[
Allow for cache entries to be access directly, i.e. without
prior copying. Use that to fix FSFS directory traversal
runtime from O(N^2) to O(n).

* subversion/libsvn_fs_fs/dag.c
  (dir_entry_id_from_node): call the new, efficient
  lookup function.
  (svn_fs_fs__dag_dir_entry): implement the new
  lookup function
  (svn_fs_fs__dag_dir_entries, svn_fs_fs__dag_delete):
  adapt to svn_fs_fs__rep_contents_dir signature change

* subversion/libsvn_fs_fs/dag.h
  (svn_fs_fs__dag_dir_entry): declare new function

* subversion/libsvn_fs_fs/fs_fs.c
  (svn_fs_fs__rep_contents_dir): add support for optionally
  returning a pinned cache reference instead of a copy.
  (svn_fs_fs__set_entry, write_final_rev): adapt to
  svn_fs_fs__rep_contents_dir signature change

* subversion/libsvn_fs_fs/fs_fs.h
  (svn_fs_fs__rep_contents_dir): add pin parameter

patch by stefanfuhrmann < at > alice-dsl.de
]]]

Index: subversion/libsvn_fs_fs/dag.c
===================================================================
--- subversion/libsvn_fs_fs/dag.c (revision 930220)
+++ subversion/libsvn_fs_fs/dag.c (working copy)
@@ -310,16 +310,10 @@
                        const char *name,
                        apr_pool_t *pool)
 {
- apr_hash_t *entries;
   svn_fs_dirent_t *dirent;
   apr_pool_t *subpool = svn_pool_create(pool);
 
- SVN_ERR(svn_fs_fs__dag_dir_entries(&entries, parent, subpool, pool));
- if (entries)
- dirent = apr_hash_get(entries, name, APR_HASH_KEY_STRING);
- else
- dirent = NULL;
-
+ SVN_ERR(svn_fs_fs__dag_dir_entry(&dirent, parent, name, subpool));
   *id_p = dirent ? svn_fs_fs__id_copy(dirent->id, pool) : NULL;
 
   svn_pool_destroy(subpool);
@@ -435,10 +429,55 @@
     return svn_error_create(SVN_ERR_FS_NOT_DIRECTORY, NULL,
                             _("Can't get entries of non-directory"));
 
- return svn_fs_fs__rep_contents_dir(entries, node->fs, noderev, pool);
+ return svn_fs_fs__rep_contents_dir(entries, node->fs, noderev, NULL, pool);
 }
 
+svn_error_t *
+svn_fs_fs__dag_dir_entry(svn_fs_dirent_t **dirent,
+ dag_node_t *node,
+ const char* name,
+ apr_pool_t *pool)
+{
+ apr_hash_t *entries;
+ node_revision_t *noderev;
+ fs_fs_data_t *ffd;
+ svn_boolean_t pinned = TRUE;
+ svn_fs_dirent_t *entry;
 
+ SVN_ERR(get_node_revision(&noderev, node, pool));
+
+ if (noderev->kind != svn_node_dir)
+ return svn_error_create(SVN_ERR_FS_NOT_DIRECTORY, NULL,
+ _("Can't get entries of non-directory"));
+
+ /* Get a dirent hash for this directory. */
+ SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, node->fs, noderev,
+ &pinned, pool));
+
+ /* Find name in the ENTRIES hash. */
+ entry = apr_hash_get(entries, name, APR_HASH_KEY_STRING);
+
+ /* Duplicate the result. */
+ if (entry)
+ {
+ svn_fs_dirent_t *new_entry = apr_palloc(pool, sizeof(*entry));
+ new_entry->name = apr_pstrdup(pool, entry->name);
+ new_entry->kind = entry->kind;
+ new_entry->id = svn_fs_fs__id_copy(entry->id, pool);
+
+ *dirent = new_entry;
+ }
+ else
+ *dirent = NULL;
+
+ /* Cleanup, if necessary */
+ ffd = node->fs->fsap_data;
+ return pinned
+ ? svn_cache__unpin((void **) entries, ffd->dir_cache, pool)
+ : SVN_NO_ERROR;
+}
+
+
 svn_error_t *
 svn_fs_fs__dag_set_entry(dag_node_t *node,
                          const char *entry_name,
@@ -769,7 +808,7 @@
   subpool = svn_pool_create(pool);
 
   /* Get a dirent hash for this directory. */
- SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, parent_noderev, subpool));
+ SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, parent_noderev, NULL, subpool));
 
   /* Find name in the ENTRIES hash. */
   dirent = apr_hash_get(entries, name, APR_HASH_KEY_STRING);
Index: subversion/libsvn_fs_fs/dag.h
===================================================================
--- subversion/libsvn_fs_fs/dag.h (revision 930220)
+++ subversion/libsvn_fs_fs/dag.h (working copy)
@@ -304,6 +304,14 @@
                                         apr_pool_t *pool,
                                         apr_pool_t *node_pool);
 
+/* Fetches the NODE's entries and returns a copy of the entry selected
+ by the key value given in NAME and set *DIRENT to a copy of that
+ entry. If such entry was found, the copy will be allocated in POOL.
+ Otherwise, the *DIRENT will be set to NULL. */
+svn_error_t * svn_fs_fs__dag_dir_entry(svn_fs_dirent_t **dirent,
+ dag_node_t *node,
+ const char* name,
+ apr_pool_t *pool);
 
 /* Set ENTRY_NAME in NODE to point to ID (with kind KIND), allocating
    from POOL. NODE must be a mutable directory. ID can refer to a
Index: subversion/libsvn_fs_fs/fs_fs.c
===================================================================
--- subversion/libsvn_fs_fs/fs_fs.c (revision 930220)
+++ subversion/libsvn_fs_fs/fs_fs.c (working copy)
@@ -3664,6 +3664,7 @@
 svn_fs_fs__rep_contents_dir(apr_hash_t **entries_p,
                             svn_fs_t *fs,
                             node_revision_t *noderev,
+ svn_boolean_t* pin,
                             apr_pool_t *pool)
 {
   fs_fs_data_t *ffd = fs->fsap_data;
@@ -3677,12 +3678,24 @@
       svn_boolean_t found;
 
       unparsed_id = svn_fs_fs__id_unparse(noderev->id, pool)->data;
- SVN_ERR(svn_cache__get((void **) entries_p, &found, ffd->dir_cache,
- unparsed_id, pool));
+
+ /* Cache lookup. Get a pinned reference if *pin has been set. */
+ if (pin && *pin)
+ SVN_ERR(svn_cache__get_pinned((void **) entries_p, &found, ffd->dir_cache,
+ unparsed_id, pool));
+ else
+ SVN_ERR(svn_cache__get((void **) entries_p, &found, ffd->dir_cache,
+ unparsed_id, pool));
+
       if (found)
         return SVN_NO_ERROR;
     }
 
+ /* not in cache (yet)
+ -> nothing has been pinned and nothing will be pinned this time. */
+ if (pin)
+ *pin = FALSE;
+
   /* Read in the directory hash. */
   unparsed_entries = apr_hash_make(pool);
   SVN_ERR(get_dir_contents(unparsed_entries, fs, noderev, pool));
@@ -4867,7 +4880,7 @@
         /* Before we can modify the directory, we need to dump its old
            contents into a mutable representation file. */
         SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, parent_noderev,
- subpool));
+ NULL, subpool));
         SVN_ERR(unparse_dir_entries(&entries, entries, subpool));
         SVN_ERR(svn_io_file_open(&file, filename,
                                  APR_WRITE | APR_CREATE | APR_BUFFERED,
@@ -5518,7 +5531,7 @@
       /* This is a directory. Write out all the children first. */
       subpool = svn_pool_create(pool);
 
- SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, noderev, pool));
+ SVN_ERR(svn_fs_fs__rep_contents_dir(&entries, fs, noderev, NULL, pool));
 
       for (hi = apr_hash_first(pool, entries); hi; hi = apr_hash_next(hi))
         {
Index: subversion/libsvn_fs_fs/fs_fs.h
===================================================================
--- subversion/libsvn_fs_fs/fs_fs.h (revision 930220)
+++ subversion/libsvn_fs_fs/fs_fs.h (working copy)
@@ -115,10 +115,16 @@
 /* Set *ENTRIES to an apr_hash_t of dirent structs that contain the
    directory entries of node-revision NODEREV in filesystem FS. The
    returned table (and its keys and values) is allocated in POOL,
- which is also used for temporary allocations. */
+ which is also used for temporary allocations.
+ If *pin is TRUE, directory entries that have already been cached
+ will be returned as pinned references instead of copies. Otherwise,
+ pin may be NULL. After the function returned, *pin will then indicate
+ whether the cache lookup was successful and the caller must unpin
+ the *entries explicitly, in that case. */
 svn_error_t *svn_fs_fs__rep_contents_dir(apr_hash_t **entries,
                                          svn_fs_t *fs,
                                          node_revision_t *noderev,
+ svn_boolean_t* pin,
                                          apr_pool_t *pool);
 
 /* Set *CONTENTS to be a readable svn_stream_t that receives the text
Received on 2010-04-06 19:56:43 CEST

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.