Speeding up string splitting in Rcpp/Cpp

Question

I'm looking to speed up an Rcpp function I have written.

The function takes in a string called vcfield, which takes the format od x:y:z. This string has 3 fields if you separate it by the :. It takes an int DSfield which tells us the index (0 based) field from vcfield which is the dosage. Dosage is always one double value.

It also takes in 2 ints called aa and bb

The program then returns the value of abs[(aa + bb) - dosage].

So calling ReturnUncertainty("1/1:1.88:0,0.12,0.88", 1, 1, 1) should return 0.12, as abs[(1+1) - 1.88] = 0.12

We should presume that the number of characters in the different fields of vcfield might vary. So it should be also be capable of taking a value like "1/1/1/1:1.88999:0,0.12,0.88".

#include <Rcpp.h>
#include <bits/stdc++.h> 

using namespace Rcpp;
using namespace std;


// [[Rcpp::export]]
double ReturnUncertainty(String vcfield, int DSfield, int aa, int bb) {

    string stdfield = vcfield; 
    vector <string> tokensMain;
    stringstream checkMain(stdfield);
    string intermediate;  

    while (getline(checkMain, intermediate, ':')) { 
        tokensMain.push_back(intermediate); 
    } 

    std::string DS = tokensMain[DSfield];
    double DSf;
    std::istringstream(DS) >> DSf;

    double aaD = static_cast<double>(aa);
    double bbD = static_cast<double>(bb);

    double genoSum = aaD + bbD;
    return abs(genoSum - DSf);
}

QUESTION: As a total newbie to C++, I was wondering whether or not I am doing anything that is very inefficient / unecessary which might be slowing my code down?

Welcome to Code Review! How fast is your code and how fast do you need it to be? — AlexV
– AlexV, Commented Feb 19, 2020 at 14:37
Mm, it's hard to say because it is part of a much larger program. I guess I was more wondering, if I am doing anything very inefficient/unnecessary, which would slow the code down. If I am not, then that's great and I can move on! I will edit the question to be more clear. — user438383
– user438383, Commented Feb 19, 2020 at 14:40

AlexV · Accepted Answer · 2020-02-19 15:31:25Z

Includes and `using namespace std;`

You should not use #include <bits/stdc++.h> in any serious program, since this will pull in all standard library headers.

Together with using namespace std; this brings a high chance of causing headache, because of possible name collisions and ambiguities.

To get the standard library function you use, just include

#include <string>
#include <sstream>
#include <cmath>

and better use the full-qualified name with leading std::.

The algorithm

Since you are only interested in a single position of the three possible tokens, there is no need to have a std::vector to store all of them.

You can also stop parsing the string once you have found the value at the desired position.

In the example below I've removed the Rcpp stuff, but I'm sure you'll be able to adapt it to your needs.

It uses a range-based for loop, mostly stolen from the std::getline documentation with an additional counter variable to be able to abort early.

If the approach using std::stod is not robust enough for all your cases, you could also switch back to your original implementation using std::istringstream.

#include <string>
#include <sstream>
#include <cmath>

#include <iostream>   // only needed for main

double ReturnUncertainty(std::string vcfield, int DSfield, int aa, int bb) 
{
    std::stringstream checkMain(vcfield);

    double dose = 0;
    int i = 0;
    for(std::string intermediate; std::getline(checkMain, intermediate, ':'); ++i) { 
        if(i == DSfield) {
            dose = std::stod(intermediate);
            break;
        }
    }

    return std::fabs(aa + bb - dose);
}

int main() {
    std::cout << ReturnUncertainty("1/1:1.88:0,0.12,0.88", 1, 1, 1) << std::endl;
}

I have not measured the performance against your code, but I'm fairly confident that it would be faster.

Incomputable · Accepted Answer · 2020-02-19 18:29:19Z

Remove unnecessary steps

for (int i = 0; i < field_number - 1; ++i) 
{ /*read discard*/ }
double value;
// read the needed value now

This will make sure that it will not do unnecessary steps if the value needed is the very first one.

Do not copy around

I believe Rcpp would provide some way to access underlying char*. That can be used to construct std::string_view, or use the char* directly.

Use better standard library functions

My first candidate is famous (infamous) function called std::from_chars. It was accepted in C++17, but the support for that is only available with VC++'s standard library (I'm as surprised as you are, the reader, though getting FP parsing right is very hard). Basically it ignores all of the limitations of standard streams, from buffer structures to locales.

The second candidate would be std::strtod, or some such. Notice that std::stod is not a good alternative, because it requires copying parts of the string.

Going beyond standard

One of the good options is fmtlib. It has convenient interface, and is actively developed. Part of it is event coming to standard library, but unfortunately not the one we are interested in.

I'm not sure how faster it will get, but perhaps Boost.Spirit may be a good candidate. It will certainly be strong spirits to your compiler.

Facts

Of course, the benchmarks will tell which way is better. May be everything I've told is heresy.

Alternative implementation

#include <charconv>
#include <string_view>
#include <cmath>

double strparse(std::string_view s, int field, int a, int b) {
    double candidates[3];
    auto format = std::chars_format::fixed;
    auto start_point = s.data();
    auto end_point = s.data() + s.size();
    switch (field) {
    case 0:
        start_point = std::from_chars(start_point, end_point, candidates[0], format);
    case 1:
        start_point = std::from_chars(start_point, end_point, candidates[1], format);
    case 2:
        start_point = std::from_chars(start_point, end_point, candidates[2], format);
    }

    double ad = a;
    double bd = b;
    return std::abs(ad + bd - candidates[field]);
}

Well, here you have it. No copying around, manual loop unroll to prevent unnecessary steps, exact flags to maximize performance in standard library calls.

Godbolt link.

Unfortunately I do not have convenient access to a windows machine to test the implementation.

thanks - i couldn't get it to compile with c++17 - it throws: functions.cpp:134:24: error: ‘std::chars_format’ has not been declared although could possibly be an rcpp thing - do you know what's up? — user438383
– user438383, Commented Feb 28, 2020 at 14:57
@sahwahn, please reread my answer. It is written there. Also, it seems like I forgot to update the code in the answer, but the code in the godbolt link should be correct. — Incomputable
– Incomputable, Commented Feb 28, 2020 at 17:38
Oh I see - I should have been clearer that I need it to compile under gcc, not msvc. thanks. — user438383
– user438383, Commented Feb 28, 2020 at 17:43
@sahwahn, that section was FYI. I’m pretty sure the support will come eventually. You might want to keep an eye out if performance is critical. — Incomputable
– Incomputable, Commented Feb 28, 2020 at 17:47

Stack Exchange Network

Speeding up string splitting in Rcpp/Cpp

2 Answers 2

Includes and `using namespace std;`

The algorithm

Remove unnecessary steps

Do not copy around

Use better standard library functions

Going beyond standard

Facts

Alternative implementation

You must log in to answer this question.

Hot Network Questions

Speeding up string splitting in Rcpp/Cpp

2 Answers 2

Includes and using namespace std;

The algorithm

Remove unnecessary steps

Do not copy around

Use better standard library functions

Going beyond standard

Facts

Alternative implementation

You must log in to answer this question.

Related

Hot Network Questions

Includes and `using namespace std;`