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
