From owner-freebsd-questions@FreeBSD.ORG Thu May 20 01:32:05 2004 Return-Path: Delivered-To: freebsd-questions@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 9A1D116A4CE for ; Thu, 20 May 2004 01:32:05 -0700 (PDT) Received: from plewe.is.tsukuba.ac.jp (plewe.is.tsukuba.ac.jp [130.158.81.199]) by mx1.FreeBSD.org (Postfix) with ESMTP id A09F343D48 for ; Thu, 20 May 2004 01:32:04 -0700 (PDT) (envelope-from till@plewe.is.tsukuba.ac.jp) Received: from plewe.is.tsukuba.ac.jp (localhost [127.0.0.1]) i4K8aWtI006130 for ; Thu, 20 May 2004 17:36:32 +0900 (JST) (envelope-from till@plewe.is.tsukuba.ac.jp) Received: (from root@localhost) by plewe.is.tsukuba.ac.jp (8.12.11/8.12.11/Submit) id i4K8aWBR006129 for freebsd-questions@freebsd.org; Thu, 20 May 2004 17:36:32 +0900 (JST) (envelope-from till) Date: Thu, 20 May 2004 17:36:31 +0900 From: Charlie Root To: freebsd-questions@freebsd.org Message-ID: <20040520083631.GA5956@plewe.is.tsukuba.ac.jp> References: <20040520050918.GA85327%till@score.is.tsukuba.ac.jp> <20040520064200.GB86452@dan.emsphone.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20040520064200.GB86452@dan.emsphone.com> User-Agent: Mutt/1.5.6i Subject: Re: memory allocation/deallocation (malloc experts needed) X-BeenThere: freebsd-questions@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list Reply-To: till@score.is.tsukuba.ac.jp List-Id: User questions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 20 May 2004 08:32:05 -0000 On Thu, May 20, 2004 at 01:42:00AM -0500, Dan Nelson wrote: > In the last episode (May 20), Till Plewe said: > > My problem is essentially that freeing large numbers of small chunks > > of memory can be very slow. I have run into this problem twice so > > far. > > Do you have a testcase? The attached program mallocs 1 million > 128-byte blocks, then frees them. With MALLOC_OPTIONS set to jz (i.e. > no filling of freed memory), it takes .184 seconds to free them all. > With it set to J, it takes 1 second. > > CPU: Intel Pentium III (909.96-MHz 686-class CPU) > ... I get NUM SIZE MALLOC_OPTIONS time 1058576 128 jz 0.044 1058576 128 JZ 0.13 128*1048576 8 jz 5.28 128*1048576 8 JZ 7.70 200*1048576 8 jz 8.25 200*1048576 8 JZ 13.17 with CPU: AMD Opteron(tm) Processor 248 (2205.02-MHz K8-class CPU) but with NUM 255*1048576 I run out of memory (although I have 6GB and your test program should only use about (sizeof(void*)+SIZE)*NUM=(8+8)*255*1048576=4GB) Using NUM 256*1048576, SIZE 8 I get # gcc -o test test.c /var/tmp//ccLxywz6.s: Assembler messages: /var/tmp//ccLxywz6.s:95: Error: .COMMon length (-2147483648.) <0! Ignored. /var/tmp//ccLxywz6.s:95: Warning: rest of line ignored; first ignored character is `,' In any case since I have the pointers in a hash table (Judy array) rather than an array I need extra time for look-up/deleting the entry in the hash table as well. If I could get malloc to use a fixed memory region for the part I want to delete (both for the hash table and the information pointed to) deletion should take no time at all. In my program I get times like this DATA 6.553015 sec JUDY 7.593997 sec deleted 1272062 hash entries, freed 28542840(Judy) + 15264744(data) bytes where judy translates hash values to pointers pointing to simple structs. Since I want to delete up to 10^8 entries the times get quite bad. I guess quite a bit of the extra time is spent jumping around in memory. Your test program frees memory in the order it was allocated which should be a quite regular pattern. I will test some more and then post some more details. Thanks for your answer. - Till