All of lore.kernel.org
 help / color / mirror / Atom feed
From: Stefan Beller <sbeller@google.com>
To: Elijah Newren <newren@gmail.com>
Cc: "Junio C Hamano" <gitster@pobox.com>, git <git@vger.kernel.org>,
	"SZEDER Gábor" <szeder.dev@gmail.com>,
	"Jonathan Nieder" <jrnieder@gmail.com>,
	"Jeff King" <peff@peff.net>
Subject: Re: [PATCH v7 17/31] merge-recursive: add a new hashmap for storing directory renames
Date: Mon, 5 Feb 2018 11:44:29 -0800	[thread overview]
Message-ID: <CAGZ79kaFud05Txp6o2Qjz-kyWu9rb3vNzDGXSA5OZSY4MxyE+w@mail.gmail.com> (raw)
In-Reply-To: <CABPp-BGc0F5023yY1wRb3Gy+oXdbHAibkHYr35+zE=OnT2bQmQ@mail.gmail.com>

>> Having a stringlist of potentially new dirs sounds like the algorithm is
>> at least n^2, but how do I know? I'll read on.
>
> Yes, I suppose it's technically n^2, but n is expected to be O(1).
> While one can trivially construct a case making n arbitrarily large,
> statistically for real world repositories, I expected the mode of n to
> be 1 and the mean to be less than 2.  My original idea was to use a
> hash for possible_new_dirs, but since hashes are so painful in C and n
> should be very small anyway, I didn't bother.  If anyone can find an
> example of a real world open source repository (linux, webkit, git,
> etc.) with a merge where n is greater than about 10, I'll be
> surprised.
>
> Does that address your concern, or does it sound like I'm kicking the
> can down the road?  If it's the latter, we can switch it out.

I think that is fine for now; the real world usage matters more
than the big O notation. But maybe you want to hint at the possibility of
speedup (in the commit message or in code?), once someone produces
a slow case and digs up the code.

  parent reply	other threads:[~2018-02-05 19:44 UTC|newest]

Thread overview: 63+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-01-30 23:25 [PATCH v7 00/31] Add directory rename detection to git Elijah Newren
2018-01-30 23:25 ` [PATCH v7 01/31] directory rename detection: basic testcases Elijah Newren
2018-01-30 23:25 ` [PATCH v7 02/31] directory rename detection: directory splitting testcases Elijah Newren
2018-01-30 23:25 ` [PATCH v7 03/31] directory rename detection: testcases to avoid taking detection too far Elijah Newren
2018-01-30 23:25 ` [PATCH v7 04/31] directory rename detection: partially renamed directory testcase/discussion Elijah Newren
2018-01-30 23:25 ` [PATCH v7 05/31] directory rename detection: files/directories in the way of some renames Elijah Newren
2018-01-30 23:25 ` [PATCH v7 06/31] directory rename detection: testcases checking which side did the rename Elijah Newren
2018-01-30 23:25 ` [PATCH v7 07/31] directory rename detection: more involved edge/corner testcases Elijah Newren
2018-01-30 23:25 ` [PATCH v7 08/31] directory rename detection: testcases exploring possibly suboptimal merges Elijah Newren
2018-01-30 23:25 ` [PATCH v7 09/31] directory rename detection: miscellaneous testcases to complete coverage Elijah Newren
2018-01-30 23:25 ` [PATCH v7 10/31] directory rename detection: tests for handling overwriting untracked files Elijah Newren
2018-01-30 23:25 ` [PATCH v7 11/31] directory rename detection: tests for handling overwriting dirty files Elijah Newren
2018-01-30 23:25 ` [PATCH v7 12/31] merge-recursive: move the get_renames() function Elijah Newren
2018-02-02 23:27   ` Stefan Beller
     [not found]     ` <CABPp-BFDgDDa_fPSFJQUSzR1k5-ix0SWrviUPFu+SCoyWfG5cQ@mail.gmail.com>
