C++ для всех

Здравствуйте, уважаемые подписчики

Сегодняшний выпуск я планировал посвятить обсуждению проблемы написания безопасного в плане исключений кода, но в связи с занятостью предлагаю свою статью по оптимизации программ. Может быть для кого-то это и рано, а может быть и нет. О ранее заявленной теме мы поговорим в следующем выпуске.

Способы оптимизации программ

Прежде чем начать, я хочу рассказать о мотивах, которые подтолкнули меня к написанию данной статьи. Дело в том, что я не люблю неоптимальных алгоритмов. Кроме того, меня крайне удивляют высказывания некоторых программистов о том, что компьютер достаточно мощный, чтобы выполнять неоптимальные программы, причем даже для случаев, когда реализация более эффективного алгоритма требует, образно говоря, два раза нажать на клавишу.

Я не буду оговаривать случай использования профайлера для полной оценки скорости работы программы,- методика работы с профайлером должна описываться руководством по его использованию. Ниже Вы увидите способы, которые просто обязаны увеличить скорость работы программы.

Оптимизация условно разделяются на две категории: высокоуровневая и низкоуровневая. Некоторые рецепты имеют определенную двоякость, поэтому нахождение их в той или иной категории является скорее моим личным восприятием.

При описании способа оптимизации кое-где я буду проводить определенные сравнения скорости выполнения оптимизированного и неоптимизированного кода, поэтому сразу определю пару функций, которые будут показывать время выполнения теста. Сразу скажу - данная методика не оптимальна, существуют достаточно продвинутые библиотеки для подобных задач, но даже с этой точностью всегда можно сказать о степени правомерности того или иного утверждения. Вот эти функции:

 #include <time.h>

 clock_t start, end;

 void startClock(){ start = clock(); }
 void finishClock()
 {
  end = clock();
  printf("clocks: %f\n",((double)(end-start))/CLOCKS_PER_SEC);
 }

В дальнейшем я буду просто писать вызовы этих функций в тестовых примерах.

Высокоуровневая оптимизация

• Выбор оптимального алгоритма
• Ищите быстрые реализации
• Не используйте механизмы, которые Вам не нужны
• Предпочитайте статические и автоматические переменные динамическим
• При создании-удалении большого числа однотипных объектов используйте собственный распределитель памяти
• Что использовать для растущих массивов: malloc-realloc или new?
• Используйте списки инициализации
• Убирайте из циклов постоянно вычисляемые одинаковые значения
• Определите для собственных итераторов функцию, сигнализирующую о неправильном значении
• Предпочитайте преинкремент вместо постинкремента
• Используйте передачу константной ссылкой или указателем вместо копирования объекта
• Что выбрать: константный указатель или константную ссылку?
• Минимизируйте число создания временных объектов
• Перенесите циклы в условия
• Приведите условие завершения цикла к сравнению с нулем
• Изучите свой компилятор

Низкоуровневая оптимизация

• Механизм развертывания циклов
• Конвейерная обработка
• Используйте быстрые типы переменных. Избегайте неравноценных присваиваний
• Быстрое приведение double-int
• Использование ассемблерных функций

Высокоуровневая оптимизация

Методы высокоуровневой оптимизации применяются в период проектирования и разработки программы. К преимуществам этих методов следует отнести отсутствие временных затрат, т.к. на этой стадии профилирование не производится, а написание оптимальных программных конструкций целиком зависит от квалификации программиста.

• Выбор оптимального алгоритма

Оптимальный алгоритм является самой действенной оптимизацией, поэтому этот метод я вынес на первое место. Самая оптимизированная пузырьковая сортировка никогда не будет работать быстрее сортировки с использованием бинарных деревьев. Соответственно, умение программиста спроектировать эффективный алгоритм, в первую очередь будет зависеть от его квалификации и личных качеств. Данная оптимизация, в отличие от многих других, не может быть проведена после этапа разработки, т.к. именно здесь необходимо проектировать и структуры данных и непосредственно алгоритмы работы программы, а перекраивание программы после того, как она уже работает, может стать довольно дорогим удовольствием. Но, как говорится, хорошая программа должна быть переписана дважды, поэтому, возможно именно на втором этапе и появиться возможность все хорошо соптимизировать.

