From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 5076 invoked by alias); 1 May 2014 18:46:50 -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 5064 invoked by uid 89); 1 May 2014 18:46:49 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 X-HELO: ipmx5.colorado.edu Received: from ipmx5.colorado.edu (HELO ipmx5.colorado.edu) (128.138.128.235) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 01 May 2014 18:46:48 +0000 From: Patrick Alken Received: from bonanza.ngdc.noaa.gov ([140.172.179.41]) by smtp.colorado.edu with ESMTP/TLS/DHE-RSA-AES256-SHA; 01 May 2014 12:46:47 -0600 Message-ID: <53629696.7070907@colorado.edu> Date: Thu, 01 May 2014 18:46:00 -0000 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> <535FFA33.90604@lanl.gov> <53600311.7040805@colorado.edu> <53602290.8020309@lanl.gov> In-Reply-To: <53602290.8020309@lanl.gov> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-SW-Source: 2014-q2/txt/msg00020.txt.bz2 Gerard, I was thinking a little more about your suggestion and just wanted to clarify something. As I understand it, what you are proposing is to define a new "allocator" structure such as: typedef struct { void *malloc(size_t size, void *param); void free(void *block, void *param); } gsl_allocator; And then for every gsl_xxx_alloc function, we should make a new function gsl_xxx_alloc_m() which would be: gsl_xxx_alloc_m(normal_args, gsl_allocator *allocator, void *allocator_param) and all malloc/free calls would then be replaced by calls to allocator->malloc and allocator->free, passing along allocator_param each time which can contain the bookkeeping structure needed by the user's own implementation of malloc/free. In this scenario, all gsl data structures would need an additional pointer to store the gsl_allocator desired by the user. The default gsl_xxx_alloc() functions would use a stub allocator which are just malloc()/free() wrappers. For this implementation, every gsl module would use the same gsl_allocator framework. I wanted to confirm with you that this is what you intended? Or are you thinking of module-specific allocators since you were focusing a lot on the spmatrix design? It seems like a reasonable idea to me, and if we are going to do it, it should be done before the 2.0 release, since every gsl_workspace will need to be modified. I'm not certain how much demand there will be for something like this, since I suspect most users won't want to write their own malloc/free implementations, but who knows :) Patrick On 04/29/2014 04:07 PM, Gerard Jungman wrote: > On 04/29/2014 01:52 PM, Patrick Alken wrote: >> However, I think this is not common, and the simplicity of the memory >> management scheme outweighs the benefit of handling this rare case I >> think. > Yeah. If a matrix has too many zeros, the client can always repack > it by copying it to a new sparse matrix. This is probably a > reasonable usage scenario. > > >> For now, the spmatrix routines internally handle all of the block >> allocation, node array pointers, etc. I don't think its really >> necessary to expose this to the general user, since its already about >> as efficient as it will probably get, and most users (like myself) >> simply want a nice easy intuitive interface to build a matrix. > It's not really about efficiency in the allocations, although that might > effect some people. It's more about control of memory layout. > > My guess is that you won't see any difference in the efficiency > of simple test code. You can run the numbers and see what the > differences are; it would be interesting to see in any case. > > The real problem is that a client may need to adjust their layout > to satisfy cache requirements or for other reasons. > > In principle, all that's needed is an extra gsl_spmatrix_alloc_xxx() > function which takes one extra argument, which is the allocation strategy. > People who need it can use it. Those who don't care can use the function > with the simpler prototype. But it should be part of a general design > for controlling allocation in all the GSL containers. > > Even just for spmatrix, there is more than just the issue of managing > the tree node lifetimes. There are issues of data locality in accessing > the tree. For example, is it better to store the numerical data > close to the node data or is it ok to be farther away? > In general, there is no one good answer to this question. > It depends on the traversal pattern, the operations performed, > and the platform. I have seen some strange and surprising answers > to questions like this on different hardware. I don't understand > the spmatrix design well-enough to tell what choices you have > made, so I'll trust that you have thought about these things. > > In the end, only the client knows the answer to the layout question. > That's why they need some flexibility in the design. > > > I have argued in the past that the GSL containers are brain-damaged > in several ways. The absence of client control over allocation and > layout is one of them. As always, I take at least half the > responsibility for this situation, since I was one of two > people who was there "on that day". I would just like to > see these questions discussed in light of the mistakes > of the past... and of the intervening 16 years of experience. > > -- > G. Jungman >