Neels J Hofmeyr wrote on Fri, Nov 16, 2012 at 09:56:38 +0100:
> On 2012-11-16 04:49, Daniel Shahaf wrote:
> >>> {
> >>> int i;
> >>> + int j;
> >>> apr_array_header_t *externals = NULL;
> >>> apr_array_header_t *lines = svn_cstring_split(desc, "\n\r", TRUE,
> >>> pool);
> >>> const char *parent_directory_display =
> >>> svn_path_is_url(parent_directory) ?
> >>> parent_directory : svn_dirent_local_style(parent_directory, pool);
> >>>
> >>> /* If an error occurs halfway through parsing, *externals_p should stay
> >>> - * untouched. So, store the list in a local var first. */
> >>> - if (externals_p)
> >>> - externals = apr_array_make(pool, 1, sizeof(svn_wc_external_item2_t
> >>> *));
> >>> + * untouched. So, store the list in a local var first. Since we are
> >>> checking
> >>> + * for duplicate targets, always compose the list regardless. */
> >>> + externals = apr_array_make(pool, 1, sizeof(svn_wc_external_item2_t *));
> >>>
> >>> for (i = 0; i < lines->nelts; i++)
> >>> {
> >>> @@ -330,8 +331,23 @@ svn_wc_parse_externals_description3(apr_
> >>> item->url = svn_dirent_canonicalize(item->url, pool);
> >>> }
> >>>
> >>> - if (externals)
> >>> - APR_ARRAY_PUSH(externals, svn_wc_external_item2_t *) = item;
> >>> + /* Has the same WC target path already been mentioned in this
> >>> prop? */
> >>> + for (j = 0; j < externals->nelts; j++)
> >>> + {
> >>
> >> This looks like an O(n²) algorithm, maybe implement something more
> >> efficient?
> >>
> >> e.g., you could construct a hash with all ->target_dir's as keys, and
> >> then check whether (apr_hash_count() == externals->nelts).
>
> That's right, didn't think of that. But the return value of the function is
> an apr_list. The function would have to record two lists or change the
> apr_hash into a list.
>
Right, the hash would be an implementation detail.
> It's not like there usually are tens of thousands of externals definitions
> in one prop... Do you think this is still worth a patch? Frankly, I guess
> that no user will ever be able to experience any difference.
>
I haven't calculated how many external definitions are needed for the
slowdown to be noticeable (due to the iterations only, or due to cache
misses), but I don't want to assume that no one will ever have more than
X lines in a single svn:externals property. (I am not aware personally
of anyone who has, say, 100 external definitions on one directory, but
I wouldn't be surprised at all if someone out there does exactly that.)
Makes sense?
> ~Neels
>
