No place to go ...

Index > Main > No place to go ...

Author

Thread

f14t

Joined: 27 Sep 2006
Posts: 36

f14t 26 Oct 2006, 12:53

I have no other place to go and post this question. Sad

(I mean no other section seemed appropriate enough.)

Please, (will any body ?) provide a generalised optimized to the neck
assembly version of the following code.

The code should perform optimally on all x86 through Px and it should
definitely outperform any compiler generated one.

Assembly language code should be in FAsm style.

Sorry if i am sounding too demanding (take it as a challenge Wink

)

Code:

void sort(int *array, int count)
{
   int i, j, t;
   for (i=1; i<count; i++)
   {
       for (j=0; j<count-i; j++)
       {
           if (array[j] > array[j+1])
           {
                t = array[j];
                array[j] = array[j+1];
                array[j+1]  = t;
            }
        }
   }
}

The code if you have'nt got yet is written in C. Wink

Quote:

Doom's Day is Today.

[/code]

26 Oct 2006, 12:53

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 26 Oct 2006, 13:53

Quote:

The code should perform optimally

what's "optimally"?

also note that hand-translating code from C code usually doesn't provide good result. C is already an abstraction of assembly language, it can be taken as subset of it.

The trick is to create algorithm thinking in assembly terms, not in C terms.

Typical example: in C you often use constructs like this:

Code:

type array[size];
for(x=0; x<size; x++) {
  array[x]  
  array[x]  
  array[x]  //used plenty of times in loop
}

in assembly, you usually write code in this manner:

Code:

x=size;
type *y=array
while(x) {
  *y
  *y
  *y //used plenty of times in loop
  y++;
  x--;
}

on most of real-world output of compilers, the second performs much faster. but very few C gurus would write the code this way.

hope you understand, and sorry not to post the bubble sort algo, i was just generally talking about asm vs. C optimization

Last edited by vid on 26 Oct 2006, 16:08; edited 1 time in total

26 Oct 2006, 13:53

Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania

Borsuc 26 Oct 2006, 15:19

f14t: I'm sure there are lots of these kind of algos written in asm. However as vid pointed out, it's not MUCH efficient (though it is a bit) than a compiler. Asm is efficient when you design the algo in low-level.

26 Oct 2006, 15:19

f14t

Joined: 27 Sep 2006
Posts: 36

f14t 27 Oct 2006, 11:44

"Optimally" means smallest and fastest code.

I will really appreciate if some assembly lover codes this thingy in
assembly Smile

instead of making excuses. Wink

Quote:

short circuit;

27 Oct 2006, 11:44

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 27 Oct 2006, 12:01

there is nothing like "optimal". for every optimal code, you can write more optimal one. and also there's nothing like code optimal for every pentium. same code may run faster on one pentium, and slower on another

27 Oct 2006, 12:01

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 27 Oct 2006, 13:47

http://www.azillionmonkeys.com/qed/asmexample.html #4

27 Oct 2006, 13:47

Goplat

Joined: 15 Sep 2006
Posts: 181

Goplat 27 Oct 2006, 18:46

Bubble sort is slow no matter how much you optimize it.

27 Oct 2006, 18:46

f0dder

Joined: 19 Feb 2004
Posts: 3175
Location: Denmark

f0dder 27 Oct 2006, 20:50

Tada, Goplat hit the nail's head.

btw vid, it will often be possible for a compiler to optimize your first example into the second example automatically...

27 Oct 2006, 20:50

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 27 Oct 2006, 21:08

f0dder: but you can seldom see such optimization in real-world app. at least those which i have seen, not sure about GCC.

27 Oct 2006, 21:08

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 28 Oct 2006, 09:54

Hey, people did you even watch that link. The thing about sorting algorithms is what they are used on. For sorted data the BubbleSort() will run once and finish in O(1) time. The QuickSort() will ALWAYS run at least O(nlogn) times. That is the partitioning and that it always has to do it.

BubbleSort() characteristics: MAX: O(n²), MIN: O(1)
QuickSort() characteristics: MAX: O(n²), MIN: O(nlogn)

Hmm, which one is better. In 3D which is more ideal than Bubble??? Like when you don't rotate an object the z-buffer you sort is always sorted and QS still takes nlogn, but BS takes 1 in this case. Your FPS will hit the ceiling at constant scenes. You can a) be happy about FPS or b) make some other useful calculations and call the sorting with bigger intervals...

