0

I've written a procedure in both C++ and PHP and I don't understand why the C++ version is so much slower than the PHP one.

I have a set of elements in which every element hold a certain amount of ids. The objective is to find a (maybe all) the combinations that cover all the ids.

E.G:

A [1, 2]
B [2, 3]
C [3]

Possible combinations: A+B, A+C

This is the C++ code (please don't judge the style, when it's consolidated i'll rewrite it better):

#include <map>
#include <vector>
#include <iostream>
#include <cassert>
#include <chrono>
using namespace std;

class cRace {
public:
    int id;
    vector<int> drivers;
};

map<int, vector<int>> d_r;
vector<cRace> r_d;
int globcount;

map<string, int> solutions;
std::chrono::time_point<std::chrono::high_resolution_clock> start;

int get_by_fewer(vector<cRace> table_by_race, string id, int count, map<int, int> coverage)
{
    auto it = table_by_race.begin();
    
    count++;
    for (int driver : (*it).drivers) {
        globcount++;
        
        string sub_id = id;
        if (sub_id.length())
            sub_id += "|";
        sub_id += to_string(driver);
        
        vector<cRace> copy_table = table_by_race;
        map<int, int> copy_coverage = coverage;
        
        auto driver_data = (*d_r.find(driver)).second;
        for (int race : driver_data) {
            copy_coverage[race] = 0;
        }
        
        if (r_d.size() == copy_coverage.size()) {
            cout << "FOUND SOLUTION: " << sub_id << " (" << count << ")\n";
            auto elapsed = std::chrono::high_resolution_clock::now() - start;
            long long microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
            long milliseconds   = (long) (microseconds/ 1000) % 1000;
            long seconds    = (((long) (microseconds / 1000) - milliseconds)/1000)%60 ;
            cout << "ELAPSED: " << seconds << "." << milliseconds << "\n";
            cout << "COUNT: " << globcount << "\n";
            return 1;
        } else {
            if (count >= 19)
                continue;
            
            while (true) {
                copy_table.erase(copy_table.begin());
                it = copy_table.begin();
                if (it == copy_table.end())
                    break;
                if (copy_coverage.find((*it).id) != copy_coverage.end())
                    continue;
                //cout << "NEXT : " << (*it).id;
                if (get_by_fewer(copy_table, sub_id, count, copy_coverage))
                    return 1;
                break;
            }
        }
    }
    
    return 0;
}

int main(int argc, char **argv)
{
  
    {
        // vectors/maps initialization
    }  
    
    cout << "START!\n";
    start = std::chrono::high_resolution_clock::now();
  get_by_fewer(r_d, "", 0, map<int, int>());
  return 0;
}

this is the PHP version:

// data initialization

global $time_start;
global $solutions;
global $solutions_min;
global $globcount;
$solutions_min = 1000;
$solutions = [];
function get_by_fewer($table_by_race, $ids = [], $count = 0)
{
    global $time_start;
    global $table;
    global $solutions;
    global $solutions_min;
    global $globcount;
    $first_key = array_key_first($table_by_race);
    $first_drivers = $table_by_race[$first_key];

    $count++;
    $skipfirst = 0;
    foreach ($first_drivers as $driver)
    {
        $globcount++;

        $sub_ids = $ids;
        $sub_ids[] = $driver;

        $copy_table = array_diff_key($table_by_race, $table[$driver]);
        if (!count($copy_table))
        {
            if ($solutions_min > $count)
            {
                if ($solutions_min < 1000)
                    echo "FOUND SOMETHING BETTER, RESETTING RESULTS\n\n";
                $solutions = [];
                $solutions_min = $count;
            }

            if ($solutions_min === $count)
            {
                $solution = implode($sub_ids, "|");
                if (!isset($solutions[$solution])) {
                    echo "FOUND SOLUTION: " . $solution . " (" . $count . ")\n";
                    $solutions[$solution] = $count;

                    $time_end = microtime(true);
                    $time = $time_end - $time_start;
                    echo "ELAPSED: " . $time . "\n";
                    echo "COUNT: " . $globcount . "\n";
                    exit;
                }
            }
        }
        if ($count + 1 < 20)
            get_by_fewer($copy_table, $sub_ids, $count);
    }
}

echo "START!\n";
$time_start = microtime(true);
get_by_fewer($reverse_table);
exit;

results:

PHP

START!
FOUND SOLUTION: 66|105|49|127|114|120|118|35|39|116|100|64|106|79|117|98|78|133|93 (19)
ELAPSED: 0.47768187522888
COUNT: 472105

C++

START!
FOUND SOLUTION: 66|105|49|127|114|120|118|35|39|116|100|64|106|79|117|98|78|133|93 (19)
ELAPSED: 29.947
COUNT: 472105
  • 1
    The C++ function takes its arguments *by value*, which means copying values and contents. You also do a lot of other copying of containers inside the function. That would be a pretty big cost there. And do you build and measure an *optimized* build? – Some programmer dude Nov 25 '21 at 11:17
  • 1
    There's also many other differences between the two implementations that make them very hard to compare directly. – Some programmer dude Nov 25 '21 at 11:19
  • No i didn't build the optimized build, i did it now and the results are still too much: ELAPSED: 6.516 better but too much. The copying is done even on the PHP side, so the difference persists – Samuele Diella Nov 25 '21 at 11:22
  • The biggest difference is the use of an additional map to hold the already covered values. I needed to do that since the values in the set are ordered by some criteria, and C++ maps arent holding the insertion position. – Samuele Diella Nov 25 '21 at 11:27
  • 1
    The program has _undefined behavior_ so timing doesn't matter. Compiling with `-g -fsanitize=address,undefined` gives "_runtime error: reference binding to null pointer of type 'struct cRace'_" – Ted Lyngmo Nov 25 '21 at 11:35
  • "_The copying is done even on the PHP side_" - I hope PHP only copies an object if you change the object, otherwise it could just count references. – Ted Lyngmo Nov 25 '21 at 11:38
  • 2
    Regarding the map issue, first of all you should probably use `std::unordered_map` which is a hash-map which makes them closer to the PHP arrays. Secondly, if you want to keep a strict insertion order then perhaps a map is the wrong type, and you should use e.g. `std::deque>` (using `deque` because head/tail insertion/removal are both O(1)). – Some programmer dude Nov 25 '21 at 11:40
  • Removing first element from a `vector` is costly as all successors must be moved. – Krzysiek Karbowiak Nov 25 '21 at 11:40
  • In any case, if you want to compare the execution time, you should also post all the compiler options that you use (optimisations, standard version, etc.). – Krzysiek Karbowiak Nov 25 '21 at 11:42
  • 1
    @TedLyngmo It seems PHP by default does a deep copy on assignment. For references special syntax is needed (see e.g. [this old answer](https://stackoverflow.com/a/2030924/440558)). – Some programmer dude Nov 25 '21 at 11:43
  • @SamueleDiella *I needed to do that since the values in the set are ordered by some criteria, and C++ maps arent holding the insertion position* -- The main issue is that you cannot simply do a line-by-line translation from one language to another and expect similar results, whether in the running time or the final output. C++ is not PHP. You can take any language and make it run slow if you don't utilize the language correctly. There are various simple mistakes you're making, such as passing objects by value. A C++ programmer who knows the language would not make this mistake. – PaulMcKenzie Nov 25 '21 at 11:53
  • @SamueleDiella *This is the C++ code (please don't judge the style, when it's consolidated i'll rewrite it better):* -- That right there *is* the problem, as stated in my previous comment. Until you know how to write optimal C++ code (and learn more basics of the language), you can't run timing tests on the C++ code that's poorly written. – PaulMcKenzie Nov 25 '21 at 11:55
  • 1
    @Someprogrammerdude Interesting - but one of the answers actually mentions that there is a distinction between what actually happens under the hood if you don't change the value. If what's passed _by value_ to the function is not actually changed in the function, it doesn't copy. It just increases the internal refcount. – Ted Lyngmo Nov 25 '21 at 11:59
  • 1
    On a very unrelated (or maybe not?) note, regarding "please don't judge the style, when it's consolidated i'll rewrite it better", you should always strive to write good, readable and maintainable code, even for prototypes. First of all because unfortunately prototypes tend to stick around longer than expected, and secondly because when it's finally being rewritten it's easier to understand what's going on and to refactor it. Unless you target a performance-constrained system, performance shouldn't be a top priority (IMO, and depending on other requirements). – Some programmer dude Nov 25 '21 at 12:00
  • the variables are passed by values because it's a recursive function, and that's the behavior on php side too. The function iterates all the items and build a tree of all the occourences, so the copies are needed to hold the subtree status (exactly as in PHP). BTW, i rewritten it with unordered_map and deque, now it's 3.609. Better again, but not close to the PHP compiling string: g++ find.cpp -g -O3 -o find && chmod +x find && ./find – Samuele Diella Nov 25 '21 at 13:49
  • @SamueleDiella -- The program is broken. You cannot run timing tests on broken programs. I took the C++ code you posted and ran it in Visual Studio. In debug mode, an assertion is triggered on `for (int driver : (*it).drivers)`. The assertion triggered stated "`Expression: can't dereference value-initialized vector iterator`. – PaulMcKenzie Nov 26 '21 at 14:26
  • @SamueleDiella *the variables are passed by values because it's a recursive function,* -- Passing by value has nothing to do with whether a function is recursive or not. For example, tree implementations and traversals written in C++ are almost always recursive, yet you don't see values of entire trees or subtrees being passed. Again, your C++ code is basically trying to copy line-by-line what PHP is doing, and so far, that approach is failing (as I would have expected). – PaulMcKenzie Nov 26 '21 at 14:28

0 Answers0