Re: switched sparse format to binary trees

[Gerard Jungman <jungman at lanl dot gov>]

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