From mboxrd@z Thu Jan 1 00:00:00 1970 From: Ian Campbell Subject: Re: [OSSTEST PATCH 08/10] cs-bisection-step: Fix memoisation of search_compute_length_at Date: Fri, 24 Jul 2015 10:26:21 +0100 Message-ID: <1437729981.24746.51.camel@citrix.com> References: <1437675564-16602-1-git-send-email-ian.jackson@eu.citrix.com> <1437675564-16602-9-git-send-email-ian.jackson@eu.citrix.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Return-path: Received: from mail6.bemta3.messagelabs.com ([195.245.230.39]) by lists.xen.org with esmtp (Exim 4.72) (envelope-from ) id 1ZIZFP-0003fG-Hr for xen-devel@lists.xenproject.org; Fri, 24 Jul 2015 09:26:31 +0000 In-Reply-To: <1437675564-16602-9-git-send-email-ian.jackson@eu.citrix.com> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org To: Ian Jackson , xen-devel@lists.xenproject.org List-Id: xen-devel@lists.xenproject.org On Thu, 2015-07-23 at 19:19 +0100, Ian Jackson wrote: > There was a half-implemented memoisation. Memoisation is necessary > because otherwise the algorithm is exponential in the commit history > depth (with base equal to the commit parent fanout). > > Sort this out: > * Break out the actual computation into a ne Some stray characters here? > search_compute_length_at_intern > * Deleting the individual memo assignments, which incidentally > means we no longer miss an (unimportant) one. > * Actually having the new memoising function > search_compute_length_at > check $n->{LengthAt} (this is the bugfix). > > Signed-off-by: Ian Jackson Acked-by: Ian Campbell