From patchwork Wed Jul 25 20:44:36 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Luc Van Oostenryck X-Patchwork-Id: 10544675 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id AC93A139A for ; Wed, 25 Jul 2018 20:46:49 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9113F2A9E7 for ; Wed, 25 Jul 2018 20:46:49 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 833DE2A9EA; Wed, 25 Jul 2018 20:46:49 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.8 required=2.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 166522A9E7 for ; Wed, 25 Jul 2018 20:46:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731290AbeGYWAL (ORCPT ); Wed, 25 Jul 2018 18:00:11 -0400 Received: from mail-ed1-f65.google.com ([209.85.208.65]:46709 "EHLO mail-ed1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730624AbeGYWAK (ORCPT ); Wed, 25 Jul 2018 18:00:10 -0400 Received: by mail-ed1-f65.google.com with SMTP id o8-v6so8307376edt.13 for ; Wed, 25 Jul 2018 13:46:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id; bh=qQl95qjAzhux/zw11g+oPYKh3twLcVoRH/f/8UUYwfY=; b=C0BGjEE+v+n617oKAcl8Sbv/TagtvFzQ7CE7qbRmI8be7Jd4D+BzT0mWma7SpIVrHJ xAgKrC4WcpXBil3xHC5C9loDUJSieL1yTxluPntK7sgwLlo00ai5m7cwhWkuZ2FbqaM3 AqY8Xd+uLxgJGBzW3XVoE7Kww3LFa1nEIp/pz2smNiUqxQ8nYuGJoxu6a85hlTL0GBZE bchXwe4r4HjpPiSpbZ4xjEsxGDkbVfPzY3iWLGPPXr+XVgDs07yN+A8drovcVxL5A9I0 vxfc9MHnuDf0Y32V06dYCU5UpSvj/fumD1+hmWoCZUt/5EGnGnCYJZH2vt7Lxl5sJibC hfzw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=qQl95qjAzhux/zw11g+oPYKh3twLcVoRH/f/8UUYwfY=; b=Ms6LUO6p3a86PFthp19+IsX1N1geuOxDpZQAQCMwpYjC3gMiBx9WTSFufNmfeTCNTx G2sRRq6iMYf/2BGvbMQJruFLR/krHMnPgwdIc0emDNAabwAX/utFIO4IsDqYTdfe8ZQY AAM0POY/hJ+2+O0JAMlwa0ZWStunAlF0o6mq+oKU9DpcRXBj/96a6fTOpfq1LToBIoRU ZaDAf6E7IOJoDAyN/8fCeIVK4ykQxW1ZZ7la+6ISpnpYtGiiuc8kCELTDPhKPSi9vxxG /Y7Iv3FI2cUSpXwfIW43n+jiP76xMY1cxtnxhRM85axqQqJUtR77i3caZ2+V1OzzWuET nQiA== X-Gm-Message-State: AOUpUlEwNQyVERXfdnDYaBAxLSfxyfgFgrnL7KCs4Fnmjc1p9TL7llMQ zY8CnyR8A5SKvnja/48LBupJq3wT X-Google-Smtp-Source: AAOMgpdvAQeRUpS+EWQIHwllImxKLwbYLl1uj4xOkrJfK5gPKlD04ppjXfQvayuE32kSWZYm6VJlFQ== X-Received: by 2002:a50:ace2:: with SMTP id x89-v6mr25021459edc.152.1532551606685; Wed, 25 Jul 2018 13:46:46 -0700 (PDT) Received: from localhost.localdomain ([2a02:a03f:40d9:b300:a08b:7c37:c755:ffe3]) by smtp.gmail.com with ESMTPSA id n64-v6sm11195114edc.49.2018.07.25.13.46.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Jul 2018 13:46:46 -0700 (PDT) From: Luc Van Oostenryck To: linux-sparse@vger.kernel.org Cc: Ramsay Jones , Luc Van Oostenryck Subject: [PATCH 0/5] some list optimizations Date: Wed, 25 Jul 2018 22:44:36 +0200 Message-Id: <20180725204441.91527-1-luc.vanoostenryck@gmail.com> X-Mailer: git-send-email 2.18.0 Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP This series contains optimizations of some list operations. In most common situations, most list used are quite small (mean of 5 elements) and these optimizations don't give any kind of measureable speedups (but no slowdowns either). However, in some (maybe pathological) situations, the lists can be quite long, especially the ones for pseudo usage, and then these optimizations can be quite effective: up to a combined speedup of 45%. Note: I'm not yet 100% convinced that patch 5 is totally safe. Note: the 'speedup' of patches 3 & 4 is lost in the noise. This series is available for review & testing in the Git repository at: git://github.com/lucvoo/sparse-dev.git list-optims-v2 Changes since v1 (thanks to Ramsay Jones): * rewrote initial test in copy_ptr_list() * better variable name in copy_ptr_list()'s loop * improved commit messages * fix typos in autodoc's markup ---------------------------------------------------------------- Luc Van Oostenryck (5): add copy_ptr_list() add ptr_list_empty() add ptr_list_multiple() add lookup_ptr_list_entry() no VOID test in convert_instruction_target() flow.c | 7 +--- linearize.h | 17 +++++++- liveness.c | 9 ----- ptrlist.c | 110 ++++++++++++++++++++++++++++++++++++++++++++++++++++ ptrlist.h | 5 +++ simplify.c | 4 +- 6 files changed, 135 insertions(+), 17 deletions(-)