From owner-freebsd-current@FreeBSD.ORG Wed Mar 28 22:36:38 2007 Return-Path: X-Original-To: freebsd-current@freebsd.org Delivered-To: freebsd-current@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 206FC16A401 for ; Wed, 28 Mar 2007 22:36:38 +0000 (UTC) (envelope-from jasone@frebsd.org) Received: from canonware.com (24-38-119-150-st.losaca.adelphia.net [24.38.119.150]) by mx1.freebsd.org (Postfix) with ESMTP id 9240C13C4D9 for ; Wed, 28 Mar 2007 22:36:37 +0000 (UTC) (envelope-from jasone@frebsd.org) Received: from [10.0.0.2] (24-38-119-150-st.losaca.adelphia.net [24.38.119.150]) by canonware.com (Postfix) with ESMTP id 470E01298DC for ; Wed, 28 Mar 2007 15:08:59 -0700 (PDT) Message-ID: <460AE766.6050409@frebsd.org> Date: Wed, 28 Mar 2007 15:08:38 -0700 From: Jason Evans User-Agent: Thunderbird 1.5.0.10 (X11/20070302) MIME-Version: 1.0 To: freebsd-current@freebsd.org References: <200703281955.l2SJt7Ua086062@repoman.freebsd.org> In-Reply-To: <200703281955.l2SJt7Ua086062@repoman.freebsd.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Thu, 29 Mar 2007 00:52:35 +0000 Subject: malloc(3) (hopefully) set for 7.0 X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 28 Mar 2007 22:36:38 -0000 === Introduction === Those of you who watch the cvs commit logs may have noticed several rather significant changes to malloc over the past few weeks. I took a fresh look at malloc after letting the details fade over the past year, and saw some significant opportunities for improvement. I appreciate the FreeBSD community's tolerance of these changes, which were perhaps of questionable wisdom given that we are now in code slush. =) Since these changes obsolete several aspects of the paper I presented last year at BSDcan, it seems like a good idea to provide a public summary of these changes and their rationale. The changes focus on two main issues: 1) mapped page reduction during low memory usage phases of application execution, and 2) fragmentation reduction. === 1) Mapped page reduction === First, here is a bit of relevant background. jemalloc breaks memory into 1MB chunks that are aligned at multiples of the chunk size. This makes it possible to find metadata for small and large user objects in constant time. (For huge objects, it takes lg(n) time, where n is the number of huge allocations.) The point is that chunks are a fundamental aspect of what makes jemalloc tick. However, there is a downside to managing memory in chunks: unless we use madvise(2), every page of a chunk that is touched remains physically backed until the entire chunk can be unmapped. Thus, even a single in-use page can cause retention of up to 1MB of memory. This is a bit of a catch-22, since madvise(2) is too expensive to enable by default, but if we really need it, then we really should be using it for all applications, since paging is a system-wide issue. There is no simple way out of this conundrum, which is why I have been working to reduce the number of chunks that remain mapped for programs that typically operate at well below their peak memory usage. In order to reduce the number of mapped pages, we need some way to preferentially pack data into certain chunks, so that others can drain. There is a simple allocation policy that in practice had been demonstrated to work very well: prefer low addresses. jemalloc already did this where convenient (a lesson learned from phkmalloc), but the recent changes push this policy throughout the allocator, almost to the maximum extreme possible. Each arena manages a set of chunks that are carved into runs. These runs back small and large allocations. jemalloc now uses the lowest fit for run allocation. Equal-sized small allocations are grouped together into runs since it is possible to fit multiple small objects in a single run. This means that such a run may have very low utilization, so we try to keep runs as full as possible in order to reduce the total number of runs in use for any given size class. Previously, jemalloc used an overly complicated run promotion/demotion system that was intended to place several consecutive allocation requests in the same run, reduce the overhead of switching between runs, and try to keep the runs moderately full. However, experiments demonstrated that run switching overhead has at most a small impact on allocator performance, and furthermore that the promotion/demotion algorithms were not very effective at decreasing run switching anyway. That being the case, I experimented with increasingly expensive run switching policies. Finally, I tried always switching to the lowest run with any unused space, which was the ideal layout policy given my goals. This change had the intended effect of tending to let high chunks drain. Much to my surprise though, there was no significant impact on runtime. I put this last experiment off a long time, because my intuition was that it would be far too expensive to add so many red-black tree modifications. I think there are two contributing factors to why I was wrong: 1) the highest run switching rate I saw for any application was ~1% of the total allocation rate (though carefully crafted code could push that up to nearly 50%), and 2) cache locality improvements tend to help a bit. My initial expectation would be for such a layout policy to *decrease* locality, since we have the potential to spread consecutive allocations across a large number of independent runs. However, in the steady state of a long-running application, we have a hard time dealing with this problem anyway, and by packing objects as low as possible in memory, we actually tend to do better than if we were to use non-full runs in MRU order. Anyway, the reason I dedicate so much space to this issue is that it still makes me uneasy, but I have been unable to find any application for which the layout policy causes significant performance degradation. If you think you may have found such a case, you will be able to gain some insight by looking at the statistics output from setting MALLOC_OPTIONS=P. Look at the 'reruns' column (# of run switches) versus the 'requests' column in order to determine what percentage of requests suffer the overhead of run switching. If you see very high run switch rates for a particular application (say, >5%), please tell me so that I can run further experiments. === 2) Fragmentation reduction === We want to fit user objects in memory as tightly as possible. jemalloc was doing a substandard job in a couple of regards. First, it used a binary buddy scheme to manage runs within chunks, meaning that runs were constrained to be 2^n pages, for 0 < n < 20. This caused significant internal fragmentation for, say, 20kB objects. To improve the situation, I switched to using a straightforward extent-based system. This was initially intended only as a fix for the problem just described, but it turned out to also be useful for runs that back small allocations. Small allocation runs can now be more precisely sized such that the run header overhead is barely below some threshold. This allows the bitmaps that track which small objects are in use to be as short as possible while still keeping metadata overhead under control. Previously, all run headers for small object runs were the same size, regardless of how many bits were actually needed in the header bitmap to track the run's objects. This was clearly wasteful. My memory is fuzzy regarding the original rationale for fixed-size run headers, but I think it had to do with the complexity of calculating run header size, number of runs, and run size all at the same time. Indeed, this proved to be tricky, but well worth the effort. === Summary === With these changes in place, all of my experiments indicate substantial improvements in memory usage, as well as overall speed improvements. We still have several months before the 7.0 release to verify that I didn't miss anything important. Even so, I tested these changes more thoroughly than any previous changes (excepting Kris Kennaway's testing before jemalloc entered cvs), so I think the risk of major problems is reasonably low. Other than bug fixes, I do not intend to make any more changes before 7.0. I have developed some novel algorithms for essentially eliminating thread contention on SMP systems, but it is too late in the development cycle to introduce such changes (not to mention that I lack the hardware to evaluate the algorithms). Thanks again for your patience and support. Please let me know if I can be of help in diagnosing suspected malloc issues. Jason