0

My IDE (CLion) suggested replacing a for-loop with a foreach, where the elements of the loop are addresses to values of type char (Option 2). I'm curious about the following:

  • What is the best way to articulate what's happening in Option 2? Do we iterate through the memory location of each character in plaintext?

  • How do Options 2 and 3 differ?

  • Does Option 3 allocate memory for a new char upon each iteration?

Option 1

void Cipher(std::string &plaintext, int key) {

  for (int i = 0; i < plaintext.length(); i++) {...}

}

Option 2

void Cipher(std::string &plaintext, int key) {

    for (char &letter : plaintext) {...}

}

Option 3

void Cipher(std::string &plaintext, int key) {

    for (char letter : plaintext) {...}

}
Tantillo
  • 367
  • 1
  • 5
  • 5
    There are no pointers in any of those three versions. – Shawn Aug 14 '19 at 01:35
  • 3
    *reference* is the term you need to read up on. – Shawn Aug 14 '19 at 01:38
  • Option 1, no. It's 2019. Option 2 only if the value of `letter` is to be changed in the loop. Option 3 is again maybe. One fun alternative is `for (const auto &letter : plaintext) {...}`. Makes transition to wide characters a bit easier in the future. – user4581301 Aug 14 '19 at 01:50
  • 1
    *I'm guessing Option 3 differs from the previous two in that it allocates memory for a new char upon each iteration. Is this correct?* only sort-of correct. that character is in Automatic storage so it's pretty much free. If the compiler sees fit, it may just sit in a register. – user4581301 Aug 14 '19 at 01:53
  • Option 1 is one of my pet hates. `.length()` is called each time through the loop. Sure it _might_ be optimised out, but never has been in my experience... – John3136 Aug 14 '19 at 01:53
  • In case you haven't already, [get a good book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). It will help you sort out the differences between Automatic and Dynamic allocations and references and pointers. C++ is far too complex a language to try to go it alone. – user4581301 Aug 14 '19 at 01:56
  • 2
    Option 1 should be used in cases where you specifically need to reference the index (passing it to say to another data structure). It's not completely outdated as others have mentioned. – jman Aug 14 '19 at 01:59
  • If you have a C++11 compiler (or better), you will also want to consider the [Range-based for loop](https://en.cppreference.com/w/cpp/language/range-for) – David C. Rankin Aug 14 '19 at 03:18
  • @jman Option1 should never be used. It's terrible coding practices like that which are killing the polar bears. See my post below. – robthebloke Aug 14 '19 at 04:37
  • @DavidC.Rankin Option2 and Option3 are range based for loops. – robthebloke Aug 14 '19 at 04:40
  • Right you are, I just added the link `:)` – David C. Rankin Aug 14 '19 at 04:43

2 Answers2

1

Option1 should be avoided at all costs!!! The problem here is that the input to the method (plaintext) is a reference, and so the string exists outside of the scope of the method. This means the compiler cannot determine the scope of that variable, and therefore is unable to determine whether it is safe to perform optimisations (not always the case, but it is here).

https://godbolt.org/z/EBtVp7

Implementing a dumb method here (just adds 12 to each char). You'll notice the ASM for the first version looks 'nice'. Its very simple, and very small, awesome. However if you toggle the 1 to 0 and compare against the second method, you'll notice the second method has an explosion in terms of the amount of asm generated, however it isn't all that bad when you look closer.

Taking a look at the first code snippet, We can see this within the first line of the inner loop:

mov rcx, qword ptr [rdi]

This kinda sucks. It's actually reading the string 'begin' pointer on each iteration (the assumption being another thread *may* resize the string, and therefore change the string length).

If however you look at the second method, it has generated some unrolled loops using the vpaddb instruction (using YMM registers). This means it's processing 32chars at a time (unlike the first method which is only able to process 1 char at a time).

If you wanted to start making option1 approach the performance of option2, you'd need to do something grim like:

void Cipher(std::string &plaintext, int key) {

  if(!plaintext.empty())
  {
    char* ptr = &plaintext[0];
    for (int i = 0, length = plaintext.length(); i < length; i++) {

       ptr[i] += 12;
    }
  }
}

This horrible change now means the compiler can see that the ptr and length variables do not change within the function scope, and so it is now able to vectorise the code. (Options 2 and 3 are still more efficient though!)

Option3 will not allocate a char on each iteration (it'll either load a char into a general purpose register, or a set of chars into a YMM register). The difference in performance in this case is moot. Use option2 if you want to modify the string, use option3 if the string is read only.

An older alternative that achieves the same thing is std::for_each, however that's no longer preferable to range based for loops.

robthebloke
  • 9,331
  • 9
  • 12
1

Point 1

What is the best way to articulate what's happening in Option 2? Do we iterate through the memory location of each character in plaintext?

It is iterating through the characters in plaintext. This means it will iterate through all of the memory locations, but so will every other loop. letter is a reference to, another name for, a character in plaintext. Don't think about references as memory locations or pointers (though a reference may be implemented with pointers behind the scenes). Think about it as letter and plaintext[0] being the same thing, assuming plaintext[0] exists. There is no letter, just an identifier that refers to plaintext[0]. When the loop finishes the first iteration and enters the second iteration (if it does) there will be a new letter (references cannot be made to refer to a different object) and it will be plaintext[1].

Point 2

How do Options 2 and 3 differ?

As covered in point 1, in option 2, letter is one of the characters in plaintext. In option 3, letter is a new variable that is a copy of one of the characters in plaintext.

Point 3

Does Option 3 allocate memory for a new char upon each iteration?

Yes, there is a new letter allocated for each iteration of the loop. However that character is an Automatic variable and not take up any space in memory at all. It may sit in a CPU register. It may sit in a stack, storage has already been allocated, and book-keeping is simply updated show that the memory is now in use. It could be floating in pixie dust. Whatever happens, you probably won't even be able to detect it once an optimizing compiler is through with it.

Community
  • 1
  • 1
user4581301
  • 33,082
  • 7
  • 33
  • 54