From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-f41.google.com (mail-wm1-f41.google.com [209.85.128.41]) by sourceware.org (Postfix) with ESMTPS id 6B8DC3836E47 for ; Thu, 2 Jun 2022 14:37:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6B8DC3836E47 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=palves.net Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-wm1-f41.google.com with SMTP id p5-20020a1c2905000000b003970dd5404dso2896386wmp.0 for ; Thu, 02 Jun 2022 07:37:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:from:to:cc:references:in-reply-to :content-transfer-encoding; bh=nDf73FOHouCe6d9H5dwiY9Ib4DijTUQrdbZjf6Uxtes=; b=8GiBloj/FlgSxFsnldFQXWggFflUWkm58mTavU4cBRUucwNiqKZeRDNx9AqfTd8PQ1 wySgY47X4WM0NLaXM+bW58MREq5/FVIGiqy1Z/PfBncy+YwMGUZYEJ9QmprqxPAg/qWI cT3YY1tvm/GGPzFHEa6KzDb+8kg76W4Da+u1DJT7nZC+09QGW+YHkW/IM9mieU9maCai IKNTTa76pVOMQbnIaNv0tYppUQLF9jNilAsX1BZJ6cB4LjY3NIb7TfUAcipLsbSCOXgt VRjh5LV1KZ1mRosTUt8qMfcoG2DHuDq3AxK3QoRwYO+W3jfZ9j6lLsl3DkT6/efXD5X5 kENw== X-Gm-Message-State: AOAM532HdRxjAhSR1TRL5gT929MzpmUNit0D0iyHoOQ3ZEJKwDfdkLUX RZ6RM8jagphkS+L1VkwDriJd0dWLORs= X-Google-Smtp-Source: ABdhPJyW8Xg+sdcgzqfdWi903NfV12W7BDEImWq89h9situZ01gozB3gakbBzzDcn122izOzPgPKyQ== X-Received: by 2002:a05:600c:1d20:b0:397:5a8b:a30a with SMTP id l32-20020a05600c1d2000b003975a8ba30amr4345810wms.89.1654180637295; Thu, 02 Jun 2022 07:37:17 -0700 (PDT) Received: from ?IPV6:2001:8a0:f924:2600:209d:85e2:409e:8726? ([2001:8a0:f924:2600:209d:85e2:409e:8726]) by smtp.gmail.com with ESMTPSA id c16-20020a7bc850000000b003942a244f48sm8507318wml.33.2022.06.02.07.37.15 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 02 Jun 2022 07:37:16 -0700 (PDT) Message-ID: <52e0e168-3ad4-df0e-5b46-2856e82b5d47@palves.net> Date: Thu, 2 Jun 2022 15:37:14 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.1 Subject: Re: [PATCH 2/5] gdbsupport: Introduce interval_tree Content-Language: en-US From: Pedro Alves To: Ilya Leoshkevich , Tom Tromey , Andrew Burgess Cc: Andreas Arnez , gdb-patches@sourceware.org References: <20220602133546.2948282-1-iii@linux.ibm.com> <20220602133546.2948282-3-iii@linux.ibm.com> <94eef992-ff81-b994-b30f-daf26b6c5915@palves.net> In-Reply-To: <94eef992-ff81-b994-b30f-daf26b6c5915@palves.net> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-5.2 required=5.0 tests=BAYES_00, FREEMAIL_FORGED_FROMDOMAIN, FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS, KAM_DMARC_STATUS, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 02 Jun 2022 14:37:20 -0000 On 2022-06-02 15:12, Pedro Alves wrote: > On 2022-06-02 14:35, Ilya Leoshkevich wrote: >> >> Adding N JITed sections has the complexity O((N**2)*log(N)), because >> adding each section involves breakpoint handling, which needs to >> resolve PCs and thus calls update_section_map(). When N is around 10k, >> this renders GDB unusable. > > Does this adding of N JITed sections happen in batch? Like, is this from > jit_inferior_init, where we loop over JIT objects? Or is it so that we > get notified about JIT objects, one at a time? > > In places where we add symbols in batch, we defer breakpoint re_setting exactly > to avoid problems like this, via SYMFILE_DEFER_BP_RESET or something similar. > Looks like jit.c doesn't try to do that. Or is it not possible in the scenario > in question? Like, doesn't the JIT API let you register more than one object > file at once? It has taken me this long to remember that I once wrote a patch series to tackle this problem... :-) It's been on a branch on sourceware since 2016... See the palves/jit-speedup branch. I completely forgot that. There, I added a number of patches deferring breakpoint_re_set in several different situations, and other simple optimizations that avoid O(N). It may be those patches are obsolete by now, but maybe they aren't. For the section sorting issue itself, the branch has this: ~~~~~~~~~~~~~~~~~~ commit 5cd42e9fb13d25febe3da26595d044a57150cee5 Author: Pedro Alves AuthorDate: Fri Apr 1 01:14:30 2016 +0100 Commit: Pedro Alves CommitDate: Mon Sep 19 15:44:41 2016 +0100 Get rid of sections sorting with qsort and use an incrementally updated addrmap instead This gives a massive speed up. The problem with the qsort is that we qsort for any one of the thousands of jit loads/unloads, and when you have thousands of objfiles, that gets very slow. In this scenario, we're constantly adding/removing a handfull of obj_sections to a set of thousands of already-sorted obj_sections. It's much cheaper to do an incremental update. I'm using a mutable addrmap for this, but I needed to add a new primitive that allowed updating a region's object, to handle the case of overlapping sections. The only primitive available, only allows setting a value to a currently-NULL region. ~~~~~~~~~~~~~~~~~~ it talks about qsort because back when we hadn't yet moved to C++ std::sort. As you see, I was using an addrmap for this (gdb/addrmap.h), which is a data structure we already have. I wonder whether the new data structure is really needed. That's a question I was going to raise anyhow, until I remembered I had once already attempted it (and seen that it works).