2018-02-05 18:57       ` Stefan Beller
2018-01-30 23:25 ` [PATCH v7 13/31] merge-recursive: introduce new functions to handle rename logic Elijah Newren
2018-02-02 23:36   ` Stefan Beller
2018-01-30 23:25 ` [PATCH v7 14/31] merge-recursive: fix leaks of allocated renames and diff_filepairs Elijah Newren
2018-02-02 23:41   ` Stefan Beller
2018-01-30 23:25 ` [PATCH v7 15/31] merge-recursive: make !o->detect_rename codepath more obvious Elijah Newren
2018-02-02 23:48   ` Stefan Beller
2018-01-30 23:25 ` [PATCH v7 16/31] merge-recursive: split out code for determining diff_filepairs Elijah Newren
2018-02-03  0:06   ` Stefan Beller
2018-02-03  1:43     ` Elijah Newren
2018-01-30 23:25 ` [PATCH v7 17/31] merge-recursive: add a new hashmap for storing directory renames Elijah Newren
2018-02-03  0:26   ` Stefan Beller
2018-02-03 21:34     ` Elijah Newren
2018-02-04  8:54       ` Johannes Sixt
2018-02-05 14:56         ` Elijah Newren
2018-02-05 20:01         ` Junio C Hamano
2018-02-05 19:44       ` Stefan Beller [this message]
2018-02-05 21:27         ` Elijah Newren
2018-01-30 23:25 ` [PATCH v7 18/31] merge-recursive: make a helper function for cleanup for handle_renames Elijah Newren
2018-02-03  0:31   ` Stefan Beller
2018-01-30 23:25 ` [PATCH v7 19/31] merge-recursive: add get_directory_renames() Elijah Newren
2018-02-03  1:02   ` Stefan Beller
2018-02-03 22:32     ` Elijah Newren
2018-02-04  2:04       ` Elijah Newren
2018-02-04  4:42         ` Eric Sunshine
2018-02-04  4:44           ` Eric Sunshine
2018-02-05 19:39       ` Stefan Beller
2018-01-30 23:25 ` [PATCH v7 20/31] merge-recursive: check for directory level conflicts Elijah Newren
2018-02-05 20:00   ` Stefan Beller
2018-02-05 21:12     ` Elijah Newren
2018-01-30 23:25 ` [PATCH v7 21/31] merge-recursive: add a new hashmap for storing file collisions Elijah Newren
2018-02-05 20:02   ` Stefan Beller
2018-01-30 23:25 ` [PATCH v7 22/31] merge-recursive: add computation of collisions due to dir rename & merging Elijah Newren
2018-01-30 23:25 ` [PATCH v7 23/31] merge-recursive: check for file level conflicts then get new name Elijah Newren
2018-01-30 23:25 ` [PATCH v7 24/31] merge-recursive: when comparing files, don't include trees Elijah Newren
2018-01-30 23:25 ` [PATCH v7 25/31] merge-recursive: apply necessary modifications for directory renames Elijah Newren
2018-02-16  1:14   ` SZEDER Gábor
2018-01-30 23:25 ` [PATCH v7 26/31] merge-recursive: avoid clobbering untracked files with " Elijah Newren
2018-01-30 23:25 ` [PATCH v7 27/31] merge-recursive: fix overwriting dirty files involved in renames Elijah Newren
2018-02-05 20:52   ` Stefan Beller
2018-02-05 21:26     ` Elijah Newren
2018-01-30 23:25 ` [PATCH v7 28/31] merge-recursive: fix remaining directory rename + dirty overwrite cases Elijah Newren
2018-02-05 21:52   ` Stefan Beller
2018-02-05 22:18     ` Elijah Newren
2018-01-30 23:25 ` [PATCH v7 29/31] directory rename detection: new testcases showcasing a pair of bugs Elijah Newren
2018-01-30 23:25 ` [PATCH v7 30/31] merge-recursive: avoid spurious rename/rename conflict from dir renames Elijah Newren
2018-01-30 23:25 ` [PATCH v7 31/31] merge-recursive: ensure we write updates for directory-renamed file Elijah Newren
2018-02-05 21:58   ` Stefan Beller
2018-01-30 23:41 ` [PATCH v7 00/31] Add directory rename detection to git Elijah Newren

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAGZ79kaFud05Txp6o2Qjz-kyWu9rb3vNzDGXSA5OZSY4MxyE+w@mail.gmail.com \
    --to=sbeller@google.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=jrnieder@gmail.com \
    --cc=newren@gmail.com \
    --cc=peff@peff.net \
    --cc=szeder.dev@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.