[linux-elitists] 32 essential computer books?

Jim Thompson jim@netgate.com
Thu Dec 18 15:27:53 PST 2003


Ben Woodard writes:
> On Thu, 2003-12-18 at 13:25, Nick Moffitt wrote:
> > begin  Ben Woodard  quotation:
> > > On Thu, 2003-12-18 at 10:02, Jim Thompson wrote:
> > > > The Art of Computer Programming, Volumes 1-3, Donald Knuth.
> > > 
> > > I think that these are fine books but I'd have to argue with you
> > > regarding them.  I think it is important for any programmer to have good
> > > algorithms and data structures experience but these books are not the
> > > way to get it. Plus they are terribly out of date not necessarily with
> > > regard to the information that they have but with regards to the place
> > > that the information has in the wider realm of computer programming.
> > > 
> > 
> > 	I would argue that they have other faaults as well.  They were
> > written during a time when memory accesses were equivalent to
> > instruction execution, and before pipelining created elaborate cache
> > hierarchies within a CPU.  Knuth is only *now* re-writing them for
> > RISC, which was So Over by 1998 that it's kind of embarassing.
> > 
> > 	They're like good heavy leather-bound legal books: they look
> > impressive on your bookshelf.  
> 
> Thank you for bringing up this point, Nick. I had forgotten about that
> one. It is rather amazing what happens to algorithms when you change
> some of the assumptions and throw all the oddities of modern hardware
> into the fray.  For example sometimes it is worth it to have the
> processor do twice as much work internally rather than doing an
> additional memory access.

Note, you haven't shown this example.
 
> For example, in my current world of high performance computing, what I
> am seeing is that most of the time you can't use data structures more
> elaborate than an array. Even linked lists are verbotten. The problem is
> if you have this massive amount of data and you need to do something to
> it, and you have lots of processors the data pretty much has to be in an
> array. There is no parallel algorithm to traverse a linked list, or most
> kinds of trees or things like that.

Bullshit.  Here is one quick example.

http://www.extreme.indiana.edu/hpjava/papers/implicit/node34.html

Now, yes, thats merging, not traversing, but traversal is part of
merging, etc.

You must be talking to a bunch of "pornographic fortran" geeks.

That all said, most scientific computing is based in matrix algebra,
and as such, is well-represented by vectors (arrays).
 
> Try to come up with a parallel algorithm that searches for something?
> What you will find is that in today's world when performance really
> matters and you are forced to do things in parallel, the computer
> science just doesn't exist.

There is a ton of reasearch on parallel search.  Google for "Young
Brothers Wait", for instance.

> I don't know if I understand the problem well enough to explain it but
> what I gather is the fundamental problem is that all the mathematics of
> computer science is based upon the assumption that you are executing on
> a Von Neuman machine and parallel computers are not Von Neuman machines.
> -ben

Wow... are you ever wrong.

I cut my teeth (first real unix kernel job) at Convex, which built
SIMD (vector) machines, then parallel SIMD machines. That was 1986 or so.

Even then, the above statement was wrong.

These days its cheap to build an N-way (for small values of 'N')
parallel machine, and various CPUs have SIMD fp units attached.

While vectorizing arrays is EZ (read: cheap to implement), arrays
bring with them their own special issues.  Accesses tend to saturate
the memory system (and thrash the data cache) 

-- 
"Speed, it seems to me, provides the one genuinely modern pleasure."
			-- Aldous Huxley (1894 - 1963)




More information about the linux-elitists mailing list