From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-1.mimecast.com (us-smtp-1.mimecast.com [205.139.110.61]) by sourceware.org (Postfix) with ESMTP id 27B59385B835 for ; Thu, 16 Apr 2020 17:51:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 27B59385B835 Received: from mail-ed1-f71.google.com (mail-ed1-f71.google.com [209.85.208.71]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-500-U7nPSSHJPXyRWTxc4qKyQg-1; Thu, 16 Apr 2020 13:51:29 -0400 X-MC-Unique: U7nPSSHJPXyRWTxc4qKyQg-1 Received: by mail-ed1-f71.google.com with SMTP id c2so5515598edx.16 for ; Thu, 16 Apr 2020 10:51:29 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:cc:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=ot9wsaT1zbdfADfIeD7As5yTJkNO+Xc0drLojWTYlLE=; b=aKh12H3V6y6k59fj/u7jD/m9Jrd10O7BCjxpuEMQFOUV4wbXB6BZf3uzwG/rbXPFM4 UkM4ez6MJR/DE6MyZ2ScMplRQLr55fJTzCdpha9ndhTMEWlG/jVmoLSX3m0/wGwumIRc tc4PPhX3tA7QvdZOXjV2Fn4huMb8iL32PuJ92twpn5AxCXF261a50K6FghXXLFYcZhZ7 BOlr9YBAEoiIXkUfymx9DQulU/Ia/4xYnsk0RvQ03wVsDfSbaVEeDyT8hy2vGYjhcTVg 7TmgK+LTUW3TzboIiH3GVxK66ckH2AulxBK9tjRfH4A+QUttkjTLeYUnsMdryAHytkm5 OV7Q== X-Gm-Message-State: AGi0PuaW7vTodpGzv5WojAw85cIb88sSEVM6vHKG4XJl3FSTrWbzvVI/ jvw7EpzIc8PffI4hOUjrXT6hcHpz+bvuNU30Wa2TJ2r+PxaGN4v2WRhpnaDiCl6nxuU5fSMLpmK xVNPrNmapnncEpyLIzJALcQ== X-Received: by 2002:a17:906:66c1:: with SMTP id k1mr11126638ejp.208.1587059487519; Thu, 16 Apr 2020 10:51:27 -0700 (PDT) X-Google-Smtp-Source: APiQypLss/Mpz5U/xg2H2J+3xI2LUCOO9mpKRhbfso7y17Oh7wDt0FtXlW95Gl2xpH4Aq3FqswkMiw== X-Received: by 2002:a17:906:66c1:: with SMTP id k1mr11126625ejp.208.1587059487220; Thu, 16 Apr 2020 10:51:27 -0700 (PDT) Received: from ?IPv6:2001:8a0:f909:7b00:56ee:75ff:fe8d:232b? ([2001:8a0:f909:7b00:56ee:75ff:fe8d:232b]) by smtp.gmail.com with ESMTPSA id i3sm3048597ejr.19.2020.04.16.10.51.25 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 16 Apr 2020 10:51:26 -0700 (PDT) Subject: Re: [PATCH] gdb: infrun: consume multiple events at each pass in stop_all_threads To: Simon Marchi , gdb-patches@sourceware.org References: <20200224193638.29578-1-simon.marchi@efficios.com> Cc: Laurent Morichetti From: Pedro Alves Message-ID: <8402549f-c733-cb8b-918c-4dfb06eeb7a0@redhat.com> Date: Thu, 16 Apr 2020 18:51:25 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 MIME-Version: 1.0 In-Reply-To: <20200224193638.29578-1-simon.marchi@efficios.com> Content-Language: en-US X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) 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, 16 Apr 2020 17:51:39 -0000 On 2/24/20 7:36 PM, Simon Marchi wrote: > From: Laurent Morichetti > > [Simon: I send this patch on behalf of Laurent Morichetti, I added the > commit message and performance measurement stuff. > > Also, this patch is better viewed with "git show -w".] Indeed it is! > > stop_all_threads, in infrun.c, is used to stop all running threads on > targets that are always non-stop. It's used, for example, when the > program hits a breakpoint while GDB is set to "non-stop off". It sends > a stop request for each running thread, then collects one wait event for > each. > > Since new threads can spawn while we are stopping the threads, it's > written in a way where it makes multiple such "send stop requests to > running threads & collect wait events" passes. The function completes > when it has made two passes where it hasn't seen any running threads. > > With the way it's written right now is, it iterates on the thread list, > sending a stop request for each running thread. It then waits for a > single event, after which it iterates through the thread list again. It > sends stop requests for any running threads that's been created since > the last iteration. It then consumes another single wait event. > > This makes it so we iterate on O(n^2) threads in total, where n is the > number of threads. This patch changes the function to reduce it to > O(n). This starts to have an impact when dealing with multiple > thousands of threads (see numbers below). At each pass, we know the > number of outstanding stop requests we have sent, for which we need to > collect a stop event. We can therefore loop to collect this many stop > events before proceeding to the next pass and iterate on the thread list > again. > > To check the performance improvements with this patch, I made an > x86/Linux program with a large number of idle threads (varying from 1000 > to 10000). The program's main thread hits a breakpoint once all these > threads have started, which causes stop_all_threads to be called to stop > all these threads. I measured (by patching stop_all_threads): > > - the execution time of stop_all_threads > - the total number of threads we iterate on during the complete > execution of the function (the total number of times we execute the > "for (thread_info *t : all_non_exited_threads ())" loop) > > These are the execution times, in milliseconds: > > # threads before after > 1000 226 106 > 2000 997 919 > 3000 3461 2323 > 4000 4330 3570 > 5000 8642 6600 > 6000 9918 8039 > 7000 12662 10930 > 8000 16652 11222 > 9000 21561 15875 > 10000 26613 20019 > > Note that I very unscientifically executed each case only once. > > These are the number of loop executions: > > # threads before after > 1000 1003002 3003 > 2000 4006002 6003 > 3000 9009002 9003 > 4000 16012002 12003 > 5000 25015002 15003 > 6000 36018002 18003 > 7000 49021002 21003 > 8000 64024002 24003 > 9000 81027002 27003 > 10000 100030002 30003 > > This last table shows pretty well the O(n^2) vs O(n) behaviors. Wow! > @@ -4758,110 +4758,114 @@ stop_all_threads (void) > if (pass > 0) > pass = -1; > > - wait_one_event event = wait_one (); > - > - if (debug_infrun) > + for (int i = 0; i < waits_needed; i++) This makes sense to me, but can you try locally to check whether if you do _more_ waits than wait_needed, like, say: for (int i = 0; i < (waits_needed * 2); i++) ... GDB still works correctly? In theory, wait_one will end up returning TARGET_WAITKIND_NO_RESUMED once you get to waits_needed, and things will all work out. The reason I'm asking this, is if a process exits, or execs, while we're trying to stop it, I think that it's possible that we won't see an exit event for each and every thread of that exiting process. Particularly execs -- see follow_exec's delete_thread calls. This is somewhat related to Tankut's patch, here: https://sourceware.org/pipermail/gdb-patches/2020-April/167416.html Thanks, Pedro Alves