From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 9834 invoked by alias); 29 Apr 2014 22:07:16 -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 9820 invoked by uid 89); 29 Apr 2014 22:07:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-6.0 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 X-HELO: proofpoint5.lanl.gov Received: from proofpoint5.lanl.gov (HELO proofpoint5.lanl.gov) (204.121.3.53) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA encrypted) ESMTPS; Tue, 29 Apr 2014 22:07:14 +0000 Received: from mailrelay2.lanl.gov (mailrelay2.lanl.gov [128.165.4.103]) by mailgate5.lanl.gov (8.14.5/8.14.5) with ESMTP id s3TM7CYY011391 for ; Tue, 29 Apr 2014 16:07:12 -0600 Received: from localhost (localhost.localdomain [127.0.0.1]) by mailrelay2.lanl.gov (Postfix) with ESMTP id 3D52DE8F0BC for ; Tue, 29 Apr 2014 16:07:12 -0600 (MDT) X-NIE-2-Virus-Scanner: amavisd-new at mailrelay2.lanl.gov Received: from manticore.lanl.gov (manticore.lanl.gov [130.55.124.157]) by mailrelay2.lanl.gov (Postfix) with ESMTP id 2CF4AE8F0BA for ; Tue, 29 Apr 2014 16:07:12 -0600 (MDT) Message-ID: <53602290.8020309@lanl.gov> Date: Tue, 29 Apr 2014 22:07: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> <535FFA33.90604@lanl.gov> <53600311.7040805@colorado.edu> In-Reply-To: <53600311.7040805@colorado.edu> 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_06:2014-04-30,2014-04-29,1970-01-01 signatures=0 X-SW-Source: 2014-q2/txt/msg00019.txt.bz2 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