4
\$\begingroup\$

So I had a similar problem to this:

https://stackoverflow.com/questions/39749430/import-huge-dataset-into-access-from-excel-via-vba/57995602#57995602

Although it was already answered, I provided a different solution on that thread if anyone else came looking for something similar.

If you don't feel like reading through it, the long and short is I have a large data set (850k records) in an Access table that needs to be updated. In my company, we receive new data from a partner in a .xlsx file and need to update said Access database from this file. The unfortunate part is the file sent to us is the entire 850k set with additions and updates (NO DELETIONS). Import tools and macros in Access and Excel take on the order of 10-15 minutes for the entire comparison and import. My solution was to save previously received .xlsx files as .txt files and then compare them to new files using the std::unordered_map from the C++ STL to produce delta files. Then query the delta files for update and upload instead of using the entire data set. In short, compare last week's .xlsx file to this week's .xlsx file for the delta (about 1k records), then write update and insert queries (queries not written yet) for those 1000 or so updates/inserts instead of comparing all 850k records.

The structure of the files are like this:

Col1\tCol2\tCol3\tCol4\tCol5\tCol6\n                        <-----this is a header
string1\tstring2\tstring3\tstring4\tstring5\tstring6\n
string1\tstring2\tstring3\tstring4\tstring5\tstring6\n
string1\tstring2\tstring3\tstring4\tstring5\tstring6\n
....
//Through 850k rows//

It's important to note that Col1 in each row is a unique identifier. It's a string of numbers followed by a terminating "A" character. For example 0000001A.

1. First Attempt

My first attempt at this used the I/O stream, a single std::unordered_map with string data only, and the first '\t' character and '\n' character as delimiters as can be seen in the thread I linked above. Comparing the input files and writing the outputs took about 5 seconds.

2. Second Attempt

I made my second attempt after seeing a YouTube lecture on Robin Hood hashing, so I researched it a little and stumbled on this.

https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/

I'm not even going to attempt to create a faster hash table. This hashtable is implemented the same as the std::unordered_map, so I downloaded it and imported it to see how much faster it was. You can see this in my code below as #include "RobinHood.h" (I renamed the file so I would recognize it but to be 100% clear, I take NO CREDIT for any of that hash). Then its implementation (with integer instead of string):

ska::flat_hash_map<int, std::string> hashMap1;
ska::flat_hash_map<int, std::string>::iterator it;

This cut the comparison time in half. Down to 2.4 seconds.

3. Third Attempt

In my third attempt, I decided I would try to exploit the numbers in Col1 as a key because integer searching of a hash table is much faster than string searching. I tried a couple of string conversions using the std library but, it seemed that the most efficient conversion for this application was the atoi() function from <cstdlib>. In my code below, you'll see it in the CreateFileHash() function: int t_key{atoi(key.c_str())};

This cut my time further down to 1.75 seconds.

4. Fourth Attempt

Now I decided I could probably speed this up, just a bit more. I thought, what would happen if I used a second data structure to store the second file and read the two files into memory in parallel, then compared the data structures instead of comparing the hash table with the I/O stream on the fly? How much time could I save?

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <iterator>
#include <cstdlib>
//#include <unordered_map> -removed, used the ska::flat_hash_map
#include "RobinHood.h"  //I renamed the ska robin hood hashing library to "RobinHood.h" so I would remember what it was.
#include <thread>

void OpenFiles(std::ifstream& f_in1, std::ifstream& f_in2, std::ofstream& f_out1, std::ofstream& f_out2, std::ofstream& f_out3);
void Get_Line_Data(std::ifstream& f_in, std::string& key, std::string& s_data);
void CreateFileVector(std::ifstream& f_in, std::vector<std::pair<int, std::string>> &f_vec, std::string& key, std::string& s_data);
void CreateFileHash(std::ifstream& f_in, ska::flat_hash_map<int, std::string> &hashMap1, ska::flat_hash_map<int, std::string>::iterator &it, std::string &key, std::string& s_data);
void printFileDivider(std::ofstream& fout, const int width);


