control structures (was "Re: Sins")

[Grant Edwards]

In article <86so055xky.fsf at g.local>, Gareth McCaughan wrote:
>Grant Edwards wrote:
>
>> At least with the compilers I've used, that depends on the case
>> values.  If the switch case values are sparse, the code
>> generated is the same as it would be for If/elif.
>> 
>> For example:
>..
>> May generate table-lookup code that is O(1), but
>> 
>>   switch (c)
>>     {
>>     case      0: [...] break;
>>     case   3450: [...] break;
>>     case -49393: [...] break;
>>     case 233450: [...] break;
>>     case -14000: [...] break;
>>     case  -9834: [...] break;
>>     }
>>     
>> Would hopefully generate O(n) linear-search code.
>
>It ought to generate code that does something more
>like a binary chop. Looking at the output of gcc -O2
>on a big random switch, that's certainly what gcc
>does.

If it's big enough, then that's what it should do -- then you
can get O(log n) [I wonder how it handles cases that
fall-through...] For a small number of cases I wouldn't be
surprised if linear code performs better.  In either case, it's
not O(1) like a table-lookup.

-- 
Grant Edwards                   grante             Yow!  .. does your DRESSING
                                  at               ROOM have enough ASPARAGUS?
                               visi.com