Re: [rfc] no ZERO_PAGE?

[William Lee Irwin III]

On Wed, Apr 04, 2007 at 05:27:31PM -0700, Linus Torvalds wrote:
>> Good point. In fact, it doesn't need to be a malloc() - I remember people 
>> doing this with Fortran programs and just having an absolutely incredibly 
>> big BSS (with traditional Fortran, dymic memory allocations are just not 
>> done).

On Thu, Apr 05, 2007 at 04:30:26AM +0200, Nick Piggin wrote:
> Sparse matrices are one thing I worry about. I don't know enough about
> HPC code to know whether they will be a problem. I know there exist
> data structures to optimise sparse matrix storage...

\begin{admission-against-interest}

Sparse matrix code goes to extreme lengths to avoid ever looking at
substantial numbers of zero floating point matrix and vector entries.
In extreme cases, hashing and various sorts of heavyweight data
structures are used to represent highly irregular structures. At various
times the matrix is not even explicitly formed. Most typical are cases
like band diagonal matrices where storage is allocated only for the
nonzero diagonals. The entire purpose of sparse algorithms is to avoid
examining or even allocating zeros.

The actual phenomenon of concern here is dense matrix code with sparse
matrix inputs. The matrices will typically not be vast but may span 1MB
or so of RAM (1024x1024 is 1M*sizeof(double), and various dense matrix
algorithms target ca. 300x300). Most of the time this will arise from
the use of dense matrix code as black box solvers called as a library
by programs not terribly concerned about efficiency until something
gets explosively inefficient (and maybe not even then), or otherwise
numerically naive programs. This, however, is arguably the majority of
the usage cases by end-user invocations, so beware, though not too much.

I'd be more concerned about large hashtables sparsely used for the
purposes of adjacency detection and other cases where large time vs.
space tradeoffs are made for probabilistic reasons involving
collisions.

\end{admission-against-interest}


-- wli
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/