Оптимальный алгоритм предусматривает выбор правильных типов данных. Возьмем, к примеру, накопительные контейнеры STL-библиотеки: если в программе постоянно происходит удаление-добавление элементов, то как хранилище лучше использовать std::list; если число элементов постоянно и требуется доступ к элементу по индексу, то эффективнее будет std::vector или просто массив; если требуется быстрый поиск по ключу - используйте std::map.

• Ищите быстрые реализации

Не верьте, что все в стандартной STL-библиотеке работает оптимально. Цель этой библиотеки - универсальность, но эффективных решений на все случаи жизни не бывает. Класс std::string далеко не самый быстрый; std::list при сравнении с простым списком, в котором не требуется обратный проход, значительно проигрывает и по скорости и по затратам памяти; для std::map, std::set и подобных классов есть аналоги значительно превосходящие по скорости работы. В-общем, нужно искать и сравнивать решения.

• Не используйте механизмы, которые Вам не нужны

А это особый случай: здесь я перечислю несколько встречающихся неразумных решений:

• Использование исключительных ситуаций как языковых конструкций. Исключения предназначены исключительно для реагирования на критические ошибочные ситуации и подменять ими стандартные языковые конструкции (switch,if-else) по меньшей мере неэффективно. Используйте исключения только по назначению.
• Использование механизм виртуальных функций в классе, который не будет базовым. Иногда приходится встречать случаи, когда даже все функции объявлены виртуальными, причем класс абсолютно не участвует ни в какой иерархии. По меньшей мере этот механизм дает дополнительный указатель на объект плюс таблицу виртуальных функций. Кроме того, вызов виртуальных функций происходит через таблицу виртуальных функций, что несколько медленнее прямого вызова.
• Перегруженность класса функциями. Иногда приходится встречать классы, функции в которых написаны на все возможные и невозможные случаи жизни. Ничего кроме увеличения размера программы и сложности в понимании работы класса это не даст. Класс должен делать только то, что от него нужно.
• Обращение к собственным данным-членам через функции-члены. Если функция не inline, то это приводит к лишним накладным расходам. Класс имеет полный доступ к собственным членам-данным - этим нужно пользоваться. С другой стороны, если обращение или модификация данных-членов являются производными нескольких сложных действий, то необходимо это делать через функции.

• Предпочитайте статические и автоматические переменные динамическим

Довольно часто возникает необходимость выделять блоки памяти (или создавать массив), максимальный размер которых не известен. Есть три возможных решения данной задачи:

• Первое - это выделить максимально большой блок, и использовать его в дальнейшем. Проблема в том, что реально максимум определить сложно, да и память не резиновая, кроме того, как всегда существует реальный шанс, что и выделенного блока нам не хватит.
• Второе решение - динамическое выделение памяти. Это вполне рабочее и надежное решение. Единственное, мы здесь говорим об эффективности, а динамическое выделение и освобождение памяти - совсем не дешевая операция. Но есть и лучший вариант - смотрим далее.
• Третье - оптимальное. А что если мы совместим два первых, т.е. выделим определенный блок или в стеке или в общей памяти (static-переменная), а на случай, когда запрашиваемый размер блока превышает первоначальный, память будем выделять динамически:

 void calcData(int count)
 {
  const int max_count = 256;
  char buf[max_count]; //static для больших массивов
 
  char *pbuf = (count > max_count) ? (char*)malloc(count) : buf; 
  ...

  if(pbuf!=buf) free(pbuf);
 }

