From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jeff King Subject: Re: move detection doesnt take filename into account Date: Wed, 9 Jul 2014 18:03:37 -0400 Message-ID: <20140709220337.GF25854@sigill.intra.peff.net> References: <53B105DA.30004@gmail.com> <287177519.16421.1404206204124.JavaMail.zimbra@dewire.com> <53B2CE4A.9060509@gmail.com> <20140709064521.GA14682@sigill.intra.peff.net> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Cc: Elliot Wolk , Robin Rosenberg , git@vger.kernel.org To: Junio C Hamano X-From: git-owner@vger.kernel.org Thu Jul 10 00:03:46 2014 Return-path: Envelope-to: gcvg-git-2@plane.gmane.org Received: from vger.kernel.org ([209.132.180.67]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1X4zxn-0006dA-P4 for gcvg-git-2@plane.gmane.org; Thu, 10 Jul 2014 00:03:44 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751749AbaGIWDk (ORCPT ); Wed, 9 Jul 2014 18:03:40 -0400 Received: from cloud.peff.net ([50.56.180.127]:59015 "HELO peff.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1751169AbaGIWDj (ORCPT ); Wed, 9 Jul 2014 18:03:39 -0400 Received: (qmail 11464 invoked by uid 102); 9 Jul 2014 22:03:39 -0000 Received: from c-71-63-4-13.hsd1.va.comcast.net (HELO sigill.intra.peff.net) (71.63.4.13) (smtp-auth username relayok, mechanism cram-md5) by peff.net (qpsmtpd/0.84) with ESMTPA; Wed, 09 Jul 2014 17:03:39 -0500 Received: by sigill.intra.peff.net (sSMTP sendmail emulation); Wed, 09 Jul 2014 18:03:37 -0400 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: On Wed, Jul 09, 2014 at 08:51:07AM -0700, Junio C Hamano wrote: > > The delta heuristics in pack-objects use pack_name_hash, which claims: > > > > /* > > * This effectively just creates a sortable number from the > > * last sixteen non-whitespace characters. Last characters > > * count "most", so things that end in ".c" sort together. > > */ > > > > which might be another option (and seems like a superset of the basename > > check, short of basenames that are longer than 16 characters). > > Perhaps. > > I am however not sure if the code to compute similarity score is as > OK with false positives, i.e. dissimilar names that happen to hash > together getting clumped in a same bin or in close bins, as the > existing callers of pack_name_hash(). I think the hash here does not collide in that way. It really is just the last sixteen characters shoved into a uint32_t. But thinking on it more, that is useful to the delta code because it wants to create a sorted list of items. In the rename code we are doing pairwise comparisons, so we are more flexible. We can compare whole basenames, or whole suffixes (so "a/foo/bar.c" is closer to "b/foo/bar.c" than to "c/other/bar.c"). Or just use a general-purpose edit-distance function. The tricky part is that the rename detection seems to take the score as a binary 0/1 "is it the same", but we would want to express more nuance (i.e., the "best" match among those that have similar content scores). -Peff