Re: [PATCH v2 06/13] merge-ort: add data structures for in-memory caching of rename detection

> From: Elijah Newren <newren@gmail.com>
> 
> When there are many renames between the old base of a series of commits
> and the new base for a series of commits, the sequence of merges
> employed to transplant those commits (from a cherry-pick or rebase
> operation) will repeatedly detect the exact same renames.  This is
> wasted effort.
> 
> Add data structures which will be used to cache rename detection
> results, along with the initialization and deallocation of these data
> structures.  Future commits will populate these caches, detect the
> appropriate circumstances when they can be used, and employ them to
> avoid re-detecting the same renames repeatedly.

> @@ -140,6 +140,37 @@ struct rename_info {
>  	int callback_data_nr, callback_data_alloc;
>  	char *callback_data_traverse_path;
>  
> +	/*
> +	 * cached_pairs: Caching of renames and deletions.
> +	 *
> +	 * These are mappings recording renames and deletions of individual
> +	 * files (not directories).  They are thus a map from an old
> +	 * filename to either NULL (for deletions) or a new filename (for
> +	 * renames).
> +	 */
> +	struct strmap cached_pairs[3];
> +
> +	/*
> +	 * cached_target_names: just the destinations from cached_pairs
> +	 *
> +	 * We sometimes want a fast lookup to determine if a given filename
> +	 * is one of the destinations in cached_pairs.  cached_target_names
> +	 * is thus duplicative information, but it provides a fast lookup.
> +	 */
> +	struct strset cached_target_names[3];

> +	/*
> +	 * cached_irrelevant: Caching of rename_sources that aren't relevant.
> +	 *
> +	 * cached_pairs records both renames and deletes.  Sometimes we
> +	 * do not know if a path is a rename or a delete because we pass
> +	 * RELEVANT_LOCATION to diffcore_rename_extended() and based on
> +	 * various optimizations it returns without detecting whether that
> +	 * path is actually a rename or a delete.  We need to cache such
> +	 * paths too, but separately from cached_pairs.
> +	 */
> +	struct strset cached_irrelevant[3];