По-моему, это и есть правильное решение. Правда, есть еще одно - это объявить статический или глобальный указатель и при необходимости увеличивать размер (т.е. не удалять при выходе из блока функции), но этот способ может привести к пустой трате памяти для случая, когда сразу был затребован большой блок, а затем используется только малая часть. Кроме того, если данная функция уже не будет использоваться, то для удаления памяти нужно вводить какой-либо глобальный идентификатор. Но все же данный метод также имеет право на жизнь:

 char *g_pbuf = 0;
 int g_bufsize = 0;

 void calcData(int count)
 {
  if(count > g_bufsize){
   g_pbuf = (char*)realloc(g_pbuf,count);
   g_bufsize = count;
  }
  ...
 }
 
 int main()
 {

  calcData(300);
  for(int i=0;i<100;++i) calcData(i);
  
  //далее функция и буфер уже не нужны

  free(g_pbuf);  
  ...  
  return 0;
 }

• При создании-удалении большого числа однотипных объектов используйте собственный распределитель памяти

Выделение памяти - довольно дорогая операция, еще хуже, когда происходит выделение-освобождение памяти под большое число объектов. Единственный выход - это выделить большой блок памяти и нарезать кусочки под новые объекты. Делается это так:

 struct SPool{
  unsigned char *data;
  SPool *next;
 };

 static SPool *curr_pool = 0;
 static int block_size = 64*1024;
 static size_t remaining = 0;
 unsigned char* space;

 static void newPool()
 {
  remaining = block_size;
  SPool *p = (SPool*)malloc(sizeof(SPool));
  p->data = (unsigned char*)malloc(block_size);
  space = p->data;
  p->next = curr_pool;
  curr_pool = p;
 }

 void openPool(){ newPool(); }

 void* poolAlloc(size_t bytes)
 {
  if(bytes > block_size)
   return ::operator new(bytes);
  if(!curr_pool || bytes > remaining) 
   newPool();
  void *memory = space;
  space += bytes;
  remaining -= bytes;
  return memory;
 }

 void poolFree(void *d){}

 void closePool()
 {
  SPool *p;
  while(curr_pool){
   p = curr_pool->next;
   free(curr_pool->data);
   free(curr_pool);
   curr_pool = p;
  }
 }
 
 //------------------------------------------------------------
 
 a) Вариант с использованием пула
 struct STest{
  double value;

  void* operator new(size_t sz){ return poolAlloc(sz); }
  void operator delete(void *d){}
 };

 б) Вариант без использованием пула
 struct STest{
  double value;
 };
 
 int main()
 {
  openAlloc();
  
  static int max_cnt = 1000000;

  startClock();
  for(int i=0;i<max_cnt;++i)
   delete new STest();
  finishClock();
  
  closePool();
  return 0;
 }

Результат по времени для вариантов такой:

 вариант с пулом  а) - 0.046000
 вариант без пула б) - 0.296000 

Итак, по тестам увеличение скорости более чем в 6 раз. Прошу заметить, что при использовании пула в структуре STest оператор delete ничего не делает. Память, выделенную пулом, следует освобождать после того, как все объекты, которые работают через пул, будут удалены. Делается это как правило путем подсчета ссылок.

• Что использовать для растущих массивов: malloc-realloc или new?

В ряде довольно авторитетных изданий (включая "Stroustrup C++ Style and Technique FAQ") иногда приходится встречать рекомендацию отказаться от применения malloc-realloc для создания и изменения размера динамически изменяющегося массива, - вместо этого предлагается использовать оператор new. Причем, часто как аргумент в пользу new приводят тот факт, что realloc якобы практически всегда при увеличении размера блока памяти вынужден выделять блок на новом месте с последующим копированием содержимого старого буфера в новый.

Да, я согласен, для массивов сложных типов, у которых определен конструктор или которые содержат данные-члены сложного типа, использование оператора new необходимо т.к. требуется вызов конструкторов для объектов, но использовать new для массивов базовых типов и типов, не нуждающихся в вызове конструктора, не уверен... Рабочие циклы создания-изменения-удаления массивов для двух случаев будут такими:

 a) Через malloc
 malloc //создание

 realloc //изменение размера

 free //удаление


 б) Через new
 new //создание
 
 new //создание нового
 memcpy //копирование старого содержимого на новое место
 delete  //удаление старого массива и обмен указателями
 
 delete //удаление

