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

ok@cs.rmit.edu.au (Richard A. O'Keefe)
2 Apr 1996 23:47:28 -0500

          From comp.compilers

Related articles
[47 earlier articles]
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? kanze@lts.sel.alcatel.de (James Kanze US/ESC 60/3/141 #40763) (1996-03-25)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? schwarz@mips.complang.tuwien.ac.at (1996-03-25)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? pardo@cs.washington.edu (1996-03-25)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? mgrice@iastate.edu (1996-03-27)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? sberg@camtronics.com (1996-03-31)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? nather@astro.as.utexas.edu (R. Edward Nather) (1996-04-02)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? ok@cs.rmit.edu.au (1996-04-02)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? sberg@camtronics.com (1996-04-06)
Re: C code .vs. Assembly code for Microcontrollers/DSPs ? ok@cs.rmit.edu.au (1996-04-10)
| List of all articles for this month |

From: ok@cs.rmit.edu.au (Richard A. O'Keefe)
Newsgroups: comp.arch,comp.compilers
Date: 2 Apr 1996 23:47:28 -0500
Organization: Comp Sci, RMIT, Melbourne, Australia
References: 96-03-006 96-03-139 96-03-218
Keywords: optimize

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.


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).


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?"


>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. Even more surprising, I have
seen "industrial" code that failed to exploit basic ideas like
software caching and batching.


>1) There will always be a need for assembly language bit-jocks, but
>both the demand and the supply pool will get smaller.


As I don't expect the 8051 family to go away any time soon, I have to agree.
--
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.
--


Post a followup to this message

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