From patchwork Wed Nov 20 11:29:51 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 1198039 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-514139-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=ucw.cz Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="tbwKUTnf"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47J0q54dslz9sPc for ; Wed, 20 Nov 2019 22:30:08 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=V5ZvJGn0B6DtqcDCn8pZ3hR0E6R3zxG/UbNh0AZFYgfiKI60u4vSA ee+Xk6mGRGP7i76Dfxopqov4P0T8Z3WKIltQbeITUDgTIP/5L6nvjsR/al5e78TV dYDV1bY+NYI6Cviv27eB9ThSiBDCj2CpDKYHxlSo5ptf56uGbjq2oI= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=jVHWB5NGPsdA8nyyCCf7G0puoMg=; b=tbwKUTnf7WkXIAI54y4M xL7/tVBtXBlQC9gmSo1SmNdmaJ1QuoISWrSyG+Yb81B3vUr7xZJWPk/N6Yl3wlrH HjKZq06BSpNUMEtLK1+KmPkb6wpgeIeph6PnGf+mgiiC00bSRTSI3Sn6FiYLftsK ZjzCeNys6WcsXXUQ8htssLU= Received: (qmail 65392 invoked by alias); 20 Nov 2019 11:29:59 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 65381 invoked by uid 89); 20 Nov 2019 11:29:58 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-10.0 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS autolearn=ham version=3.3.1 spammy=UD:cfgloop.h, cfglooph, cfgloop.h, profiles X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 20 Nov 2019 11:29:55 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id EE438287DDE; Wed, 20 Nov 2019 12:29:51 +0100 (CET) Date: Wed, 20 Nov 2019 12:29:51 +0100 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, rguenther@suse.de Subject: Optimize fibonacci heap allocations Message-ID: <20191120112951.esx6px4dr5shm245@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) Hi, since inliner got faster malloc overhead starts to show up in profiles. This patch eliminates a lot of malloc/free traffic by putting fibonaci heaps nodes into pool allocators. It also fixes a silly issue with constant sized vector not being allocated on stack (which actually seems most important problem here). I went with pool_allocator rather than object_allocator because I do not know how to call non-default constructor which of fibonnaci node which is used by fibonacci_heap::insert. By default every heap has its own allocator. We implement (but do not use) union_with operation for which I needed to add a way to allocate multiple heaps in one allocator. Bootstrapped/regtested x86_64-linux, OK? Honza * fibonacci_heap.h (fibonacci_heap::fibonacci_heap): Add allocator parameter. (fibonacci_heap::~fibonacci_heap): Optimize destruction. (fibonacci_heap::m_allocator): New. (fibonacci_heap::m_own_allocator): New. (fibonacci_heap::insert): Use allocator. (fibonacci_heap::extract_min): Likewise. (fibonacci_heap::union_with): Assert that both heaps share allocator. (fibonacci_heap::consolidate): Allocate constant sized vector on stack. * fibonacci_heap.c: Include alloc-pool (test_empty_heap): Initialize allocator. (test_union): Likewise. * bb-reorder.c: Include alloc-pool.h. * tracer.c: Inlclude alloc-pool.h. Index: fibonacci_heap.h =================================================================== --- fibonacci_heap.h (revision 278464) +++ fibonacci_heap.h (working copy) @@ -145,17 +145,36 @@ class fibonacci_heap friend class fibonacci_node; public: - /* Default constructor. */ - fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL), - m_global_min_key (global_min_key) + /* Default constructor. ALLOCATOR is optional and is primarily useful + when heaps are going to be merged (in that case they need to be allocated + in same alloc pool). */ + fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL): + m_nodes (0), m_min (NULL), m_root (NULL), + m_global_min_key (global_min_key), + m_allocator (allocator), m_own_allocator (false) { + if (!m_allocator) + { + m_allocator = new pool_allocator ("Fibonacci heap", + sizeof (fibonacci_node_t)); + m_own_allocator = true; + } } /* Destructor. */ ~fibonacci_heap () { - while (m_min != NULL) - delete (extract_minimum_node ()); + /* Actual memory will be released by the destructor of m_allocator. */ + if (need_finalization_p () || !m_own_allocator) + while (m_min != NULL) + { + fibonacci_node_t *n = extract_minimum_node (); + n->~fibonacci_node_t (); + if (!m_own_allocator) + m_allocator->remove (n); + } + if (m_own_allocator) + delete m_allocator; } /* Insert new node given by KEY and DATA associated with the key. */ @@ -259,6 +278,11 @@ private: fibonacci_node_t *m_root; /* Global minimum given in the heap construction. */ K m_global_min_key; + + /* Allocator used to hold nodes. */ + pool_allocator *m_allocator; + /* True if alocator is owned by the current heap only. */ + bool m_own_allocator; }; /* Remove fibonacci heap node. */ @@ -333,7 +357,8 @@ fibonacci_node* fibonacci_heap::insert (K key, V *data) { /* Create the new node. */ - fibonacci_node *node = new fibonacci_node_t (key, data); + fibonacci_node *node = new (m_allocator->allocate ()) + fibonacci_node_t (key, data); return insert_node (node); } @@ -438,7 +463,10 @@ fibonacci_heap::extract_min (bool r ret = z->m_data; if (release) - delete (z); + { + z->~fibonacci_node_t (); + m_allocator->remove (z); + } } return ret; @@ -474,6 +502,9 @@ fibonacci_heap::union_with (fibonac fibonacci_node *a_root, *b_root; + /* Both heaps must share allocator. */ + gcc_checking_assert (m_allocator == heapb->m_allocator); + /* If one of the heaps is empty, the union is just the other heap. */ if ((a_root = heapa->m_root) == NULL) { @@ -616,8 +647,8 @@ fibonacci_heap::remove_root (fibona template void fibonacci_heap::consolidate () { - int D = 1 + 8 * sizeof (long); - auto_vec *> a (D); + const int D = 1 + 8 * sizeof (long); + auto_vec *, D> a; a.safe_grow_cleared (D); fibonacci_node *w, *x, *y; int i, d; Index: fibonacci_heap.c =================================================================== --- fibonacci_heap.c (revision 278464) +++ fibonacci_heap.c (working copy) @@ -21,6 +21,7 @@ along with GCC; see the file COPYING3. #include "config.h" #include "system.h" #include "coretypes.h" +#include "alloc-pool.h" #include "fibonacci_heap.h" #include "selftest.h" @@ -38,13 +39,14 @@ typedef fibonacci_heap int_he static void test_empty_heap () { - int_heap_t *h1 = new int_heap_t (INT_MIN); + pool_allocator allocator ("fibheap test"); + int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator); ASSERT_TRUE (h1->empty ()); ASSERT_EQ (0, h1->nodes ()); ASSERT_EQ (NULL, h1->min ()); - int_heap_t *h2 = new int_heap_t (INT_MIN); + int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator); int_heap_t *r = h1->union_with (h2); ASSERT_TRUE (r->empty ()); @@ -169,12 +171,13 @@ static void test_union () { int value = 777; + pool_allocator allocator ("fibheap test"); - int_heap_t *heap1 = new int_heap_t (INT_MIN); + int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator); for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++) heap1->insert (i, &value); - int_heap_t *heap2 = new int_heap_t (INT_MIN); + int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator); for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++) heap2->insert (i, &value); Index: bb-reorder.c =================================================================== --- bb-reorder.c (revision 278464) +++ bb-reorder.c (working copy) @@ -112,6 +112,7 @@ #include "cfgcleanup.h" #include "bb-reorder.h" #include "except.h" +#include "alloc-pool.h" #include "fibonacci_heap.h" #include "stringpool.h" #include "attribs.h" Index: tracer.c =================================================================== --- tracer.c (revision 278464) +++ tracer.c (working copy) @@ -49,6 +49,7 @@ #include "tree-ssa.h" #include "tree-inline.h" #include "cfgloop.h" +#include "alloc-pool.h" #include "fibonacci_heap.h" #include "tracer.h"