3
\$\begingroup\$

I work in a project based on C language. I want to read a file that contains two lines of numeric characters.

Example

9
8 9 5456 32 2 45 34 98 5

I want to pass the elements of the second line into an array. As you saw the first line tell us how big needs to be the array. In the above example we want to create an array with size of 9 to hold 9 numbers.

I created a code that does that exactly but it's too complicated and I want to make it more flexible.

The logic of my code it the following:

I try to read the entire file in one go into a single char*, then splits that by line into an array of char* and then lastly converts each line to an int by calling atoi.

The function count_lines() counts the number of words and enter key(new line). The function is_linebreaks(p) checks if the character is a space (' '), an enter key (\n) or a carriage return (\r). If this condition is true, it increment rows counter and eats the other breaks. Eating other breaks means, for example, that if you had multiple spaces (' ') it would skip them until the next valid character (or one of the other breaks).

So, if number_of_rows (in the main function) is not actually rows, but number of words, each line will have one word!

I created the code just to hold 2.000.000 numbers as fast as possible so i want to keep the same logic of the code. But if you have a better idea to store so many numbers so fast please proceed to expain.

The problem is that in the second linespace, every element is one space separated so I don't need to kill all the whitespaces. Also I have only two line in the file.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <time.h>

int is_end(char* input) {
    return *input == 0;
}

int is_linebreak(char* input) {
    return *input == '\r' || *input == '\n' || *input == ' ';
}

char* eat_linebreaks(char* input) {
    while (is_linebreak(input))
        ++input;

    return input;
}

size_t count_lines(char* input) {
    char* p = input;
    size_t rows = 1;

    if (is_end(p))
        return 0;

    while (!is_end(p)) {
        if (is_linebreak(p)) {
            ++rows;
            p = eat_linebreaks(p);
        }
        else {
            ++p;
        }
    }
    return rows;
}

/* split string by lines */
char** get_lines(char* input, size_t line_count) {
    char* p = input;
    char* from = input;
    size_t length = 0;
    size_t line = 0;
        int i;
    char** lines = (char**)malloc(line_count * sizeof(char*));

    do {
        if (is_end(p) || is_linebreak(p)) {
            lines[line] = (char*)malloc(length + 1);
            for (i = 0; i < length; ++i)
                lines[line][i] = *(from + i);

            lines[line][length] = 0;
            length = 0;
            ++line;
            p = eat_linebreaks(p);
            from = p;

        }
        else {
            ++length;
            ++p;
        }
    } while (!is_end(p));

    // Copy the last line as well in case the input doesn't end in line-break
    lines[line] = (char*)malloc(length + 1);
    for (i = 0; i < length; ++i)
        lines[line][i] = *(from + i);

    lines[line][length] = 0;
    ++line;


    return lines;
}