Лишние операции налицо. А что по скорости работы? Ответить на этот вопрос нам поможет простенький тест:

 a) Вариант с realloc
 int main()
 {
  char *p = 0;
  const int max_cnt = 128*1024;
  
  startClock();
  
  for(int i=1;i<max_cnt;++i)
   p = (char*)realloc(p,i);
  free(p);
  
  finishClock();
  
  return 0;
 }

 б) Вариант с new
 int main()
 {
  char *p,*p1=0;
  const int max_cnt = 128*1024;
  
  startClock();
  
  for(int i=1;i<max_cnt;++i){  
   p = new char[i];
   if(p1){
    memcpy(p,p1,i-1);
    delete [] p1;
   }
   p1 = p;
  }
  delete [] p;
  
  finishClock();
  
  return 0;
 }

Результаты такие:

 вариант а) - 0.015000
 вариант б) - 5.375000

Причем, во варианте б), как и ожидалось, практически всю разницу в скорости выполнения между вариантами дает memcpy. Если для примера, закомментировать строку memcpy(p,p1,i-1), то получим уже 0.078000.

Теперь посмотрим, сколько раз функция realloc перемещала блок на новое место:

 int main(int argc, char* argv[])
 {
  char *p = 0,*p1 = 0;
  int ncnt=0;
  const int max_cnt = 128*1024;
  
  for(int i=1;i<max_cnt;++i){
   p = (char*)realloc(p,i);
   if(p1!=p) ++ncnt;
   p1 = p;
  }
  free(p);  

  --ncnt; //исключим первое выделение памяти
  
  printf("new place: %d, cycles: %d\n",ncnt,max_cnt);
  
  return 0;
 }

Результаты на экране такие:

 new place: 2, cycles: 131072

Т.е. при изменении размера массива произошло только два перемещения. Но не все так хорошо. Дело в том, что в данном примере размер увеличивался линейно, а функция malloc, как и realloc вправе (зависит от реализации) выделять несколько больший буфер, чем запрашивается, с учетом возможного в дальнейшем запроса на изменения или же при выделении использовать пул.

Давайте тогда несколько изменим тест. Увеличивать буфер будем не на единицу, а на 33:

 int main()
 {
  char *p = 0,*p1 = 0;
  int ncnt=0;
  const int max_cnt = 128*1024;
  
  for(int i=1;i<max_cnt;i+=33){
   p = (char*)realloc(p,i);
   if(p1!=p) ++ncnt;
   p1 = p;
  }
  free(p);

  --ncnt; //исключим первое выделение памяти
  
  printf("new place: %d, cycles: %d\n",ncnt,max_cnt);
  
  return 0;
 }

Результаты на экране такие:

 new place: 12, cycles: 131072

Перемещений в несколько раз больше, причем самих операций увеличения буфера (max_cnt) было проведено в 33 раза меньше. Все же, даже при самом худшем варианте скорость при использовании realloc значительно выше чем при использовании new.

Теперь посмотрим, что будет в случае резких изменений размеров массива:

 int main()
 {
  char *p = 0,*p1 = 0;
  int ncnt=0;
  int i,rnd,last_size=0;
  const int max_cnt = 128*1024;
  const int max_block = 1024*256;
  static int lbuf[max_cnt];

  for(i=0;i<max_cnt;++i)
   lbuf[i] = (8*rand())%max_block;
  
  //вариант с realloc
  startClock();
  for(i=0;i<max_cnt;++i){
   p = (char*)realloc(p,lbuf[i]);
   if(p!=p1) ++ncnt;
   p1 = p;
  }
  --ncnt;
  free(p);
  finishClock();

  //вариант с new
  p1=0;
  startClock();
  for(i=0;i<max_cnt;++i){
   rnd = lbuf[i];
   p = new char[rnd];
   if(p1){
    memcpy(p,p1,last_size < rnd ? last_size : rnd);
    delete [] p1;
   }
   p1 = p;
   last_size = rnd;
  }
  delete [] p;
  finishClock();

  printf("new place: %d, cycles: %d\n",ncnt,max_cnt);

  return 0;
}

