CODEWITHSUNDEEP
c++arraysperformanceloopsfor-loop
Peter Carter
Peter Carter

Reputation: 2728

C++ loops continually evaluating if statement, making it too slow

I currently have a C++ program which is supposed to generate every possible domain name up to a set number of digits. The code I have is current pretty verbose (this is fine) but also tediously slow once it starts generating past 4 digits. The loops where things really start to go wrong are shown here:

const char* chars[] = {"a","b","c","d","e","f","g","h","i","j","k",
"l","m","n","o","p","q","r","s","t","u","v","w","x","y","z", "0", "1",
"2", "3", "4", "5", "6", "7", "8", "9", "-"};
int char_num = 1;

[...]

if(char_num == 5) {
    for(int i = 0; i < 36; i++) {
      for(int j = 0; j < 37; j++) {
        for(int k = 0; k < 37; k++) {
          for(int l = 0; l < 37; l++) {
            for(int m = 0; m < 36; m++) {
              cout << "adding " << chars[i] << chars[j] << chars[k] << chars[l] << chars[m] << ".com to list\n";
              if(i == 35 && j == 36 && k == 36 && l == 36 && m == 35) {
                char_num++;
                cout << "Generating to " << char_num + 1  << " characters\n";
              }
            }
          }
        }
      }
    }
  }

I am intending at least three or four additional if statements after this one, with incrementally more for loops in each. I'm also going to need to write the output to a file, and to use this file to do DNS lookups, so I need every drop of performance I can get so I'm not waiting weeks for the program to complete.

My main concern at present is that the program is evaluating the if statement on every single interation which I presume is having a significant effect on performance, given the number of nested loops. To stop this I tried moving the if statement into a separate function and having it return a value once it finished, but I noticed that when I do this I'm not able to log to the console from within the function, which makes things more complicated.

What is the correct process for doing this in C++ and are there any other ways to speed up the code? I did try writing the code in node.js before but it went berserk and threw a bunch of out of memory errors when I started writing to a file, and I figured C++ would probably be quicker anyway, hence I switched languages.

Upvotes: 0

Views: 813

Answers (2)

mattbuell
mattbuell

Reputation: 56

Focus on code optimizations. In the statement you are constantly re accessing the same member of the char array every iteration wasting clock cycles.

`cout << "adding " << chars[i] << chars[j] << chars[k] << chars[l] << chars[m] << ".com to list\n";`

A way to optimize this is by adding temporary variables. 

char tempI;
char tempJ;
char tempK;
char tempL;
if(char_num == 5) {
  for(int i = 0; i < 36; i++) {
    tempI = char[i];
      for(int j = 0; j < 37; j++) {
        tempJ = char[j];
          for(int k = 0; k < 37; k++) {
           tempK = char[k];
            for(int l = 0; l < 37; l++) {
             tempL = char[l];
              for(int m = 0; m < 36; m++) {
                cout << "adding " << tempI << tempJ << tempK << tempL << 
  chars[m] << ".com to list\n";
                if(i == 35 && j == 36 && k == 36 && l == 36 && m == 35) {
                char_num++;
                cout << "Generating to " << char_num + 1  << " characters\n";
              }
            }
          }
        }
      }
    }
  }

There are things you can do that make your code faster in regards to temporal and spatial locality just by the way you write it.

Also use compiler optimizations -03 with g++, etc.

Or consider rewriting your algorithm, because there might be a better way altogether in regards to time complexity

Upvotes: 2

Nathan.Eilisha Shiraini
Nathan.Eilisha Shiraini

Reputation: 687

Your if statement seems to be checking for the end of the loop. There is a simple solution to avoid this: remove the if and put the code after the loop!

However, if you need to add more ifs that depend on loop variables, I don't really know how you can optimize it. Don't, however, put them in a function: the overhead of calling the function will slow your code (and an optimizing compiler will inline your function anyway).

Here are a few possibilities you can explore:

  • use multithreading/multiprocessing. If done well, this can divide the execution time by up to the number of CPU cores on your computer
  • enable compiler optimization (-O3 or -Ofast with g++)

One last thing: if the consumer program accepts data from the standard input, piping the output of your program into it will be twice as fast as generating the names then using them. EG instead of

producer > storage.txt
consumer < storage.txt

do

producer | consumer

Upvotes: 2

Related Questions