Disable SMT for my process?

Index > Windows > Disable SMT for my process?

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

Author

Thread

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:08

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

04 Sep 2009, 09:08

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:09

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

04 Sep 2009, 09:09

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:12

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

04 Sep 2009, 09:12

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:13

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

04 Sep 2009, 09:13

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:14

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

04 Sep 2009, 09:14

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:15

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

04 Sep 2009, 09:15

revolution
When all else fails, read the source

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

revolution 04 Sep 2009, 09:17

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

04 Sep 2009, 09:17

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:18

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?

04 Sep 2009, 09:18

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:19

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

04 Sep 2009, 09:19

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:23

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

04 Sep 2009, 09:23

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:25

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.

04 Sep 2009, 09:25

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:30

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.

04 Sep 2009, 09:30

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:32

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

04 Sep 2009, 09:32

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:33

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

04 Sep 2009, 09:33

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:34

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?

04 Sep 2009, 09:34

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:36

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

04 Sep 2009, 09:36

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:36

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.

04 Sep 2009, 09:36

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 09:37

n = 123

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

It equals 0.0650406504

04 Sep 2009, 09:37

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:40

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.

04 Sep 2009, 09:40

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8359
Location: Kraków, Poland

Tomasz Grysztar 04 Sep 2009, 09:41

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

04 Sep 2009, 09:41

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