Re: Fwd: [Daniel Shahaf: Re: svn commit: r1409883 - in /subversion/trunk/subversion: libsvn_wc/externals.c tests/cmdline/externals_tests.py]

[Daniel Shahaf <d....@daniel.shahaf.name>]

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
>