From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 32154 invoked by alias); 29 Apr 2014 19:15:06 -0000 Mailing-List: contact gsl-discuss-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gsl-discuss-owner@sourceware.org Received: (qmail 32121 invoked by uid 89); 29 Apr 2014 19:15:03 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-6.1 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 X-HELO: proofpoint4.lanl.gov Received: from proofpoint4.lanl.gov (HELO proofpoint4.lanl.gov) (204.121.3.52) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA encrypted) ESMTPS; Tue, 29 Apr 2014 19:15:02 +0000 Received: from mailrelay1.lanl.gov (mailrelay1.lanl.gov [128.165.4.101]) by mailgate4.lanl.gov (8.14.5/8.14.5) with ESMTP id s3TJExo4016211 for ; Tue, 29 Apr 2014 13:14:59 -0600 Received: from localhost (localhost.localdomain [127.0.0.1]) by mailrelay1.lanl.gov (Postfix) with ESMTP id 88B921366F61 for ; Tue, 29 Apr 2014 13:14:59 -0600 (MDT) X-NIE-2-Virus-Scanner: amavisd-new at mailrelay1.lanl.gov Received: from manticore.lanl.gov (manticore.lanl.gov [130.55.124.157]) by mailrelay1.lanl.gov (Postfix) with ESMTP id 758371366F5E for ; Tue, 29 Apr 2014 13:14:59 -0600 (MDT) Message-ID: <535FFA33.90604@lanl.gov> Date: Tue, 29 Apr 2014 19:15:00 -0000 From: Gerard Jungman User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 MIME-Version: 1.0 To: gsl-discuss@sourceware.org Subject: Re: switched sparse format to binary trees References: <535DAFC0.8090402@colorado.edu> <535ED7A5.7020309@lanl.gov> <535EFCA5.8050807@colorado.edu> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.11.96,1.0.14,0.0.0000 definitions=2014-04-29_05:2014-04-29,2014-04-29,1970-01-01 signatures=0 X-SW-Source: 2014-q2/txt/msg00017.txt.bz2 On 04/29/2014 02:39 AM, Frank Reininghaus wrote: > you can create an array of many tree nodes in a single allocation > though. The allocator struct could then store a pointer to this array, > the total size of the array, and the index of the next node that is > not in use yet. Right. This is what I meant by a pool allocator. Just to clarify, if GSL provides an allocator mechanism, it should be more general than this, but it is a good idea to provide an implementation of something like this that a client can just invoke if they want. It also gives clients an example implementation that they can use to create their own variations when necessary. This is why the avl library provides such a mechanism themselves. They know that some clients really need it. > And saving memory for each individual node also means > that the entire tree will become more cache-friendly > and thus possibly more performant. Even more important than the memory savings is the control that the client gains over cache coherency and other memory layout issues. The main lossage with malloc is that there is only one. So allocations of different kinds of memory can get interleaved, and it may become impossible to control your layout and caching. If the allocations are not exposed, then the client is wedged. > If individual nodes could be deleted at some point, then the > allocator needed some bookkeeping of reusable nodes of its own, > but the only node deletion that can take place is that all nodes > are deleted together, then this would probably be quite > straightforward to implement. In practice, you are probably right, the nodes would all be deleted together. So we do not have to worry about it too much. For the sake of completeness though, it is worth pointing out at least one simple way to handle the general case. An allocator can implement a lazy-deletion strategy, where the pool is allowed to fragment, until the client requests a repacking. You can also trigger a repacking when a certain fragmentation level is reached, although this kind of approach (garbage collection) is somewhat dangerous if the client loses control of when it happens. In any case, it is not hard to implement this sort of thing. Anyway, the main point is that once a general mechanism exists, the client can create any arbitrarily complicated scheme for themselves. They get to take control of allocations, if they need to. On 04/28/2014 07:13 PM, Patrick Alken wrote: > Anyway the study found that AVL trees were much superior to hash > tables in terms of speed. The study is here: > > http://link.springer.com/chapter/10.1007%2F978-3-540-25944-2_135 It's a shame they don't explain why this is happening. Those large factors are kind of nuts. -- G. Jungman