Результаты на экране такие:

 clocks: 0.031000
 clocks: 21.438000

 new place: 11, cycles: 131072

Тенденция та же - realloc работает значительно быстрее. При меньших выделяемых блоках памяти (в данном тесте максимально возможный блок 256Кб) разница в скорости значительно падает, но все же realloc остается раз в 20-30 быстрее.

Сделаем окончательный вывод: динамические массивы простых типов (базовые типы и типы, не требующие вызова конструктора) настоятельно рекомендуется создавать через malloc, размер изменять с помощью realloc. Если сильно тянет работать через new, то однозначно следует писать свою функцию memcpy на ассемблере с использованием mmx-регистров, раза в два-три скорость копирования увеличить можно.

• Используйте списки инициализации

Пример:

 class A
 {
  int val;
  double dval;
 public:
  A(int v,double d)
  {
   val = v;
   dval = d;
  }
 };

Намного лучше:

 class A
 {
  int val;
  double dval;
 public:
  A(int v,double d):val(v),dval(d){}
 };

Использование списка инициализации позволяет обойтись без выполнения лишнего конструктора для членов-данных класса, в этом случае вызывается только копирующий конструктор. Иначе нам не избежать вызова конструктора по умолчанию. Для простых объектов это мелочи, но для сложных вызов лишнего конструктора может привести к значительным накладным и, к тому же, абсолютно ненужным расходам. Кроме того, реализация оператора присваивания в сложных классах предусматривает предварительную очистку прежних данных, т.е. к расходам можно еще добавить различные проверки, реализованные в операторе присваивания.

Посмотрим такой пример:

 а) Вариант с оператором присваивания
 struct STest{
  std::map<int,int> map1,map2,map3;

  STest(const std::map<int,int> &m)
  {
   map1 = m;
   map2 = m;
   map3 = m;
  }
 };

 б) Вариант с копирующим конструктором
 struct STest{
  std::map<int,int> map1,map2,map3;

  STest(const std::map<int,int> &m):map1(m),map2(m),map3(m){}
 };

 int main()
 {          
  std::map<int,int> m;
  int i = 1000000;

  startClock();
  while(i--){
    STest t(m);
  }
  finishClock();
        
  return 0;
 }

Результаты такие:

 вариант с оператором присваивания а) - 0.828000
 вариант с копирующим конструктором б) - 0.718000

Разница в скорости почти 15 процентов, - по-моему неплохо, причем этот тест над довольно простой структурой, в реальном сложном классе разница будет еще более заметная.

• Убирайте из циклов постоянно вычисляемые одинаковые значения

Во многих программах можно увидеть подобный алгоритм обхода списка:

 std::list<int> lst;
 ...
 std::list<int>::iterator it;
 for(it=lst.begin();it!=lst.end();++it){
  ...
 }
 --it; //допустимая операция, для непустого списка укажет на последний элемент

Здесь я вижу два неприятных момента:

• Во-первых, функцией lst.end() постоянно создается объект типа std::list<int>::iterator, который сравнивается с текущим итератором it.
• Во-вторых, для STL-классов итератор, возвращаемый функцией end(), указывает на следующий за последним объект в списке, т.е. это не какой-то пустой итератор и применив оператор -- к lst.end(), мы имеем возможность (если список не пустой) обратиться к последнему элементу. Я веду к тому, что функция end() может вернуть итератор двумя способами: или хранить указатель на последний объект (почти все так и делают) или каждый раз проходить весь список для нахождения последнего объекта. Последний способ может возникнуть при разработке классов, требовательных к памяти или в случаях когда сложно выделить либо контролировать последний элемент. В этом случае, функция end() или должна возвращать пустой итератор (итератор, который говорит, что он некорректен) или вообще должна отсутствовать, тогда итератор берет на себя контроль за корректностью.

