From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 7568 invoked by alias); 6 Aug 2012 11:27:46 -0000 Received: (qmail 7560 invoked by uid 22791); 6 Aug 2012 11:27:46 -0000 X-SWARE-Spam-Status: No, hits=-5.0 required=5.0 tests=AWL,BAYES_00,DKIM_SIGNED,DKIM_VALID,FREEMAIL_FROM,KHOP_RCVD_TRUST,KHOP_THREADED,RCVD_IN_DNSWL_LOW,RCVD_IN_HOSTKARMA_YE,TW_FC X-Spam-Check-By: sourceware.org Received: from mail-pb0-f47.google.com (HELO mail-pb0-f47.google.com) (209.85.160.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 06 Aug 2012 11:27:33 +0000 Received: by pbcwy7 with SMTP id wy7so1535207pbc.20 for ; Mon, 06 Aug 2012 04:27:32 -0700 (PDT) Received: by 10.68.225.70 with SMTP id ri6mr7721962pbc.128.1344252452579; Mon, 06 Aug 2012 04:27:32 -0700 (PDT) Received: from yakj.usersys.redhat.com (93-34-169-1.ip50.fastwebnet.it. [93.34.169.1]) by mx.google.com with ESMTPS id nr8sm5371385pbc.43.2012.08.06.04.27.29 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 06 Aug 2012 04:27:31 -0700 (PDT) Message-ID: <501FAA1E.1040000@gnu.org> Date: Mon, 06 Aug 2012 11:27:00 -0000 From: Paolo Bonzini User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120615 Thunderbird/13.0.1 MIME-Version: 1.0 To: Steven Bosscher CC: GCC Patches Subject: Re: [patch] speed up ifcvt:cond_move_convert_if_block References: <501FA55B.7030706@gnu.org> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit 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 X-SW-Source: 2012-08/txt/msg00296.txt.bz2 Il 06/08/2012 13:15, Steven Bosscher ha scritto: > On Mon, Aug 6, 2012 at 1:07 PM, Paolo Bonzini wrote: >> Il 06/08/2012 08:54, Steven Bosscher ha scritto: >>> Hello, >>> >>> In PR54146, ifcvt spends a lot of time just clearing memory. This >>> patch changes the value maps to pointer-maps to fix this issue. >>> >>> Bootstrapped&tested on x86_64-unknown-linux-gnu. OK? >> >> Nice, but perhaps we need a sparsemap to do even better? > > If you mean sparseset: no, it won't do any better. No, I mean "inventing" a sparseset that cannot do boolean operations, but can store an associative value in a second dense array. That is sparsemap_insert(m, k, v) { if (!sparsemap_contains(m, k)) { s->sparse[k] = s->members++; s->dense_keys[i] = k; } i = s->sparse[k]; s->dense_values[i] = v; } sparsemap_contains(m, k) { if (!sparsemap_contains(m, k)) { return -1; } else { return s->dense_values[i]; } > My first idea was to use a sparseset, but: > > 1. The amount of memory allocated is simply too big. In fact, it'd be > even worse than before: 4*max_regno*sizeof(rtx) instead of "only" > 2*max_regno*sizeof(rtx). Yeah, sparseset wastes some memory. I wonder if the dense array should be allocated separately and even made dynamically resizable, also because... > 2. sparseset has the same problem of memory clearing (for valgrind, > see sparseset_alloc). ... only the sparse array needs this clearing, but currently we do it for both. > What could work, is to allocate a sparseset once at the beginning of > if_convert, but I don't see any good reason to add a pair of global > variables for this. Yes, this is what I meant. Fast clearing is where sparsesets behave well, so it makes sense to make them global in that case. What I missed was that the maps remain small. Otherwise they would also need clearing. Paolo