-1

I was testing some sorting algorithms and measuring their execution time and found something quite strange and came up with the question, is >= faster than > ?

user1493813
  • 981
  • 1
  • 8
  • 16
  • 8
    mind that you changed the sorting algorithm itself. if you want to check these two against each other the correct while-statement would be: `while (j>-1 && aux.key < pA->Positions[j].key) – Vogel612 Feb 18 '13 at 16:15
  • You're comparing different algorithms. – Luchian Grigore Feb 18 '13 at 16:17
  • 1
    This is actually an interesting question, but you've given it a title that makes it look like an uninteresting question. In compiled code, in the absence of overloaded operators, `>=` and `>` should take the same time to within measurment noise (it is literally a change from a `BGT` to a `BGE` machine instruction). However, your change makes the sorting algorithm behave differently, and *that* could easily make a large difference in how long it runs – zwol Feb 18 '13 at 16:17
  • @Zack so how is it interesting? It would be if the measurements were correct and the timings were different. – Luchian Grigore Feb 18 '13 at 16:18
  • @LuchianGrigore It's interesting because it demonstrates that a sorting algorithm can still be correct but have radically different performance characteristics based on subtle design choices. An interesting answer would talk about how this affects how items get moved around and thus changes the number of comparisons and swaps. – zwol Feb 18 '13 at 16:20
  • 1
    @Zack but the algorithm isn't correct. – Luchian Grigore Feb 18 '13 at 16:20
  • There's another answer (perhaps more useful) to your question here: http://stackoverflow.com/questions/11763399/which-operator-is-faster-or-or/11763604#11763604 – Richard J. Ross III Feb 18 '13 at 16:21
  • @LuchianGrigore Isn't it? It looks right to me either way, but it's been a long time since I had to know exactly how insertion sort works. If one is correct and the other is wrong, talking about why you need to use a particular form of comparison in this algorithm would also make an interesting answer. – zwol Feb 18 '13 at 16:22
  • @Zack IDK if either one is correct, but they're not doing the same thing. So, if the algorithms are different, talking about `<` vs `<=` is useless. – Luchian Grigore Feb 18 '13 at 16:23
  • @LuchianGrigore That's my point! It *looks like* a question about `<` vs `<=` (and has now erroneously been closed as a duplicate because of that, feh) but it is *actually* an interesting question about subtle details of insertion sort. – zwol Feb 18 '13 at 16:24
  • The algorithm for insertion sort is correct Luchian Grigore, and thanks for the fast answers. – user1493813 Feb 18 '13 at 16:33
  • @user1493813 why did it have to be this algorithm? Why can't you test the performance of `>=` and `>` is a different way? Like, say, just measuring them? – Luchian Grigore Feb 18 '13 at 16:35
  • You're right, i expressed myself wrong, I used this algorithm for the question because the question arose from it. – user1493813 Feb 18 '13 at 16:38

2 Answers2

2

CPU architecture specific. How can you measure it on modern processors anyway?

However if key is not really an int (that is you anonymized it to one) and there is no specific overloaded operator for <= than the code performance of <= will be much worse than <.

In your specific algorithm, changing between <= and < is going to wreck you algorithm so that's what happened here.

Joshua
  • 40,822
  • 8
  • 72
  • 132
1

No, there is no performance difference between > and >= on any modern hardware, any timing deltas are artificial and purely coincidental. Are you sure the code snippets actually do the same thing? Are your compiler settings set to maximize optimization (it's useless to time code in debug mode)?

By the way, you probably shouldn't start your type names with "T" in C++. This isn't Pascal ^^

Thomas
  • 3,321
  • 1
  • 21
  • 44