# Merge two pulses if they match

The function processFus() takes :

• Two lists of pulses (200 000 in each), as an input
• Two lists of pulse, empty, pulseValid and invalid. The function must fill them at the end of the process.

The function check for each pulse in listPulseA if it matches with one pulse in listPulseB. To check for the match the pulse in listPulseB must first be inside a time window.

I'm looking for advice in style and in performance.

In the (worst) case we can have 200 000 pulse in listPulseB separated by 1 micro sec, so that makes 300 000 000 check (200 000 pulsesA, * 1500 pulseB that are inside the time window -> cf #define THRESHOLD_SEARCH 1.5) and it takes too much time (~800 ms while i'd like to take less than 200 ms).

Pulses in listPulseA and listPulseB are sorted by timeOfArrival.

The test inside the main shows 200 000 matches, and so 200 000 pulses valid and 400 000 invalid. To see no match and no fusion you must set DIFF_MAX_TOA_A_B to 0. in this case you'll have 400 000 pulses valid and 0 invalid

fus.hpp :

#ifndef SRS_FUS_HPP_
#define SRS_FUS_HPP_

#include <list>

#define LSB_TIME_PRECISION 10
#define listPulse_MAXSIZE 400000

struct Pulse //Can't modify this structure
{
unsigned long long timeOfArrival; //Ns
unsigned long frequency;
unsigned long duration;
unsigned long timePrecision;
unsigned int quality;
bool isValid;
bool isRejected;
bool isTruncated;

};

struct ListPulse
{
Pulse listPulse[listPulse_MAXSIZE];
long size = 0;
};

struct InfoPulse
{
Pulse pulse;
unsigned long long timePrecision;
};

class Fus {
public:
Fus(){}
virtual ~Fus(){}

void processFus(std::list<Pulse> &listPulseA, std::list<Pulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid);

private:

void filterListB(std::list<Pulse> &listPulseB, std::list<InfoPulse> &listInfoPulseB);

inline bool checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &seuilMatch, const unsigned long long &sumTOADurationA);

void createPulse(const Pulse &pulseA, const Pulse &pulseB, Pulse &pulseFus);

void fillListOut(const std::list<Pulse> &listPulseA, const std::list<InfoPulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid);
void chooseListToAdd(const Pulse &pulse, ListPulse &pulseValid, ListPulse &pulseInvalid);
void addToList(const Pulse &pulse, ListPulse &listPulse);

};

#endif


fus.cpp :

#include "fus.hpp"
#include <iostream>

#define THRESHOLD_SEARCH 1.5 // ms, can't change it
#define DIFF_MAX_TOA_A_B 200 // ns
#define MS_TO_NS 1000000

//listPulseA and listPulseB are sorted by timeOfArrival before
//We need to check for each pulseA if it match with a pulseB, and if it's the case create a new pulse, insert it inside the listPulseB
//If two pulse match they become invalid and the new one is valid
//at the ned of the process we must fill the two list "pulseValid" and "pulseInvalid"
void Fus::processFus(std::list<Pulse> &listPulseA, std::list<Pulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid)
{
pulseValid.size = 0;
pulseInvalid.size = 0;

std::list<InfoPulse> listInfoPulseB;

filterListB(listPulseB, listInfoPulseB);

std::list<InfoPulse>::iterator indB = listInfoPulseB.begin();
std::list<InfoPulse>::iterator lastIndB = listInfoPulseB.begin();

for(auto &pulseA:listPulseA)
{
if(pulseA.isRejected || pulseA.isTruncated) //Filter
{
pulseA.isValid = 0;
}
else
{
pulseA.isValid = 1;

bool keepGoing = true;
indB = lastIndB; // Get the last indB which was inside the time window, so we don't have to get through the whole list everytime

unsigned long long toaWindowA = 0;
if(pulseA.timeOfArrival > THRESHOLD_SEARCH * MS_TO_NS)
{
toaWindowA = pulseA.timeOfArrival - THRESHOLD_SEARCH * MS_TO_NS;
}
const unsigned long long thresholdMatchA = DIFF_MAX_TOA_A_B + pulseA.timePrecision * LSB_TIME_PRECISION;
const unsigned long long sumTOADurationA = pulseA.timeOfArrival + pulseA.duration;

//Get the first pulse B inside the time window of the pulse A
while(keepGoing && indB != listInfoPulseB.end())
{
InfoPulse &refPulseB = *indB;
if(refPulseB.pulse.isValid && toaWindowA < refPulseB.pulse.timeOfArrival)
{
keepGoing = false;
lastIndB = indB;
}
else
{
++indB;
}
}

keepGoing = true;
// Once we get the first pulseB inside the window
// while we are still inside the window and there is no match, continue
while(keepGoing && indB != listInfoPulseB.end())
{
InfoPulse &refPulseB = *indB;
const unsigned long long thresholdMatch = thresholdMatchA + refPulseB.timePrecision;
const long long isInWindow = thresholdMatch + sumTOADurationA - refPulseB.pulse.timeOfArrival;
if(isInWindow < 0)
{
keepGoing = false;
}
else
{
{
//If match, we create a new pulse, and we insert it in the listB
// the two old pulses are not valid anymore
Pulse pulseFus;
createPulse(pulseA, refPulseB.pulse, pulseFus);
pulseA.isValid = false;
refPulseB.pulse.isValid = false;

InfoPulse infoPulseB = {pulseFus, pulseFus.timeOfArrival + pulseFus.duration, pulseFus.timePrecision * LSB_TIME_PRECISION};
listInfoPulseB.insert(indB, infoPulseB);
keepGoing = false;
}
++indB;
}
}
}

}

fillListOut(listPulseA, listInfoPulseB, pulseValid, pulseInvalid);

}

void Fus::filterListB(std::list<Pulse> &listPulseB, std::list<InfoPulse> &listInfoPulseB)
{
for(auto &pulse:listPulseB)
{
if(pulse.isRejected || pulse.isTruncated) //Filter
{
pulse.isValid = 0;
}
else
{
pulse.isValid = 1;
}
InfoPulse infoPulseB = {pulse, pulse.timeOfArrival + pulse.duration, pulse.timePrecision * LSB_TIME_PRECISION};
listInfoPulseB.push_back(infoPulseB);
}

}

bool Fus::checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &thresholdMatch, const unsigned long long &sumTOADurationA)
{
if(pulseA.timeOfArrival > pulseB.pulse.timeOfArrival)
{
if(tmp < 0 || pulseA.timeOfArrival - pulseB.pulse.timeOfArrival < thresholdMatch)
{
return true;
}
}
else
{
if(pulseB.pulse.timeOfArrival - pulseA.timeOfArrival < thresholdMatch)
{
return true;
}
}
return false;
}

void Fus::createPulse(const Pulse &pulseA, const Pulse &pulseB, Pulse &pulseFus)
{
if(pulseB.quality > 4)
{
pulseFus = pulseB;
pulseFus.isValid = true;
}
else
{
pulseFus = pulseA;
pulseFus.frequency = pulseB.frequency;
pulseFus.isValid = true;
}
}

void Fus::fillListOut(const std::list<Pulse> &listPulseA, const std::list<InfoPulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid)
{
auto indA = listPulseA.cbegin();
auto indB = listPulseB.cbegin();
auto endA = listPulseA.cend();
auto endB = listPulseB.cend();

while(indA != endA || indB != endB)
{
if(indA == endA)
{
++indB;
}
else if(indB == endB)
{
++indA;
}
else
{
if(indA->timeOfArrival < indB->pulse.timeOfArrival)
{
++indA;
}
else
{
++indB;
}
}
}
}

void Fus::chooseListToAdd(const Pulse &pulse, ListPulse &pulseValid, ListPulse &pulseInvalid)
{
if(pulse.isValid)
{
}
else
{
}
}

void Fus::addToList(const Pulse &pulse, ListPulse &listPulse)
{
if(listPulse.size < listPulse_MAXSIZE)
{
listPulse.listPulse[listPulse.size] = pulse;
listPulse.size++;
}
}

int main()
{
Fus fus;
std::list<Pulse> listPulseA;
std::list<Pulse> listPulseB;
static ListPulse pulseValid;
static ListPulse pulseInvalid;

Pulse pulse{0, 10, 100, 0, 10, false, false, false};
for(int i = 0; i < 200000; ++i)
{
pulse.timeOfArrival = i * 1000;
listPulseA.push_back(pulse);
pulse.timeOfArrival = i * 1000 + 1;
pulse.duration = 1;
listPulseB.push_back(pulse);
}

fus.processFus(listPulseA, listPulseB, pulseValid, pulseInvalid);

std::cout << "pulseValid size : "   << pulseValid.size << std::endl;
std::cout << "pulseInvalid size : " << pulseInvalid.size << std::endl;
}


a few quick things that stick out...

void Fus::processFus(std::list<Pulse> &listPulseA, std::list<Pulse> &listPulseB, ListPulse &pulseValid, ListPulse &pulseInvalid) {
I think a lot of those parameters ought to be const. Pass input stuff by const & not just by plain &. Also, it's orthodox C++ style (since Stroustrup's first book in the 80's) to put the & with the type, not the variable name; e.g. const std::string& name.

std::list<InfoPulse>::iterator indB = listInfoPulseB.begin();
std::list<InfoPulse>::iterator lastIndB = listInfoPulseB.begin();


Use auto. It simplifies things and makes it easier to write generic code that is easy to change later.

#define THRESHOLD_SEARCH 1.5 // ms, can't change it
#define DIFF_MAX_TOA_A_B 200 // ns
#define MS_TO_NS 1000000


Do not use #define. These should be normal variables, declared constexpr.

 Fus(){}
virtual ~Fus(){}


Use =default, assuming you need to declare them at all.

Why did you declare the destructor as virtual when you have no virtual functions in the class otherwise? Clearly you won't be using it in a polymorphic manner... and I don't see anything being derived from it anyway.

inline bool checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &seuilMatch, const unsigned long long &sumTOADurationA);
The inline keyword is redundant on functions declared inside the class body. And there is no function body here! What do you think inline will do here?

It appears that class Fus does not have any state at all. That is, no data members. So what is the point of defining the constructor and destructor?

The code is doing a lot of work to pulseFus, which suggests that there should be member functions of that class (Pulse).

These functions operate on a pure "out" parameter, which is bad. Use function return values to return results! A simple example is
void Fus::createPulse(const Pulse &pulseA, const Pulse &pulseB, Pulse &pulseFus)
which ought to be something like

Pulse choose (const Pulse& A, const Pulse& B)
{
Pulse result = B.quality>4 ? B : A;
result.isValid= true;
result.frequency= B.frequency;
return result;
}


But really the constructor of Pulse ought to be setting isValid and take the values to use.

while(indA != endA || indB != endB)
{
if(indA == endA)
{
// take the rest of B only
}
else if(indB == endB)
{
// take the rest of A only
}
else
{
// the normal code to choose from the two lists
}
}
}


This is checking for the end cases at the beginning of every iteration, which is not only inefficient but reverses the order of the code. That is, the normal stuff you want to do in the loop is way at the end, nested inside a conditional statement.

Change the loop condition from either containing something to both containing something, and put the make-up stuff after that loop. So, it looks like this:

while (indA != endA && indB != endB)
{
// normal code to choose from the two lists
}
while (indA != endA)
{
// take the rest of A only
}
while (indB != endB)
{
// take the rest of B only
}


BTW, ind vs end are confusingly similar names.

 pulse.isValid = 0;
...
pulse.isValid = 1;


I think you forgot that this is bool? You use true and false in other places.

Take a look at the whole passage:

if(pulse.isRejected || pulse.isTruncated) //Filter
{
pulse.isValid = 0;
}
else
{
pulse.isValid = 1;
}


You need to realize that boolean expressions, made up of other boolean values and operations such as AND and OR, are no different than any other value-carrying expression. The stuff in an if statement is not a special unique kind of thing, but just an expression like any other. This is convoluted, when you just want the result of the expression as the value in isValid. That is, write: pulse.isValid = !(pulse.isRejected || pulse.isTruncated);
and that's it! No control flow, extra braces, repeating the intent, etc. It's just the expression assigned to the variable.

