Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!udel!haven.umd.edu!socrates.umd.edu!socrates!rockwell From: rockwell@socrates.umd.edu (Raul Rockwell) Newsgroups: comp.arch Subject: Re: Compilers and efficiency Message-ID: Date: 11 May 91 04:38:55 GMT References: <9782@mentor.cc.purdue.edu> <11411@mentor.cc.purdue.edu> <653@ctycal.UUCP> <1991May8.205106.6039@Stardent.COM> <28297C23.6984@tct.com> Sender: rockwell@socrates.umd.edu (Raul Rockwell) Organization: Traveller Lines: 46 In-Reply-To: wright@Stardent.COM's message of 8 May 91 20: 51:06 GMT Herman Rubin: >> Consider the following two operations, ... >> 1. Examine a bit, ... >> 2. Find the distance to the next one in a bit stream. Terry Ingoldsby: >I have got to ask. Why is it so generally important that the >distance between bits can be determined efficiently. David Wright: Hear hear. And this leads to a second question of HR, which has been posed once before but not answered (or I missed it): Why does your application have to work on a bit stream? Chip Salzenberg: That kind of problem is not "generally important" in that it does not come up in the "general computing base". harumph. At work we have a hand-optimized assembly routine to convert from a bit array to a list of indices. It gets used a lot. Please note that a bit list is very handy for dealing with selection problems. They are very compact, and have very predictable size requirements. Selection problems include highlighting text for emphasis, intermediate results during a database query, as well as Herman Rubin's probabalistic models. They're also handy in some domains for converting from some arbitrary list of integers to a unique, sorted list (but otherwise the same integers), in O(n). We use "bit lists as integers" for other things too (once you have a generic feature you tend to use it whenever it's handy -- particularly if it's fast). As for the problem of "distance between bits" vs "absolute position of bits" note that if you have a _lot_ of bits you start talking about very long lists of integers (and possibly even exceeding maxint, or whatever for the representation you're using). This is particularly painful if your bitlist is dense. Both have their uses (as does a list ordered pairs of the form (position, offset)), and we happen to use them a lot. Raul Rockwell