flat assembler
Message board for the users of flat assembler.

Index > Windows > Disable SMT for my process?

Goto page Previous  1, 2, 3, 4, 5, 6, 7  Next
Author
Thread Post new topic Reply to topic
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
So shouldn't the SIMD way be O(1) until n>16 ( at which point it would be O(ceiling(n/16)) )?

To recapitulate: there's no such thing as "O(1) until n>16". You can say that algorithm is O(something) only when your n is arbitrarily large (approaches infinity, as mathematicians may say).

This makes O() notation not always useful to aid in choosing the fastest algorithm. Sometimes (well, in fact: very often) the algorithm of worse complexity can execute faster for very small inputs. It's only for very large inputs when the O() complexity starts to really matter.
For example, FFT multiplication (which Ender presented at fasmcon 2009) is faster than the ordinary multiplication only for a really very big numbers (like millions of digits).


Last edited by Tomasz Grysztar on 04 Sep 2009, 09:10; edited 1 time in total
Post 04 Sep 2009, 09:08
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
Tomasz Grysztar wrote:
revolution wrote:
Azu wrote:
But my example of SIMD vs non-SIMD uses different operations. And different algorithms (one loops n times, one runs once).. but you said they have the same big-O notation since in the end they both do the same thing.. Confused
They do the same thing, they both add bytes. But conceivably there could be another algorithm that achieves the same end results but instead of adding bytes it does a table lookup of all possible x+y combinations. Lookups are O(1) but clearly a 128bitx128bit table would not be practical and might even be slower if you had to store it on HDD.

You cannot talk about O() notation when clearly your data size is limited. O() notation is the asimptotic one, and therefore requires algorithms working on data of arbitrary size. And even if you use lookup tables of 128x128 bit size, you'd have to do this for every 128-bit part of the input and thus get O(N) in the end, anyway.

The same mistake Azu made, when he said "only needs ran once (as long as n<17)". Well, the point is, when you take assumption like "n<17", you can not say anything about O() complexity. The O() notation applies only to the case, when your algorithm is able to handle input of ANY size. And clearly, to process the hundred megabytes of data, you'd still have to run your SIMD instruction in a loop.
Okay, so like I said a few pages back, my SIMD way is O(ceiling(n/16))) forever. Definitely not O(n) like the non-SIMD one.
Post 04 Sep 2009, 09:09
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
Okay, so like I said a few pages back, my SIMD way is O(ceiling(n/16))) forever. Definitely not O(n) like the non-SIMD one.

O(celiling(n/16)) is exactly the same thing as O(n). They both are linear. I suggest you should read more about limits and asimptotic behaviors.

For example O(N) is the same as O(1000N), and O(N^2+1000N) is the same as O(N^2).
Post 04 Sep 2009, 09:12
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
But it goes in steps of 16.. if it was O(n), then it would do 16 times less if given 1 input than it would if given 16.. but it does the same either way..
Post 04 Sep 2009, 09:13
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Really, O(16N)=O(N). Please confirm with some mathematical book if you don't believe me.

I know that limits might confusing, especially when you first meet them - but if you want to understand what theoreticians mean, you need to understand their notations first.


Last edited by Tomasz Grysztar on 04 Sep 2009, 09:16; edited 1 time in total
Post 04 Sep 2009, 09:14
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
I don't mean 16*N.. if it was 16*N, it would do 16 times less work if given 1 input than it would if given 16 inputs. I mean ceiling(N/16). It has no difference between 1 input and 16. There is difference between 16 inputs and 17 though. Same difference as between 1 input and 17.. so not linear, I think..
Post 04 Sep 2009, 09:15
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17476
Location: In your JS exploiting you and your system
revolution
Azu wrote:
But it goes in steps of 16..
Purely a linear speed up, nothing else. It won't affect the big-O.


Last edited by revolution on 04 Sep 2009, 09:17; edited 1 time in total
Post 04 Sep 2009, 09:17
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
I don't mean 16*N.. if it was 16*N, it would do 16 times less work if given 1 input than it would if given 16 inputs. I mean ceiling(N/16).

That's the same thing. Since O(16N)=O(N), then O(N)=O(N/16).

Tell me, but seriously, what is your level of mathematical education?
Post 04 Sep 2009, 09:18
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
I didn't say n/16.. I said ceiling(n/16)..

If it is n/16, then again, giving it 1 input would make it do 16 times less work than giving it 16 inputs. My algorithm will work just as much for 1 through 16 inputs (and twice as much for 17 through 32 inputs, etc). So shouldn't it have a notation that reflects this?


Look;


