Avoid allocating a large amount of memory for concatenation in C programming

Question

The provided code reads lines from a text file and stores them in a dynamically allocated 2D array called lines (the pattern always repeats after line 32767). It then concatenates specific lines (lines[j], lines[k], lines[m]) and prints the result in an output file. The problem is that my input.txt file is so huge that my PC cannot handle this - 100GB. Because with malloc I allocate so much memory for a 2D array that my hard drive is full. Is there any possibility to change my code that i did not have to allocate so much memory? Thanks for any help!

#include <stdlib.h>
#include <string.h>

#define MAX_LINE_LENGTH 300          // specifies the maximum length of a line in the input file
#define MAX_LINES 500000000          // specifies the maximum number of lines of the input file

int main()
{
   // Open the file
   FILE *fp = fopen("input.txt", "r");
   if (fp == NULL)
   {
       printf("Failed to open the file.\n");
       return 1;
   }


   // Allocate memory for lines
   char **lines = (char **)malloc(MAX_LINES * sizeof(char *));
   if (lines == NULL)
   {
       printf("Failed to allocate memory for lines.\n");
       fclose(fp);
       return 1;
   }

   for (int i = 0; i < MAX_LINES; i++)
   {
       lines[i] = (char *)malloc(MAX_LINE_LENGTH * sizeof(char));
       if (lines[i] == NULL)
       {
           printf("Failed to allocate memory for line %d.\n", i);
           // Free previously allocated lines
           for (int j = 0; j < i; j++)
           {
               free(lines[j]);
           }
           free(lines);
           fclose(fp);
           return 1;
       }
   }

   // Reset file pointer to the beginning
   fseek(fp, 0, SEEK_SET);

   // Read lines from the file and store them in lines array
   int lineIndex = 0;
   char line[MAX_LINE_LENGTH];
   while (fgets(line, sizeof(line), fp) != NULL)
   {
       // Remove newline character from the end of the line
       if (line[strlen(line) - 1] == '\n')
           line[strlen(line) - 1] = '\0';
       strcpy(lines[lineIndex], line);
       lineIndex++;
   }

   fclose(fp);

   // Create output file
   FILE *outputFile = fopen("output.txt", "w");
   if (outputFile == NULL)
   {
       perror("Error creating output file");
       // Free allocated lines
       for (int i = 0; i < MAX_LINES; i++)
       {
           free(lines[i]);
       }
       free(lines);
       return 1;
   }
   int i=1;
   int j=5;         //begin Permno number
   int k=10927;     //begin PRC date
   int m=21849;     //begin DLRETX data
   int count=0;

   int jj=10923;    // end PERNMO data
   int kk=21846;    // end PRC data
   int mm=32767;    // end DLRETX data
   int count_whileLoop=0;


   // Append lines
   for (i,j,k,m;  j<=jj,k<=kk,m<=mm;  i++,j++,k++,m++)
   {
       fprintf(outputFile, "%s%s%s\n", lines[j], lines[k], lines[m]);

   }

   // Free allocated memory
   for (int i = 0; i < MAX_LINES; i++)
   {
       free(lines[i]);
   }
   free(lines);

   // Close the output file
   fclose(outputFile);

   return 0;
}

Answer 1

A few ideas ...

1. With large files, it's better to use mmap instead of reading in the data.

2. If we remember the starting offset of a line and its length [in an array of "line" struct], we don't have to remove the newline [so the file can be mapped R/O].

3. With this, each line only uses two size_t values for offset/length. (i.e.) We don't have to strdup/malloc the actual data.

4. We can put line ranges into a struct (called a "segment" in the code below). We can have as many as we want [vs. just the 3 in the problem].

5. We can stop reading after we hit the maximum line number. This is a major reduction in space (e.g. In your example, the maximum line number is 32767).

6. Doing fprintf with a format of %s%s%s\n" to create a joined output line is relatively slow. Better to use fputc or fwrite

For some background on the mmap idea, here is an answer of mine: read line by line in the most efficient way platform specific

---

Here is the reimagined code. It is annotated.

For testing, it allows a -G option to specify the generation of a random input test file.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/stat.h>
#include <sys/mman.h>

#define sysfault(_fmt...) \
    do { \
        printf(_fmt); \
        exit(1); \
    } while (0)

#if DEBUG
#define dbgprt(_fmt...) \
    printf(_fmt)
#else
#define dbgprt(_fmt...) \
    do { } while (0)
#endif

// dynamic list control
typedef struct {
    void *list_base;                    // pointer to data
    size_t list_size;                   // sizeof(element)
    size_t list_count;                  // # of elements used
    size_t list_cap;                    // # of elements allocated (capacity)
} list_t;

