4
\$\begingroup\$

At the time I'm trying to read a quite big file into a C program for later user. The file size is in the range of 800 megabytes containing around 20 million lines of data of the following format:

YYYYMMDD HHMMSSMMM,X.XXXXX0,X,XXXXX0,0

  • Y: Year
  • M: Month
  • D: Day
  • H: Hour
  • M: Minute
  • S: Second
  • M: Milliseconds
  • X: floating point number

Here are a few examples:

20150101 130021493,1.209650,1.210070,0 
20150101 130044493,1.209720,1.210140,0
20150101 130044743,1.209650,1.210070,0
20150101 130045493,1.209720,1.210140,0 
20150101 130045743,1.209670,1.210090,0

I want to read the data of a single line into the following structure:

struct forexData {
  struct tm timestamp;

  uint32_t bidQuote;
  uint32_t askQuote;
};

As you can already imagine, this data represents the bid/ask quotes at a specific point in time. The bid/ask quotes are stored in uint32_t, since I prefer an integer value over floats for later use. The structures of each line are placed in another structure, which will contain all data.

struct forexDataSet {
  struct forexData **data;

  uint32_t capacity;
  uint32_t cardinality;
};

The data-property points to an array of pointers to forexData structures. The capacity-property describes how many pointers the array can hold and cardinality holds, how many pointers are currently used.

Here are the routines to read in the file:

#include <time.h>
#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <stdlib.h>

#define INITIAL_SET_SIZE  10000000
#define SET_INCREASE_STEP 1000000

// fileDescriptor returned by open(fileName, O_RDONLY, 0);
struct forexDataSet *createForexDataSetFromFile(int fileDescriptor) {
  char     buf[39000];
  ssize_t nBytesRead;

  struct forexDataSet *set = calloc(1, sizeof(struct forexDataSet));
  set->data = malloc(INITIAL_SET_SIZE * sizeof(struct forexData *));

  if (!set->data) {
    return NULL;
  }

  set->capacity = INITIAL_SET_SIZE;

  do {
    nBytesRead = read(fileDescriptor, buf, sizeof(buf));

    size_t lineStart;
    for (lineStart = 0; lineStart < nBytesRead; lineStart += 39) {
      struct forexData *tmp = createForexDataFromString(buf + lineStart); 

      if (!tmp) {
        freeForexDataSet(set);
        return NULL;
      } else {
        if (set->cardinality == set->capacity) {
          struct forexData **increasedData = realloc(set->data, sizeof(struct forexData *) * (set->capacity + SET_INCREASE_STEP));

          if (increasedData == NULL) {
            freeForexDataSet(set);
            free(tmp);
            return NULL;
          }

          set->data = increasedData;
          set->capacity += SET_INCREASE_STEP;
        }

        set->data[set->cardinality++] = tmp;
      }
    }

  } while(nBytesRead == sizeof(buf));

  return set;
}

struct forexData *createForexDataFromString(const char *str) {
  struct forexData *tmp = calloc(1, sizeof(struct forexData));

  if (!tmp) {
    return NULL;
  }

  strptime(str, "%Y%m%d %H%M%S", &tmp->timestamp);

  tmp->bidQuote = (uint32_t) (atof(str + 19) * 1000000);
  tmp->askQuote = (uint32_t) (atof(str + 28) * 1000000);

  return tmp;
}

void freeForexDataSet(struct forexDataSet *set) {
  size_t dataIndex;

  for (dataIndex = 0; dataIndex < set->cardinality; dataIndex++) {
    free(set->data[dataIndex]);
  }

  free(set->data);
  free(set);
}

The code compile with clang flags -Weverything -Wextra without warnings except one warning (comparing size_t to ssize_t in a for-loop).

