Path: utzoo!attcan!uunet!lll-winken!ncis.llnl.gov!helios.ee.lbl.gov!pasteur!agate!bionet!csd4.milw.wisc.edu!mailrus!bbn!gatech!hubcap!dave
From: dave@vax1.cc.uakron.edu (David Stoutamire)
Newsgroups: comp.parallel
Subject: Re: clever programming tricks.
Summary: table lookups
Message-ID: <4158@hubcap.UUCP>
Date: 20 Jan 89 16:09:01 GMT
Sender: fpst@hubcap.UUCP
Lines: 44
Approved: parallel@hubcap.clemson.edu

In article <4147@hubcap.UUCP>, sestrich@Alliant.COM (Joe Sestrich) writes:
> 		There are a total of FIVE similar copies of this for 
> 		the complete algorithm (The original poster said 4).

The four copies were for the 16-bit example.  32 bits does
of course require five repetitions.

Joe and several others mentioned using table lookup.  For my
particular needs, I rejected this:

   1) This was (due to the nature of the contest) a program that
      had to be written entirely in Pascal under VM on an IBM 3090.
      Array/table lookups would require bounds checking,
      not to mention address calculation w/multiplication
      (yes, you can optimize your way out of these things, but
      in this case I couldn't).  This version of Pascal happened
      to offer the non-`Standard' bit operations.

   2) On a virtual memory machine, using large lookup tables
      increases the risk of being delayed for demand paging.

   3) Generating the tables take time; a 64K lookup table to do
      two sixteen bit counts does initially require those
      64K computations.  Precalculation (before execution time)
      was not a possibility.

   4) (Because this is comp.parallel) If this were being done
      on a parallel machine, memory bandwidth is something
      one wants to keep at a minimum.  Local caches don't
      help much if your lookups don't exhibit spacial (memorial? :-)
      locality.  This would depend on the machine, of course,
      but in any general purpose machine also running other users'
      code, one cannot count on the availability of fast-access
      memory.  Table lookups are grand, but are the most silicon
      expensive way of implementing a function, over any other
      non-redundant means.  Generality vs. speed and real estate.
      This doesn't mean they aren't great for specific applications,
      just not this particular one.

By the way, I did use a lookup table for board evaluation results,
but that required lookups *far* less often.  The program never
lost a game...

					     -= David Stoutamire =-