From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS31976 209.132.180.0/23 X-Spam-Status: No, score=-3.8 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.1 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 dcvr.yhbt.net (Postfix) with ESMTPS id 857171F597 for ; Wed, 1 Aug 2018 07:01:54 +0000 (UTC) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:cc:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; q=dns; s=default; b=HbvlT9DdSL9IPQTE jZuYcnLiyL25SO7MrylAGhoMHSjLVKnAL1EKLbfAooXFud2FaURTHDdx62QsqaaG 3GNwb2BoGXDjen44CzRdPUthOLYbAuE8UJavDXPna0udqoRf1iWWkHku1Hl61QRh eeiZ42vAdBmBG6/DNGWgf4bd7JQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:cc:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; s=default; bh=KQosnGzrXfwHPFYrMcI4C6 4uIts=; b=JUU+C0Fp6knGXUapAEdirfmEjNks3zsfDvK0QbTs8GwRJ4u2S8ukuZ XYtIbMMwxdTB3ZH9MXzS6OXh9LQgOQA596GwSh7yoqx/bPNMtgnJaA1XJN0eBHCC g2tDUHyjASaaFvQ++P4tp/ilUJVnWd4FvriMAi+6ZQcwnW1lqj7+g= Received: (qmail 80324 invoked by alias); 1 Aug 2018 07:01:40 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Received: (qmail 73488 invoked by uid 89); 1 Aug 2018 07:01:33 -0000 Authentication-Results: sourceware.org; auth=none X-HELO: mail-qt0-f194.google.com Subject: Re: [RFC/PoC] malloc: use wfcqueue to speed up remote frees To: Eric Wong Cc: libc-alpha@sourceware.org References: <20180731084936.g4yw6wnvt677miti@dcvr> <0cfdccea-d173-486c-85f4-27e285a30a1a@redhat.com> <20180731231819.57xsqvdfdyfxrzy5@whir> <20180801062352.rlrjqmsszntkzlfe@untitled> From: Carlos O'Donell Openpgp: preference=signencrypt Message-ID: Date: Wed, 1 Aug 2018 03:01:22 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: <20180801062352.rlrjqmsszntkzlfe@untitled> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit On 08/01/2018 02:23 AM, Eric Wong wrote: > Carlos O'Donell wrote: >> On 07/31/2018 07:18 PM, Eric Wong wrote: >>>> - Can you explain the RSS reduction given this patch? You >>>> might think that just adding the frees to a queue wouldn't >>>> result in any RSS gains. >>> >>> At least two reasons I can see: >>> >>> 1) With lock contention, the freeing thread can lose to the >>> allocating thread. This makes the allocating thread hit >>> sysmalloc since it prevented the freeing thread from doing >>> its job. sysmalloc is the slow path, so the lock gets held >>> even longer and the problem compounds from there. >> >> How does this impact RSS? It would only block the remote thread >> from freeing in a timely fashion, but it would eventually make >> progress. > > Blocking the freeing thread causes the allocating thread to > sysmalloc more. If the freeing thread could always beat the > allocating thread, then the freed memory would be available in > the arena by the time the allocating thread takes the lock. I see what you mean now. Yes, that could reduce RSS by reducing the time between when the remote thread frees memory and when the producer thread (let's call it that) can reuse the returned chunks. >>> 2) thread caching - memory ends up in the wrong thread and >>> could never get used in some cases. Fortunately this is >>> bounded, but still a waste. >> >> We can't have memory end up in the wrong thread. The remote thread >> computes the arena from the chunk it has, and then frees back to >> the appropriate arena, even if it's not the arena that the thread >> is attached to. > > Really? I see: > > __libc_free -> MAYBE_INIT_TCACHE && _int_free -> tcache_put > > I am not seeing anything in _int_free which makes the tcache_put > arena-aware. If we drop MAYBE_INIT_TCACHE from __libc_free, > then the tcache_put could be avoided. Thank you, that clarifies it for me, I was glossing over tcache. Yes, the tcache layer doesn't care where the block came from and will happily cache it. In a producer-consumer model though, as this seems to be the example from which we are drawing parallels, the consumer rarely needs to allocate anything, so yes, the tcache effectively slows the initial rate of frees to the producer thread, but only to a limit (as you note). >>> I'm still new to the code, but it looks like threads are pinned >>> to the arena and the memory used for arenas never gets released. >>> Is that correct? >> >> Threads are pinned to their arenas, but they can move in the event >> of allocation failures, particularly to the main arena to attempt >> sbrk to get more memory. > > OK. > >>> I was wondering if there was another possibility: the allocating >>> thread gives up the arena and creates a new one because the >>> freeing thread locked it, but I don't think that's the case. >> >> No. >> >>> Also, if I spawn a bunch of threads and get a bunch of >>> arenas early in the program lifetime; and then only have few >>> threads later, there can be a lot of idle arenas. >> >> Yes. That is true. We don't coalesce arenas to match the thread >> demand. > > Eep :< If contention can be avoided (which tcache seems to > work well for), limiting arenas to CPU count seems desirable and > worth trying. Agreed. In general it is not as bad as you think. An arena is made up of a chain of heaps, each an mmap'd block, and if we can manage to free an entire heap then we unmap the heap, and if we're lucky we can manage to free down the entire arena (_int_free -> large chunk / consolidate -> heap_trim -> shrink_heap). So we might just end up with a large number of arena's that don't have very much allocated at all, but are all on the arena free list waiting for a thread to attach to them to reduce overall contention. I agree that it would be *better* if we had one arena per CPU and each thread could easily determine the CPU it was on (via a restartable sequence) and then allocate CPU-local memory to work with (the best you can do; ignoring NUMA effects). > > >>>> - Adding urcu as a build-time dependency is not acceptable for >>>> bootstrap, instead we would bundle a copy of urcu and keep it >>>> in sync with upstream. Would that make your work easier? >>> >>> Yes, bundling that sounds great. I assume it's something for >>> you or one of the regular contributors to work on (build systems >>> scare me :x) >> >> Yes, that is something we'd have to do. > > OK, I noticed my patch fails conformance tests because > (despite my use of __cds_wfcq_splice_nonblocking) it references > poll(), despite poll() being in an impossible code path: > > __cds_wfcq_splice_nonblocking -> ___cds_wfcq_splice > -> ___cds_wfcq_busy_wait -> poll > > The poll call is impossible because the `blocking' parameter is 0; > but I guess the linker doesn't know that? Correct. We can fix that easily at a later date. Don't worry about it. -- Cheers, Carlos.