Most memory efficient way to remove duplicate lines in a text file using C++

Question

I understand how to do this using std::string and std::unordered_set, however, each line and each element of the set takes up a lot of unnecessary, inefficient memory, resulting in an unordered_set and half the lines from the file being 5 -10 times larger than the file itself.

Is it possible (and how, if so) to somehow reduce memory consumption, for example, so that you can remove duplicates from a 10 gigabyte file using no more than 20 gigabytes of RAM? In this case, of course, it is necessary to do this at a speed of O(n).

Answer 1

I know it's a bit late for an answer to this question, but just for fun I wrote an implementation that I think is quite memory-efficient while still being reasonably performant.

In particular, this solution runs in O(N*log(N)) time and uses (on my machine) just 360 kilobytes(!) of heap memory while de-duping a 100,000,000 line (5 gigabyte) text file that contains 99,990,000 randomly-arranged duplicate lines, and finishes in 6 minutes, 32 seconds.

Of course it does cheat a bit, in that it writes out a temporary index file to disk (the index contains a hash value for each line in the input file, as well as that line's position within the input file). The index file needs 16 bytes for each text line, so it came out to ~1.4GB in my test.

To do the de-duplication, the program mmap()'s the index file into RAM, sorts its contents by hash code, then scans the index and invalidates any now-adjacent entries with the same hash code that refer to the same string in the input file.

After that it, re-sorts the index file by byte-offset, and then iterates through the index one more time to generate the de-duped output file.

Output from my test run (on a 2018 Intel Mac Mini) is as follows:

Jeremys-Mac-mini-2:~ jaf$ time ./a.out
Step 1:  Read input file [big_input_file.txt] and write index file [index_file.tmp]
Step 2:  mmap() index file [index_file.tmp] into RAM and sort its entries by hash-code
Step 3:  Iterate through index file [index_file.tmp] and invalidate any duplicate entries
Step 4:  Re-sort the index file [index_file.tmp] by byte-offset in preparation for generating output
Step 5:  Write output file [big_output_file.txt]
Step 6:  Delete index file and exit
Final result:  Out of 100000001 lines read, 99990000 duplicate lines detected and removed.
real        6m32.800s
user        3m39.215s
sys         2m41.448s

Source code is below (I compiled it with g++ -std=c++20 -O3 ./dedup_file.cpp):

#include <fcntl.h>
#include <stdint.h>
#include <unistd.h>
#include <sys/mman.h>

#include <array>
#include <fstream>
#include <iostream>
#include <span>
#include <string>

using SizeTPair = std::array<size_t, 2>;

static const SizeTPair INVALID_INDEX_ENTRY = {(std::size_t)-1, (std::size_t)-1};  // special value meaning "not a valid index entry"

// Given a pointer into the contents of the input file, returns a string_view representing
// the line of text starting there.  (This is necessary since we can't modify the input file
// and the lines in the input file are not NUL-terminated)
static std::string_view GetStringAtOffset(const char * inputFileMap, size_t offset)
{
   if (offset == (size_t)-1) return "";

   const char * s  = &inputFileMap[offset];
   const char * nl = strchr(s, '\n');
   return nl ? std::string_view(s, nl-s) : std::string_view(s);
}

// Comparison functor to sort SizeTPairs by the text they point to
// breaks ties by sorting by line-number (so that if a duplicate line is
// detected in the text, it will always be the second instance of that line that
// is excluded from our program's output, not the first instance)
class SortIndicesByStringCompareFunctor
{
public:
   SortIndicesByStringCompareFunctor(const char * inputFileMap) : _inputFileMap(inputFileMap) {/* empty */}

   bool operator()(const SizeTPair & a, const SizeTPair & b) const
   {
      const std::string_view textA = GetStringAtOffset(_inputFileMap, a[0]);
      const std::string_view textB = GetStringAtOffset(_inputFileMap, b[0]);
      if (textA != textB) return (textA < textB);
      return (a[1] < b[1]); // sub-sort by line number
   }

private:
   const char * _inputFileMap;
};

static void WriteEntryToIndexFile(std::ofstream & indexFile, const SizeTPair & entry, size_t & indexSizeItems)
{
   indexFile.write(reinterpret_cast<const char *>(&entry), 2*sizeof(size_t));
   indexSizeItems++;
}

int main(int, char **)
{
   const char * bigInputFileName  = "big_input_file.txt";
   const char * indexFileName     = "index_file.tmp";
   const char * bigOutputFileName = "big_output_file.txt";

   std::cout << "Step 1:  Read input file [" << bigInputFileName << "] and write index file [" << indexFileName << "]" << std::endl;

   // Step 1.  Read through the big input-text file, and generate a binary
   // index-file containing (for each line) that line's hash-code and also
   // its location in the input file
   size_t indexSizeItems = 0;
   size_t inputFileSizeBytes = 0;
   {
      std::ifstream inputFile;
      inputFile.open(bigInputFileName, std::ios_base::binary | std::ios_base::ate);  // binary only so we can get valid file-offsets out of tellg()
      inputFileSizeBytes = inputFile.tellg();  // get file size
      inputFile.seekg(0, std::ios_base::beg);  // then go back to the beginning of the file so we can read it

      std::ofstream indexFile;
      indexFile.open(indexFileName, std::ios_base::binary);

      std::string nextLine;
      while(inputFile.good())
      {
         const std::streampos curFileOffset = inputFile.tellg();  // do this before reading the line:  record our current read-offset into the file
         std::getline(inputFile, nextLine);
         WriteEntryToIndexFile(indexFile, {std::hash<std::string>()(nextLine), (std::size_t)curFileOffset}, indexSizeItems);
      }

      // Add a final dummy-entry to the end of the index, just to force the flushing of any
      // final text-line(s) in our for-loop in step (3)
      WriteEntryToIndexFile(indexFile, INVALID_INDEX_ENTRY, indexSizeItems);
   }

   std::cout << "Step 2:  mmap() index file [" << indexFileName << "] into RAM and sort its entries by hash-code" << std::endl;

   // Step 2.  mmap() the index-file we just generated, and sort its contents by hash-code (sub-sort by byte-offset)
   const int indexFD = open(indexFileName, O_RDWR, (mode_t)0666);
   if (indexFD < 0) {std::cerr << "Couldn't open() index file!" << std::endl; exit(10);}

   char * indexFileMap = (char *) mmap(0, indexSizeItems*(2*sizeof(size_t)), PROT_READ | PROT_WRITE, MAP_SHARED, indexFD, 0);
   if (indexFileMap == MAP_FAILED) {std::cerr << "mmap() of index file failed!" << std::endl; exit(10);}

   SizeTPair * index = reinterpret_cast<SizeTPair *>(indexFileMap);
   std::span<SizeTPair> indexSpan(index, index+indexSizeItems);
   std::sort(std::begin(indexSpan), std::end(indexSpan));

   std::cout << "Step 3:  Iterate through index file [" << indexFileName << "] and invalidate any duplicate entries" << std::endl;

   // Step 3.  Go through the index file and invalidate any duplicate
   // entries (i.e. any entries that have the same hash code and same
   // underlying string as a previous entry)
   const int inputFD = open(bigInputFileName, O_RDONLY, (mode_t)0666);
   if (inputFD < 0) {std::cerr << "Couldn't open() input file!" << std::endl; exit(10);}

   const char * inputFileMap = (const char *) mmap(0, inputFileSizeBytes, PROT_READ, MAP_SHARED, inputFD, 0);
   if (indexFileMap == MAP_FAILED) {std::cerr << "mmap() of index file failed!" << std::endl; exit(10);}

   size_t dupesRemoved = 0;
   ssize_t runStartIdx = -1;
   for (size_t i=0; i<indexSizeItems; i++)
   {
      SizeTPair & curEntry = index[i];

      // swap to put the line number in [0] and the hash in [1], since in the future
      // we will want to sort by line number and this will make it easier to do that.
      std::swap(curEntry[0], curEntry[1]);

      const size_t curByteOffset = curEntry[0];
      const size_t curHash       = curEntry[1];

      if (runStartIdx >= 0)
      {
         if (curHash != index[runStartIdx][1])
         {
            // A run of identical hashes started at (runStartIdx) and ended just before (i)
            if ((i-runStartIdx)>1)
            {
               // Re-sort the index-entries-with-identical-hashes by the strings they represent
               // so that we can find and remove any duplicate-strings easily.  (We have to do this
               // because the same hash could, at least in principle, be associted with two different strings)
               std::span<SizeTPair> duplicateHashesSpan(index+runStartIdx, index+i);
               std::sort(std::begin(duplicateHashesSpan), std::end(duplicateHashesSpan), SortIndicesByStringCompareFunctor(inputFileMap));
               std::string_view previousEntryTextLine;
               for (size_t j=runStartIdx; j<i; j++)
               {
                  const std::string_view curEntryTextLine = GetStringAtOffset(inputFileMap, index[j][0]);
                  if (curEntryTextLine == previousEntryTextLine)
                  {
                     index[j] = INVALID_INDEX_ENTRY;
                     dupesRemoved++;
                  }
                  previousEntryTextLine = curEntryTextLine;
               }
            }
            runStartIdx = i;
         }
      }
      else runStartIdx = i;
   }

   std::cout << "Step 4:  Re-sort the index file [" << indexFileName << "] by byte-offset in preparation for generating output" << std::endl;

   // Step 4.  Re-sort the index file by byte-offset (note that each line's byte-offset is stored
   //          as the first entry in its SizeTPair now!)
   std::sort(std::begin(indexSpan), std::end(indexSpan));

   std::cout << "Step 5:  Write output file [" << bigOutputFileName << "]" << std::endl;

   // Step 5.  Read through the big text file one more time, and
   // write out only those lines that still exist in the index file
   std::ofstream outputFile;
   outputFile.open(bigOutputFileName);
   for (size_t i=0; i<indexSizeItems; i++)
   {
      const SizeTPair & curEntry = index[i];
      if (curEntry == INVALID_INDEX_ENTRY) break;  // these will all have been sorted to the end so we can stop now
                                      else outputFile << GetStringAtOffset(inputFileMap, curEntry[0]) << std::endl;
   }
   outputFile.close();

   // Step 6.  Clean up our mess and exit
   std::cout << "Step 6:  Delete index file and exit" << std::endl;
   close(inputFD);
   close(indexFD);
   remove(indexFileName);

   std::cout << "Final result:  Out of " << (indexSizeItems-1) << " lines read, " << dupesRemoved << " duplicate lines detected and removed. " << std::endl;
   return 0;
}

Answer 2

You can quickly find duplicate lines using the hash of each line as shown in other answers. But if you only store the hashes then that assumes there is no hash collision. If you use std::hash that won't be true. You can probably get away with it if you use a good cryptographic hash.

With your input being only 10G I would suggest a different approach. Well, apart from the trivial. 10G is something you can probably just load into memory and store each line as string on modern systems.

But lets save some memory:

• First you should mmap the file so all its data is accessible from C++ without it being loaded into memory all at the same time.
• create a std::unordered_multimap<std::size_t, std::string_view> lines; to keep track of lines already seen in the input
• loop over the input file and create a string_view for every line of text, compute the hash and look if up in lines. If the hash exists compare the line against the other lines with the same hash. If the line is unique then add it to lines and output it.

This will use 32 bytes of memory per (unique) line I think. So with short lines the memory required might be more than the input file. On the other hand with short lines there are probably a lot less unique lines.

PS: You can save memory by only storing the beginning of each line. And if you estimate the number of (unique) lines you can use a hashtable with a different collision strategy (without bins) to bring it down to 8 byte per line.

Answer 3

This code is reading the input file line by line, storing only hashes of the strings in memory. If the line was not seen before, it writes the result into the output file. If the line was seen before, it does not do anything.

It uses sparsepp to reduce the memory footprint.

Input data:

• 12 GB file size
• ~197.000.000 different lines
• line length < 120 characters

Build:

• C++20
• release build
• do not run within Visual Studio (no debugger attached)

Processing:

• AMD Ryzen 2700X
• 32 GB of RAM
• Seagate SSD
• 190 seconds
• 954 MB virtual memory peak

Is that good enough? I can't tell, because your performance requirements are quite vague and you didn't give proper performance comparison data. It may depend on your machine, your data, your RAM size, your hard disk speed, ...

#include <chrono>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <random>
#include <string>
#include "spp.h"
int main()
{
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    std::ifstream input;
    std::ofstream output;
    input.open("10gb.txt");
    output.open("10gb_nodupes.txt");
    std::string inputline;
    spp::sparse_hash_map<size_t, size_t> hashes;
    while (std::getline(input, inputline))
    {
        std::size_t hash = std::hash<std::string>{}(inputline);
        if (!hashes.contains(hash))
        {
            output << inputline << '\n';
            hashes[hash]=0;
        }
    }
    input.close();
    output.close();
    std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::seconds>(end - begin).count() << "[s]" << std::endl;
    std::cout << "Done";
}

Answer 4

Sure, you can do this in O(n^2) time using only the amount of memory required to hold two lines, a boolean flag, and two file offsets.

The basic algorithm would be:

• Open input file
• Open output file
• Set flag to false
• Set pre-read offset to 0
• While more input:
  • Read a first input line
  • Save current input file offset as post-read offset
  • Seek input file to offset 0
  • While current input file offset is less than pre-read offset:
    • Read a second input line
    • If first input line equals second input line:
      • Set flag to true
      • Break
  • If flag is false:
    • Write first input line to output file
  • Set flag to false
  • Seek input file to post-read offset
  • Set pre-read offset to post-read offset

This is, of course, extremely time-inefficient, but it's about as memory-efficient as you can get.

Possible C++ implementation:

std::ifstream input(inputFilePath);
std::ofstream output(outputFilePath);

std::streamoff offset_before = 0;
std::streamoff offset_after = 0;
bool found_dupe = false;

std::string line1;
while (std::getline(input, line1)) {
    offset_after = input.tellg();

    input.seekg(0);
    std::string line2;
    while (input.tellg() < offset_before && std::getline(input, line2)) {
        if (line1 == line2) {
            found_dupe = true;
            break;
        }
    }

    if (!found_dupe) {
        output << line1 << '\n';
    }

    found_dupe = false;
    input.seekg(offset_after);
    offset_before = offset_after;
}

Live Demo