Path: utzoo!attcan!uunet!lll-winken!ames!ucsd!orion.cf.uci.edu!oberon!nunki.usc.edu!jeenglis
From: jeenglis@nunki.usc.edu (Joe English)
Newsgroups: comp.lang.c
Subject: Re: BIT Counting: C programming problem
Message-ID: <2481@nunki.usc.edu>
Date: 27 Jan 89 03:21:41 GMT
References: <8398@dasys1.UUCP> <1238@goofy.megatest.UUCP>
Reply-To: jeenglis@nunki.usc.edu (Joe English)
Organization: University of Southern California, Los Angeles, CA
Lines: 38


djones@megatest.UUCP (Dave Jones) writes:
<From article <8398@dasys1.UUCP>, by ejablow@dasys1.UUCP (Eric Robert Jablow):
<> In article <35329@think.UUCP> barmar@kulla.think.com.UUCP (Barry Margolin) writes:
<>>I haven't seen anyone so far suggest the far end of the time/space
<>>trade-off: have a 64K table, with each element N containing the number
<>>of bits in N 

<> That is a ridiculous idea.  For microscopic savings in speed, you
<> waste 63K of space.

<As I type this letter, I am using what is, by today's standards, an
<excellent, but rather commonplace workstation: a Sun3/60.  It has 8Meg
<of RAM and a virtual memory of about 42Meg, if I remember correctly.
<So 64K is less than two tenths of one percent of the virtual memory.

<Always bear in mind that "ridiculous" depends on the point of view of
<the ridiculer.

Well, this here ridiculer also thinks the idea is
ridiculous: Even though you've got 8 Meg of RAM, if
the program is running under Unix it's not going to
have it all to itself, and that 64K table is likely
to be swapped out.  So now the ultrafast straight
lookup algorithm may take a _large_ disk read and
has lost whatever speed advantages it might have
had.

Besides that, a 64K lookup table for bit-counting
strikes me as just plain inelegant and wasteful,
even if it's going to be run on a machine with 8
gigabytes of core.  Don't you know there are
starving Lisp processes out there? :-)


--Joe English

  jeenglis@nunki.usc.edu