C/C++ hash looking in flat database compared to PHP

Question

I have a hash table which I would like to query as fast as possible. The hash table is stored this way :

When I query a hash, I extract first 4 characters then use it to find the file. For instance a hash starting by e0a458. I extract e0a4 and go to the file ./e/0/a4

On each file I have one line per hash[4].hash[5] couple, so 256 lines each one terminated by new line. I store the position of each of the 256 lines as offset on the first line.

1. 8bytes offset of each line \n
2. Data for 0x00 \n
3. Data for 0x01 \n
4. Etc...

Each word in each line is separated by 0x06 character (totally arbitrary).

Now, when I query a hash I look into the file, fseek the position of offset, read 8 characters, then fseek to that position, get the line, then go through each word, hash it and compare to query. At first I did that in PHP because I prefer it. Below is my code, running on PHP 8.1. Note that it isn't indented because I wrote it on nano on my server and it isn't really user friendly for indenting.

<?php
if(isset($argv[1]))
$hashes= fopen($argv[1],"r");
else
return 0;
while(!feof($hashes))
{
$hash = rtrim(fgets($hashes),"\n");
if($hash !== "")
{
$file= fopen($hash[0].'/'.$hash[1].'/'.$hash[2].$hash[3],'r');
fseek($file,hexdec($hash[4].$hash[5]) * 8);
$offset = fread($file,8);
fseek($file,$offset);
$dataLine = rtrim(fgets($file),"\n");
fclose($file);
$arr = explode("\x06",$dataLine );
foreach($arras as $word)
{
$md5 = md5($word);
if($md5 === $hash)
        break;
}
}
}
fclose($file);
?>

I didn't find any more optimization to do on this code so I decided to move on to "faster" languages and I tried C and C++. The C version seem to run at same speed than PHP (but I don't really know how to code in C), while the C++ runs really slower than PHP. For a file containing 150,000 hashes, the PHP takes between 2 and 3s while the C++ one takes 45s. Here's the C++ version :

#include <iostream>
#include <fstream>
#include <string>
#include <boost/algorithm/string.hpp>
#include "md5.h"

int main(int argc, char *argv[])
{
    if (argc < 2)
    {
        return 1;
    }

    std::ifstream hashes(argv[1]);
    if (!hashes)
    {
        std::cout << "Could not open file: '" << argv[1] << "'\n";
        return 1;
    }
    std::string hash;
    std::string filePath = "./";
    while(getline(hashes,hash)){
        filePath += hash[0];
        filePath += "/";
        filePath += hash[1];
        filePath += "/";
        filePath += hash[2];
        filePath += hash[3];
        std::ifstream dataFile(filePath);
        if(!dataFile){
            std::cout << "Could not open data file\n";
            return 1;
        }
        std::string firstOffset;
        firstOffset += hash[4];
        firstOffset += hash[5];
        unsigned int x = std::stoul(firstOffset, nullptr, 16);
        dataFile.seekg(x*8,std::ios_base::beg);
        std::string offsetLine;
        offsetLine.resize(8, ' ');
        char* begin = &*offsetLine.begin();
        dataFile.read(begin,8);
        dataFile.seekg(std::stoul(offsetLine,nullptr,10),std::ios_base::beg);
        std::string dataLine;
        getline(dataFile,dataLine);
        std::vector<std::string> result;
        boost::split(result, dataLine, boost::is_any_of("\x06"));
        int limit = result.size();
        for (int i = 0; i < limit; i++){
        if(md5(result[i]) == hash)
        {
            dataFile.close();
            break;
        }
        }
        filePath = "./";
    }
    return 0;
}

Now I had to learn C and C++ while writing this code so I guess it's not optimized since I cannot think of PHP as faster than C++.

Also for the sake of it, here's the C code :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/md5.h>

#define MAXLENGTH 500000

