Disable SMT for my process?

Index > Windows > Disable SMT for my process?

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

Author

Thread

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 15:43

c+N doesn't change the algorithm though. The c is just a constant overhead always there, outside of the loop. In my example the algorithm itself is changed.. to the point where most of the time, changing N doesn't change complexity.

P.S.:
Anyways, if big-O doesn't work where there is a maximum number of elements, big-O doesn't work for computers, since they have finite resources.

04 Sep 2009, 15:43

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, 15:47

Azu wrote:

P.S.:
Anyways, if big-O doesn't work where there is a maximum number of elements, big-O doesn't work for computers, since they have finite resources.

In a sense you are correct, big-O is just an approximation. But it is a very useful tool so don't be too hasty to discount it.

04 Sep 2009, 15:47

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 15:50

It should be versatile enough to take limitations into account, I think.

For example, you have two algorithms, and neither of them can process over a million elements.. wouldn't it make sense not to calculate past 1 million then? One of them might theoretically scale way better if it goes to infinity, but since that can't happen, your results could be incorrect..

04 Sep 2009, 15:50

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, 15:52

Azu wrote:

It should be versatile enough to take limitations into account, I think.

For example, you have two algorithms, and neither of them can process over a million elements.. wouldn't it make sense not to calculate past 1 million then? One of them might theoretically scale way better if it goes to infinity, but since that can't happen, your results could be incorrect..

This is already a known caveat with big-O.

04 Sep 2009, 15:52

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 15:55

revolution wrote:

Azu wrote:
It should be versatile enough to take limitations into account, I think.

For example, you have two algorithms, and neither of them can process over a million elements.. wouldn't it make sense not to calculate past 1 million then? One of them might theoretically scale way better if it goes to infinity, but since that can't happen, your results could be incorrect..
This is already a known caveat with big-O.

Is there a version of it that isn't like this? Like big-P or something?

04 Sep 2009, 15:55

Borsuc

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

Borsuc 04 Sep 2009, 15:57

Azu wrote:

P.S.:
Anyways, if big-O doesn't work where there is a maximum number of elements, big-O doesn't work for computers, since they have finite resources.

Big-O tells you the mathematical relationship as N increases -- is it linear? is it exponential? That's the question it answers.

It does not tell you when X is faster that Y, depending on N. It tells you the relationship of the functions as they increase.

Bubble Sort increases quadratically, known fact. That is what Big-O tells you, not that it would run slower than quicksort for TWO elements (which is false, it's obviously faster).

Also I said before the "upper limits" are conditions imposed in the function, and conditions do not work in mathematics with a single notation.

What if you have a function that checks if N is prime (let's say MAGICALLY does so in 1 clock cycle), and if it is, then it does operation X which is O(N^2), otherwise operation Y which is O(N).

How would you rate such function's complexity? It is impossible to do it with one Big-O notation. You can apply conditions like "if N isn't prime, O(N), otherwise O(N^2)" but that uses two notations as you can see...

_________________
Previously known as The_Grey_Beast

04 Sep 2009, 15:57

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 16:00

I used two notations though

I said if N<17 O(1) else O(ceiling(n/16))

P.S. your function does not need magic, it needs huuuuuuuuuuuge LUT.

04 Sep 2009, 16:00

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, 16:02

Azu wrote:

... big-P ...

Yeah, umm, sorry what was that you were saying, I just had to go take a big-P, but I am back now. Razz

04 Sep 2009, 16:02

Borsuc

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

Borsuc 04 Sep 2009, 16:02

Correct but in that case, it's like you have two functions. The actual function must have the condition, not just your classification (e.g if you called a different function if N>=17, then it would qualify) Smile

_________________
Previously known as The_Grey_Beast

04 Sep 2009, 16:02

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, 16:03

Azu wrote:

P.S. your function does not need magic, it needs huuuuuuuuuuuge LUT.

And a sloooooooooooow clock so make it only take one cycle.

04 Sep 2009, 16:03

Borsuc

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

Borsuc 04 Sep 2009, 16:04

Unless the huuuuuuuge LUT is in the cache Smile

04 Sep 2009, 16:04

Azu

Joined: 16 Dec 2008
Posts: 1159

Azu 04 Sep 2009, 16:06

Borsuc wrote:

Correct but in that case, it's like you have two functions. The actual function must have the condition, not just your classification (e.g if you called a different function if N>=17, then it would qualify)

Like this? Confused

Code:

cmp ecx,16
ja loopz
movdqa xmm0,dqword[esi]  
movdqa xmm1,dqword[edi]  
paddb xmm0,xmm1  
movdqa dqword[edi],xmm0
ret
loopz:
movdqa xmm0,dqword[esi]  
movdqa xmm1,dqword[edi]  
sub ecx,16
paddb xmm0,xmm1  
movdqa dqword[edi],xmm0
jns loopz
ret

revolution wrote:

Azu wrote:
P.S. your function does not need magic, it needs huuuuuuuuuuuge LUT.
And a sloooooooooooow clock so make it only take one cycle.

i7s have slow clocks Very Happy

_________________

04 Sep 2009, 16:06

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

< 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