From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 106967 invoked by alias); 19 Oct 2018 08:18:08 -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 106775 invoked by uid 89); 19 Oct 2018 08:18:07 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=hacked, books, xf X-HELO: mail-oi1-f195.google.com Received: from mail-oi1-f195.google.com (HELO mail-oi1-f195.google.com) (209.85.167.195) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 19 Oct 2018 08:18:05 +0000 Received: by mail-oi1-f195.google.com with SMTP id y81-v6so26175617oia.6 for ; Fri, 19 Oct 2018 01:18:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=72ysVH5R0FOqvKvkYpYcIfnNsn+rmOHnddrHoXWZyZg=; b=I/0y8yF6x6JQNvrAL0H8iuirx5SWVUEV2hcbgqFgWEkp57eWq72HCMdaYmKRpR0l+f eGmhYV/2WKhZu5pPWP1glFexMSfBFGmtVxVk/zhjUwyYwfcDxagEDsab5R99I0ND5SZs bw/1z+FbDzTRvsz+cuiXgHBGtPRUUlMTE4hohib9yUhFeTRgkn/0PBf4yZV3zy6ORDsw ay4pa5k1Z4VLlohoAPz7PlHNtSdHBYr2kSkuaBIuVu+mWKFACOyJ9tuo2APs8d7fSMZ5 35KyY4QwvRdC1TZhWiNv66Lfu/gR+wNU0Fn9IdbyWUG24FOfZWDKFw2+tUQoNt9ARtxz jWHg== MIME-Version: 1.0 References: <877eif8ih9.fsf@arm.com> <87woqf55k3.fsf@arm.com> <74926395-0C13-4048-B9F0-62F44408D7B1@suse.de> In-Reply-To: <74926395-0C13-4048-B9F0-62F44408D7B1@suse.de> From: Steven Bosscher Date: Fri, 19 Oct 2018 09:10:00 -0000 Message-ID: Subject: Re: [PATCH] Add splay-tree "view" for bitmap To: Richard Biener Cc: richard.sandiford@arm.com, GCC Patches Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2018-10/txt/msg01177.txt.bz2 On Fri, Oct 19, 2018 at 8:46 AM Richard Biener <> wrote: > Yeah. I also noticed some 'obvious' shortcomings in the heuristics... > I guess in the end well predicted branches in the out of line code are important... What also would help is to put bitmaps on their own obstack to improve cache locality. As for the patch, I never hacked it with "production code" in mind, it was just a proof of concept. Not all of it is optimal or even safe as-is. For example you probably should add "gcc_checking_assert(!(BITMAP)->tree-form)" tests in the bmp_iter_*_init functions. And perhaps semi-splaying trees work better for the use cases of GCC (x.f. "Rehabilitation of an unloved child: semi-splaying"). I implemented classic splay trees because I could not find a semi-splay tree implementation in any of the usual text books while classic splay tree implementations were given in all of those books ;-) Ciao! Steven