I++ Less Efficient Than ++I, How to Show This

i++ less efficient than ++i, how to show this?

In the general case, the post increment will result in a copy where a pre-increment will not. Of course this will be optimized away in a large number of cases and in the cases where it isn't the copy operation will be negligible (ie., for built in types).

Here's a small example that show the potential inefficiency of post-increment.

#include <stdio.h>

class foo 
{

public:
    int x;

    foo() : x(0) { 
        printf( "construct foo()\n"); 
    };

    foo( foo const& other) { 
        printf( "copy foo()\n"); 
        x = other.x; 
    };

    foo& operator=( foo const& rhs) { 
        printf( "assign foo()\n"); 
        x = rhs.x;
        return *this; 
    };

    foo& operator++() { 
        printf( "preincrement foo\n"); 
        ++x; 
        return *this; 
    };

    foo operator++( int) { 
        printf( "postincrement foo\n"); 
        foo temp( *this);
        ++x;
        return temp; 
    };

};

int main()
{
    foo bar;

    printf( "\n" "preinc example: \n");
    ++bar;

    printf( "\n" "postinc example: \n");
    bar++;
}

The results from an optimized build (which actually removes a second copy operation in the post-increment case due to RVO):

construct foo()

preinc example: 
preincrement foo

postinc example: 
postincrement foo
copy foo()

In general, if you don't need the semantics of the post-increment, why take the chance that an unnecessary copy will occur?

Of course, it's good to keep in mind that a custom operator++() - either the pre or post variant - is free to return whatever it wants (or even do whatever it wants), and I'd imagine that there are quite a few that don't follow the usual rules. Occasionally I've come across implementations that return "void", which makes the usual semantic difference go away.

Is (*i).member less efficient than i-member

When you return a reference, that's exactly the same as passing back a pointer, pointer semantics excluded.

You pass back a sizeof(void*) element, not a sizeof(yourClass).

So when you do that:

Person& Person::someFunction(){
    ...
    return *this;
}

You return a reference, and that reference has the same intrinsic size than a pointer, so there's no runtime difference.

Same goes for your use of (*i).name, but in that case you create an l-value, which has then the same semantics as a reference (see also here)

Why is ++i more efficient than i++?

i++ increments i and returns the initial value of i. Which means:

int i = 1;
i++; // == 1 but i == 2

But ++i returns the actual incremented value:

int i = 1;
++i; // == 2 and i == 2 too, so no need for a temporary variable

In the first case, the compiler has to create a temporary variable (when used) for returning 1 instead of 2 (in the case where it's not a constant of course but a dynamic value, a return from a call for example).

In the second case, it does not have to. So the second case is guaranteed to be at least as effective.

Often, the compiler will be able to optimize the first case into the second case, but sometimes it may not be able to.

Anyway, we're talking about highly negligible impact.

But on more complicated objects such as iterators-like objects, having a temporary state may be pretty slower if iterated millions of times.

Rule of thumb

Use prefix version unless you specifically want the postfix semantics.

Is there a performance difference between i++ and ++i in C++?

[Executive Summary: Use ++i if you don't have a specific reason to use i++.]

For C++, the answer is a bit more complicated.

If i is a simple type (not an instance of a C++ class), then the answer given for C ("No there is no performance difference") holds, since the compiler is generating the code.

However, if i is an instance of a C++ class, then i++ and ++i are making calls to one of the operator++ functions. Here's a standard pair of these functions:

Foo& Foo::operator++()   // called for ++i
{
    this->data += 1;
    return *this;
}

Foo Foo::operator++(int ignored_dummy_value)   // called for i++
{
    Foo tmp(*this);   // variable "tmp" cannot be optimized away by the compiler
    ++(*this);
    return tmp;
}

Since the compiler isn't generating code, but just calling an operator++ function, there is no way to optimize away the tmp variable and its associated copy constructor. If the copy constructor is expensive, then this can have a significant performance impact.

Is ternary operator less efficient than an if statement that sets a different value to a variable

In your case, your ternary operation and your if statement are not the same, since you don't have an else statement after if, so it only checks whether a>b.

If you are interested in the question about the performance difference in case of semantically equal Ternary operation and if-else block, then the answer is No, there is no much of the difference. Ternary Operator is just a syntactic sugar of writing if-else.

Here is the bytecode comparison in the simplest Java program, with only one (an entry-point) main method, where in first case I implement Ternary Operator, and in the second one - if-else statement.

 //First example, having Ternary Operator
  public static void main(java.lang.String[]);
    Code:
       0: iconst_0
       1: istore_1
       2: iconst_1
       3: istore_2
       4: iload_1
       5: iload_2
       6: if_icmple     13
       9: iload_2
      10: goto          14
      13: iload_1
      14: istore_1
      15: return
}

---

//Second Example, having if-else alternative
  public static void main(java.lang.String[]);
    Code:
       0: iconst_0
       1: istore_1
       2: iconst_1
       3: istore_2
       4: iload_1
       5: iload_2
       6: if_icmple     14
       9: iload_2
      10: istore_1
      11: goto          16
      14: iload_1
      15: istore_1
      16: return
}

Did I just prove that sieve of Eratosthenes is less efficient than trial division?

