From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14388 invoked by alias); 15 Dec 2012 18:24:23 -0000 Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Workers List List-Post: List-Help: X-Seq: 30889 Received: (qmail 7048 invoked from network); 15 Dec 2012 18:24:20 -0000 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.2 Received-SPF: neutral (ns1.primenet.com.au: 74.125.82.171 is neither permitted nor denied by SPF record at ntlworld.com) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-proxyuser-ip:date:from:to:subject:message-id:in-reply-to :references:x-mailer:mime-version:content-type :content-transfer-encoding:x-gm-message-state; bh=DUtuj1A9TQjEZoK4lSunoffONzvhCCcyKIAUIQHloj8=; b=O98nQ+hTyry7AYlIp/chzPJxGZ8G0zu284uAB2cLj/SmcfqE5dwcOBHDcWQHLrPUxx s/bNEd5hwaC37yozLI1XxmneSHT2M/O3c3REJJxHI/IYdDo6qYT0GA2TH//eVtrFDNC9 E/FnLJEBskb0zR3hsPJHI8f6vlDJzji68Z9NRl6G8ZIRTCxJB/3504K3odyghgdWmS0r TIZbfdqVo9L6qbOvOv7PuQeAz1B4ePEVF3s9OkPe+cFO8QlPTJZsE32MDumLGKl4wq56 xfXAX7a+XGqW2RJ9TWbTcMWOyO6J48nOObcAY42RS8fDASFYV+u+3MRdgy6S6c8UA+ei Mc9w== X-ProxyUser-IP: 82.8.55.192 Date: Sat, 15 Dec 2012 18:16:14 +0000 From: Peter Stephenson To: "Zsh Hackers' List" Subject: Re: It's time for 5.0.1 Message-ID: <20121215181614.3c173f85@pws-pc.ntlworld.com> In-Reply-To: <121212112913.ZM28328@torch.brasslantern.com> References: <20121206194404.698168c9@pws-pc.ntlworld.com> <121208115416.ZM27266@torch.brasslantern.com> <20121209191005.27a7ba33@pws-pc.ntlworld.com> <121212001411.ZM27450@torch.brasslantern.com> <20121212095628.66cb27f3@pwslap01u.europe.root.pri> <121212112913.ZM28328@torch.brasslantern.com> X-Mailer: Claws Mail 3.8.0 (GTK+ 2.24.7; x86_64-redhat-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Gm-Message-State: ALoCoQlM5rtaBWYMfbhJMyW+lhPxa6aYC94lrOC67qCVAMUwrJdqcZteIAMb23AQffa/VmZI6vYB On Wed, 12 Dec 2012 11:29:13 -0800 Bart Schaefer wrote: > } it's much less wasteful to forget about > } heapstacks altogether and simply mark the current heap and start a new > } one when you push. Then you just have the one linked list and > } everything stays linear. > > Well, there are still two linked lists: the currently growing heap and > the stack of pushed heaps. I think we can do away with the Heapstack > struct and use the heapstack pointer in the Heap struct to manage the > pushed heaps. Right, there's the full linked list and what is essentially a parallel linked list with each link pointing some way back into the full list. So I suppose by default you'd just duplicate the second link from the previous node when you pushed something onto the main list. > } I think wasting something of order 16 kB each > } time we push (and getting it back when we pop) is probably neither here > } nor there these days. > > Well ... in a pathological case (lots of allocations of 8k+1 bytes) you > might be wasting as much space as was already in use. But you could > construct a similar pathological case for the current algorithm, so I > don't think it's worth solving right now. Actually, given that the whole point of the heap is so you don't have to free things immediately and hence you're already sacrificing memory you don't strictly need in favour of speed, I don't regard even that case as particularly high up the pathology scale; it registers as a moderate cold rather than the black death. Anyway, it sounds to me like this is a post-5.0.1 project and there's not a lot of point in short term fiddling, given that the problems aren't new. -- Peter Stephenson Web page now at http://homepage.ntlworld.com/p.w.stephenson/