2

I have a huge code size. I recently added some new code and it works fine until I added a new simple if statement. After adding this add statement the runtime increases by 100X which is nonsense.

Some part of my code is below. The if statement is added in terminate_ongoing function and even if I remove everything inside if statement, the program is still slow. But if I comment this if statement, it becomes fast again.

The if statement is 

if ( emitted_vulnerable_list.size() > 100000 ){
}

As you can see, I removed everything inside if, but the problem is not resolved. Could you please provide some hints to find the source of problem and solve it.

class flip_flop_vulnerable_time{
public:
   list <vulnerable_time> emitted_vulnerable_list;
   list <vulnerable_time> ongoing_vulnerable_list;


   void terminate_ongoing(int PO, int minimum_delay , int cycle, long long elimination_time){
     for (list<vulnerable_time>::iterator it=ongoing_vulnerable_list.begin(); it!=ongoing_vulnerable_list.end(); it++){
       if ( it-> PO_signal_number == PO && it->cycles_passed == cycle && it->min_delay == minimum_delay ){
         it-> elimination_time = elimination_time;
         if ( cycle == 0 && elimination_time - it->appearance_time < 500 )
           ongoing_vulnerable_list.erase(it);
         else{
           emitted_vulnerable_list.splice(emitted_vulnerable_list.end(),ongoing_vulnerable_list, it);
           if ( emitted_vulnerable_list.size() > 100000 ){
           }
         }
         return;
       }
     }
     cout<<"\tError: can't find the following ongoing vulnerable_time object"<<endl;
     exit(0);
   }

   // Some other functions here
};
Mojtaba Ebrahimi
  • 51
  • 8
  • 1
    The `size` function may need to traverse the whole list in order to calculate the size. Should be pretty easy to find in the list header. – Retired Ninja Jan 03 '15 at 01:13
  • 2
    Maybe `list::size()` is very slow? [This](http://www.cplusplus.com/reference/list/list/size/) says that the time for it can be "up to linear" in non C++11, so that's probably the issue. – BWG Jan 03 '15 at 01:13
  • 1
    Actually I was reading the docs of `list::size()` and it says that in C++11 it has a constant time so maybe changing the compiler to a more recent version should work. For the record, [this is the doc file](http://www.cplusplus.com/reference/list/list/size/). – Carlos Vergara Jan 03 '15 at 01:14
  • Wait a minute, what sort of retarded implementation would not have a cached size variable? – BWG Jan 03 '15 at 01:14
  • 1
    @BWG: One that was made over ten years ago. – Carlos Vergara Jan 03 '15 at 01:16
  • @user1231958 Let me guess, back then memory was 1000x more important than processor cycles? – BWG Jan 03 '15 at 01:16
  • 2
    @BWG Caching the list size can make splice slower. There are always tradeoffs. http://stackoverflow.com/questions/228908/is-listsize-really-on – Retired Ninja Jan 03 '15 at 01:16
  • 1
    Thanks a lot for your great answers. Indeed I think this has to be the source of problem, because my list has something about one million elements and for adding each of them I call this function. – Mojtaba Ebrahimi Jan 03 '15 at 01:17
  • I am using gcc and unfortunately the list::size function is linear to number of objects in the list. – Mojtaba Ebrahimi Jan 03 '15 at 01:26
  • 1
    Yes, libstdc++ doesn't have constant time `size()` on `std::list`, even in C++11/14 mode, because it would be ABI breaking to make that change. – T.C. Jan 03 '15 at 02:05

2 Answers2

3

The list::size() implementation in gcc is of O(n) and in huge lists, calling this function multiple times might be very time consuming.

Mojtaba Ebrahimi
  • 51
  • 8
  • Please add that C++11 onwards solve this issue by making it a constant, for future readers. – Carlos Vergara Jan 03 '15 at 01:41
  • @user1231958 But according to [this](http://stackoverflow.com/questions/228908/is-listsize-really-on) the current implementation of gcc does not follow this specific item yet. – Mojtaba Ebrahimi Jan 03 '15 at 01:44
  • What's actually more important is that gcc is NOT going to make this code O(n), because apparently it would make C++98 and C++11 incompatible, as stated [here](http://stackoverflow.com/questions/19154205/should-stdlistsize-have-constant-complexity-in-c11). – Carlos Vergara Jan 03 '15 at 02:08
  • 2
    @user1231958 They will, eventually. They are just saving up all the ABI breaking changes for one release (GCC 5, it seems). – T.C. Jan 03 '15 at 02:12
  • Hopefully that's the case. Thank you. – Carlos Vergara Jan 03 '15 at 02:14
1

the problem with list::size() is that you are using list::splice(), and there is no way to track list sizes unless moved items are counted. but it doesn't look that hard to track the sizes manually using two variables.

Sergi0
  • 1,084
  • 14
  • 28