how to increase speed in c++

[skulkarni]

Hi,
I want to know if using STL vectors slows the execution of program. I have used a lot of vectors in my code and its taking around 400 seconds which the same code written in Lisp took 10 seconds. Are there any general aspects to be taken care of which can improve the speed.
Thanks.
Srinivas.

[Alexey B]

Using iterators instead of subscripts can increase the speed a great deal.

[stober]

I don't know diddly squat about Lisp so I can't compare it. How does Lisp do it?

A great deal depends on what you are doing with all those vectors. Can you substitute simple arrays of char** instead? such as:

char* vector1[255];
char* vector2[255];

The above may be a good solution to only the simplest cases.

Another possible alternative is to use some kind of linked list class that does not have all the extra baggage of the vector template.

[jfaust]

Srinivas,

By all common sense and by everything I've heard, C++ should be faster than Lisp. There's probably something you are doing incorrectly. If you post an example of how you are using it, or all the code if it's not too long, I'm sure somebody will be willing to give a few pointers, pun not intended.

But actually, if this is slowing the program down, you may need to go to C arrays to get the speed you need. By doing this, you sacrifice maintainability for the purpose of speed. This is an expensive move even if it gets the results you seek, and should only be done after careful consideration.

There are also profilers available that can tell you where the application is spending its time.

What's the application? Are you accessing the data for use in numeric calculations?

Jeff

[Gabriel Fleseriu]

Jeff: If Srinivas' measurements are correct, we're talking about a 40 times faster execution of Lisp on C++. Switching to C is not an option, IMO - he has to check the algorithm he uses in C++ first, and to profile the C++ code to see where the execution time is going.
IMO, switching to C would be a mistake, like that made by many programmers who want to speed up a poorly designed algorithm by switching to assembler.


Aside (or maybe not):
I remember running into a speed problem with std::vector. I had to parse a memory block who's representation was a

std::vector<std::vector<int> >

The problem was that you couldn't tell the size of each inner vector until you had parsed the block (The size could be as less as 3 or as much as 16'000). So I first used push_back() w/o reserving any spce for the vectors, and let them do the job with allocating the memory. That lead into a chaos of memory blocks being copied and re-copied, making the function painfully slow. As I reserved a (over the thumb) value of 10 integers for the inner vector (seemed to be a good mean value), and ran the same test harness, I got a speed-up of more than 100x!! std::vector managing the memory for you is in most cases *a good thing*, but that does not mean that you should turn off your brain, as I did

This article made a few things clear to me. I think it's worth reading.

[jfaust]

Gabriel,

Yes and yes--I was saying basically the same thing and tried to stress the move to C arrays should be a last resort. However, even a 100x increase will still cause this to take 4 seconds. Depending on where this is happening, it's still a long time. As you move away from the generality of STL, you do gain some more options for optimization. The trade-off for this is maintainability. Maintainability is almost always a more important consideration than performance, and this trade-off should not be made lightly.

More information on the application would be helpful in determining a good solution.

Jeff

[AnthonyMai]

When you are talking about whether the result comes out on the screen in 0.01 seconds or 0.1 seconds, performance is not an issue and maintainability is more important.

But when you are talking about something that takes 400 seconds to get the result, maintainability is not an issue. And even performance is not an issue. Because you do not have something that has any usability value at all to maintain or to improve performance. Your first job is create something that can be used at all.

It is possible that by improving your algorithm, you should be able to gain significantly in speed, even if you still use STL. But the problem with STL is there are so much going on underneath within STL, that a seemingly simple code line will easily kill you in performance and you never know why.

Among other things, objects are frequent back and over again and again within STL, most of times it is totally un-necesary object copying. This along could easily kill you in performance if unfortunately the objects you deal with is not trivial to copy.

I encourage people to look into the source code of STL and judge by themselves whether they want to use piece of code like that, or they are allowed to write code in that kind of style, after they have seen the STL source code for themselves. Lack of knowledge of STL internals is the most frequent cause of mis-use of STL by programmers.

[jfaust]

I think we're in agreement when it comes to performance and maintainability, but I'd like to clarify. Maintainability should be the primary focus until there is demonsratable and specific performance problem. Then that problem should be examined and fixed appropriately, and with eyes wide open about what you are giving up in order to improve performance.

Now as for usability, it depends where the time is being used. Some operations are necessarily lengthy. It all depends on the expectations of the user. Simply navigating around an interface should be quick. But if you are setting up a simulation that attempts to reproduce physical phenomena, it could take minutes, hours, or days.

Jeff

[AnthonyMai]

Now as for usability, it depends where the time is being used. Some operations are necessarily lengthy. It all depends on the expectations of the user. Simply navigating around an interface should be quick. But if you are setting up a simulation that attempts to reproduce physical phenomena, it could take minutes, hours, or days.

I believe usability stops and performance issues starts at where human user starts to wait for the machine to produce result. The reason behind it is human time is much much more precious than machine time.

The cut off line is whether the user has to wait or not. This cut off line is true for things as simple as GUI or as complicated as massive scientific calculations.

In the first case if the time it takes the machine to produce a visual output is much longer than the time it takes the user to percept what he saw on the screen and response, you have a usability issue.

In the second case, if the time it takes for a computer to produce result of scientific calculation is longer (one year) than the time for the researcher to analysis the result and write a research paper and send it out for publishing (one month), then there is a big usability issue.

I don't care what you are trying to calculate, if the profession has to spend more time waiting for the machine to produce result, than the time it takes the profession to think about the research and write research papers, then the professor's time would be much better spent on applying for more fund to buy faster super computer, or on trying to develop a better algorithm that reduces calculation time, rather than just sit and wait for the machine.

[jfaust]

The point is that when "talking about something that takes 400 seconds", you need to take into account what that something is.

Jeff

[skulkarni]

thanks to all,
well my question has given rise to nice arguments. I am using the same algorithm and the same logic that has been used in LISP. Theroetically c++ is faster than LISP. I have even tried making changes as suggested by Gabriel, i.e allocating approximate amount of memory in the beginning and thus avoiding push_back() (which i have used at many places) but still the improvement is not significant.now its taking around 350 seconds. well i am attaching one of the major files.

[skulkarni]

well here is the file

[skulkarni]

and another major file

[Paul McKenzie]

As someone else pointed out, what you need to do is to use a code profiler and profile your code. If you don't profile your code, you could be on a wild goose chase, thinking that "this is the part of the code that's slow", and waste time trying to optimize something that doesn't need optimization. A profiler will quicky tell you which functions, lines, etc. that are taking up the most time.

Also, you should attach the entire program source, not just one file, along with an int main() stub that demonstrates the problem.

Regards,

Paul McKenzie

[Paul McKenzie]

I took a quick glance at one of the files. I didn't get a chance to compile it, but I think that your problem is that you don't ever use references when you are passing your vectors around. You are passing vectors by value instead of by reference, making the compiler create unneccessary copies of the vector.

For example:

vector<itinerary> expand_itinerary(vector<list_values> value_list, itinerary parent, user_profile user)

You are passing vector<list_values> by value, meaning the compiler makes an entire copy of the vector. This may be what is taking up a lot of the time. Unless this is your intention, to pass a vector by value, then try this instead:

vector<itinerary> expand_itinerary(vector<list_values>& value_list, itinerary parent, user_profile user)

Also post the .h files. The goal is to have it so that any one else here can compile and run your program.

Regards,

Paul McKenzie