int main(int argc, char* argv[]) {
    clock_t start;
    unsigned long microseconds;
    float seconds;
    char** lines;
    size_t size;
    size_t number_of_rows;
    int count;
    int* my_array;
    start = clock();

    FILE *stream;
    char *contents;
    int fileSize = 0;
        int i;

    // Open file, find the size of it
    stream = fopen(argv[1], "rb");
    fseek(stream, 0L, SEEK_END);
    fileSize = ftell(stream);
    fseek(stream, 0L, SEEK_SET);

    // Allocate space for the entire file content
    contents = (char*)malloc(fileSize + 1);

    // Stream file into memory
    size = fread(contents, 1, fileSize, stream);
    contents[size] = 0; 
    fclose(stream);

    // Count rows in content
    number_of_rows = count_lines(contents);

    // Get array of char*, one for each line
    lines = get_lines(contents, number_of_rows);

    // Get the numbers out of the lines
    count = atoi(lines[0]); // First row has count
    my_array = (int*)malloc(count * sizeof(int));
    for (i = 0; i < count; ++i) {
        my_array[i] = atoi(lines[i + 1]);
    }

    microseconds = clock() - start;
    seconds = microseconds / 1000000.0f;
    printf("Took %fs", seconds);


    return 0;
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Why do you want to know the number of rows? You are just reading one line of numbers. So you really only care about the first two lines. \$\endgroup\$ – Martin York Dec 5 '14 at 3:18
  • \$\begingroup\$ thats my problem. I can't update the my code making it to read only the first two lines! (upvoted comment) \$\endgroup\$ – Nikos KLon Dec 5 '14 at 11:56
3
\$\begingroup\$

Here are some things that may help you improve your code:

Be careful with signed and unsigned

In two cases, the code compares an int i with an unsigned size_t length. It would be better to declare i to also be size_t.

Think of the user

What happens when the user does not specify a file name on the command line? The answer on my machine is that I get a segmentation fault and a crash. Not nice. It's easily solved by checking argc to make sure that the user has specified at least one argument and by checking to make sure that fopen has not returned NULL.

Free memory that you allocate

This program leaks memory because you have allocated space using malloc but never released with free. That's bad practice.

Carefully consider whether memory allocation is required

Reading the entire file into memory is not really a necessary step for this algorithm. Better would be to read from the file using something like fscanf since the file is probably buffered in memory anyway. This would make your code more flexible and eliminate the need for both memory allocation for the file contents and the count_lines routine.

Don't use unnecessary #includes

The code has #include <assert.h> but nothing from that include file is actually in the code. For that reason, that #include should be eliminated.

Handle error conditions

Whenever one works with file I/O or memory allocation, there is a chance these operations can fail. For that reason, all such operations should not only be checked for errors, but also the program should handle those errors in some appropriate way. For instance, what if the input file claims there are 9 numbers but there are actually on 4 in the file? Your program will need to handle that.

\$\endgroup\$
4
  • \$\begingroup\$ i understand your point. First this is a project and the employe told us not to take any restrictions or error conditions. So don't worry about that. Second, I didn't use fscanf cause I want the procidure to be done in less than 1.5 seconds and with fscanf I would need aproximately 3 - 4 seconds. I want to keep the structure of the code but to make it cleaner so the user can understand what is going on! :) \$\endgroup\$ – Nikos KLon Dec 3 '14 at 14:50
  • \$\begingroup\$ there are parts in my code that I don't need. So I wrote a code that isn't tided up. That's why i post it here. I don't have any other idea to think. \$\endgroup\$ – Nikos KLon Dec 3 '14 at 14:52
  • \$\begingroup\$ @Opo: you should test your assumption about fscanf being "too slow." On my machine, using an input file with 10 million random numbers, your program takes 1.49 seconds and leaks 210 megabytes. My modified version, using fscanf and with all error handling, takes 0.99 seconds and leaks no memory. \$\endgroup\$ – Edward Dec 3 '14 at 15:15
  • \$\begingroup\$ so what have yout try? Your modified version? Also notice that the maximum memory I can use is 64 MB \$\endgroup\$ – Nikos KLon Dec 3 '14 at 15:31
1
\$\begingroup\$

K.I.S.S (Keep It Silly Simple)

You're writing a lot of code in an effort to try to be clever and squeeze the maximum performance out of the machine, this is a common fallacy for inexperienced software developers, they think they can do it better in half a day than the experts who spent thousands of hours optimizing the standard library.

Case in point, here's my trivial code using the standard library (please excuse the crudity of the model, I didn't have time to build it to scale or to paint it):

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int main(int argc, char** argv)
{
  clock_t start = clock();
  FILE * f = fopen(argv[1],"r");
  int n;
  fscanf(f, "%d", &n);
  int* v = malloc(sizeof(int)*n);
  for(int i=0; i < n; ++i){
    fscanf(f, "%d", &v[i]);
  }
  fclose (f);

  unsigned long microseconds = clock() - start;
  printf("Took %d us\n", microseconds);

  int sum = 0;
  for(int i = 0; i < n; ++i){
    sum += v[i];
  }

  printf("n: %d sum: %d\n", n, sum);
  free(v);
}

Printing the sum was just a quick and dirty way of testing that it actually produced the same result as OP's code (which it does).

I compiled both my and OP's code with gcc -O3 -march=native

I ran both my and OP's code on the same test input with 1E8 numbers ten times just to try to remove noise from the results. I changed OP's code to print microseconds and compute the sum of the results (outside of the timed section).

Here are the results:

$ for run in {1..10}; do ./my xtest100000000; done
Took 5828125 us
n: 100000000 sum: -981509729
Took 5781250 us
n: 100000000 sum: -981509729
Took 5796875 us
n: 100000000 sum: -981509729
Took 5796875 us
n: 100000000 sum: -981509729
Took 5812500 us
n: 100000000 sum: -981509729
Took 6031250 us
n: 100000000 sum: -981509729
Took 6484375 us
n: 100000000 sum: -981509729
Took 6312500 us
n: 100000000 sum: -981509729
Took 6234375 us
n: 100000000 sum: -981509729
Took 6140625 us
n: 100000000 sum: -981509729

$ for run in {1..10}; do ./op xtest100000000; done
Took 7625000 us
n: 100000000 sum: -981509729
Took 8046875 us
n: 100000000 sum: -981509729
Took 7656250 us
n: 100000000 sum: -981509729
Took 7984375 us
n: 100000000 sum: -981509729
Took 7546875 us
n: 100000000 sum: -981509729
Took 7812500 us
n: 100000000 sum: -981509729
Took 7484375 us
n: 100000000 sum: -981509729
Took 7562500 us
n: 100000000 sum: -981509729
Took 8062500 us
n: 100000000 sum: -981509729
Took 7796875 us
n: 100000000 sum: -981509729