What I'd like to get reviewed / brainstormed:

  • Performance. Currently the process takes around 7 seconds to complete and I was wondering if there is anything major I did wrong.
  • Buffer size. 39000 (exactly 1000 lines, since one line contains 39 characters). I only read in whole lines at a time, otherwise I'd had a problem with overlapping lines and parsing, but I chose 39000 without a specific reason. I once even tried to allocate a buffer sized as big as the file and it worked pretty well (I have 16GB of RAM), but I would prefer to not suck up all the RAM while parsing.
  • Hard-Coded-Pieces. As you probably already saw a lot of this is hard coded atof(str + 19), 39000 bytes buffer size, strptime(str, "%Y%m%d %H%M%S", &tmp->timestamp); and I was wondering how to improve these without to implement a fairly complex formatting string parser. Maybe there is a clever way to determine the buffer size of something like this.
  • Error handling and freeing. Is everything freed correctly, when something could not get allocated, etc.
\$\endgroup\$
  • \$\begingroup\$ Back up a bit, if you could. Why is it necessary for the entire file to be in memory? What kind of processing are you doing? \$\endgroup\$ – Reinderien Mar 13 '16 at 20:17
6
\$\begingroup\$

No need for realloc

The first thing I noticed is that your program has an inefficient reallocation strategy. On a file with 20 million entries, your program will need to reallocate 10 times. But you don't even need to reallocate at all. Since you know that the file contains entries of length 39, all you need to do is measure the file size and divide by 39 to determine the number of entries. Here is the code I used to do it:

#define INPUT_LINE_LEN    39

    // In createForexDataSetFromFile()
    off_t    fsize;
    ssize_t  numEntries;

    fsize      = lseek(fileDescriptor, 0, SEEK_END);
    numEntries = (fsize + INPUT_LINE_LEN - 1) / INPUT_LINE_LEN;
    lseek(fileDescriptor, 0, SEEK_SET);

This change didn't end up speeding up the program, but it did simplify things by removing the whole reallocation portion of the code. It also reduced the total memory usage from around 1.7 GB to about 1.3 GB for a 20 million line input file.

One array of structs

Right now, you allocate an array of pointers, and then allocate one data structure per line in the file. You end up calling malloc 20 million times more than you need to. Instead of an array of pointers, you should just allocate one array of structs. The code would look like this:

struct forexDataSet {
    struct forexData *data;
    uint32_t numEntries;
};

// fileDescriptor returned by open(fileName, O_RDONLY, 0);
struct forexDataSet *createForexDataSetFromFile(int fileDescriptor) {
    char     buf[INPUT_LINE_LEN * 1000];
    ssize_t nBytesRead;
    off_t    fsize;
    ssize_t  numEntries;
    ssize_t  entryNum = 0;

    fsize      = lseek(fileDescriptor, 0, SEEK_END);
    numEntries = (fsize + INPUT_LINE_LEN - 1) / INPUT_LINE_LEN;
    lseek(fileDescriptor, 0, SEEK_SET);

    struct forexDataSet *set = calloc(1, sizeof(struct forexDataSet));
    set->data = malloc(numEntries * sizeof(struct forexData));

    if (!set->data) {
        free(set);
        return NULL;
    }

    set->numEntries = numEntries;
    do {
        nBytesRead = read(fileDescriptor, buf, sizeof(buf));

        size_t lineStart;
        for (lineStart = 0; lineStart < nBytesRead; lineStart += 39) {
            createForexDataFromString(buf + lineStart, &set->data[entryNum++]);
        }
    } while(nBytesRead == sizeof(buf));
    return set;
}

void createForexDataFromString(const char *str, struct forexData *tmp) {
    strptime(str, "%Y%m%d %H%M%S", &tmp->timestamp);

    tmp->bidQuote = (uint32_t) (atof(str + 19) * 1000000);
    tmp->askQuote = (uint32_t) (atof(str + 28) * 1000000);
}

This change sped up the program from 21 sec to 17.2 sec on my test case. It also reduced the memory usage from 1.3 GB to 1.0 GB.

Custom read time

One of the slower parts of the program is the call to strptime(). Since the time is in a fixed format, you could do better by writing your own custom time parser, like this:

static inline int getInt4(const char *str)
{
    return (str[0] - '0') * 1000 + (str[1] - '0') * 100 +
           (str[2] - '0') * 10 + (str[3] - '0');
}

static inline int getInt2(const char *str)
{
    return (str[0] - '0') * 10 + (str[1] - '0');
}