int main(int argc, char* argv[])
{
    const int width{81};
    int newRecordIndex{1};
    int changedRecordIndex{1};
    std::string key1; 
    std::string key2;
    std::string wholeLine1; 
    std::string wholeLine2;

    std::vector<std::pair<int, std::string>> vec;


    //robin hood hash map. interfaces just like std::unordered_map
    ska::flat_hash_map<int, std::string> hashMap1;
    ska::flat_hash_map<int, std::string>::iterator it;


    std::ifstream fin1;          //in files
    std::ifstream fin2;

    std::ofstream fout1;         //out files
    std::ofstream fout2;
    std::ofstream fout3;

    OpenFiles(fin1, fin2, fout1, fout2, fout3);

    //skip the header
    fin1.ignore(80, '\n');
    //
    std::thread t1(CreateFileHash, std::ref(fin1), std::ref(hashMap1), std::ref(it), std::ref(key1), std::ref(wholeLine1));

    //skip the header
    fin2.ignore(80, '\n');
    std::thread t2(CreateFileVector, std::ref(fin2), std::ref(vec), std::ref(key2), std::ref(wholeLine2));

    //closing threads and files
    t2.join();
    fin2.close();
    t1.join();
    fin1.close();

    //put the header in the output files
    fout2 << "COL1\t" <<    "COL2\t"    << "COL3\t" << "COL4\t" << "COL5\t" << "COL6\n";
    fout3 << "COL1\t" <<    "COL2\t"    << "COL3\t" << "COL4\t" << "COL5\t" << "COL6\n";

    //loop to compare the data structures
    for(auto v_it = vec.begin(); v_it != vec.end(); ++v_it)
    {
        //look up the key1 data from the vector in the key2 data from hash map
        it = hashMap1.find(v_it->first);

        if(it != hashMap1.end()) //if the key is found compare the data
        {
            if(it->second != v_it->second)
            {
                //print the result to the changed record file. Don't forget to put the 'A' back in the string
                printFileDivider(fout1, width);
                fout1 << changedRecordIndex << ". CHANGED RECORD\n";
                fout1 << "Old Record" << "\t" << it->first << "A" << it->second << "\n";
                fout1 << "New Record" << "\t" << v_it->first << "A" << v_it->second << "\n";
                printFileDivider(fout1, width);
                fout1 << "\n";

                //print the new record to the update file. Don't forget to put the 'A' back in the string
                fout2 << v_it->first << "A" << v_it->second << "\n";
                ++changedRecordIndex;
            }
        }
        else //if the key is not found - print the new record to the upload file
        {
            fout3 << v_it->first << "A" << v_it->second << "\n";
            ++newRecordIndex;
        }
    }

    fout1.close();
    fout2.close();
    fout3.close();
    return 0;
}

void OpenFiles(std::ifstream& f_in1, std::ifstream& f_in2, std::ofstream& f_out1, std::ofstream& f_out2, std::ofstream& f_out3)
{
    f_in1.open("OldFile.txt");          //the old input file
    f_in2.open("NewFile.txt");          //the new input file
    f_out1.open("Changed Records.txt");
    f_out2.open("Update.txt");
    f_out3.open("Upload.txt");
}

void Get_Line_Data(std::ifstream& f_in, std::string& key, std::string& s_data)
{
    getline(f_in, key, 'A');                              
    getline(f_in, s_data, '\n');                             
}


void CreateFileVector(std::ifstream& f_in, std::vector<std::pair<int, std::string>> &f_vec, std::string& key, std::string& s_data) //
{
    while(f_in)
    {
        if(f_in.eof())  
            break;
        Get_Line_Data(f_in, key, s_data);                    
        int t_key{atoi(key.c_str())};                        
        f_vec.push_back(make_pair(t_key, s_data));
    }

}

//Creates the hash table to store information from the old data file
void CreateFileHash(std::ifstream& f_in, ska::flat_hash_map<int, std::string> &hashMap1, ska::flat_hash_map<int, std::string>::iterator &it, std::string &key, std::string& s_data)
{
    while(f_in)
    {
        if(f_in.eof())  //check for end of file if so break loop
            break;
        Get_Line_Data(f_in, key, s_data);                     //get the data
        int t_key{atoi(key.c_str())};                         //convert the key string to an int -- this is for faster hashing
        hashMap1[t_key] = s_data;                                //add these to the hash table
    }
}

Down to 1.4 seconds.

10-15 minutes - 1.4 seconds. This does not yet include the update and insert queries but we hope that inserting and updating 1k records will be much faster than an entire set of 850k records. I'm still learning. Want to learn more. Harsh criticism welcomed. Tell me what's wrong or what I could do better and please don't be nice about it. Should I use an array of structs instead of a vector as the second data structure? Is there a better more efficient way to do this? I want to make this more readable, more efficient and I want to get better at this. If that code doesn't compile, let me know. It's copied over from a different machine and SHOULD work. Thanks!

