| Message ID | 20250213090040.16133-1-meetsoni3017@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | merge-recursive: optimize time complexity | expand |
Hi everyone. Adding the missing CCs who were unintentionally dropped in my original email. Please refer to the previous message for the patch details. Link to the patch: https://lore.kernel.org/git/20250213090040.16133-1-meetsoni3017@gmail.com/ Thanks, Meet
Hi, On Thu, Feb 13, 2025 at 1:01 AM Meet Soni <meetsoni3017@gmail.com> wrote: > > changes in this version: > - Updated comment and commit message as per review. > - Added another commit implementing optimization logic. > - added an RFC tag since, if the changes in 2nd commit are > appropriate, we can apply similar logic in other places as > well. The 1st patch looks good. The 2nd appears to have some problems, as per comments I left on it -- it might be easier to drop the second patch and just apply the first. I don't think merge-recursive is worth putting much effort into (there's value in providing feedback on patches by new contributors, because new contributors are valuable, but there's really not much value in tweaking this particular file), so I'd advise against adding more patches to this series that transform more of merge-recursive.
changes in this version: - Updated comment and commit message as per review. - Added another commit implementing optimization logic. - added an RFC tag since, if the changes in 2nd commit are appropriate, we can apply similar logic in other places as well. Meet Soni (2): merge-recursive: optimize time complexity for process_renames merge-recursive: optimize time complexity for get_unmerged merge-recursive.c | 25 ++++++++++++------------- 1 file changed, 12 insertions(+), 13 deletions(-) Range-diff: 1: ec96e4010e ! 1: c7dca6e971 merge-recursive: optimize string_list construction @@ Metadata Author: Meet Soni <meetsoni3017@gmail.com> ## Commit message ## - merge-recursive: optimize string_list construction + merge-recursive: optimize time complexity for process_renames - Avoid O(n^2) complexity when building a sorted `string_list` by - constructing it unsorted and sorting it afterward, reducing the - complexity to O(n log n). + Avoid O(n^2) complexity in `process_renames()` when building a sorted + `string_list` by constructing it unsorted and sorting it afterward, + reducing the complexity to O(n log n). Signed-off-by: Meet Soni <meetsoni3017@gmail.com> ## merge-recursive.c ## @@ merge-recursive.c: static int process_renames(struct merge_options *opt, - struct string_list b_by_dst = STRING_LIST_INIT_NODUP; const struct rename *sre; -- /* + /* - * FIXME: As string-list.h notes, it's O(n^2) to build a sorted - * string_list one-by-one, but O(n log n) to build it unsorted and - * then sort it. Note that as we build the list, we do not need to - * check if the existing destination path is already in the list, - * because the structure of diffcore_rename guarantees we won't - * have duplicates. -- */ ++ * Note that as we build the list, we do not need to check if the ++ * existing destination path is already in the list, because the ++ * structure of diffcore_rename guarantees we won't have duplicates. + */ for (i = 0; i < a_renames->nr; i++) { sre = a_renames->items[i].util; - string_list_insert(&a_by_dst, sre->pair->two->path)->util -: ---------- > 2: 78a007be7d merge-recursive: optimize time complexity for get_unmerged