Re: Linear Search

["Randy Brukardt" <randy@rrsoftware.com>]

"Jeffrey R. Carter" <spam.jrcarter.not@spam.not.acm.org> wrote in message 
news:nshih3$lk$1@dont-email.me...
> On 09/28/2016 01:21 PM, Randy Brukardt wrote:
>>
>> Or, say compiling Ada and the search is in generated parse tables. (I was
>> able to speed up the parsing speed of our compiler by an order of 
>> magitude
>> by replacing the linear search for the next symbol by a tuned search.)
>
> Sure, I've done that, too. And when I did it, the time difference made the
> program significantly more responsive to users. But I was never searching
> anything close to 7M items. If I had written the same program today, with 
> the
> same linear search, it seems likely that it would have been fast enough, 
> and I'd
> never have needed to change it.

The problem with that logic is that people seem to expect to be able to 
compile ever-bigger programs with their much faster machines. I can't take 
all of that performance improvement for the compiler itself. (Indeed, we 
have a formal policy to take no more than the square root of the improvement 
for the optimizer, which is handled by limiting the maximum chunk that can 
be optimized.) And they also want the compiles to get done as fast as 
possible; million line programs aren't that uncommon. Sloppy algorithms can 
matter a lot. (Of course, the key is to only improve the ones that really 
matter, and not the other 90% that have no effect. But that 10% can be a big 
deal.)

                                     Randy.