TL;DR: comparing the speed of code variants at just one input size is meaningless; comparing empirical orders of growth truly reflects algorithmic nature of the code and will be consistent across different test platforms, for the same test range of input sizes. Comparing absolute speed values is only meaningful for code variants which exhibit same asymptotic or at least local growth behaviour.

---

It is not enough to measure speed of your two implementations just at one input size. Usually several data points are needed, to assess the run time empirical orders of growth of our code (because the code can be run with varying input sizes). It is found as the logarithm of the ratio of run times, in base of the ratio of input sizes.

So even if at some input code_1 runs 10 times faster than code_2, but its run time doubles with each doubling of the input size, whereas for code_2 it only grows as 1.1x, very soon code_2 will become much much faster than code_1.

So the real measure of an algorithm's efficiency is its run time complexity (and the complexity of its space i.e. memory requirements). And when we measure it empirically, we only measure if for the particular code at hand (at a particular range of input sizes), not for the algorithm itself, i.e. the ideal implementation of it.

In particular, the theoretical complexity of trial division is O(n^1.5 / (log n)^0.5), in n primes produced, usually seen as ~ n^1.40..1.45 empirical order of growth (but it can be ~n^1.3 initially, for smaller input sizes). For the sieve of Eratosthenes it is O(n log n log (log n)), seen usually as ~ n^1.1..1.2. But there certainly are sub-optimal implementations of both the trial division and the sieve of Eratosthenes that run at ~n^2.0 and worse.

So no, this proves nothing. One datapoint is meaningless, at least three are needed to get a "big picture" i.e. to be able to predict with some certainty the run time ⁄ space needed for bigger input sizes.

Prediction with known certainty is what the scientific method is all about.

---

BTW your run times are very long. The calculation of 10,000 primes should be nearly instantaneous, much less than 1/100th of a second for a C program run on a fast box. Perhaps you're measuring printing time as well. Don't. :)

\d less efficient than [0-9]

\d checks all Unicode digits, while [0-9] is limited to these 10 characters. For example, Persian digits, ۱۲۳۴۵۶۷۸۹, are an example of Unicode digits which are matched with \d, but not [0-9].

You can generate a list of all such characters using the following code:

var sb = new StringBuilder();
for(UInt16 i = 0; i < UInt16.MaxValue; i++)
{
    string str = Convert.ToChar(i).ToString();
    if (Regex.IsMatch(str, @"\d"))
        sb.Append(str);
}
Console.WriteLine(sb.ToString());

Which generates:

0123456789٠١٢٣٤٥٦٧٨٩۰۱۲۳۴۵۶۷۸۹߀߁߂߃߄߅߆߇߈߉०१२३४५६७८९০১২৩৪৫৬৭৮৯੦੧੨੩੪੫੬੭੮੯૦૧૨૩૪૫૬૭૮૯୦୧୨୩୪୫୬୭୮୯௦௧௨௩௪௫௬௭௮௯౦౧౨౩౪౫౬౭౮౯೦೧೨೩೪೫೬೭೮೯൦൧൨൩൪൫൬൭൮൯๐๑๒๓๔๕๖๗๘๙໐໑໒໓໔໕໖໗໘໙༠༡༢༣༤༥༦༧༨༩၀၁၂၃၄၅၆၇၈၉႐႑႒႓႔႕႖႗႘႙០១២៣៤៥៦៧៨៩᠐᠑᠒᠓᠔᠕᠖᠗᠘᠙᥆᥇᥈᥉᥊᥋᥌᥍᥎᥏᧐᧑᧒᧓᧔᧕᧖᧗᧘᧙᭐᭑᭒᭓᭔᭕᭖᭗᭘᭙᮰᮱᮲᮳᮴᮵᮶᮷᮸᮹᱀᱁᱂᱃᱄᱅᱆᱇᱈᱉᱐᱑᱒᱓᱔᱕᱖᱗᱘᱙꘠꘡꘢꘣꘤꘥꘦꘧꘨꘩꣐꣑꣒꣓꣔꣕꣖꣗꣘꣙꤀꤁꤂꤃꤄꤅꤆꤇꤈꤉꩐꩑꩒꩓꩔꩕꩖꩗꩘꩙０１２３４５６７８９

Will an index become less efficient as cardinality decreases for values rarely used?

B-Tree indexes are balanced, and their overall structure ( depth ) depends only on the cardinality of the table, the length of the keys and fill percentage of the pages. Therefore, you won't see structural issues as a column's data distribution changes (assuming you're doing proper index maintenance.)

However, this skewed data distribution will cause issues with statistics.

Consider this query: "select ... from Customer where LastName = @p" There is no best plan for all possible values of @p. Some values will return a few rows, some values will return millions.

A filtered index CREATE IX ON CUSTOMER (LastName) WHERE LastName <> '***' partially addresses this issue. The index will only contain interesting rows, hence will be smaller. Some query changes may be required to ensure this new index is actually used... for example select ... from Customer where LastName = @p and LastName <> '***' or select ... from Customer where LastName = @p (option recompile).

SQL Server 2022 (currently unreleased) will introduce "Parameter Sensitive Plan Optimization" which attempts to address this issue as well.

---

Related Topics