From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14583 invoked by alias); 28 Apr 2014 22:35:22 -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 14564 invoked by uid 89); 28 Apr 2014 22:35:22 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-6.2 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; Mon, 28 Apr 2014 22:35:19 +0000 Received: from mailrelay2.lanl.gov (mailrelay2.lanl.gov [128.165.4.103]) by mailgate4.lanl.gov (8.14.5/8.14.5) with ESMTP id s3SMZHXA024247 for ; Mon, 28 Apr 2014 16:35:17 -0600 Received: from localhost (localhost.localdomain [127.0.0.1]) by mailrelay2.lanl.gov (Postfix) with ESMTP id D79EFE8EECE for ; Mon, 28 Apr 2014 16:35:17 -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 C9351E8EEC3 for ; Mon, 28 Apr 2014 16:35:17 -0600 (MDT) Message-ID: <535ED7A5.7020309@lanl.gov> Date: Mon, 28 Apr 2014 22:35: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> In-Reply-To: <535DAFC0.8090402@colorado.edu> Content-Type: text/plain; charset=ISO-8859-1; 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-28_03:2014-04-28,2014-04-28,1970-01-01 signatures=0 X-SW-Source: 2014-q2/txt/msg00014.txt.bz2 On 04/27/2014 07:32 PM, Patrick Alken wrote: > This actually makes a huge speed improvement in duplicate detection and > element retrieval for large sparse matrices. There may however be a > performance hit since a new tree node must be allocated each time an > element is added to the matrix. But I believe the tradeoff is worth it. For what it's worth, the right thing to do is probably to expose the avl allocation strategy to the GSL client in some way. It could be as simple as an extra argument to gsl_spmatrix_alloc(), which could be a pointer to a generic allocator strategy struct (similar or identical to 'struct libavl_allocator'). This is the most general solution, which requires that clients who care be able to write their own allocator. As an aid, GSL could also supply a replacement allocator strategy object, maybe based on a pool allocator with a variable amortization size. This would be in addition to the default (and now implicit by design) malloc/free strategy. This opens a generic issue regarding GSL containers, which is one of the many reasons I avoid them. That is, the allocation strategy is not exposed. You can trace the allocations down to the gsl_block level, where there is a hard-coded malloc(). Very sad. This could all be fixed by adding gsl container allocation functions (parallel to the current xxx_alloc functions) which take an extra argument (something like pointer to a struct of function pointers) for the allocation strategy. The extra argument could be passed down to the gsl_block level where it is invoked. On the other hand, all this needs to be studied a bit. My understanding is that modern linux implementations will use mmap() for large enough allocations. This will change the tradeoffs. I have no idea what other platforms do. It's not just your old malloc anymore... -- G. Jungman