linux-kernel - Re: [rfc] no ZERO

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20070405053729.GQ2986@holomorphy.com>
Date:	Wed, 4 Apr 2007 22:37:29 -0700
From:	William Lee Irwin III <wli@...omorphy.com>
To:	Nick Piggin <npiggin@...e.de>
Cc:	Linus Torvalds <torvalds@...ux-foundation.org>,
	Valdis.Kletnieks@...edu, Hugh Dickins <hugh@...itas.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Linux Memory Management List <linux-mm@...ck.org>,
	tee@....com, holt@....com, Andrea Arcangeli <andrea@...e.de>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [rfc] no ZERO_PAGE?

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@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/