From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.8 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5B158C433DB for ; Tue, 26 Jan 2021 20:01:53 +0000 (UTC) Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id ED00922B3B for ; Tue, 26 Jan 2021 20:01:52 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org ED00922B3B Authentication-Results: mail.kernel.org; dmarc=fail (p=quarantine dis=none) header.from=etezian.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=intel-gfx-bounces@lists.freedesktop.org Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id 9312E899A3; Tue, 26 Jan 2021 20:01:52 +0000 (UTC) X-Greylist: delayed 8400 seconds by postgrey-1.36 at gabe; Tue, 26 Jan 2021 20:01:51 UTC Received: from 1.mo4.mail-out.ovh.net (1.mo4.mail-out.ovh.net [178.33.248.196]) by gabe.freedesktop.org (Postfix) with ESMTPS id 3E671899A3 for ; Tue, 26 Jan 2021 20:01:51 +0000 (UTC) Received: from player798.ha.ovh.net (unknown [10.110.103.195]) by mo4.mail-out.ovh.net (Postfix) with ESMTP id 90BA2264C02 for ; Tue, 26 Jan 2021 18:34:54 +0100 (CET) Received: from etezian.org (213-243-141-64.bb.dnainternet.fi [213.243.141.64]) (Authenticated sender: andi@etezian.org) by player798.ha.ovh.net (Postfix) with ESMTPSA id 8E7561A82BCDE; Tue, 26 Jan 2021 17:34:49 +0000 (UTC) Authentication-Results: garm.ovh; auth=pass (GARM-96R001e0fe970e-34a9-41d5-bec1-bfca8970be0b, FCD1BBE7D880F588B4D98BD35E77FB0D8B597664) smtp.auth=andi@etezian.org X-OVh-ClientIp: 213.243.141.64 Date: Tue, 26 Jan 2021 19:34:48 +0200 From: Andi Shyti To: Chris Wilson Message-ID: References: <20210120122205.2808-1-chris@chris-wilson.co.uk> <20210120122205.2808-10-chris@chris-wilson.co.uk> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20210120122205.2808-10-chris@chris-wilson.co.uk> X-Ovh-Tracer-Id: 5961921481763635721 X-VR-SPAMSTATE: OK X-VR-SPAMSCORE: -100 X-VR-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgeduledrvdeigdegudcutefuodetggdotefrodftvfcurfhrohhfihhlvgemucfqggfjpdevjffgvefmvefgnecuuegrihhlohhuthemucehtddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenucfjughrpeffhffvuffkfhggtggujgesthdtredttddtvdenucfhrhhomheptehnughiucfuhhihthhiuceorghnughisegvthgviihirghnrdhorhhgqeenucggtffrrghtthgvrhhnpedtgfduudfhfeeuueejfeeihedtfeetgfegveehgfeuleelhfduteegieekudeifeenucfkpheptddrtddrtddrtddpvddufedrvdegfedrudeguddrieegnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmohguvgepshhmthhpqdhouhhtpdhhvghlohepphhlrgihvghrjeelkedrhhgrrdhovhhhrdhnvghtpdhinhgvtheptddrtddrtddrtddpmhgrihhlfhhrohhmpegrnhguihesvghtvgiiihgrnhdrohhrghdprhgtphhtthhopehinhhtvghlqdhgfhigsehlihhsthhsrdhfrhgvvgguvghskhhtohhprdhorhhg Subject: Re: [Intel-gfx] [PATCH 10/10] drm/i915: Improve DFS for priority inheritance X-BeenThere: intel-gfx@lists.freedesktop.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Intel graphics driver community testing & development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: intel-gfx@lists.freedesktop.org Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: intel-gfx-bounces@lists.freedesktop.org Sender: "Intel-gfx" Hi Chris, On Wed, Jan 20, 2021 at 12:22:05PM +0000, Chris Wilson wrote: > The core of the scheduling algorithm is that we compute the topological > order of the fence DAG. Knowing that we have a DAG, we should be able to > use a DFS to compute the topological sort in linear time. However, > during the conversion of the recursive algorithm into an iterative one, > the memoization of how far we had progressed down a branch was memoization? > forgotten. The result was that instead of running in linear time, it was > running in geometric time and could easily run for a few hundred > milliseconds given a wide enough graph, not the microseconds as required. > > Signed-off-by: Chris Wilson I have seen this patch long time ago... I'm r-b'eing starting from the last patch :) Reviewed-by: Andi Shyti Andi _______________________________________________ Intel-gfx mailing list Intel-gfx@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/intel-gfx