From nobody Sat Mar 25 22:29:47 2023 X-Original-To: freebsd-current@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4PkYfn1WTyz41pBZ for ; Sat, 25 Mar 2023 22:29:53 +0000 (UTC) (envelope-from thj@freebsd.org) Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com [66.111.4.25]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4PkYfm6lGxz472g for ; Sat, 25 Mar 2023 22:29:52 +0000 (UTC) (envelope-from thj@freebsd.org) Authentication-Results: mx1.freebsd.org; none Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailout.nyi.internal (Postfix) with ESMTP id 35A2F5C00C0; Sat, 25 Mar 2023 18:29:52 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute5.internal (MEProxy); Sat, 25 Mar 2023 18:29:52 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:content-type:date:date :feedback-id:feedback-id:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:sender:subject :subject:to:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm2; t=1679783392; x=1679869792; bh=kHMCn/a8AdopF RUQBc4hn98ZrhBaPjuaWXMY0MOjmwE=; b=MAqsssM7laFso3DhzZMlJyXqThuBx CGK91XTQTrPDaN/rUDATPhNw1Q3NzAzlczmg5vTQkrHFYX7zZNIEDrk9ZqgO/wVF 4o7oPjAUvZrK0rtNkEBS3dgo1JSCxCYp1twjYt8njk0FK4MMz1DwqLyqESxRxkDf Xz3RBTldOexyCAc5miHdI2CfvA0IPX71JKTWublGF9WRFSgKfctmdtd7gWIP868c NILD6fYDphbos7+KTIBi2uZo/bM3aVCY1B3RHEY8JgQqIYVZjFVbIiDwfsWbJ860 4hrYEpSqSJ3DKB8iVvENdBSl4FmwVJM3A54RisiKNpTlmh7DOQaDhx6Eg== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvhedrvdegkedgudeihecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehttdertddttddvnecuhfhrohhmpefvohhm ucflohhnvghsuceothhhjhesfhhrvggvsghsugdrohhrgheqnecuggftrfgrthhtvghrnh eptdegueevjeeitddvtdefjeeiteelieeufeelfffhkeettedugeeiheevieegudeunecu ffhomhgrihhnpegtrghtfhhlrghprdhorhhgpdhfrhgvvggsshgurdhorhhgnecuvehluh hsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepthhhjhesfhhrvggv sghsugdrohhrgh X-ME-Proxy: Feedback-ID: ib75146ab:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Sat, 25 Mar 2023 18:29:51 -0400 (EDT) Date: Sat, 25 Mar 2023 22:29:47 +0000 From: Tom Jones To: Jamie Landeg-Jones Cc: freebsd-current@freebsd.org Subject: Re: diff(1) goes into cpu-hogging endless loop Message-ID: References: <202303252155.32PLtEPF072349@donotpassgo.dyslexicfish.net> List-Id: Discussions about the use of FreeBSD-current List-Archive: https://lists.freebsd.org/archives/freebsd-current List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-freebsd-current@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <202303252155.32PLtEPF072349@donotpassgo.dyslexicfish.net> X-Rspamd-Queue-Id: 4PkYfm6lGxz472g X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:19151, ipnet:66.111.4.0/24, country:US] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On Sat, Mar 25, 2023 at 09:55:14PM +0000, Jamie Landeg-Jones wrote: > Hi, A "diff" of 2 files: > > 1 77,933,904 bytes > 2 63,013,818 bytes > > , goes into an endless loop, whilst "gdiff" completes the operation in > about 5 seconds. > > I tested using the latest "diff" from current, and get the same result. > > Splitting both files into 10Mb chunks, and diffing these was successful. > > A ktrace of the "diff" actually stops producing any output after about > 5 seconds, whilst the cpu looping continues. > > Any ideas on what to do next? Does anyone else get the same result? > > The files are just utf-8 freebsd git logs, and are available here if > anyone would like to test: > > http://www.catflap.org/jamie/1.xz (13,282,864 bytes) > http://www.catflap.org/jamie/2.xz (12,221,164 bytes) > > Cheers, Jamie My guess is that you are hitting a worst case in the stone algorithm. I have a WIP review to integrate the Myers algorithm from libdiff here: https://reviews.freebsd.org/D36860 - Tom