Hi fellows, is there a special optimized function (in assembler maybe) for quick sorting some elements of an array, in ascending order (for C6000 architecture, or in general if is in C)? I was looking through TI site but I found nothing. Any clue is valuable. I know about the sorting code from NR but is not fast enough. Thank you! Cris
sorting
Started by ●March 11, 2004
Reply by ●March 11, 20042004-03-11
cristian wrote:> Hi fellows, > > > > is there a special optimized function (in assembler maybe) for quick sorting > some elements of an array, in ascending order (for C6000 architecture, or in > general if is in C)? I was looking through TI site but I found nothing. Any > clue is valuable. I know about the sorting code from NR but is not fast > enough. > > Thank you! > > > > CrisAn assembler instruction for sorting boggles my mind! The tendency nowadays is toward RISC sets, or at least closer to that than VAX-like CISC. A block-move instruction probably finds its way into modern processors only as a legacy of the past. I can see it now: srt listStart, length, itemSize, sortCriterion "srt" probably doesn't need more arguments, and I suppose that if numerical order were assumed, the last argument could be up-or-down. Special-purpose instructions are boldly embodied in DSPs. Zero-overhead looping can be seen as general purpose -- most programs have loops. Contrary-wise, circular buffering and bit-reversed addressing are about as special as I can imagine. Still, I don't think you'll find an assembler sort instruction in any processor. A C library call, coded in assembler, might be much faster than the high-level code from NR. If there is none but you need the speed, you might roll your own. You might also think about doing an insertion sort on the data item by item as they are acquired. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●March 11, 20042004-03-11
"Me" <secad@netspace.net.au> wrote in message news:c2qek2$4ti$1@otis.netspace.net.au...> Jerry Avins wrote: > > > srt listStart, length, itemSize, sortCriterion > > Why stop there? Let us create the instr set we always wanted. I saw the > following some years ago: > > dmns ; do what I mean, not what I say > bbw ; branch both ways > bnt ; branch to telephone number > ptp ; punch tape > pdsk ; punch disk > pop ; punch operator > hcf ; halt and catch fire > > Perhaps a group project to devise the microcode? > Jim AdamthwaiteYay! Byte magazine , some considerable time ago ran a feature on proposed Basic extensions to take advantage of the expansion in power of the new 9 bit microprocessors that would soon be on the market. If I remember correctly it had such 'higher level' gems as the COME FROM instruction and FORGET( X) where X could be a matrix! I'm so happy that we can at last look forward to an assembler version (and please can you include the esp instr in your development). Thanks - Mike
Reply by ●March 12, 20042004-03-12
Jerry Avins wrote:> srt listStart, length, itemSize, sortCriterionWhy stop there? Let us create the instr set we always wanted. I saw the following some years ago: dmns ; do what I mean, not what I say bbw ; branch both ways bnt ; branch to telephone number ptp ; punch tape pdsk ; punch disk pop ; punch operator hcf ; halt and catch fire Perhaps a group project to devise the microcode? Jim Adamthwaite
Reply by ●March 12, 20042004-03-12
cristian wrote:> is there a special optimized function (in assembler maybe) for quick sorting > some elements of an array, in ascending order (for C6000 architecture, or in > general if is in C)?Sorting is an art form. A while back I had to write a sorting function for SHARC DSP architecture - you won't find it on any of the DSP vendor's web sites. I guess sorting is not considered DSP enough.> I was looking through TI site but I found nothing. Any > clue is valuable. I know about the sorting code from NR but is not fast > enough.Well, I know the guys from NR are fond of the heap sort algorithm, because it not only has an average O(n log n) but also worst case O(n log n) runtime. In my implementation it was however more than two times slower than a (slightly modified) quick sort on average. Also, quick sort had a much smaller variance than heap sort. Both can be implemented in place (but you need an additional size O(log n) stack for quick sort). Sorting is a challange in real time systems due to its non-deterministic run time. I basically implemented all the sorting functions from descriptions in Wikipedia (http://www.wikipedia.org). Also, the fastest sorting algorithm for small array sizes is not quick sort. If you have a pure quick sort, you can speed it up quite nicely by using an insertion sort for the final stages. The break-point is a matter of trial and error (it depends on how fast you implemented the insertion sort). I spent quite some time until I had the optimal version.> Thank you!Regards, Andor
Reply by ●March 12, 20042004-03-12
Me wrote:> Jerry Avins wrote: > >> srt listStart, length, itemSize, sortCriterion > > Why stop there? Let us create the instr set we always wanted. I > saw the following some years ago: > > dmns ; do what I mean, not what I say > bbw ; branch both ways > bnt ; branch to telephone number > ptp ; punch tape > pdsk ; punch disk > pop ; punch operator > hcf ; halt and catch fire > > Perhaps a group project to devise the microcode? > Jim AdamthwaiteWe all certainly need one like iec ; if error correct which should certainly not be a conditional branch :) Bernhard
Reply by ●March 12, 20042004-03-12
Bernhard Holzmayer wrote:> We all certainly need one like > iec ; if error correct > which should certainly not be a conditional branch :)And don't forget the if-then-unless contruct. I guess it'd be handy for leap year calcualtions. -- Jim Thomas Principal Applications Engineer Bittware, Inc jthomas@bittware.com http://www.bittware.com (703) 779-7770 Build a man a fire and he is warm for a day. Set a man on fire and he is warm for the rest of his life.
Reply by ●March 12, 20042004-03-12
Is 'esp' is the mnemonic contraction of 'extra-senseless perception'? This would be a much more powerful and generalised version of 'dmns'. Jim A.
Reply by ●March 12, 20042004-03-12
Jim Thomas wrote:> > And don't forget the if-then-unless contruct. I guess it'd be handy for > leap year calcualtions. >I beleive that Perl actually has something like this. Paul
Reply by ●March 14, 20042004-03-14
Mike Yarwood wrote: (snip)> Yay! Byte magazine , some considerable time ago ran a feature on proposed > Basic extensions to take advantage of the expansion in power of the new 9 > bit microprocessors that would soon be on the market. If I remember > correctly it had such 'higher level' gems as the COME FROM instruction and > FORGET( X) where X could be a matrix! I'm so happy that we can at last look > forward to an assembler version (and please can you include the esp instr in > your development). Thanks - MikeA COME FROM statement was implemented in a PL/I compiler sometime around 1976 or so. There was a DATAMATION article about it. -- glen