int main (int argc, char *argv[])
{
    if(argc > 1){
        FILE* hashes;
        hashes = fopen(argv[1], "r");
        char hash[257];
        char filePath[7];
        char* sep = "/";
        char totalFilePath[16];
        while(fgets(hash,257,hashes) != NULL)
        {
            filePath[0] = hash[0];
            filePath[1] = sep[0];
            filePath[2] = hash[1];
            filePath[3] = sep[0];
            filePath[4] = hash[2];
            filePath[5] = hash[3];
            char offsetHexa[3];
            offsetHexa[0] = hash[4];
            offsetHexa[1] = hash[5];
            strcat(strcpy(totalFilePath,"./"),filePath);
            FILE* file;
            file= fopen(totalFilePath,"r");
            if ( file== NULL ) {
                printf( "Cannot open file %s\n", totalFilePath );
                exit( 0 );
            }
            else{
                char offset[9];
                unsigned char decimal = 0;
                decimal = (unsigned char)strtoul(offsetHexa,NULL,16);
                fseek(file,decimal*8,0);
                fgets(offset,9,file);
                char *line= malloc(MAXLENGTH);;
                fseek(file,(int) strtol(offset,(char **)NULL,10),0);
                fgets(line,MAXLENGTH,file);
                char* word;
                while( (word = strsep(&line,"\x06")) != NULL)
                {
                        char md5word[33] = "";
                        int i;
    char unsigned md5[MD5_DIGEST_LENGTH] = {0};

    MD5((const unsigned char *)word, strlen(word), md5);

    for (i=0; i < MD5_DIGEST_LENGTH; i++) {
        sprintf(md5word + 2*i, "%02x", md5[i]);
    }
                        if(strncmp(md5word,hash,32) == 0)
                        {
                                break;
                        }
                }
            }
            fclose(file);
        }
        fclose(hashes);
    }


    return 0;
}

So I know this code will seem nooby to actual C/C++ developpers and it is. I have issues with string concatenation in C.

Would you have advises to improve C/C++ runtime ? I didn't find a way to split the data line without storing it in a vector, which doesn't seem fine to me.

Thank you for your enlightments and sorry for the code, I do that as a hobby.

Answer 1

Overview and General Observations

For a hobby programmer this is pretty good! Some of the common mistakes made are not in this code.

Unfortunately I don't know the latest versions of PHP and really can't comment on it, since I haven't used it in 8 years. I was proficient with PHP 4 and I don't maintain web pages where it would be useful.

Where there are common issues with the C and C++ I will identify them.

Optimization

I will address optimization as I can.

One possible optimization would be to read much more of the input file at one time, such as reading in 4K or 8K blocks of text and then processing the resulting buffer as a string, rather than using fgets() in C and getline() in C++. File I/O is very expensive as far as performance goes. Every time fgets() or getline() is called there is a system call to the system I/O functions. In time sharing systems the program may be put into a wait state (the program is put back into the queue and the CPU processes other tasks) while these functions are called.

Indentation

Professional programmers indent because it really helps to read and maintain the code.

The PHP version and the C version contain issues with the indentation. Indentation should be consistent, it isn't in the C code:

                while( (word = strsep(&line,"\x06")) != NULL)
                {
                        char md5word[33] = "";
                        int i;
    char unsigned md5[MD5_DIGEST_LENGTH] = {0};

    MD5((const unsigned char *)word, strlen(word), md5);

    for (i=0; i < MD5_DIGEST_LENGTH; i++) {
        sprintf(md5word + 2*i, "%02x", md5[i]);
    }
                        if(strncmp(md5word,hash,32) == 0)
                        {
                                break;
                        }
                }

Vertical and Horizontal Spacing

The code is more difficult to read than it could be because it is missing vertical spacing. This is true in both the C++ version and the C version of the code. Vertical spacing can be used to separate logical blocks of code.

One importance of indentation is if the code is indented too far, that may indicate a good place to create a function to reduce the complexity of the code.

