From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 62805 invoked by alias); 17 Apr 2019 20:17:22 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 62797 invoked by uid 89); 17 Apr 2019 20:17:21 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00,SPF_PASS autolearn=ham version=3.3.1 spammy=H*R:D*gcc.gnu.org, H*R:D*gnu.org, Competitive, Marc X-HELO: mail3-relais-sop.national.inria.fr Received: from mail3-relais-sop.national.inria.fr (HELO mail3-relais-sop.national.inria.fr) (192.134.164.104) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 17 Apr 2019 20:17:20 +0000 Received: from 85-171-184-78.rev.numericable.fr (HELO stedding) ([85.171.184.78]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 17 Apr 2019 22:17:17 +0200 Date: Wed, 17 Apr 2019 20:36:00 -0000 From: Marc Glisse Reply-To: gcc-patches@gcc.gnu.org To: Jeff Law cc: Richard Biener , gcc-patches@gcc.gnu.org, Jakub Jelinek Subject: Re: [PATCH][RFC] Improve get_qualified_type linear list walk In-Reply-To: <52598ebb-fe58-fa8f-976e-8c21f5980055@redhat.com> Message-ID: References: <52598ebb-fe58-fa8f-976e-8c21f5980055@redhat.com> User-Agent: Alpine 2.21 (DEB 202 2017-01-01) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed X-SW-Source: 2019-04/txt/msg00739.txt.bz2 On Wed, 17 Apr 2019, Jeff Law wrote: >> * tree.c (get_qualified_type): Put found type variants at the >> head of the variant list. > Seems quite reasonable to me. I just hope we don't find a case where > this is the exact worst case behavior ;-) That seems unlikely. Competitive analysis of the list update problem shows that the move-to-front strategy is 2-competitive. Here we also have insertions so the problem is different, but still close. -- Marc Glisse