typedef struct {
    size_t line_off;                    // absolute offset of line start
    size_t line_len;                    // line length (inc newline)
} line_t;

typedef struct {
    size_t seg_beg;                     // starting line index (inclusive)
    size_t seg_end;                     // ending line index (inclusive)
    size_t seg_cur;                     // current line index (inclusive)
    size_t seg_count;                   // line count
} seg_t;

int opt_a;                              // load _all_ data
size_t opt_G;                           // generate input of this many bytes
int opt_L;                              // maximum line width

list_t *seglist;
size_t segend;                          // maximum line number we have to get

const char *inpbase;                    // pointer to input file data
size_t inpsize;                         // input file size
list_t *linelist;                       // list of lines

// listnew -- get new list
list_t *
listnew(size_t siz)
{
    list_t *list = calloc(1,sizeof(*list));

    list->list_size = siz;

    return list;
}

// listloc -- point to list entry
void *
listloc(list_t *list,size_t idx)
{
    void *ptr = list->list_base;
    ptr += idx * list->list_size;
    return ptr;
}

// listadd -- point to new list entry
void *
listadd(list_t *list)
{

    if (list->list_count >= list->list_cap) {
        list->list_cap += 100;
        list->list_base = realloc(list->list_base,
            list->list_size * list->list_cap);
    }

    void *ptr = listloc(list,list->list_count);
    list->list_count += 1;

    return ptr;
}

// seginit -- initialize line number range segment
void
seginit(size_t beg,size_t end)
{

    seg_t *seg = listadd(seglist);

    seg->seg_beg = beg;
    seg->seg_end = end;
    seg->seg_count = (end + 1) + beg;

    if (end > segend)
        segend = end;

    printf("seginit: seg_beg=%zu seg_end=%zu seg_count=%zu\n",
        seg->seg_beg,seg->seg_end,seg->seg_count);

    seg->seg_cur = seg->seg_beg;
}

// linegeta -- read in all input lines
void
linegeta(size_t maxlines)
{

    const char *lhs = inpbase;
    size_t remsize = inpsize;
    const char *rhs;
    size_t curlen;

    if (maxlines != 0)
        maxlines += 20;

    printf("lineget: remsize=%zu maxlines=%zu\n",remsize,maxlines);

    list_t *list = listnew(sizeof(line_t));
    linelist = list;

    for (;  remsize > 0;  remsize -= curlen) {
        rhs = memchr(lhs,'\n',remsize);
        if (rhs == NULL)
            break;

        // point past newline
        ++rhs;

        // get length of line (inc newline)
        curlen = rhs - lhs;

        // remember starting offset and length of current line
        line_t *line = listadd(list);
        line->line_off = lhs - inpbase;
        line->line_len = curlen;

        // point past newline
        lhs = rhs;

        // stop on line limit
        if (maxlines != 0) {
            if (list->list_count >= maxlines)
                break;
        }
    }

    printf("lineget: list_count=%zu\n",list->list_count);
}

// segput -- output a line segment
size_t
segput(FILE *xfout,seg_t *seg)
{
    size_t outlen = 0;

    do {
        size_t lnoidx = seg->seg_cur;
        int over = (lnoidx > seg->seg_end);
        dbgprt("segput: seg_cur=%zu seg_end=%zu%s\n",
            seg->seg_cur,seg->seg_end,over ? " OVER" : "");

        if (over)
            break;
        ++seg->seg_cur;

        const line_t *line = listloc(linelist,lnoidx);
        const char *buf = inpbase + line->line_off;

        size_t explen = line->line_len - 1;

        outlen = fwrite(buf,1,explen,xfout);
        if (outlen == explen)
            break;

        sysfault("segput: explen=%zu outlen=%zu -- %s\n",
            explen,outlen,strerror(errno));
    } while (0);

    return outlen;
}

// lineput -- create an output line
int
lineput(FILE *xfout)
{
    list_t *list = seglist;
    int outcnt = 0;

    for (int segidx = 0;  segidx < list->list_count;  ++segidx) {
        seg_t *seg = listloc(list,segidx);
        if (segput(xfout,seg))
            ++outcnt;
    }

    if (outcnt > 0)
        fprintf(xfout,"\n");

    return outcnt;
}

// lineputa -- output all joined lines
void
lineputa(FILE *xfout)
{
    size_t outcnt = 0;

    while (1) {
        if (! lineput(xfout))
            break;

        ++outcnt;
        if (outcnt > linelist->list_count)
            sysfault("lineputa: too much output\n");

    }
}

