Re: C code .vs. Assembly code for Microcontrollers/DSPs ?

sberg@camtronics.com (Scott A. Berg) writes:
>Well in general I agree, but no one seems to have covered the all too
>common dead end. Suppose you want to sort a list of a few hundred
>seemingly random integers (no special properties to exploit like being
>generated in almost sorted order) and you are already using quicksort
>(or some other O(n log n) algorithm) and it's still too slow. There
>ARE no faster algorithms and diddling with the code to squeeze a few
>constants can make the difference.


ok@cs.rmit.edu.au says...
>Wrong. Being integers is a special property, and there ARE faster
>algorithms, including radix sort (for *fixed* integer sizes it is O(N)
>and the cross-over point for when it's better than quicksort is
>typically about 100) and bucket sort (which is O(N) average time and
>O(NlgN) worst case, and quite easy to program).


So these are 32 or even 64 bit integers or even floating point
numbers, randomly and uniformly spread across the entire range. How
many buckets is this? Or perhaps you're using different names for
sorts than I'm used to seeing.


>If I were in that kind of dead end, I'd turn around and say "hmm,
>where did these integers come from? Can I change the code that
>_generates_ them?"


I agree. Too many times the "easy" solution takes months to find
because no one questioned the basics. Then again, sometimes you're
stuck with tough problems (that's what NP-complete is all about...).


>>Besides, I've rarely run into the need for such a distinct function as
>>a list sort or a string search or some other "classroom example"
>>algorithm, and deriving minimal big-oh algorithms is rarely a pastime
>>in industry.


>I have seen "industrial" code using an O(N**3) algorithm when an
>O(N.lgN) algorithm is known. I have seen "industrial" code failing to
>take advantage of 'modern' data structures like splay trees or skip
>lists when they could have been used.


Alas, so have I. Perhaps we should spend less time attempting to
create the ultimate compiler and more time teaching practitioners how
to use what they've got! Besides, if you see these sort of problems
with the applications, why do you think the compilers are any better?
--
Scott A. Berg
--

Return to the comp.compilers page.
Search the comp.compilers archives again.