void createForexDataFromString(const char *str, struct forexData *tmp) {
    tmp->timestamp.tm_year = getInt4(str) - 1900;
    tmp->timestamp.tm_mon  = getInt2(str+4) - 1;
    tmp->timestamp.tm_mday = getInt2(str+6);
    tmp->timestamp.tm_hour = getInt2(str+9);
    tmp->timestamp.tm_min  = getInt2(str+11);
    tmp->timestamp.tm_sec  = getInt2(str+13);

    tmp->bidQuote = (uint32_t) (atof(str + 19) * 1000000);
    tmp->askQuote = (uint32_t) (atof(str + 28) * 1000000);
}

This change sped up the program from 17.2 sec to 7.8 sec.

More compact time format

I'm not sure if you need the time in a struct tm format, but that format wastes a lot of space. It is defined as a struct containing 9 int fields, which is typically going to be 36 bytes. Multiply that by 20 million entries and you are using 720 MB just to hold the timestamps. I changed the timestamp to a custom struct which uses only 8 bytes, like this:

struct forexTimestamp {
    uint8_t sec;
    uint8_t min;
    uint8_t hour;
    uint8_t day;
    uint8_t mon;
    uint16_t year;
};

struct forexData {
    struct forexTimestamp timestamp;

    uint32_t bidQuote;
    uint32_t askQuote;
};

This change only sped up the program from 7.8 to 7.6 sec, but it reduced the memory usage from over 1 GB to about 320 MB.

Custom read float

The other slow part of the program is reading the float and converting to an integer. You can make your own custom float reading function as well:

// Assumes float is in the format X.XXXXXX and returns the float
// multiplied by 1000000.
static inline uint32_t getFloat_1_6(const char *str)
{
    return (str[0] - '0') * 1000000 + (str[2] - '0') * 100000 +
           (str[3] - '0') * 10000   + (str[4] - '0') * 1000   +
           (str[4] - '0') * 100     + (str[5] - '0') * 10    +
           (str[6] - '0');
}

void createForexDataFromString(const char *str, struct forexData *tmp) {
    tmp->timestamp.year = getInt4(str);
    tmp->timestamp.mon  = getInt2(str+4);
    tmp->timestamp.day  = getInt2(str+6);
    tmp->timestamp.hour = getInt2(str+9);
    tmp->timestamp.min  = getInt2(str+11);
    tmp->timestamp.sec  = getInt2(str+13);

    tmp->bidQuote = getFloat_1_6(str + 19);
    tmp->askQuote = getFloat_1_6(str + 28);
}

This change reduced the runtime of the program from 7.6 sec to 0.79 sec.

Summary

In total, the program runtime was reduced from 21 sec to 0.79 sec, or 26.6 times faster than the original. The memory usage was also decreased from 1.7 GB to 320 MB. The biggest gains were from the custom parsings of two parts of the input line. The final program was this:

#include <time.h>
#include <stdio.h>
#include <fcntl.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <stdlib.h>

struct forexTimestamp {
    uint8_t sec;
    uint8_t min;
    uint8_t hour;
    uint8_t day;
    uint8_t mon;
    uint16_t year;
};

struct forexData {
    struct forexTimestamp timestamp;

    uint32_t bidQuote;
    uint32_t askQuote;
};

struct forexDataSet {
    struct forexData *data;
    uint32_t numEntries;
};

#define INPUT_LINE_LEN    39

static void createForexDataFromString(const char *str, struct forexData *tmp);

// fileDescriptor returned by open(fileName, O_RDONLY, 0);
struct forexDataSet *createForexDataSetFromFile(int fileDescriptor)
{
    char     buf[INPUT_LINE_LEN * 1000];
    ssize_t  nBytesRead;
    off_t    fsize;
    ssize_t  numEntries;
    ssize_t  entryNum = 0;

    fsize      = lseek(fileDescriptor, 0, SEEK_END);
    numEntries = (fsize + INPUT_LINE_LEN - 1) / INPUT_LINE_LEN;
    lseek(fileDescriptor, 0, SEEK_SET);