// xrand -- fast random number generator
unsigned int
xrand(void)
{
    static unsigned int seed = 1;

    // this is random in TYPE_0 (linear congruential) mode with the mask
    // removed to get full range numbers
    // this does _not_ produce overlaps
    seed = (seed * 1103515245) + 12345;

    return seed;
}

// genline -- generate a line number
size_t
genline(FILE *xfdst,size_t lno)
{
    char buf[1000];
    char *bp = buf;

    size_t off = ftell(xfdst);
    bp += sprintf(bp," %zu/%zu:",off,lno);

    ssize_t remlen = bp - buf;
    remlen = (opt_L - 20) - remlen;
    if (remlen <= 0)
        remlen = 1;
    remlen = (xrand() % remlen) + 1;

    for (;  remlen > 0;  --remlen, ++bp) {
        int chr = xrand() % 26;
        chr += 'A';
        *bp = chr;
    }

    *bp++ = '\n';

    size_t explen = bp - buf;
    size_t actlen = fwrite(buf,1,explen,xfdst);
    if (actlen != explen)
        sysfault("genline: fwrite lno=%zu -- %s\n",lno,strerror(errno));

    return actlen;
}

// genfile -- generate random input file
void
genfile(const char *file,size_t maxsize,size_t lnomax)
{

    size_t totsize = 0;
    size_t curlen;
    size_t lnocur = 1;

    if (lnomax != 0)
        lnomax += 1000;

    printf("genfile: maxsize=%zu lnomax=%zu\n",maxsize,lnomax);

    FILE *xfdst = fopen(file,"w");

    for (;  (totsize < maxsize);  totsize += curlen, ++lnocur) {
        if ((lnomax != 0) && (lnocur >= lnomax))
            break;
        curlen = genline(xfdst,lnocur);
    }

    fclose(xfdst);

    printf("genfile: totsize=%zu lnocur=%zu\n",totsize,lnocur);
}

int
main(int argc,char **argv)
{

    --argc;
    ++argv;

    for (;  argc > 0;  --argc, ++argv) {
        char *cp = *argv;
        if (*cp != '-')
            break;

        cp += 2;
        switch (cp[-1]) {
        case 'a':
            opt_a = ! opt_a;
            break;
        case 'G':
            opt_G = (*cp != 0) ? strtol(cp,&cp,10) : 100;
            switch (*cp) {
            case 'M':
                opt_G *= 1024 * 1024;
                break;
            default:
                opt_G *= 1024 * 1024 * 1024;
                break;
            }
            break;
        case 'L':
            opt_L = (*cp != 0) ? strtol(cp,&cp,10) : 40;
            break;
        }
    }

    if (opt_L <= 0)
        opt_L = 40;

    // get ranges we want
    seglist = listnew(sizeof(seg_t));
    seginit(5,10923);  // Permno number
    seginit(10927,21846);  // PRC date
    seginit(21849,32767);  // DLRETX data
    if (opt_a)
        segend = 0;

    if (argc != 2)
        sysfault("main: need two args\n");

    const char *inpfile = *argv++;
    const char *outfile = *argv++;

    // DEBUG: generate random test input file (careful!)
    if (opt_G)
        genfile(inpfile,opt_G,segend);

    int fdinp = open(inpfile,O_RDONLY);
    if (fdinp < 0)
        sysfault("main: unable to open '%s' -- %s\n",inpfile,strerror(errno));

    struct stat st;
    fstat(fdinp,&st);
    inpsize = st.st_size;
    printf("st_size=%zu\n",inpsize);

    // map the input file
    void *base = mmap(NULL,inpsize,PROT_READ,MAP_SHARED,fdinp,0);
    if (base == MAP_FAILED)
        sysfault("main: unable to mmap -- %s\n",strerror(errno));
    inpbase = base;

    // find all input line offsets and lengths
    linegeta(segend);

    FILE *xfout = fopen(outfile,"w");
    if (xfout == NULL)
        sysfault("main: unable to open '%s' -- %s\n",inpfile,strerror(errno));

    // output all joined lines
    lineputa(xfout);

    fclose(xfout);

    munmap(base,st.st_size);
    close(fdinp);

    return 0;
}

Answer 2

Another take on the problem, in line with the original coding style.

Since you are reading lines of unspecified length, a better alternative to gets() is getline() (available here if you are using MSVC). It allows you to read lines without worry of correctly sizing the input buffer.