Улучшения ситуации в приведенном выше примере я вижу так:

 std::list<int> lst;
 ...
 std::list<int>::iterator it_end = lst.end();
 std::list<int>::iterator it;
 for(it=lst.begin();it!=it_end;++it){
  ...
 }
 --it; //допустимая операция, для непустого списка укажет на последний элемент

Для классов, у которых итератор по достижении конца списка становиться некорректным (невозможно откатиться с помощью оператора декремента) лучше делать так:

 MyList<int> lst;
 ...
 MyList<int>::iterator it;
 for(it=lst.begin();it.isValid();++it){
  ...
 }
 --it; //для некорректного итератора перехода на последний элемент не произойдет

Еще один часто распространенный случай:

 for(int i=0;i<list.count();++i){
  ...
 }

Лучше сделать так:

 int cnt = list.count();
 for(int i=0;i<cnt;++i){
  ...
 }

И еще один:

 const int buf_size = 1024;
 int buf[buf_size];
 ...

 int i = 10; //любое значение
 if(buf[i]==1){
  ...
 }
 else if(buf[i]==2){
  ...
 }
 else if(buf[i]==3){
 }
 ...

Лучше сделать так:

 ...

 int i = 10; //любое значение
 int bf_val = buf[i];
 if(bf_val==1){
  ...
 }
 else if(bf_val==2){
  ...
 }
 else if(bf_val==3){
 }

• Определите для собственных итераторов функцию, сигнализирующую о неправильном значении

В рассмотренном выше примере присутствовала функция isValid(). Для всех итераторов, которые Вы разрабатываете, я рекомендую определить подобную функцию и использовать ее вместо вызова функции базового контейнерного объекта end(), которая возвращает объект.

• Предпочитайте преинкремент вместо постинкремента

Здесь все понятно, просто смотрим пример:

 class A
 {
 public:
  A(int d_=0):d(0){}
  ~A(){ printf("~A()\n"); }

  A& operator++()
  {
   ++d;
   return *this;
  }
  const A operator++(int)
  {
   A tmp(d);
   ++*this;
   return tmp;
  }  
 private:
  int d;
 };

 int main()
 {
  {
   A a;
   a++;
  }
  printf("----------------------------\n");
  {
   A a;
   ++a;
  }
  return 0;
 }
 

На экране увидим:

 ~A()
 ~A()
 ----------------------------
 ~A()

Итак, когда мы используем постинкремент, то всегда происходит создание временного объекта.

• Используйте передачу константной ссылкой или указателем вместо копирования объекта

Когда Вы пишите так:

 struct SStrings{
  std::string s1,s2,s3;
 };
 void func(SStrings s){
  ...
 }

Вы всегда передаете в функцию копию вашего объекта. Чем сложнее объект тем, соответственно, дороже Вам будет стоить эта передача. Поэтому, если передаваемый объект сложный и не планируется использовать неконстантные функции объекта, то его следует передавать как константную ссылку:

 void func(const SStrings &s){
  ...
 }

• Что выбрать: константный указатель или константную ссылку?

В принципе, эти два способа на низком уровне делают одно и тоже - в функцию передается адрес, но для нас может быть разница. Во-первых, когда в функцию передается указатель, то допускается вариант, когда указатель ни на что не указывает, то есть равен нулю. В этом случае в функции должен присутствовать код проверки на равенство нулю. Также при передаче указателя существует вероятность по ошибке оператором delete удалить константный объект, что совсем нехорошо. Поэтому лично я пользуюсь таким правилом - если передаваемый объект всегда существует, то в функцию передается константная ссылка, иначе передается константный указатель с обязательной проверкой в функции на нуль.

