Re: switched sparse format to binary trees

[Gerard Jungman <jungman@lanl.gov>]

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