switched sparse format to binary trees

[Gerard Jungman]

On 05/01/2014 12:46 PM, Patrick Alken wrote:
> 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;

That's the idea. Just like the avl allocator mechanism.

> 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)

We need to think about the allocator parameter. There is
probably a design issue here. It is hard to insure that
the client uses the correct parameter if there are
several "pools" or "heaps" in existence. So the
state data represented by the parameter is
somewhat dangerous.

There may even be deeper semantic issues in keeping track
of state data like that, even though it seems attractive
to encapsulate the state in some explicit way. It has to
do with the fact that an an allocator resource is sort
of a singleton. Even if you have different ones floating
around, each one is probably doing a unique job, just
like the unique malloc/free heap.

Notice that the avl library allocator abstraction
avoids any notion of allocator state.

A client can always hide their state data behind a functional
interface. So they could easily create a "heap" for vectors,
and a "heap" for matrices, or whatever, each with their
own malloc. So it may be best to avoid any explicit
notion of state and let the client do what they want
behind the functions.

> and all malloc/free calls would then be replaced by calls to 
> allocator->malloc and allocator->free

Yup.

> In this scenario, all gsl data structures would need an additional 
> pointer to store the gsl_allocator desired by the user.

This seems correct, in order to match the allocation call with the
correct free call.

But there may be more to it as well. Basically, any function
which currently does a malloc or free needs to be thought
about, probably requiring an additional interface also
taking an allocator parameter. It is clearly possible
and probably not too difficult to do the operations
in the right order, swap the allocator pointers,
and move on, so that the container is always in
a consistent state with regard to its allocator.

> The default gsl_xxx_alloc() functions would use a stub allocator which 
> are just malloc()/free() wrappers.

Yup.

> 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?

Most of the containers have a homogeneous structure, basically
using one layer of heap allocation, for their data blocks.
When we get to something like spmatrix, there are really
at least two distinct allocation needs, for the data
and for the tree nodes. So it may well be correct to
design a more semantically rich allocation framework
for those containers.

It may be as simple as providng two allocators,
one for the nodes, one for the data. But maybe
more is needed, to allow control of the relative
locality of the nodes and data, as I wondered
earlier.

Other places in GSL may need some custom tailoring
as well. Basically, I will just grep for all the malloc
and free calls currently, and estimate what needs to
be done. Anybody interested in this should do the
same. Then we can discuss.

> 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.

Exactly.

> 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 :)

It is hard to say. But let's think about what it might entail
and weigh the costs and benefits when we know more.

--
G. Jungman