• Минимизируйте число создания временных объектов

Посмотрите на этот пример. Здесь внутри большого цикла постоянно создаются и уничтожаются объекты, которые используются только внутри цикла. Ситуация может значительно ухудшиться, если объекты будут сложными.

 for(int i=0;i<max_cnt;++i){
  char buf[64];
  double d1,d2;
  ...  
 }

Да, создание и удаление стековых переменных происходит быстро, но можно обойтись и без этого:

 char buf[64];
 double d1,d2;
 for(int i=0;i<max_cnt;++i){
  ...  
 }

• Перенесите циклы в условия

Посмотрим на исходное условие:

 int xval;
 ...
 for(int i=0;i<max_cnt;++i){
  if(xval>X_COUNT && xval<Y_COUNT){
   func(i);
  }
  else if(xval>X1_COUNT && xval<Y1_COUNT){
   func1(i);
  }
  else if(xval>X2_COUNT && xval<Y2_COUNT){
   func2(i);
  }
 }

В данном случае можно избавиться от многочисленных проверок переместив цикл внутрь. В большинстве случаев работать будет быстрее, но размер программы несколько увеличиться.

 int i;
 if(xval>X_COUNT && xval<Y_COUNT){
  for(i=0;i<max_cnt;+i){
   func(i);
  }
 }
 else if(xval>X1_COUNT && xval<Y1_COUNT){
  for(i=0;i<max_cnt;+i){
   func1(i);
  }
 }
 else if(xval>X2_COUNT && xval<Y2_COUNT){
  for(i=0;i<max_cnt;+i){
   func2(i);
  }
 }

• Приведите условие завершения цикла к сравнению с нулем

Для случаев, когда порядок обхода массива (или подобного по поведению объекта) не имеет значения, следует условие завершение свести к сравнению с нулем:

 int cnt = list.count();
 for(int i=0;i<cnt;++i)
  list[i] = i;
 

Быстрее:

 for(int i=list.count();i;)
  list[--i] = i;

• Изучите свой компилятор

Рассмотрим простой пример у себя на компьютере:

 struct STest{
  ~STest(){ printf("~STest()"); }

  STest copy(){ return *this; }
 };
 
 void func(STest s){}
 
 int main()
 {
  STest s;
  func(s.copy());

  return 0;
 }

Данный код я проверил на двух известных компиляторах с включенной полной оптимизацией: один вывел две строки, другой три. И таких отличий в поведении может быть много.

Практически каждый компилятор имеет ряд ключей, которые в ту или иную сторону влияют на скорость работы программы. В-общем, читайте матчасть.

Низкоуровневая оптимизация

Методы низкоуровневой оптимизации применяются после разработки основной части программы. Как правило требуют наличия профайлера или иного инструмента замера производительности участков программы. Также в этом случае полезно почитать документацию на сайтах производителей процессоров, например: Intel, AMD.

• Механизм развертывания циклов

Не скажу, что это стопроцентно прибавит скорость, но попробовать стоит. Почему я сомневаюсь? Потому что практически все оптимизирующие компиляторы вполне успешно самостоятельно справляются с данной проблемой. В общем, нужно смотреть профайлером. Пример:

 int buf[3];
 for(int i=0;i<3;++i)
  buf[i];

Должно работать быстрее:

 int buf[3];
 buf[0] = 0;
 buf[1] = 1;
 buf[2] = 2;

• Конвейерная обработка

Архитектурно современные процессоры способны выполнять несколько операций за один такт. Хотя такие вещи в полной мере можно реализовать только на ассемблере (там есть вопросы типа спаривания инструкций и т.п.), все же кое-что можно попробовать. Напишем для примера функцию вычисления длины строки:

 int xstrlen(const char *s)
 {
  const char *p = s;
  while(*p) ++p;
  
  return p-s;
 }

