flat assembler
Message board for the users of flat assembler.

Index > Main > No place to go ...

Author
Thread Post new topic Reply to topic
f14t



Joined: 27 Sep 2006
Posts: 36
f14t
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]
Post 26 Oct 2006, 12:53
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
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
Post 26 Oct 2006, 13:53
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Borsuc



Joined: 29 Dec 2005
Posts: 2466
Location: Bucharest, Romania
Borsuc
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.
Post 26 Oct 2006, 15:19
View user's profile Send private message Reply with quote
f14t



Joined: 27 Sep 2006
Posts: 36
f14t
"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;
Post 27 Oct 2006, 11:44
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
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
Post 27 Oct 2006, 12:01
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
Post 27 Oct 2006, 13:47
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Goplat



Joined: 15 Sep 2006
Posts: 181
Goplat
Bubble sort is slow no matter how much you optimize it.
Post 27 Oct 2006, 18:46
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
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...
Post 27 Oct 2006, 20:50
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
f0dder: but you can seldom see such optimization in real-world app. at least those which i have seen, not sure about GCC.
Post 27 Oct 2006, 21:08
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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...
Post 28 Oct 2006, 09:54
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
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...
Post 28 Oct 2006, 12:27
View user's profile Send private message Visit poster's website Reply with quote
f14t



Joined: 27 Sep 2006
Posts: 36
f14t
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.
Post 31 Oct 2006, 08:13
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
Post 31 Oct 2006, 09:47
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
tom tobias



Joined: 09 Sep 2003
Posts: 1320
Location: usa
tom tobias
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.
Post 31 Oct 2006, 10:00
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17492
Location: In your JS exploiting you and your system
revolution
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.
Post 31 Oct 2006, 10:39
View user's profile Send private message Visit poster's website Reply with quote
f14t



Joined: 27 Sep 2006
Posts: 36
f14t
Shocked 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 Laughing
Post 31 Oct 2006, 11:05
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.