For horizontal spacing, operators should be separated by operands by spaces. In function calls the comma , which is an operator should be followed by a space.

    while(getline(hashes, hash)){
    
    ...

        dataFile.seekg(x * 8, std::ios_base::beg);

In the above code why is x being multiplied by 8?

Magic Numbers

There are Magic Numbers in the main() function (0, 1, 2, 3 and 8), it might be better to create symbolic constants for them to make the code more readable and easier to maintain. These numbers may be used in many places and being able to change them by editing only one line makes maintenance easier.

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them. There is a discussion of this on stackoverflow.

Error Handling

In both the C and C++ versions error handling can be improved, in the C version error handling is almost non-existent. In the C version the code never checks if the input file was successfully opened. The C program does check argc but doesn't exit. The C++ program needs to report that no input file name was on the command line before quitting.

• Report all errors.

• Both C and C++ have special streams for error output, for C++ use std::cerr rather than std::cout for reporting errors. In the C programming language report errors to stderr.

Exit Status

Both C and C++ provide symbolic constants for the exit status of a program. By including stdlib.h (cstdlib in C++) you get access to the symbolic constants EXIT_SUCCESS and EXIT_FAILURE. These symbolic constants make the code more readable:

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        std::cerr << "Usage: " << argv[0] << " FILE NAME\n";
        return EXIT_FAILURE;
    }

    std::ifstream hashes(argv[1]);
    if (!hashes)
    {
        std::cerr << "Could not open file: " << argv[1] << " for input.\n";
        return EXIT_FAILURE;
    }

    ...

    return EXIT_SUCCESS;
}

Code Complexity

One of the generally accepted best practices is that an entire function should be viewable at one time in an editor or IDE. This makes the code easier to understand for many reasons. In both the C and C++ versions this is almost true, but there really are too many lines of code in each version, especially if vertical spacing is applied.

Another thing to consider is that in formal computer science studies one of the concepts taught at the very beginning is breaking the problem into smaller and smaller pieces until each piece is very simple to solve. In object oriented programming this is called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

Both the C++ and C versions of the program would benefit by being broken up into smaller functions.

As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

#include <boost/algorithm/string.hpp>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include "md5.h"

static std::string buildHashedFilePath(std::string& hash)
{
    std::string filePath("./");

    filePath += hash[0];
    filePath += "/";
    filePath += hash[1];
    filePath += "/";
    filePath += hash[2];
    filePath += hash[3];

    return filePath;
}

static void processMyData(std::ifstream& dataFile, std::string& hash)
{
    std::string firstOffset;
    firstOffset += hash[4];
    firstOffset += hash[5];

    unsigned int x = std::stoul(firstOffset, nullptr, 16);

    dataFile.seekg(x * 8, std::ios_base::beg);
    std::string offsetLine;
    offsetLine.resize(8, ' ');
    char* begin = &*offsetLine.begin();
    dataFile.read(begin, 8);
    dataFile.seekg(std::stoul(offsetLine, nullptr, 10), std::ios_base::beg);

    std::string dataLine;
    getline(dataFile, dataLine);

    std::vector<std::string> result;
    boost::split(result, dataLine, boost::is_any_of("\x06"));
    int limit = result.size();
    for (int i = 0; i < limit; i++) {
        if (md5(result[i]) == hash)
        {
            dataFile.close();
            break;
        }
    }
}

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        std::cerr << "Usage: " << argv[0] << "FILENAME \n";
        return EXIT_FAILURE;
    }

    std::ifstream hashes(argv[1]);
    if (!hashes)
    {
        std::cerr << "Could not open file: '" << argv[1] << "'\n";
        return EXIT_FAILURE;
    }

    std::string hash;
    while (getline(hashes, hash)) {
        std::string filePath = buildHashedFilePath(hash);
        std::ifstream dataFile(filePath);
        if (!dataFile) {
            std::cout << "Could not open data file\n";
            return EXIT_FAILURE;
        }
        processMyData(dataFile, hash);
    }

    return EXIT_SUCCESS;
}

C++ Review

Missing Include

The code is missing the include for std::vector. In some versions of C++ the include for std::string might include this, but that is not portable to all compilers. In my version of C++ this doesn't compile.

A generally accepted best practice is to put the includes in alphabetic order.

#include <boost/algorithm/string.hpp>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include "md5.h"

C Review

Use return Rather Than exit(EXITSTATUS) In main()

There is never a reason to call the exit() function in main() the use of the exit function is only necessary in functions other than main. The code gets this correct in the C++ version but wrong in the C version.