[C] swapping vars
Moderator: MaxCoderz Staff
-
- Calc King
- Posts: 1513
- Joined: Sat 05 Aug, 2006 7:22 am
That's my point remember..
Do you know there is a sorting algorithm that actually sorts in O(n+d) time (always - best and worst case) d being (array.max - array.min)? downside is that it takes d*element_size memory and that it only works if each element is unique. It's better than qsort if you know all elements to be unique and if you have the space (so practically never).
When an array is almost sorted and short in length then Shellsort could actually out-perform qsort, but how would you know an array is almost sorted? Typically you don't, and if you try to find out then you'd lose so much time that it isn't worth it at all - especially not if the outcome is that it isn't "mostly sorted" anyway.
So, the conclusion of that is: just use quicksort.
So why not do some low-lvl optimisation aswell? Once you compile your program, no one is going to run it on a different processor than you compiled it for because they can't, so you might aswell super-optimize it for that processor.
And we all know the story behind RIS processors don't we? They exist only because compilers are too lazy to utilize the full instructionset of CIS processors. Obviously this must be true, otherwise the SPARC would never have existed.
conclusion: compilers aren't that smart after all, in fact, they don't think at all, they pretend to be smart by using build-in tricks, but they're there because the programmer made it so, and that programmer isn't infallible - so that leaves some tricks unused and makes the compiled program less optimized than it could have been.
why conventional swap is ugly: it declares a variable that you do not need.
why it doesn't matter using 3 xor's: the compiler knows you mean a swap.
why you should add comments: someone may come along, read your code, and fail to understand it without comments.
imo, this leaves no reason not to use 3 xors
but it makes me wonder.. why do high level languages not have a swap keyword? or even as operator? a<->b maybe?
Do you know there is a sorting algorithm that actually sorts in O(n+d) time (always - best and worst case) d being (array.max - array.min)? downside is that it takes d*element_size memory and that it only works if each element is unique. It's better than qsort if you know all elements to be unique and if you have the space (so practically never).
When an array is almost sorted and short in length then Shellsort could actually out-perform qsort, but how would you know an array is almost sorted? Typically you don't, and if you try to find out then you'd lose so much time that it isn't worth it at all - especially not if the outcome is that it isn't "mostly sorted" anyway.
So, the conclusion of that is: just use quicksort.
So why not do some low-lvl optimisation aswell? Once you compile your program, no one is going to run it on a different processor than you compiled it for because they can't, so you might aswell super-optimize it for that processor.
And we all know the story behind RIS processors don't we? They exist only because compilers are too lazy to utilize the full instructionset of CIS processors. Obviously this must be true, otherwise the SPARC would never have existed.
conclusion: compilers aren't that smart after all, in fact, they don't think at all, they pretend to be smart by using build-in tricks, but they're there because the programmer made it so, and that programmer isn't infallible - so that leaves some tricks unused and makes the compiled program less optimized than it could have been.
why conventional swap is ugly: it declares a variable that you do not need.
why it doesn't matter using 3 xor's: the compiler knows you mean a swap.
why you should add comments: someone may come along, read your code, and fail to understand it without comments.
imo, this leaves no reason not to use 3 xors
but it makes me wonder.. why do high level languages not have a swap keyword? or even as operator? a<->b maybe?
- benryves
- Maxcoderz Staff
- Posts: 3089
- Joined: Thu 16 Dec, 2004 10:06 pm
- Location: Croydon, England
- Contact:
Not entirely true. Different CPUs of the same basic type (eg, "x86-compatibles") can have different extensions (MMX, 3DNow!, SSE et al) that are incompatible.King Harold wrote:Once you compile your program, no one is going to run it on a different processor than you compiled it for because they can't, so you might aswell super-optimize it for that processor.
The way to resolve these differences are intelligent JIT compilers that take advantage of a particular configuration's hardware.
I, for one, hope that the days of native applications are numbered.
-
- Calc King
- Posts: 1513
- Joined: Sat 05 Aug, 2006 7:22 am
So do I, but those JIT compilers will have to be quite intelligent, and not give cryptic errors as they currently do.I, for one, hope that the days of native applications are numbered.
If they do not support some extension that you are using then they won't run the program - they could try, but fail (at least at some point). Too bad for them.Not entirely true. Different CPUs of the same basic type (eg, "x86-compatibles") can have different extensions (MMX, 3DNow!, SSE et al) that are incompatible.
JIT compiler could solve that, but they'll have to be pretty damn good to be worth the overhead, otherwise they'd only be good for the programmer and not for the user - it has to be good for both ofcourse.
Personally I wouldn't mind running a program that is super-optimized for my own processor, in fact I'm always quite happy when I see that someone took the effort to make such a version.
-
- MCF Legend
- Posts: 1601
- Joined: Mon 20 Dec, 2004 8:45 am
- Location: Budapest, Absurdistan
- Contact:
Oh my dear, please do just a little bit of research before passing the verdict... Modern compilers are packed with advanced algorithms.King Harold wrote:conclusion: compilers aren't that smart after all, in fact, they don't think at all, they pretend to be smart by using build-in tricks, but they're there because the programmer made it so, and that programmer isn't infallible - so that leaves some tricks unused and makes the compiled program less optimized than it could have been.
Why the xor swap is ugly: it adds three unnecessary operations.King Harold wrote:why conventional swap is ugly: it declares a variable that you do not need.
It doesn’t matter for this particular implementation of this particular operation. But if you extend this attitude to implementing more complicated algorithms, you’ll end up worse off.King Harold wrote:why it doesn't matter using 3 xor's: the compiler knows you mean a swap.
If a simple operation like swapping two variables requires comments to be understood, you are on the wrong way...King Harold wrote:why you should add comments: someone may come along, read your code, and fail to understand it without comments.
Quite a few (especially interpreted ones) do, even ancient ones like CLU; it’s normally written as ‘a, b = b, a’ or something along those lines.King Harold wrote:but it makes me wonder.. why do high level languages not have a swap keyword? or even as operator? a<->b maybe?
Open source.benryves wrote:The way to resolve these differences are intelligent JIT compilers that take advantage of a particular configuration's hardware.
You’re thinking in terms a very narrow application area then.benryves wrote:I, for one, hope that the days of native applications are numbered.