N/16 does not equal N/15 or N/1


But ceiling(N/16) and ceiling(N/15) and ceiling(N/1) all equal the same.. see?



Edit: wait.. I think I used the wrong math to describe this.. let me fix it before you reply please


Last edited by Azu on 04 Sep 2009, 09:24; edited 1 time in total
Post 04 Sep 2009, 09:19
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
I didn't say n/16.. I said ceiling(n/16)..

This behaves asimptotically the same as linear. lim celing(n)/n = 1
Azu wrote:
So shouldn't it have a notation that reflects this?
Maybe so, but the asimptotic notation is not the right one for this. It deals with analyzing how your algorithm behaves, when the input goes larger and larger (into a very very big ones). You on the contrary analyze how your algorithm behaves locally, for some small input sizes. Those are completely different things, and different methods and notations should be used for them.


Last edited by Tomasz Grysztar on 04 Sep 2009, 09:27; edited 1 time in total
Post 04 Sep 2009, 09:23
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
Okay here is the right example. Sorry about my previous post;

n=16
N/16
does not equal
n=15
N/16
or
n=1
N/16

But..
n=16
ceiling(N/16)
and
n=15
ceiling(N/16)
and
n=1
ceiling(N/16) all equal the same.. see?


This difference isn't linear.. so why doesn't at least O(ceiling(n/16)) work? It should work no matter how big the input is, I think.. where as the O(1) only works if it is below 17, and I get now that that is invalid use of the notation, since it must be self contained.
Post 04 Sep 2009, 09:25
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
Okay here is the right example. Sorry about my previous post;

n=16
N/16
does not equal
n=15
N/16
or
n=1
N/16

But..
n=16
ceiling(N/16)
and
n=15
ceiling(N/16)
and
n=1
ceiling(N/16) all equal the same.. see?


This difference isn't linear..

Of course it IS linear. Just look at it for large input sizes.
Post 04 Sep 2009, 09:30
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
To show you on example:

N=100000
N-celing(N/16)=93750

N=1000000
N-celing(N/16)=937500

N=10000000
N-celing(N/16)=9375000

and so on, till the infinity. The growth of this difference is linear.


Last edited by Tomasz Grysztar on 04 Sep 2009, 09:33; edited 1 time in total
Post 04 Sep 2009, 09:32
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
Image

I think the one on the left is linear ( O(n) ), but not the one on the right ( O(ceil(n/16)) )..


If it is linear, then whenever there is a different n, there should be different complexity, right?


Last edited by Azu on 04 Sep 2009, 09:35; edited 1 time in total
Post 04 Sep 2009, 09:33
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
I think the one on the left is linear ( O(n) ), but not the one on the right ( O(ceil(n/16)) )..

Asimptotically they both are. As I said, lim ceiling(N)/N = 1
Do you know what a mathematical notation of limit is?
Post 04 Sep 2009, 09:34
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
ceiling(N) will always equal N if N is an integer.. there is supposed to be division done on it first to make it a float..


Like this

lim ceiling(N/16)/N


Last edited by Azu on 04 Sep 2009, 09:37; edited 1 time in total
Post 04 Sep 2009, 09:36
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
If it is linear, then whenever there is a different n, there should be different complexity, right?

The O(N) notation mean asimptotically linear, not the plain linear you know from elementary school.
Post 04 Sep 2009, 09:36
View user's profile Send private message Visit poster's website Reply with quote
Azu



Joined: 16 Dec 2008
Posts: 1159
Azu
n = 123

lim ceiling(N/16)/N does not equal 1


It equals 0.0650406504
Post 04 Sep 2009, 09:37
View user's profile Send private message Send e-mail AIM Address Yahoo Messenger MSN Messenger ICQ Number Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
ceiling(N) will always equal N if N is an integer.. there is supposed to be division done on it first to make it a float..


Like this

lim ceiling(N/16)/N

lim ceiling(N)/N = 1 even if we take real N, not integer one.
As for the lim ceiling(N/16)/N, it is equal to 1/16, which tells us that asimptotically ceiling(N/16) is linear in relation to N.
Post 04 Sep 2009, 09:40
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 7756
Location: Kraków, Poland
Tomasz Grysztar
Azu wrote:
lim ceiling(N/16)/N does not equal 1

True, it does not - it equal to 1/16.

Azu wrote:
It equals 0.0650406504

You haven't answered my earlier question. Do you know what a limit is?


Last edited by Tomasz Grysztar on 04 Sep 2009, 09:41; edited 1 time in total
Post 04 Sep 2009, 09:41
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2, 3, 4, 5, 6, 7  Next

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