\$\endgroup\$
  • 2
    \$\begingroup\$ If I understand correctly. 10-15 mins is the time of some general tools to proceed with the entire import? I mean, including the database operations, right? And your algorithm is 1.4s but the database part is not yet implemented, right? Then I'd suggest to move on to the database part and see if you're not optimizing something that is a ridiculously small part of the entire job. \$\endgroup\$ – slepic Nov 12 at 16:11
  • \$\begingroup\$ Yes that’s our next step! I will clarify above a little better about the numbers. At the moment we’re updating 800+K records using an 800+K row file. The optimization will come in by having to call queries to about 1000 specific records to change or insert rather than the entire set. I think the speed is largely an MS Access/Excel problem. Thanks! \$\endgroup\$ – Dan Nov 12 at 16:17
  • 1
    \$\begingroup\$ Don't take me wrong. Your code definitely deserves a review and has space for improvement in many aspects. Although I'm not the right person to give a review on a code of this size, as C++ I only do as hobby. But at this point performance should be the least of your concerns as it seems you've already done good enough job. Implement the database part and see how it does. Then come back to this if it seems that speeding up this part can have significant impact on the entire work. \$\endgroup\$ – slepic Nov 12 at 16:29
  • \$\begingroup\$ Maybe I should say it the same way you have. We are currently using Excel and Access tools to import the entire data set (10-15 min). I’ve made it a ridiculously small job in comparison with this code to query to import/update 1000 samples rather than 850k. This should only take seconds, I would think but I will be sure to update the question when we do it. \$\endgroup\$ – Dan Nov 12 at 16:32
  • 1
    \$\begingroup\$ Don't do it. It would be against rules of this site. You should not edit question after you receive at least one review. And I'm sure you will get some :) Post a new review for the database part when you have it. \$\endgroup\$ – slepic Nov 12 at 16:35
2
\$\begingroup\$

C++ related

  • Streams close when they go out of scope. No need to call .close() at the end of the function.
  • File names can be provided when you create the streams. No need to pass 5 streams to a function (and risk mixing them up) for that.
  • You're passing way to many parameters into the functions that read from the file. Why not declare most of them in the body of the function? What is the hashtable iterator doing there as a parameter?
  • The result of getline is not checked after the call.

Performance related

As always, profiling helps identify bottlenecks.

Allocating all those strings can get costly. Reading the whole file in memory and using std::string_view might avoid that.

If the key is an int, how big is it? Perhaps a big enough vector is enough instead of the hash table.

\$\endgroup\$
  • \$\begingroup\$ Awesome! Thanks! \$\endgroup\$ – Dan Nov 12 at 21:47
  • 1
    \$\begingroup\$ I did try to use string_view initially and couldn’t figure a way to do it without allocating a string. I actually did have a function to read the whole file at once and it took 4 times as long to do, unless I was doing that wrong. I have since deleted that. I’ll see if I can duplicate that and re-sub in a new thread. \$\endgroup\$ – Dan Nov 12 at 21:51
  • \$\begingroup\$ I was unsure about the iterator. I only included it because I was initially using it in the function but then forgot to remove it. Thanks for pointing that out. I've included other things that I needed but by ref because I needed them (or thought I needed them) in the function and in the main. Ill see what I can do to clean it up a little. So maybe return the vector and hash table instead of creating them and passing by ref? Also, I used the hash table because of the comparison. I figured it would be faster to only have to go through one of the structures one by one and use col1 as a key. \$\endgroup\$ – Dan Nov 13 at 12:35
  • \$\begingroup\$ So I have tried the suggestions. Loaded both entire files to strings and used string_view to compare them. Searching the first column value through the second string exponentially increases the search time such that the hash function becomes more efficient, with about 3-4 new record entries. I have yet to use the strings in place of only the vector. \$\endgroup\$ – Dan Nov 20 at 14:33
  • \$\begingroup\$ Just replaced the vector with a string, using the string_view to navigate. Iterating the entire string with string_view and comparing to the hash table takes almost a minute. comparing a vector to the hash is it. Will work on queries, make them stored procedures and post new with a reference to this thread when I'm done. \$\endgroup\$ – Dan Nov 20 at 18:22

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.