Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!sdd.hp.com!wuarchive!udel!rochester!cornell!uw-beaver!rice!ariel.rice.edu!preston
From: preston@ariel.rice.edu (Preston Briggs)
Newsgroups: comp.arch
Subject: Re: Compilers and efficiency
Message-ID: <1991Apr28.161032.8379@rice.edu>
Date: 28 Apr 91 16:10:32 GMT
References: <9782@mentor.cc.purdue.edu> <4082@batman.moravian.EDU> <11411@mentor.cc.purdue.edu>
Sender: news@rice.edu (News)
Organization: Rice University, Houston
Lines: 44

hrubin@pop.stat.purdue.edu (Herman Rubin) writes:

>Consider the following two operations, which comprise more than 25% of the 
>operations in some highly efficient, from the "picocode" standpoint, methods
>for generating non-uniform random numbers.
>
>1.  Examine a bit, and take some action depending on it.
>    Also, the next time this is to be done, this bit effectively
>    no longer exists.  It is necessary to make provision at least
>    somewhere for replenishing the supply of bits.
>
>2.  Find the distance to the next one in a bit stream.
>    The same considerations as above apply.

These sort of things are certainly CISCish and would be difficult to
recognize in a compiler.  However, I would argue that they are
possibly misrepresented.

How about a linked-list (oh no!) of integers.
An element in the list represents a "1" bit.
The integer is number of "zero" bits preceding the 1.
The stream starting with 001010000001...
would look like

	(2, 1, 6, ...)

So, a single memory access per 1 bit.  The "distance to next 1 bit" 
questions can be answered immediately.  The "examine a bit and take
an action" can be done with some of those fancy "decrement, test, and branch"
instructions people use for closing loops.

Alternatively, ...
It seems like there's something producing the bits and something consuming
them and making decisions based on them.  Why not have the producer
simply call the alternate choices in the consumer directly?


Generally though, my critisism is that you're thinking very low-level.
You decided how you want these operations represented and you seem
unwilling to talk about them at a level above "bit stream".
If you must think this way, I expect you're going to have to
code in the same fashion; that is, in assembly.

Preston Briggs