GSL containers (switched sparse format to binary trees)

[Gerard Jungman <jungman at lanl dot gov>]

Here is an example of the sort of thing that
troubles me.

http://stackoverflow.com/questions/15988836/better-memory-management-for-gsl-gsl-vector

It is a reasonable discussion of exactly the sort of
use case that keeps coming up. A couple independent
issues are raised here.

First is the question of allocation/deallocation overhead,
which I think is the smaller of the issues, although it is
important for people who need a lot of small vectors.
This is the standard example justifying use of a
custom pool allocator.

Someone suggested using a single large gsl_block, effectively
using that as a pool. This is not stupid, although it only
works for some kinds of codes, where the allocation and
hand-off of memory can be done in a central place, like
at application startup time or something. At least that
is how I think of that usage case. It appears that the
OP was in one of the more de-centralized situations,
where this would not work nicely.

Ignore the associated comment about the "price you pay"
when using a language without built-in garbage collection.
Garbage collection (or lack thereof) is not the problem.
But that is a separate discussion. See Stroustrup's comments
about the correct use of the heap, in various talks lately.

Second is the issue of value-semantics for containers. This
is very tricky, possibly the deepest problem of all. Notice
how the OP created a custom allocation function which returns
a gsl_vector by value, not by pointer. That may or may not be
the right choice for him, but it is interesting that he chose
to do it that way.

Value-semantics is probably the most important issue for
container design, probably for several reasons. At the
top of my list is the desire to get things onto the
stack whenever possible. The fact that gsl_vector
(the struct itself, not the data) is off the heap
is an annoyance.

And it's the kind of annoyance that may be no problem
for some people and a show-stopper for others. It's
too hard to tell in advance, since it is too hard
to predict how modern hardware will treat your
code. Stack-based computation helps, and linear
traversal of data structures helps a lot, because
the pre-fetcher will bring in the pages you need
before you actually need them, as long as it can
predict which ones are needed next.

The heap tends to gum everything up on modern architectures,
unless you are careful. And taking that kind of care may
require taking over the alloc/free control from the
standard library.


So, the specific point raised by this value-semantics
business, and its effect on heap confusion, is this:
what to do about the fact that the GSL container
structs are always off the heap?


The final post in this short thread may hit the nail on
the head. What he suggests is what I almost always do:
use C++ containers and C++ code as much as possible,
and bang the pointers into GSL functions when necessary.
A bit sad.