28 Oct 2006, 09:54

f0dder

Joined: 19 Feb 2004
Posts: 3175
Location: Denmark

f0dder 28 Oct 2006, 12:27

Madis: those are some good points too. QuickSort and BubbleSort are usually the ones mentioned in situations like this because they're well-known and easy to implement - and quicksort is a good "all-round" algorithm (at least partially because it requires no extra memory, doing sorting in-place).

But of course you can often use specific algorithm if you know specific things about your dataset - if it's often sorted, even partially, qsort is not necessarily a good choice Smile

. Hybrid sorts are also interesting (one of the simples hybrids is to use bubblesort or similar in qsort when you're processing a small range).

A problem I've seen with some comp.sci. educated people is that they get entirely lost in Big-O notation, and forget to think for themselves. Bubblesort doesn't have particularly good Big-O properties, but if you're only sorting three items (but doing it some million times - think polygin rasterizer setup) bubblesort isn't all bad, and more complex but better Big-O algos die in performance because of setup overhead...

28 Oct 2006, 12:27

f14t

Joined: 27 Sep 2006
Posts: 36

f14t 31 Oct 2006, 08:13

That's all good and well said by all of you !

But optimal or not
PLEASE code the thingy in Assembly.

For GOD's sake, stop making excuses.

31 Oct 2006, 08:13

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 31 Oct 2006, 09:47

http://www.google.com/search?hs=4BV&hl=en&lr=&client=opera&rls=en&q=bubblesort+assembly&btnG=Search

31 Oct 2006, 09:47

tom tobias

Joined: 09 Sep 2003
Posts: 1320
Location: usa

tom tobias 31 Oct 2006, 10:00

Quote:

For GOD's sake, stop making excuses

In my opinion, the question of studying various sorting algorithms has little to do with notions of religion. Sorting algorithms are based on VERIFIABLE data, while supernatural gremlins, ghosts, witches, sorcerers, (today is Halloween!) and various deities, including delusions about "god", are based upon fantasy, imagination, and creativity. I would suggest this book by Donald Knuth, where you will find many different kinds of sort routines, written in assembly language:
The Art of Computer Programming, second edition, volume 3/Sorting and Searching, Addison Wesley, publisher, 1998, ISBN 0-201-89685-0.
http://pl.wikipedia.org/wiki/The_Art_of_Computer_Programming
You can purchase the book, new, here:
http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850
There are also links to the same book, used rather than new, therefore less expensive, advertised at the same site.

31 Oct 2006, 10:00

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20422
Location: In your JS exploiting you and your system

revolution 31 Oct 2006, 10:39

f14t wrote:

PLEASE code the thingy in Assembly.

f14t you are being too demanding, there are already numerous examples on the net, use google before you start demanding efforts from people in this (or any) forum, it is just common manners.

The reason nobody is posting a solution for you is because it has already been done thousands of times and the results are freely available to anyone (that means you) that takes the time to actually search for themselves. Please take some of your own time to solve the problem you have. Later if you have a specific difficulty then feel free to ask for help from the people here and I am sure you will get the help you need. At least show that you have put in some effort of your own brefore posting then people will respect your post more and give it due attention.

31 Oct 2006, 10:39

f14t

Joined: 27 Sep 2006
Posts: 36

f14t 31 Oct 2006, 11:05

Okay

Code:

proc sort uses ebx esi edi array:DWORD, length:DWORD
    mov esi, [array]
    mov eax, 1
    jmp .l1_test
 .l1:
    xor ebx, ebx
    jmp .l2_test
 .l2:
   mov ecx, ebx
   inc ecx
   mov edi, [esi + ebx * 4]
   mov edx, [esi + ecx * 4]
   cmp edi, edx
   jb .skip_Swap
   mov [esi + ebx * 4], edx 
   mov [esi + ecx * 4], edi
 .skip_Swap:
   inc ebx
 .l2_test:
    mov ecx, [length]
    sub ecx, eax
    cmp ebx, ecx
    jb .l2
    inc eax
 .l1_test:
    cmp eax, [length]
    jb .l1
     ret
endp

Done

31 Oct 2006, 11:05

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum