Any ideas to speed up ?

[Junhui Liao]

Dear all,

Recently, I was involved to deal with this job, re-organize the tsv data.
Original data is like this:
First line: time_1.1 signal_1.1 time_2.1 signal_2.1 ...
time_4096.1 signal_4096.1 (total 4096 pairs).
Second line: time_1.2 signal_1.2 time_2.2 signal_2.2 ...
time_4096.2 signal_4096.2(total 4096 pairs).
.......
last line(totally 2048 lines): time_1.2048 signal_1.2048 time_2.2048
signal_2.2048 ... time_4096.2048 signal_4096.2048 (total 4096 pairs).

What shall I do is,

Step 0, all of the time_n.* should subtract to the time_n.1. That is to
say,
time_1.1, time_1.2, ... time_1.2048 should subtract time_1.1.
time_2.1, time_2.2, ... time_2.2048 should subtract time_2.1.
....
time_4096.1, time_4096.2, ... time_4096.2048 should subtract
time_4096.1.

Step 1, make all of the time_k.* and signal_k.* in each line collected
together and save in files, let's say, file_k.tsv .
Namely, all of the time_1.1 , signal_1.1, time_1.2, signal_1.2 ......
time_1.2048, signal_1.2048 should save in file_1.tsv. And the first line
is time_1.1 signal_1.1; the second line is time_1.2, signal_1.2 ......
the last line is time_1.2048, signal_1.2048.

All of the time_2.1 , signal_2.1, time_2.2, signal_2.2 ......
time_2.2048, signal_1.2048 should save in file_2.tsv. And the first line
is time_2.1 signal_2.1; the second line is time_2.2, signal_2.2 ......
the last line is time_2.2048, signal_2.2048.
......
All of the time_4096.1 , signal_4096.1, time_4096.2, signal_4096.2
...... time_4096.2048, signal_4096.2048 should save in file_4096.tsv.
And the first line is time_4096.1 signal_4096.1; the second line is
time_4096.2, signal_4096.2 ...... the last line is time_4096.2048,
signal_4096.2048.

Finally, I developed a script like following, but it took around 3 hours.
My target(wish) is less than 30 minutes :-).
Any body have suggests to make it speed up ?

Many thanks in advance !

Junhui

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <string>#include <cstring>
#include <iomanip>

using namespace std;

int main () 
{   
    //ifstream inFile ("../test_7_10lines.tsv");
    ifstream inFile ("../two_ch.tsv");
   if (!inFile.good() || !inFile.is_open() )
   {
      std::cout << "\nWARNING! Cannot read from file: " <<" ../two_ch.tsv"<< std::endl;
   } 
    string line;    int linenum = 0;
    vector <double> time;
    vector <double> time_pick;
    vector <double> vol;
    vector <double> vol_pick;
    double time_base[4096];
    while (getline (inFile, line))

    {
        linenum++;
        int itemnum = 0;
        istringstream linestream(line);
        if(linenum >= 22)
        {
             string item;
             itemnum = 0;
              while (getline (linestream, item, '       '))
              {
                 double time_, vol_, time_origin;
                 itemnum ++;
                 if ( (itemnum % 2) != 0)
                    {
                       istringstream(item) >>time_  ;
                       //cout << "time_ = " <<setprecision(15) << scientific <<time_<<endl;
                       time.push_back(time_) ;
                    }
                 else
                    {
                       istringstream(item) >> vol_  ;
                       //cout << "vol_ = " <<setprecision(5) << scientific <<vol_<<endl;
                       vol.push_back(vol_);
                    }
              }//end of while(getline ()) loop
         }//end of if(linenum >=22)
    }//end of while (inFile, line)

    inFile.close();
        
         for(int i = 0; i<4096; i++)
         {
         time_base[i] = time[i];
         //cout << "time_base = "<<setprecision(15) << scientific<<time_base[i]<<endl;
         }   
             
           //re-organize the vector,make each signal(1024 points) connects to another. 
            int i = 0, j = 4095, k =4096, n = 0, p = 0, q = 0, r = 1024, t = 0;
            for (i = 0; i <= j; i++)//j means the index of file name. This loop to obtain 1024 files.
            {    
               for (int m = 0; m < time.size()/2; m++)//This loop to reorganize channel 1 in vector.
               {    
                  n = m%k; //cout << "n= " <<n<<endl;
                  if (i == n)//k means each 4096 items compose a "group"
                  {    
                    time_pick.push_back(time[m]);
                    vol_pick.push_back(vol[m]);
                    //cout << "time["<<p<<"] ="<<setprecision(15) << scientific<<time_pick[p] << "\tvol["<<p<<"] ="<<setprecision(5) << scientific<<vol_pick[p]<<endl;
                    //p++;
                  }    
               }    

               for (int m = time.size()/2; m < time.size(); m++)//This to reorganize channel 2 in vector.
               {
                  n = m%k; //cout << "n= " <<n<<endl;
                  if (i == n)//this to get all points of all channel 2's signals.
                  {
                    time_pick.push_back(time[m]);
                    vol_pick.push_back(vol[m]);
                  }
               }

            }

            //for(int p = 0; p < time.size(); p++)
            //{
            //  cout << "time["<<p<<"] ="<<setprecision(15) << scientific<<time_pick[p] << "\tvol["<<p<<"] ="<<setprecision(3) << scientific<<vol_pick[p]<<endl;
            //}
            //cout<<"time.size()= "<<time.size()<<endl;

           //Begin to save files
            for (int m = 0; m < time.size(); m++)
            {
               q = m/(2*r) ; //r == 1024;
               if ((m >= q*2*r)&&(m < (q+1)*2*r))
               {
                     stringstream sstrm;
                     sstrm <<"vector_ch1ch2_"<< q << ".tsv";
                     ofstream outFile(sstrm.str().c_str(),ios_base::app);
                     outFile << setprecision(15) << scientific << time_pick[m] - time_base[q] <<"       " << setprecision(2) << scientific<<vol_pick[m] << endl;
               }  
               //cout << "q1 = "<<q<<endl;
            }       
    outFile.close();
    return 0;     
}//End of main() 

PS : During the period of debugging, a few guys presented their suggestions and
advices. Thanks a lot for their help again.

[kbw]

I'm not clear on the details of what you're doing, but you can improve your use of vectors.

1. If you know how large the vectors are going to be, you can initialise them to the correct size to begin with.

2. If you don't know, but you have an idea of how large they may become, you can reserve space. The idea is to stop them expanding in your loops.

3. If you know the indexes, and you've already resized the vectors, use the index operator to put values in them rather than push_back.

4. In your loops, use pre-increment rather than post-increment on counters. i.e. use ++m rather than m++.

As a rule, you want to optimize the code that appears in loops. You do a lot of multiplies and divides in your loops.

[midnightcarousel]

Thanks, kbw, this is helpful to me too as I'm just learning about vectors.

I've heard many people mention your number 4 about using ++m vs. m++. However, for me at least, the two programs produce exactly the same assembly code:

main() {
    for (int i=0; i < 10; i++) ;
}

and

main() {
    for(int i=0; i < 10; ++i) ;
}

Perhaps there are situations where the two will produce different assembly, i.e. if the body of the for loop were more complicated? Or perhaps some compilers (mine) make no distinction between the two?

-Ben

[RedX]

For default data types (int, char, ...) it will produce the same code.
For classes one copy is eliminated since pre-increment does not need to store a and return a copy.

[kbw]

The compiler is free to make a number of optimisations. For example, the entire for loop in your example could be ignored as it does nothing. You can't know a priori what optimisations the compiler will apply.

For all types, post-increments must consider the use of a temporary. It's maintenance is more costly than if you avoided it completely with pre-increment. An optimiser may come along later and determine that the temp isn't used, and so use pre-increment instead where it can be sure it's ok to do so, that is with intrinsic types.

This optimistation exists because it's a common mistake, but just because the compiler takes care of it in some case you've examined, doesn't mean it's always applied. It's better to just write the correct code to begin with.

[Galik]

You may gain some performance by moving your istringstream definition outside the loops and just reset its buffer each time:

	istringstream iss; // pre-declare this
	while(getline(linestream, item, '  '))
	{
		double time_, vol_, time_origin;
		itemnum++;
		if((itemnum % 2) != 0)
		{
			iss.str(item); // reset string stream
			iss >> time_; // convert
			time.push_back(time_);
		}
		else
		{
			iss.str(item); // reset string stream
			iss >> vol_; // convert
			vol.push_back(vol_);
		}
	}

[Galik]

In fact in my tests using a stringstream is even faster:

	stringstream ss; // pre-declare this

	while(getline(linestream, item, '  '))
	{
		double time_, vol_, time_origin;
		itemnum++;

		ss << item; // send in string

		if((itemnum % 2) != 0)
		{
			ss >> time_; // retrieve double
			time.push_back(time_);
		}
		else
		{
			ss >> vol_; // retrieve double
			vol.push_back(vol_);
		}
	}

[Junhui Liao]

Thanks a lot for your guys comment.

To kbw, I modified your No:4 comment.
To your comment 1, I did know how big the vector is. But I didn't know
how to define a dynamic allocated object vector with a fixed number of
capacity. That is to say, "vector <double> time;", this kind of definition
did not confirm the capacity of vector. Another kind is array - like, but
I don't know how to use heap memory here.
Yes, I can define an array with heap memory, but in that case, I have
to make an expression like "linenum * 4096 + itemnum" to save ALL
of the elements to the array. Which should took a lots of time consume.
This is the answer to your comment 3 also.

Moreover, I knew the total time of re-organize the original data is around
30 minutes (in my script, corresponding to the part of before //Begin to save files).
But the time spent on saving files took around 2 hours 15 minutes.

Do you have some ideas to speed up this?



To Galik, I tried your two suggestion. It's not so good, since once I run my
script the vol value is all zero. And time value is a few constants, like,
the first 8192 values of time is, let's say, 1.0E-8; the second 8192 is
1.2E-8......

[Galik]

@Junhui Liao Can you post the new code?

[kbw]

You can set a vector size on construction or with the resize() method. You check the vector's size with size().

You can use reserve() to make the vector allocate memory without changing it's size. You can check this size with capacity().

[Junhui Liao]

To Galik,

Followed is the part of saving into vector.

Thanks a lot, anyway.

Cheers,
Junhui

   //At first, dump all of the data into vector.
    while (getline (inFile, line))
    {
        linenum++;
        int itemnum = 0;
        istringstream linestream(line);
        if(linenum >= 22)
        {
             string item;
             itemnum = 0;
             stringstream ss;
              while (getline (linestream, item, '       '))
              {
                 double time_, vol_, time_origin;
                 itemnum ++;
                 ss << item;
                 if ( (itemnum % 2) != 0)
                    {
                       //istringstream(item) >>time_  ;
                        ss >> time_;
                       //cout << "time_ = " <<setprecision(15) << scientific <<time_<<endl;
                       time.push_back(time_) ;
                       //time[linenum*4096 + itenum] = time_;
                    }
                 else
                    {
                       //istringstream(item) >> vol_  ;
                       ss >> vol_ ;
                       //cout << "vol_ = " <<setprecision(5) << scientific <<vol_<<endl;
                       vol.push_back(vol_);
                       //vol[linenum*4096 + itenum] = vol_;
                    }
              }//end of while(getline ()) loop
         }//end of if(linenum >=22)
    }//end of while (inFile, line)
    inFile.close();

[Junhui Liao]

To kbw,

Thanks a lot for your comment.
I will update to see what will happen.

Best,
Junhui

[Galik]

Hi. You have the code right there. One thing I don't understand is this statement:

 while (getline (linestream, item, '       '))

That shouldn't compile because you appear to have a number of spaces in those single quotes which should accept only one space. It is actually a TAB character in there? If so you should really use this: '\t' .

However if there are an unreliable number of space characters between your data then you might want to try this:

while (linestream >> item)

It will read each item ignoring all whitespace characters separating them. It will probably be faster too.

[jmc]

If pre-increment or post-increment would make an insignificant difference regardless of whether most compiler of today optimze this issue or not.
If it is principally only about speed you can improve this script a lot, but its readability might be suffering a bit/a lot:
1. Read the whole file into memory at the start, if possible, if not use as big chunks as you can. You should be able to allocate at least one single chunk and your whole output of that chunk in memory.
2. Classes, objects and vectors sure have a lot of advantages, but they are slow compared to directly accessed types e.g. arrays. They will have at the very most the same speed. (read&write in&from char arrays)
3. You can use a different thread to read/write the files from where you make your changes in memory. That way you are less dependant on your hd speed (write your output into memory first and write your files when your hd is in an idle state).

This should only be used if your main concern is speed, but if that is the case it will a lot faster.

[Junhui Liao]

Hi, Galik,

It compiled well actually.
And that is a TAB there, inside of ' '.
If replace it with a '\t', should be OK.
But I can't see any possibility to make
the script faster.

Anyway, thanks a lot for you comment :-).

Best regards

[Junhui Liao]

Hi, guys,

Thanks a lot for your comments and suggestions.
You guys taught me a lot, I appreciate you very much.

While, I switched to ruby to deal with the job already
and it took around 2 hours (less than ~3 hours as C++).
And the code just teens lines.

As a guy commented before, C++ is a good language but
maybe is not a best solution to my current case. As a result,
I will try to update my ruby code and see if I can make it
speed up or not.

Anyway, thanks again in my soul and heart !

Best regards,
Junhui