Speed of Assembler code in comparision with other languages

[REM]

Now my question is, how fast is Assembler code in comparision with other languages such as C++ or Visual Basic. I know it is a LOT faster, but can someone give me an example?

Later(z)

REM

[Paul282]

depends on the app.

A windows app will see little difference as far as speed of the interface is concerned because it's still API calls, but in an intensive loop for compression, encryption or math calculations for graphics you would see quite good performance increases.

[REM]

OK, thanks for your reply paul, but i was wondering about certain situations. For example, compare the speed at which a program could find all prime numbers from 1 to 10000000 (10 million). Take a program in C++ and a program in assembler. What sort of speed ratios are we talking here. Note, no GUIs, just outputting the primes to a file. How much faster would assembler be roughly? 10% faster, 100% faster, 200% faster?!?!?!?

Thanks, i am curious at the speed. If you have rough idea, please post.

Later

REM

[V(ery) Basic]

I'm doing this now in VB. Then I'll do it in C++:

Looping 1 through 10000001 (step 2) and seeing if they are prime numbers. (No outputting to a file, it would be a bit too big I think). I'm using GetTickCount to find the time in milliseconds. I don't have a ASM compiler (or know anything about the ASM language) so I'm hoping parksie can do that.

Oh.

I think VB's just crashed. Maybe 10,000,000 is a bit too much.

[Paul282]

I did this a while ago in VB and Borland C++ builder.

The results were disappointing (from a lang change point of view).

My software could calculate:

78,498 primes (all the primes from 1 to 1,000,000 in 45.48537 seconds) or (because the factors are much smaller) all the primes from 1 to 100,000 (9,592 of them) in 0.7 seconds

BCB was 2 seconds slower from the 1,000,000 and about the same for 100,000

I still have the source code for both.

I found a little pattern in primes which lets me speed the app up by about 500%, I'd be interested if you could calc all the primes from 1 to 1,000,000 faster and hold them in an array (or whatever)