Переделаем и сравним:

 int fast_xstrlen(const char *s)
 {
  const char *p = s;
  while(*p){
   if(!p[1]){ ++p;  break; }
   if(!p[2]){ p+=2; break; }
   if(!p[3]){ p+=3; break; }
   if(!p[4]){ p+=4; break; }
   if(!p[5]){ p+=5; break; }
   if(!p[6]){ p+=6; break; }
   if(!p[7]){ p+=7; break; }
   if(!p[8]){ p+=8; break; }
   p+=9;
  }
  return p-s;
 }

 int main()
 {
         const int max_cnt = 1000000;
  const char *s = "12892834u843u8543843dfsuihsiudfhiusdf829823982938";

  startClock();        
  for(int i=0;i<max_cnt;++i)
   strlen(s);
  finishClock();

  startClock();        
  for(int i=0;i<max_cnt;++i)
   xstrlen(s);
  finishClock();

  startClock();        
  for(int i=0;i<max_cnt;++i)
   fast_xstrlen(s);
  finishClock();
  
  return 0;
 }

Результаты такие:

 стандартная функция  0.054500
 без оптимизации      0.360000
 с оптимизацией       0.210000

• Используйте быстрые типы переменных. Избегайте неравноценных присваиваний

В 32-битных системах наиболее быстрым типом является int. Поэтому, по возможности, как можно чаще используйте именно этот тип.

 char y;
 int x;

 x = y;

Быстрее:

 int x,y;

 x = y;

• Быстрое приведение double-int

Как и большинство методов низкоуровневой оптимизации, данный метод нельзя назвать универсальным, так что использовать его или нет - решать Вам. Кроме того, использовать его следует только при больших вычислительных задачах.

 #define DOUBLE2INT(d,i){ double t = ((d)+6755399441055744.0); i=*((int *)(&t)); }
 
 int main()
 {
         const int max_cnt = 10000000;
  int i,val;
  double dval;

  startClock();
  for(i=0;i<max_cnt;++i){
   val = (int)dval;
  }   
  finishClock();

  startClock();
  for(i=0;<max_cnt;++i){
   DOUBLE2INT(dval,val);
  }   
  finishClock();

  return 0;
 }

Результаты выполнения теста такие:

 простое приведение  0.265000
 оптимизированное    0.047000

Как видим - прирост довольно значительный.

• Использование ассемблерных функций

Данный пункт я вынес последним в советах по оптимизации, поскольку использование ассемблера сразу означает проблемы с переносимостью С++ программ, а С++ тем и хорош, что позволяет при правильном написании довольно легко переносить программы между платформами.

Итак, когда нужно использовать ассемблер и что в плане скорости он нам даст? На ассемблере следует писать только действительно критические участки программы - не нужно писать на нем функции ввода-вывода,- этот механизм Вы ускорить не сможете. Реальный средний прирост от переписывания правильно написанных (в смысле алгоритма) С++ функций на ассемблер составляет около 2-5 процентов. Да, есть случаи, когда простой перестановкой местами двух инструкций в ассемблерной процедуре Вы можете увеличить скорость ее работы в два раза, но это довольно специфические ситуации.

Если Вы собрались что-то писать на ассемблере, то компилятор ассемблера следует выбирать портируемый, например fasm, а функции писать не вставками в С++ код (будет почти стопроцентная зависимость от конкретного С++-компилятора), а внешними модулями, которые будут подлинковываться. В таком случае проблем при переносе на другие платформы будет несколько меньше.

Подведем итог. Оптимизация программы - важная и необходимая часть в разработке любых критических ко времени выполнения программ. Использование оптимизирующих конструкций и методов иногда может спасти самый гиблый в плане скорости проект, однако не нужно забывать, что главная оптимизация происходит еще на стадии проектирования и до написания первой строки кода.

Успехов

На сегодня все. Пожелания, предложения, вопросы прошу на iqsoft@cg.ukrtel.net

В следующем выпуске - написание безопасного в плане исключений кода