Take a look at this function:

bool Fus::checkMatch(const Pulse &pulseA, const InfoPulse &pulseB, const unsigned long long &thresholdMatch, const unsigned long long &sumTOADurationA)
{
if(pulseA.timeOfArrival > pulseB.pulse.timeOfArrival)
{
if(tmp < 0 || pulseA.timeOfArrival - pulseB.pulse.timeOfArrival < thresholdMatch)
{
return true;
}
}
else
{
if(pulseB.pulse.timeOfArrival - pulseA.timeOfArrival < thresholdMatch)
{
return true;
}
}
return false;
}


There is a lot of repetition, and seemingly a lot of fluff with actually a simple amount of code.

pulseA.timeOfArrival - pulseB.pulse.timeOfArrival < thresholdMatch looks to be repeated with variations, but the identical structure. That is, it should be a helper function. Even tmp is just the same thing, broken out in an odd way (subtract rather than compare, then use by comparing against 0 rather than just using the boolean result). The inner else is just testing the same thing with the parameters reversed -- this just flips the sign of the result, so that difference could be broken out, and the sign used in the test rather than repeating the same difference again as a relational operator. Something like:

const auto diff = pulseA.timeOfArrival - pulseB.pulse.timeOfArrival;
if (diff > 0) {
} else {
return -diff < thresholdMatch;
}


hmmm... I guess the complicating factor here is the use of unsigned values, so that won't work. Can you change to signed values -- that is, do you really need one more bit of range in the values? With unsigned values, you can still flip the order of the subtraction by negating the result; it just won't work as the test to see if it's negative or not.

# performance

Don't use std::list for collections. Jumping around in memory is slow, due to caching. Modern CPU architectures are such that memory is the major bottleneck. For your output, you seem to be doing nothing but push_back, so you have overhead of dynamic memory allocation for every single item. For the inputs, you are just traversing, not modifying the list, right?

Use std::vector. You can gain more performance by using reserve. Accessing your inputs in a vector means the memory will be contiguous, with each cache line containing several values, and the regular progression will cause the CPU to notice that and pre-fetch the next chunk of memory needed ahead of time -- this is the opposite of what happens with a linked list, where the next address needed cannot be determined in advance and is some different (not yet cached) piece of memory.

• Thank's for the answer. For your first point, I cannot make them const as I need to modify them during the process (changing the value of isValid).
– Saya
Jun 9, 2021 at 14:15
• By the way if you have some advices on a performance point of view that would be perfect !
– Saya
Jun 9, 2021 at 14:35
• Performance: I added to my answer. Jun 9, 2021 at 14:50

# Interface

Is it really necessary to use (sequential) std::list rather than a random-access collection?

This fixed-size structure should simply be replaced with a std::vector:

struct ListPulse
{
Pulse listPulse[listPulse_MAXSIZE];
long size = 0;
};


The InfoPulse type seems to add no value, since we only ever populate with derived data that can easily be recomputed as needed. If it's really needed downstream, then simplify its creation by giving it a constructor:

InfoPulse(Pulse p)
: pulse{std::move(p)},
timePrecision{pulse.timePrecision * LSB_TIME_PRECISION}
{}


Class Fus has no data members, and looks like it should just be a namespace of functions.

# Algorithm

Include <algorithm> and make use of it. For example:

        bool keepGoing = true;
//Get the first pulse B inside the time window of the pulse A
while (keepGoing && indB != listInfoPulseB.end()) {
InfoPulse &refPulseB = *indB;
if (refPulseB.pulse.isValid && toaWindowA < refPulseB.pulse.timeOfArrival) {
keepGoing = false;
lastIndB = indB;
} else {
++indB;
}
}


That looks a lot like std::lower_bound().

We seem to be doing far too much copying between lists. I don't see that we need any intermediate storage - we should be able to filter internally, and populate the output lists without creating any other collections.

I think the complexity of the code can be reduced greatly. As a newcomer to this code, I took a long time to get much idea of what it's trying to do.