Not good enough at assembly yet to write it :-( sorry.

[Paul282]

I should add though that BCB4.0's pentium pro compile made little difference which was a common whinge yet VB p6 compile made a substancial difference.

Recompile in BCB5 might help (but I don't own it)

[kb244]

I think it might be good to note, that you can embed ASM in C++, belive it's called ASM Inline, you just start an ASM block, and type in your ASM codes. as far as the one that said the loop crashed in VB, and 10,000,000 might have been too much. that depends on the Data Type you used

Byte 0 to 255
Boolean True or False
Integer -32,768 to 32,767
Long -2,147,483,648 to 2,147,483,647
Single -3.402823E38 to -1.401298E-45 for negative values;
1.401298E-45 to 3.402823E38 for positive values
Double -1.79769313486231E308 to -4.94065645841247E-324
4.94065645841247E-324 to 1.79769313486232E308
Currency -922,337,203,685,477.5808 to
922,337,203,685,477.5807
Decimal
+/-79,228,162,514,264,337,593,543,950,335
with no decimal point;
+/-7.9228162514264337593543950335
with 28 places to the right of the decimal; smallest
non-zero number is
+/-0.0000000000000000000000000001
Date January 1, 100 to December 31, 9999

for 10,000,000 sounds like you need to use a double at the least(A Long wont go past 2 mil)

[REM]

Thanks guys. assembler definately seems worth looking into. Thanks for all your replies BTW, kb244, how do you add assembler source to your C++ project? I have the Sams teach Yourself C++ in 21 Days, but it doesn't cover such things as that. Could you explain or point me to a web iste that does? Thanks.

Later

REM

[kb244]

Of course a book like that isnt going to cover that topic since it's not within the scope in the book, and wouldnt mean much to a beginner. anyways check MSDN msdn.microsoft.com, there were also a few books I had that mentioned it

it was something like


asm {
//you ASM codes go here
}

it was something to that degree. I think what it does is when it compiles C++, it ends up being machine language anyways, and ASM in my opinion is very close to machine code, so it just jabbs the ASM code when that routine is called and has a inline/inserted ASM block in it, so machine code next to machine code goes just fine, (caution though, if you dont know what you are doing the ASM codes can have bad effects)

[parksie]

In C and C++, the arguments are passed on the stack in reverse order.

void MyFunc(long A, long B);

Any calls to this would be expanded to:

push B
push A
call MyFunc

In C, the return value is stored in the extended AX register (EAX).

However, when using inline asm, you can access the parameters by name (which makes it a hell of a lot easier!)

// inlinetest.cpp
#include <iostream>
using namespace std;

int power2(int num, int power);

void main() {
   cout << "3 times 2 to the power of 5 is " << power2(3, 5) << endl;
}

int power2(int num, int power) {
   __asm {
      mov eax, num    ; Get first argument
      mov ecx, power  ; Get second argument
      shl eax, cl     ; EAX = EAX * ( 2 to the power of CL )
   }
   /* Return with result in EAX */
}

That works on VC++ 5 (no service pack).

[kb244]

Very nice example Parksie, and yes I agree being able to call the names within the ASM does make it a hell of a lot easier.

[parksie]

It's a much better alternative than contaminating the stack when you try and access the parameters or change anything .

[REM]

That is cool. Thanks for that. I can now see how easy Assembler code would be to implement into C++. Programming is cool, especially C++ and Asembler

Later

REM

[kb244]

Yea its great when you got some huge routine that you need sped up, and would rather not waste stack space on the extra's C++ can throw in , however I havent done much ASM in C++, but I will tell you this

It's a ***** to debug large ASM codes.

[V(ery) Basic]

Originally posted by kb244
Long -2,147,483,648 to 2,147,483,647

for 10,000,000 sounds like you need to use a double at the least(A Long wont go past 2 mil)

I used Long, but Long goes up to 2 billion (not million) so it wasn't an overflow.

I think it was that I didn't use DoEvents.
But you shouldn't need to use DoEvents should you?

I don't know.

I made it in C++, but then i realised that C++ doesn't have GetTickCount. duh. It's VC++ that's got all the APIs. another big duh. So I couldn't really test it.

[Paul282]

All of VB's numeric data types are signed unfortunately, it'd be nice to have unsingned types too so a long could handle 4bil.

Some fascinating reading for those interested in ASM is how the sign works as far as the 2's compliment rule.

ie if you add two signed or two unsigned values the processor does the same thing and gives the same result.

so if 0000 0001 = 1 and the highest bit is the sign then 1000 0001 is NOT -1

shish, one too many drinks on that spiel, wonder if anyone understood it ....

[parksie]

V(ery) - as a replacement for GetTickCount(), try the clock() function, defined in time.h.

[V(ery) Basic]

Thanks, that another C++ thing I didn't know

How do you find out about all the different headers you can use, and what they do?

My book just uses IOStream and it doesn't even explain it, it just uses it.

Is there a website or a book, or do you just go through your folder and read through all of the .h files?

(Sorry to be off-topic)

[parksie]

I use a combination of my old K&R C book, and MSDN.

V(ery), which book do you have?

I have The Complete Idiots Guide to C++, and it uses like 3 different headers(IOStream, stdio, stdlib, and few more i think).

[parksie]

I would suggest using the standard headers: that is, don't use iostream.h, use iostream. That way, you get all the STL features.

#include <iostream>

using namespace std; // This must be here!

[kb244]

For C++ I recomend "C++ From the Ground Up" it covers alot, even some of the more complex matters, and it does everything in the Standard. (STL)

[V(ery) Basic]

Teach Yourself VC++ in 21 Days is quite good, but it must be really hard if you don't hav experience in other languages because it doesn't describe (for example) what classes are, why you would need them and what they do.

I've had it for a couple of weeks now and in currently on Day 9 - References.

I took about 3 days to realise what pointers were (and what the * meant in the different contexts)

The reason I'm a little stick on references is that I'm not sure if there is any difference in the &AddressOf or the &ByRefernce operators. The guy doesn't go into any great detail.

Next is Linked Lists, and I don't know what the hell they are, but arrays seem more familiar.

[kb244]

Erm, dont know pointers, or linked list? You may want to get a better book for that topic,

to give you a quick overview of linked list

they are structures (or other forms) that link to eachother using pointers.

a sample of a node may be

struct mynode
{
int number;
mynode *next;
};


in this case, you would create a node

mynode newnode = new mynode; (looks kinda confusing doesnt it)

and then you would attatch a new node (I'll do it a simple way)

newnode.next = new mynode;

so now next points to the next in the list, and that next node, can point to another one in turn, (using 2 pointers, like a head pointer, and current pointer, you can move yourself down the list)

this is much more efficient than static arrays for many reason, you can reorganize them easily by changing the nodes they point to, you can add more easily, you only take up as much memory as needed, unlike a static array which takes up memory for 10 ints, even if you dont use all 10 spots. etc.

[CthulhuDragon]

kb244 - I think that should be:
mynode * newnode = new mynode;

It needs to be a pointer, not a regular variable.

Also for V(ery) - the type of list that kb244 is called a singly linked list. Its called that because it only points one way. You can only go forward not back. There is also a double linked list. The node would look like this.
class mynode
{
int number;
mynode *next;
mynode *prev;
};

Now you can point to the nodes on both sides of you in the list. So you can go back and forth. You should start with singly linked and then move to double, because while double is more powerful, it can be a headache to keep track of until you get the hang of it.

[kb244]

I meant to put a * there

[KWell]

Paul282, i calculate all the primes in a array. It take 29.68671 secondes for those from 1 to 1,000,000 and 1.58600 seconde for those from 1 to 100,000.

[Edited by kwell on 09-14-2000 at 02:31 AM]

[Paul282]

DAMN!

I'll try writing another one in powerbasic, it handles inline ASM, asigning vars to registers and my tests show it seems to run at about 10 - 20 times the speed for VB as far as math is concerned. (also compiles to 10- 50k exe!)

as you can probably tell I'm a recent convert, just bought it this week.

so the record for 1,000,000 primes is 29.68671 ...

I'll port my code and get back to you

[KWell]

New record Paul282, 3.93267 seconds to find all primes numbers between 1 to 1,000,000 and 0.22565 second for those between 1 to 100,000.

[KWell]

New record (again) Paul282, 0.29245 second to find all primes numbers between 1 to 1,000,000 and 0.01891 second for those between 1 to 100,000.

[[Digital-X-Treme]]

Could you please post the code you are using to do the prime generation in like 0.2 seconds. I would be interested in seeing how you coded it...

[HarryW]

What's the special way of doing this then? The way I'd do it (probably a slow way) is to check whether each number was divisible by any of the primes already found.

[Paul282]

That's the way I was doing it! Although once you're checking numbers over 1000 you can just check the first 10% of the primes to find them, this speeds things up heaps but not like the times listed above! I'd very much like to see the code too!

[HarryW]

But if you only check against the first 10% of primes you won't find some of the bigger ones. Of course you don't check any even numbers, and I suppose you could not check against any primes less than 1/3 of the number you're testing... that make sense? I would say 1/2 but since you only have odd nos you can cut it down to 1/3.

[HarryW]

Oops, should never start a sentence with 'but', excuse me

[Paul282]

Not true!

I tried all up to 1,000,000 and the results are the same for searching all primes or just 10%. I graphed it to see if any numbers had higher prime factors and thay don't (at least not up to about 2,000,000. There are larger factors but not larger prime factor pairs.

eg, 3x999991 both are prime but you'll find it when you check 3. So yes there are prime factors over 10% but all of their 'partners' are under 10% of the number you're searching for so you'll have found out that the number isn't prime already.

BUT, it's not as fast as the code above so I'd like to see it!

[HarryW]

In my previous post it should say 'more than 1/3' instead of 'less than 1/3'.

Where does the figure of 10% come from then?

I suppose then, by that logic, you need only check the primes less than or equal to the square root of the number you're checking. The only problem with that is that I think root functions are probably pretty slow. Perhaps you could make an estimate... or actually, pre-construct an array containing the roots so that no calculation is necessary once you've found them once. Mind you that's not really speeding it up, just kind of doing part of it first. *Hmms*

How fast is a square root function generally?

[Paul282]

10% comes from trial and error, I graphed it to see how high I needed to check and it's about 10% at 1000 curving sharply from the lower numbers and dropping to about 8% by about 1,000,000

' Module Code

Public primes() As Long
Public NoOfPrimes As Long

Public Type PrimeType
    Number As Long   'primes don't have factors dummy!!
    Highest_Prime_Factor As Long ' eliminating upward from 2
    No_of_Prime_Factors As Long
End Type

' previous graph as percent of the number of primes found up to
' a certain number (ie 100,000 = 9592) 10.x%

' meaning (as only 1/9th of numbers need be searched) that no
' number over 1000 has a prime factor over 10% it's value
' ... over it's sqr root ?

Public Sub FindPrimes2(candidate As Long)

    Dim search As Long
    Dim IsPrime As Boolean
    
    IsPrime = True
    
    For search = 1 To NoOfPrimes \ 9
        If candidate Mod primes(search) = 0 Then
            IsPrime = False
            search = NoOfPrimes + 1
        End If
    Next
    
    If IsPrime = True Then
        NoOfPrimes = NoOfPrimes + 1
        primes(NoOfPrimes) = candidate
    End If
    
End Sub



' Form Code

Public Limit As Long

Private Sub cmdFactor_Click()

    Dim start As Single
    Dim low_total As Integer
    Dim NoLoop As Long
    Dim no_need As Boolean
    Dim Limit As Long
    
    Limit = CLng(Text1.Text)
    If Limit < 2 Or Limit > 100000000 Then
        MsgBox ("Please type number from 2 to 100,000,000")
        Exit Sub
    End If
    
    If Limit < 1001 Then
        low_total = Limit
        no_need = True
    Else
        no_need = False
        low_total = 1000
    End If

    List1.Clear
    ReDim primes(Limit / 2 + 100)
    
    primes(1) = 2
    NoOfPrimes = 1
    
    start = Timer
    
    For NoLoop = 3 To low_total
    
        FindPrimes (NoLoop)
        If NoLoop Mod 1000 = 0 Then
            Label1.Caption = NoLoop & " Checked!"
            DoEvents
        End If
        
    Next
    
    If no_need = False Then
        For NoLoop = 1001 To Limit
            FindPrimes2 (NoLoop)
            If NoLoop Mod 1000 = 0 Then
                Label1.Caption = NoLoop & " Checked!"
                DoEvents
            End If
        Next
    End If
    
    Label2.Caption = Timer - start & " Seconds"
    MsgBox ("Done! " & NoOfPrimes & " Primes Found")

End Sub

Public Sub FindPrimes(candidate As Long)

    Dim search As Long
    Dim IsPrime As Boolean
    
    IsPrime = True
    
    For search = 1 To NoOfPrimes
        If candidate Mod primes(search) = 0 Then
            IsPrime = False
            search = NoOfPrimes + 1
        End If
    Next
    
    If IsPrime = True Then
        NoOfPrimes = NoOfPrimes + 1
        primes(NoOfPrimes) = candidate
    End If

End Sub

Private Sub cmdPercent_Click()
    
    Dim Half As Long
    Dim HalfCount As Long
    Dim List As String
    Dim List2 As String
    
    List = ""
    List2 = ""
    text2.Text = ""
    
    For x = 1 To NoOfPrimes
        
        Half = primes(x) / 2
        
        For y = 1 To NoOfPrimes
            If Half > primes(y) Then
                HalfCount = y
            Else
                y = NoOfPrimes + 1
            End If
        Next
        
        List = List & (x & vbTab & primes(x) & vbTab & (HalfCount / x * 100)) & vbTab & (x / primes(x) * 100) & vbCrLf
        If x Mod 100 = o Then
            List2 = List2 + List
            List = ""
            DoEvents
        End If
    Next
    
    text2.Text = List2
    
End Sub

Private Sub cmdPrint_Click()

    time1 = Timer
    
    List1.Visible = False
    

    List1.AddItem ("Count" & vbTab & "Prime")
    For x = 1 To NoOfPrimes
        List1.AddItem (x & vbTab & primes(x))
    Next
    
    List1.Visible = True
    
    time2 = Timer
    
    Label6.Caption = time2 - time1
    

End Sub

[HarryW]

I got the square root from looking at your statement '3x999991 both are prime but you'll find it when you check 3' from a mathematical point of view. The most that the lowest prime out of the factors will be is when there are only 2 factors and they are the same ie. the highest factor you have to check to see if the number 83 is prime is its square root, rounded down (9). By checking for factors of 2, 3, 5, and 7 we already know it's prime.

I suppose you don't have to check numbers ending in 5 either, although it might be quicker not to check.

Lots of code there, too much for me to read at 6:30 am (need to sleep!). How fast is the Mod operator? Might it be faster to check this?

candidate/primes(search) = candidate\primes(search)

Hmm, probably not...

Anyway, any ideas on the speed of sqr()?

[Paul282]

not sure about VB's mod operator, I'm sure that this code can be optermised but I want to see KWell's code because from the times I think he's using a different algorithm and I'd like to know what it is.