The values work out to:

  • My: 6.021875 s average 0.257820 s stddev
  • Op: 7.757813 s average 0.215407 s stddev

In other words, my simple version is 28% faster according to my benchmarks.

For fun I implemented the same code in C++ using the STL:

#include <iostream>
#include <fstream>
#include <vector>
#include <chrono>
#include <functional>
#include <numeric>

using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::microseconds;

int main(int argc, char** argv){
  if(argc != 2){
    return 1;
  }

  auto t1 = high_resolution_clock::now();
  std::ifstream ifs(argv[1]);
  int n;
  ifs>>n;
  std::vector<int> v;
  v.reserve(n);
  for(int i = 0; i < n; ++i){
    int x;
    ifs>>x;
    v.emplace_back(x);
  }
  auto t2 = high_resolution_clock::now();

  std::cout<<"Took "<<duration_cast<microseconds>(t2-t1).count()<<" us"<<std::endl;

  std::cout<<"n: "<<n<<" Size: "<<v.size()<<" Sum: "<<std::accumulate(v.begin(), v.end(), 0)<<std::endl;

}

And here are the results for the same input:

$ for run in {1..10}; do ./cc xtest100000000; done
Took 5091717 us
n: 100000000 Sum: -981509729
Took 5222749 us
n: 100000000 Sum: -981509729
Took 5098467 us
n: 100000000 Sum: -981509729
Took 5124035 us
n: 100000000 Sum: -981509729
Took 5127467 us
n: 100000000 Sum: -981509729
Took 4977138 us
n: 100000000 Sum: -981509729
Took 5188494 us
n: 100000000 Sum: -981509729
Took 4992880 us
n: 100000000 Sum: -981509729
Took 5073020 us
n: 100000000 Sum: -981509729
Took 5121874 us
n: 100000000 Sum: -981509729

This works out to: 5.101784 s average 0.076045 s stddev.

Interestingly the "slow" C++ I/O is 18% faster than the C implementation with a much tighter standard deviation. Some people will tell you using C-style I/O is always faster than using C++ streams, this shows that it's not always the case. Infact, it's been my experience that every time I've converted C to C++ either the binary shrunk or the code got faster er both, despite "paying extra for C++ overhead".

Edit

I ran the C++ code as compiled by clang as well, the results are: 5.030151 s average 0.112417 s stddev.

The results are 1.4% faster than the GCC compiled C++ code with a slight regression in stddev, however without a more controlled benchmark it's hard to say if this is within margin of error or not.

Summary

Just write the simplest code possible that is easy to maintain; worry about optimizing once you have evidence that your code is too slow. And at that point profile, and compare to make sure your optimizations are actually working and not just making the code slower.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It's great to see that C++ myth debunked (again). It's possible that C++ allows more people to write bloated, slow programs, but in competent hands it's a very capable language. If this were a C++ review, I'd recommend replacing the for loop with std::copy_n(), showing again how much more productive we can be (almost no need for any flow-control statements). \$\endgroup\$ – Toby Speight 13 hours ago
  • 1
    \$\begingroup\$ A sufficiently skilled engineer can create an mess in any language... I think C++ offers more and easier paths to create correct and fast programs than C, on the other hand it also has more and shinier foot-guns that people may be tempted the (mis)use. \$\endgroup\$ – Emily L. 12 hours ago
-2
\$\begingroup\$
#include <stdio.h>
#include <stdlib.h>
int main()
{   //i is the index to write into array, size if length of our possible array
    int i = 0, size;
    //Create a file pointer to open file
    FILE * fp;            //read mode
    fp = fopen("file.txt","r"); //open file
    if (fp == NULL){
        printf("Error. Can't open the file\n");
        exit(1);
    }
    //get the size of an array
    fscanf(fp,"%d",&size);
    //create an array of length size
    int array[size];
    //fill up an array
    while (i < size){
        fscanf(fp,"%d",&array[i]);
        i +=1;
    }
    //print the array / Test
    for (i = 0; i < size; i++){
        printf("%d\n",array[i]);
    }
    fclose(fp);
    return 0;
}
New contributor
Shoby is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to CodeReview@SE. Just presenting different code to accomplish the same as the code presented for review in the question is not a valid and useful CR answer. Please see How do I write a Good Answer?. While it would have been preferable that Nikos KLon supplemented the question, see the comments to the other answer and respond to the concern about fscanf() speed. \$\endgroup\$ – greybeard 23 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.