switched sparse format to binary trees

[Patrick Alken]

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
>