Given that we are appending, another useful function is defined here to realloc and append. Then things are pretty standard: I define a vector of sections starting points, the section length (so we don't need to worry that they are of the same size) and their number.

Then, as soon as we reach a section we start appending the first section, then the second, then the third, to the same lines. Output is just writing the lines to file.

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

#ifdef _MSC_VER
#include "getline.h"
#endif

const int sections[] = {
    5,      // PERNMO
    10927,  // PRC
    21849,  // DLRETX
};
const int sections_lengths = 10919;
const int nsections = 3;

// Tries to realloc dst to allow appending src.
ssize_t strcat_realloc(char ** dst, const char *src)
{
    if (dst == NULL || src == NULL) {
        errno = EINVAL;
        return -1;
    }

    size_t ndst = *dst ? strlen(*dst) : 0;
    size_t nsrc = strlen(src);
    char *tmp = realloc(*dst, ndst + nsrc + 1);
    if (tmp == NULL) {
        errno = ENOMEM;
        return -1;
    }
    memcpy(tmp + ndst, src, nsrc + 1);
    *dst = tmp;
    return ndst + nsrc;
}

int main(void)
{
    FILE *fp = fopen("input.txt", "r");
    if (fp == NULL) {
        printf("Failed to open the file.\n");
        return 1;
    }

    char **lines = calloc(sections_lengths, sizeof(char*));

    int cur = 0;
    int lineIndex = 0;
    char *line = NULL;
    size_t len = 0;
    while (getline(&line,&len, fp) != -1) {
        line[strcspn(line, "\n")] = 0; // Remove newline character from the end of the line
        if (lineIndex == sections[cur] + sections_lengths) {
            ++cur;
            if (cur == nsections) {
                break;
            }
        }
        if (lineIndex >= sections[cur]) {
            strcat_realloc(lines + lineIndex - sections[cur], line); // TODO: manage errors
        }
        lineIndex++;
    }

    fclose(fp);

    int result = 0;
    // Create output file
    FILE *outputFile = fopen("output.txt", "w");
    if (outputFile == NULL) {
        perror("Error creating output file");
        result = 1;
    }
    else {
        // Append lines
        for (int i = 0; i < sections_lengths; ++i) {
            fprintf(outputFile, "%s\n", lines[i]);
        }
        fclose(outputFile);
    }

    // Free allocated memory
    for (int i = 0; i < sections_lengths; ++i) {
        free(lines[i]);
    }
    free(lines);

    return result;
}

Answer 3

You're only processing the first 32768 lines of the file, so you don't need to read any more than that. However, you also said:

the pattern always repeats after line 32767

So I'm assuming what you really want is to process batches of 32768 lines. In either case, that means you only need space to store that many lines at a time, not the whole file all at once. That's only about 10MB, which can easily be set aside in a file scope variable.

So change the code to use a static buffer of that size, eliminating any dynamic allocation, then loop through reading 32768 lines at a time and processing them.

Also:

• j<=jj,k<=kk,m<=mm doesn't do what you expect. You probably want j<=jj && k<=kk && m<=mm
• The variables jj, kk, and mm are not very descriptive. Better to use names for the section start/end points.

With the above changes, you now have the following:

#include <stdlib.h>
#include <string.h>

#define MAX_LINE_LENGTH 300      // maximum length of a line in the input file
#define MAX_BATCH 32768          // the number of lines in an input batch

#define PERMO_START 5
#define PRC_START 10927
#define DLRETX_START 21849

#define PERMO_END 10923
#define PRC_END 21846
#define DLRETX_END 32767

char lines[MAX_BATCH][MAX_LINE_LENGTH];

int main()
{
   // Open the input file
   FILE *fp = fopen("input.txt", "r");
   if (fp == NULL)
   {
       printf("Failed to open the file.\n");
       return 1;
   }

   // Create output file
   FILE *outputFile = fopen("output.txt", "w");
   if (outputFile == NULL)
   {
       perror("Error creating output file");
       return 1;
   }

   int done = 0;
   do {
       memset(lines, 0, sizeof lines);

       // Read lines from the file and store them in lines array
       int lineIndex = 0;
       char line[MAX_LINE_LENGTH];
       while ((lineIndex < MAX_BATCH) && (fgets(line, sizeof(line), fp) != NULL))
       {
           // Remove newline character from the end of the line
           if (line[strlen(line) - 1] == '\n')
               line[strlen(line) - 1] = '\0';
           strcpy(lines[lineIndex], line);
           lineIndex++;
       }

       done = lineIndex < MAX_BATCH;

       // Append lines
       for (int j=PERMO_START, k=PRC_START, m=DLRETX_START;
                j<=PERMO_END && k<=PRC_END && m<=DLRETX_END;
                j++,k++,m++)
       {
           fprintf(outputFile, "%s%s%s\n", lines[j], lines[k], lines[m]);
       }
   } while (!done);

   // Close the input and output file
   fclose(fp);
   fclose(outputFile);

   return 0;
}