    struct forexDataSet *set = calloc(1, sizeof(struct forexDataSet));
    set->data = malloc(numEntries * sizeof(struct forexData));
    set->numEntries = numEntries;

    if (!set->data) {
        free(set);
        return NULL;
    }

    do {
        nBytesRead = read(fileDescriptor, buf, sizeof(buf));

        size_t lineStart;
        for (lineStart = 0; lineStart < nBytesRead; lineStart += 39)
            createForexDataFromString(buf + lineStart, &set->data[entryNum++]);
    } while(nBytesRead == sizeof(buf));

    return set;
}

static inline int getInt4(const char *str)
{
    return (str[0] - '0') * 1000 + (str[1] - '0') * 100 +
           (str[2] - '0') * 10   + (str[3] - '0');
}

static inline int getInt2(const char *str)
{
    return (str[0] - '0') * 10 + (str[1] - '0');
}

// Assumes float is in the format X.XXXXXX and returns the float
// multiplied by 1000000.   
static inline uint32_t getFloat_1_6(const char *str)
{
    return (str[0] - '0') * 1000000 + (str[2] - '0') * 100000 +
           (str[3] - '0') * 10000   + (str[4] - '0') * 1000   +
           (str[4] - '0') * 100     + (str[5] - '0') * 10    +
           (str[6] - '0');
}

static void createForexDataFromString(const char *str, struct forexData *tmp)
{
    tmp->timestamp.year = getInt4(str);
    tmp->timestamp.mon  = getInt2(str+4);
    tmp->timestamp.day  = getInt2(str+6);
    tmp->timestamp.hour = getInt2(str+9);
    tmp->timestamp.min  = getInt2(str+11);
    tmp->timestamp.sec  = getInt2(str+13);

    tmp->bidQuote = getFloat_1_6(str + 19);
    tmp->askQuote = getFloat_1_6(str + 28);
}

void freeForexDataSet(struct forexDataSet *set)
{
    free(set->data);
    free(set);
}

int main(int argc, char *argv[])
{
    struct forexDataSet *set;
    int fd;

    if (argc < 2) {
        return 0;
    }
    fd = open(argv[1], O_RDONLY, 0);
    set = createForexDataSetFromFile(fd);
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Awesome review, thanks for taking your time. I probably need to stick with tm structs, since later I'll have to calculate the difference between two timestamps. The standard lib has pretty convenient ways to do so (difftime(mktime(struct tm timestamp1), mtkime(struct tm timestamp2))). I don't really want to deal with leapyears and so on by myself. I also wanted to ask, what do you think of the random selected buffer size ofer INPUT_LINE_LEN * 1000? \$\endgroup\$ – LastSecondsToLive Mar 14 '16 at 9:43
  • \$\begingroup\$ The buffer size of 39k is reasonable. It should be something large enough so that you don't make too many calls to read(), but small enough so that you don't need a huge allocation. Typically when I am reading from a large file I'd use something like a 32KB or 64KB buffer, so 39KB fits right in there. \$\endgroup\$ – JS1 Mar 14 '16 at 22:33
  • \$\begingroup\$ @LastSecondsToLive About the tm struct, you could use your own struct to save memory, and then when you need to calculate the difference, you could convert to a tm struct pretty quickly and then run mktime on that. It depends on 1) if you need to save memory and 2) how frequently you need to operate on the timestamps. \$\endgroup\$ – JS1 Mar 15 '16 at 3:33
2
\$\begingroup\$

Considerations:

If the file format as stated occupies 800MB on disc, it will occupy less memory when loaded in binary form IF the structure is one, two, or four-byte-packed (aligned). If the alignment is higher than four bytes, access performance due to bus characteristics might improve at the cost of increased memory occupation. You would be best to try several different alignments to measure the difference.

You should consider loading into an SQLite instance. SQLite supports indexes, and you should probably be indexing by the timestamp at the least.

Finally, you could decrease the load time through a multi-threaded approach. Spread offsets evenly throughout the file, and load from those offsets. You'll need one file handle per thread.

\$\endgroup\$

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.