This is the mail archive of the
gsl-discuss@sourceware.org
mailing list for the GSL project.
Re: switched sparse format to binary trees
- From: Gerard Jungman <jungman at lanl dot gov>
- To: gsl-discuss at sourceware dot org
- Date: Tue, 29 Apr 2014 16:07:12 -0600
- Subject: Re: switched sparse format to binary trees
- Authentication-results: sourceware.org; auth=none
- References: <535DAFC0 dot 8090402 at colorado dot edu> <535ED7A5 dot 7020309 at lanl dot gov> <535EFCA5 dot 8050807 at colorado dot edu> <CAFoZWWg9ENCX0cxNBMGJLc9AxT0Tt2a9yaBq7NctcLLK4jLeVA at mail dot gmail dot com> <535FFA33 dot 90604 at lanl dot gov> <53600311 dot 7040805 at colorado dot edu>
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