Архив рубрики: gcc

Virtual inline методы C++

C++ даёт возможность определять встраиваемые (inline) функции и методы. Реализация таких функций будет встраиваться в другие функции по месту вызова (за исключением некоторых случаев, когда это невозможно). Как правило, в конечном исполняемом файле или динамической библиотеке отдельной реализации таких функций не генерируется.
Другой замечательный механизм, предоставляемый языком C++ — это виртуальные методы. Эти методы участвуют в полиморфизме. Вы может вызывать такие функции из производного класс по указателю или ссылке на базовый. Достигается это путём помещения указателя на конкретную реализацию в таблицу виртуальных функций, которая помещается компилятором в известное ему место относительно полиморфного указателя или ссылке (конкретная реализация не стандартизирована и зависит от компилятора).

Стандарт C++ позволяет применять модификатор virtual к inline функциям. Тут мы наталкиваемся на неоднозначность. Как в таблицу виртуальных функций попадёт указатель, если тело функции не генерируется? Ответ на этот вопрос также не стандартизирован и зависит от компилятора. Давайте попробуем разобраться.
Итак, допустим у нас есть такой код
extern "C" void exFunction(int);

class Base
{
public:
virtual int doSomething(int x, int y)
{
return x + y;
}
};

class Child : public Base
{
public:
virtual int doSomething(int x, int y)
{
return x * y;
}
};

extern "C" void run()
{
Base base;
int result = base.doSomething(1, 2);
exFunction(result);
Child child;
result = child.doSomething(2, 2);
exFunction(result);
}
Функция exFunction нужна лишь для того, чтобы компилятор не соптимизировал наши вычисления.
Я буду использовать компилятор g++ 4.7.2 и операционную систему Debian GNU/Linux 7.0 (wheezy) 64 bit.
Сохраним исходный текст в файл test.cpp соберём динамическую библиотеку с помощью команды
g++ -g -O2 -shared -fPIC  test.cpp
Я собираю динамическую библиотеку, чтобы было меньше мусора в дампе. Кроме того, я включил оптимизацию и отладочные символы. Посмотрим результат компиляции с помощью программы objdump.
objdump -d a.out
00000000000006e0 <run>:
6e0: 48 83 ec 08 sub $0x8,%rsp
6e4: bf 03 00 00 00 mov $0x3,%edi
6e9: e8 e2 fe ff ff callq 5d0 <exFunction@plt>
6ee: bf 04 00 00 00 mov $0x4,%edi
6f3: 48 83 c4 08 add $0x8,%rsp
6f7: e9 d4 fe ff ff jmpq 5d0 <exFunction@plt>
Как видим, компилятор не обратил внимание на модификатор virtual и просто встроил inline методы в код, соптимизировав сложение и умножение.
Теперь добавим в код полиморфизма.
extern "C" void exFunction(int);

class Base
{
public:
virtual int doSomething(int x, int y)
{
return x + y;
}
};

class Child : public Base
{
public:
virtual int doSomething(int x, int y)
{
return x * y;
}
};

extern "C" void run()
{
Base base;
int result = base.doSomething(1, 2);
exFunction(result);
Child child;
result = child.doSomething(2, 2);
exFunction(result);
Base * polymorphic = &child;
result = polymorphic->doSomething(3, 3);
exFunction(result);
}
Скомпилируем и посмотрим на дизассемблированный код.
0000000000000a50 <run>:
a50: 48 83 ec 18 sub $0x18,%rsp
a54: bf 03 00 00 00 mov $0x3,%edi
a59: e8 e2 fe ff ff callq 940 <exFunction@plt>
a5e: 48 8b 05 e3 03 20 00 mov 0x2003e3(%rip),%rax # 200e48 <_DYNAMIC+0x228>
a65: bf 04 00 00 00 mov $0x4,%edi
a6a: 48 83 c0 10 add $0x10,%rax
a6e: 48 89 04 24 mov %rax,(%rsp)
a72: e8 c9 fe ff ff callq 940 <exFunction@plt>
a77: 48 8b 04 24 mov (%rsp),%rax
a7b: 48 89 e7 mov %rsp,%rdi
a7e: ba 03 00 00 00 mov $0x3,%edx
a83: be 03 00 00 00 mov $0x3,%esi
a88: ff 10 callq *(%rax)
a8a: 89 c7 mov %eax,%edi
a8c: e8 af fe ff ff callq 940 <exFunction@plt>
a91: 48 83 c4 18 add $0x18,%rsp
a95: c3 retq
a96: 90 nop
a97: 90 nop
a98: 90 nop
a99: 90 nop
a9a: 90 nop
a9b: 90 nop
a9c: 90 nop
a9d: 90 nop
a9e: 90 nop
a9f: 90 nop

0000000000000aa0 <_ZN4Base11doSomethingEii>:
aa0: 8d 04 16 lea (%rsi,%rdx,1),%eax
aa3: c3 retq
aa4: 90 nop
aa5: 90 nop
aa6: 90 nop
aa7: 90 nop
aa8: 90 nop
aa9: 90 nop
aaa: 90 nop
aab: 90 nop
aac: 90 nop
aad: 90 nop
aae: 90 nop
aaf: 90 nop

0000000000000ab0 <_ZN5Child11doSomethingEii>:
ab0: 89 f0 mov %esi,%eax
ab2: 0f af c2 imul %edx,%eax
ab5: c3 retq
ab6: 90 nop
ab7: 90 nop
Теперь мы видим, что компилятор сгенерировал реализации для виртуальных методов и использовал виртуальную таблицу для третьего вызова. При этом первые два вызова остались встроенными.

Вообще говоря, компилятор всегда будет генерировать тело inline функции, если где-либо в программе требуется её адрес (явно или неявно). При этом, Вы можете расчитывать на встраивание virtual inline функции, если не используете для её вызова указатель или ссылку.

Я провёл подобное исследование с Visual C++, и оказалось, что этот компилятор ведёт себя аналогичным образом.

Анализ и оптимизация кода на C++ для Linux

Какие проблемы могут нас подстерегать при разработке программ? Неэффективные алгоритмы, утечки памяти, работа с невалидными указателями и не инициализированными переменными. Даже несмотря на, казалось бы, тщательное написание кода, мы порой делаем ошибки. Человеку свойственно ошибаться, поэтому эта статья посвящена контролю машин над человеком -- машинной проверки кода и исполняемых файлов. Я поделю весь процесс на три части:
  1. Статический анализ исходных текстов;
  2. Проверка утечек памяти;
  3. Нахождение участков кода, требующих неприлично много машинного времени.
В этой статье, говоря о компиляторе, я буду подразумевать g++, входящий в состав GCC (GNU Compiler Collection).

Статический анализ исходных текстов

Этот раздел опирается, во многом, на этот пост на хабре.

g++

Наряду со статическими анализаторами, компилятор g++ может выдать очень много полезной информации. Для того, чтобы добиться от компилятора максимум возмущений, следует добавит несколько опций.
-Wall - включает почти все стандартные предупреждения. Эту опцию нужно ставить всегда и везде, это должно стать Вашим правилом.
-Wextra - сообщит об ошибках в условных операторах, пустые if'ы и сравнение signed с unsigned.
-pedantic - по приказу этой опции компилятор начнёт следовать стандарту ISO C++. Например, запретит тип long long.
-Weffc++ -  эта опция напомнит Вам о некоторых правилах Скотта Майерса, которые Вы все, надеюсь, читали. В частности, это следующие правила из книги "Эффективное использование C++. 50 рекомендаций по улучшению ваших программ и проектов":
  • Правило 11. "Для классов с динамическим выделением памяти объявляйте копирующий конструктор и оператор присваивания".
  • Правило 12. "Предпочитайте инициализацию присваиванию в конструкторах".
  • Правило 14. "Убедитесь, что базовые классы имеют виртуальные деструкторы".
  • Правило 15. "operator= должен возвращать ссылку на *this".
  • Правило 23. "Никогда не пытайтесь вернуть ссылку, когда вы должны вернуть объект".
И несколько правил из книги "Наиболее эффективное использование C++. 35 новых рекомендаций по улучшению ваших программ и проектов":
  • Правило 6. "Различайте префиксную и постфиксную формы операторов инкремента и декремента".
  • Правило 7. "Никогда не перегружайте операторы &&, || и ,".
-Woverloaded-virtual - сообщит о перегрузке виртуальных функций.
-Wctor-dtor-privacy - возмутится, если найдёт у Вас в коде класс с закрытыми конструкторами и деструктором, который нигде не используется.
-Wnon-virtual-dtor - этой опции не нравятся не виртуальные деструкторы.
-Wold-style-cast - поможет избавится от приведений типов в стиле языка C.
-Wconversion -Wsign-conversion - заставят компилятор сказать пару ласковых о неверных приведениях типов, при которых Вы можете лишиться  части своих значений.
-Wunreachable-code - укажет на участки кода, которые никогда не будут выполнены. Эта опция может выдать очень много ворнингов даже в стандартной библиотеке, полезно её включать только при проверке.

Давайте проверим всё вышесказанное на практике. Для этой цели я написал следующий код полный ошибок
#include <iostream>

class CBicycle
{
public:
CBicycle(unsigned short max_speed)
{
m_max_speed = max_speed;
}

unsigned short GetMaxSpeed() const
{
return m_max_speed;
}

private:
short m_max_speed;
};

class CBicyclist
{
public:
CBicyclist(const CBicycle & bicycle)
{
mp_bicycle = new CBicycle(bicycle);
m_speed = 0;
}

unsigned short GetSpeed() const
{
return m_speed;
}

bool Move(short speed)
{
bool result = true;
if(speed <= mp_bicycle->GetMaxSpeed())
{
m_speed = speed;
std::cout << "I'm move with speed of " << m_speed << " km/hn";
}
else
{
result = false;
std::cout << "Sorry, this bicycle can't move with speed of " <<
speed << " km/hn";
}
return result;
}

private:
CBicycle * mp_bicycle;
unsigned short m_speed;
};

int TestMaxSpeed(CBicyclist & bicyclist)
{
int speed = bicyclist.GetSpeed();
int max_speed = speed;
bool loop = true;
do
{
if(bicyclist.Move(max_speed))
{
++max_speed;
}
else
{
loop = false;
--max_speed;
bicyclist.Move(speed);
}
} while(loop);
return max_speed;
}

int main()
{
CBicycle * bicycle = new CBicycle(75);
CBicyclist * bicyclist = new CBicyclist(*bicycle);
bicyclist->Move(600);
std::cout << "Begin max speed testn";
int max_speed = TestMaxSpeed(*bicyclist);
std::cout << "End max speed test. Max speed = " << max_speed << std::endl;
return 0;
}
У нас есть некое подобие классов, класс велосипеда и класс велосипедиста. Велосипед принимает в конструкторе максимальную скорость, а велосипедист - велосипед. Велосипедист может разогнаться на столько быстро, на сколько позволит велосипед или тип unsigned short, с которым у меня в коде связано много ошибок. Класс велосипедиста "забывает" удалить свой велосипед, а функция main "забывает" не только про велосипед, но и про велосипедиста. Задача функции TestMaxSpeed проверить, какая же скорость у велосипеда максимальная, используя для этой цели только велосипедиста. Но и у этой функции не всё в порядке с типами.
Итак, скомпилируем код с вышеуказанными опциями.
$ g++ -Wall -Wextra -pedantic -Weffc++ -Woverloaded-virtual -Wctor-dtor-privacy -Wnon-virtual-dtor -Wold-style-cast -Wconversion -Wsign-conversion -Wunreachable-code -g -O0  -c main.cpp
main.cpp: In constructor ‘CBicycle::CBicycle(short unsigned int)’:
main.cpp:6: warning: ‘CBicycle::m_max_speed’ should be initialized in the member initialization list
main.cpp:8: warning: conversion to ‘short int’ from ‘short unsigned int’ may change the sign of the result
main.cpp: In member function ‘short unsigned int CBicycle::GetMaxSpeed() const’:
main.cpp:13: warning: conversion to ‘short unsigned int’ from ‘short int’ may change the sign of the result
main.cpp: In constructor ‘CBicyclist::CBicyclist(const CBicycle&)’:
main.cpp:23: warning: ‘CBicyclist::mp_bicycle’ should be initialized in the member initialization list
main.cpp:23: warning: ‘CBicyclist::m_speed’ should be initialized in the member initialization list
main.cpp: In member function ‘bool CBicyclist::Move(short int)’:
main.cpp:39: warning: conversion to ‘short unsigned int’ from ‘short int’ may change the sign of the result
main.cpp: In function ‘int TestMaxSpeed(CBicyclist&)’:
main.cpp:63: warning: conversion to ‘short int’ from ‘int’ may alter its value
main.cpp:71: warning: conversion to ‘short int’ from ‘int’ may alter its value
main.cpp: In constructor ‘CBicyclist::CBicyclist(const CBicycle&)’:
main.cpp:25: warning: will never be executed
g++ -Wall -Wextra -pedantic -Weffc++ -Woverloaded-virtual -Wctor-dtor-privacy -Wnon-virtual-dtor -Wold-style-cast -Wconversion -Wsign-conversion -Wunreachable-code -g -O0 *.o -o test
Теперь давайте проанализируем вывод компилятора.
main.cpp: In constructor ‘CBicycle::CBicycle(short unsigned int)’:
main.cpp:6: warning: ‘CBicycle::m_max_speed’ should be initialized in the member initialization list
Нам сообщают, что в конструкторе класса CBicycle мы должны инициализировать член m_speed в списке инициализации, а не в теле конструктора.
main.cpp:8: warning: conversion to ‘short int’ from ‘short unsigned int’ may change the sign of the result
Конструктор CBicycle принимает значение unsigned short и присваивает его, почему-то, переменной типа short. (Это мы забыли написать unsigned в типе переменной-члена m_max_speed).
main.cpp: In member function ‘short unsigned int CBicycle::GetMaxSpeed() const’:
main.cpp:13: warning: conversion to ‘short unsigned int’ from ‘short int’ may change the sign of the result
Теперь мы ещё и возвращаем short от туда, от куда должны вернуть unsigned short.
main.cpp:23: warning: ‘CBicyclist::mp_bicycle’ should be initialized in the member initialization list
main.cpp:23: warning: ‘CBicyclist::m_speed’ should be initialized in the member initialization list
Класс CBicyclist повторил "подвиг" класса CBicycle и инициализировал все свои переменные в теле, а не в списке инициализации.
main.cpp: In member function ‘bool CBicyclist::Move(short int)’:
main.cpp:39: warning: conversion to ‘short unsigned int’ from ‘short int’ may change the sign of the result
Опять забыли про unsigned, какие же мы невнимательные.
main.cpp: In function ‘int TestMaxSpeed(CBicyclist&)’:
main.cpp:63: warning: conversion to ‘short int’ from ‘int’ may alter its value
main.cpp:71: warning: conversion to ‘short int’ from ‘int’ may alter its value
А это уже претенденты на потерю данных, конверсия из int в short.
main.cpp: In constructor ‘CBicyclist::CBicyclist(const CBicycle&)’:
main.cpp:25: warning: will never be executed
Этот ворнинг выдаёт опция -Wunreachable-code, его нужно проанализировать, и если Вы уверены, что всё в порядке -- можно проигнорировать.

cppcheck

Существуют специальные программы для анализа исходных текстов на C++, которые позволяют выявить потенциальные ошибки ещё до сборки (или использования) программ. Одна из таких программ -- cppcheck. В man руководстве к этой программе говорится, что она предназначена для выявления тех ошибок, которые не находит компилятор. Это такие ошибки как некоторые утечки памяти, выход за границу массива, исключения в деструкторах, разыменование нулевых и освобождённых указателей, виртуальность деструктора базовых классов и другое.
Работать с этой программой очень просто. Для демонстрации возьмём следующий небольшой пример.
int main()
{
int * x = new int[10];
x = 0;
return 0;
}
После запуска cppcheck в этом малюсеньком коде обнаруживается сразу две ошибки.
$ cppcheck --enable=all -v .
Checking ./main.cpp...
[./main.cpp:6]: (style) Variable 'x' is assigned a value that is never used
[./main.cpp:7]: (error) Memory leak: x
Checking usage of global functions..
Во-первых, мы объявили переменную x и никогда её не используем, а во-вторых, у нас зафиксирована утечка памяти.

Проверка утечек памяти

Практика показывает, что не всегда можно найти утечки памяти статическими анализаторами. Первый приведённый в этой статье листинг -- тому подтверждение. Если запустить cppcheck для этой программы, то мы ничего не найдём. Но отчаиваться ещё рано, нам может помочь утилита valgrind, предназначенная специально для этого.  Эта утилита находит утечки памяти не статически, а при работе программы. Давайте познокомимся с выводом этой программы
$ valgrind --leak-check=full -v ./test > /dev/null
==31174== Memcheck, a memory error detector
==31174== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==31174== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==31174== Command: ./test
==31174==
--31174-- Valgrind options:
--31174-- --suppressions=/usr/lib/valgrind/debian-libc6-dbg.supp
--31174-- --leak-check=full
--31174-- -v
--31174-- Contents of /proc/version:
--31174-- Linux version 2.6.32-5-amd64 (Debian 2.6.32-29) (ben@decadent.org.uk) (gcc version 4.3.5 (Debian 4.3.5-4) ) #1 SMP Fri Dec 10 15:35:08 UTC 2010
--31174-- Arch and hwcaps: AMD64, amd64-sse3-cx16
--31174-- Page sizes: currently 4096, max supported 4096
--31174-- Valgrind library directory: /usr/lib/valgrind
--31174-- Reading syms from /mnt/data/projects/blog/CodeOptimize/code/test (0x400000)
--31174-- Reading syms from /lib/ld-2.11.2.so (0x4000000)
--31174-- Considering /lib/ld-2.11.2.so ..
--31174-- .. CRC mismatch (computed 91367345 wanted f148be98)
--31174-- Considering /usr/lib/debug/lib/ld-2.11.2.so ..
--31174-- .. CRC is valid
--31174-- Reading syms from /usr/lib/valgrind/memcheck-amd64-linux (0x38000000)
--31174-- object doesn't have a dynamic symbol table
--31174-- Reading suppressions file: /usr/lib/valgrind/debian-libc6-dbg.supp
--31174-- Reading suppressions file: /usr/lib/valgrind/default.supp
--31174-- REDIR: 0x40162d0 (strlen) redirected to 0x380408a7 (vgPlain_amd64_linux_REDIR_FOR_strlen)
--31174-- Reading syms from /usr/lib/valgrind/vgpreload_core-amd64-linux.so (0x4a20000)
--31174-- Reading syms from /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so (0x4c21000)
==31174== WARNING: new redirection conflicts with existing -- ignoring it
--31174-- new: 0x040162d0 (strlen ) R-> 0x04c25850 strlen
--31174-- REDIR: 0x4016140 (index) redirected to 0x4c25460 (index)
--31174-- REDIR: 0x40161c0 (strcmp) redirected to 0x4c25e30 (strcmp)
--31174-- Reading syms from /usr/lib/libstdc++.so.6.0.13 (0x4e29000)
--31174-- object doesn't have a symbol table
--31174-- Reading syms from /lib/libm-2.11.2.so (0x513d000)
--31174-- Considering /lib/libm-2.11.2.so ..
--31174-- .. CRC mismatch (computed b0a7ab6b wanted 907fac55)
--31174-- Considering /usr/lib/debug/lib/libm-2.11.2.so ..
--31174-- .. CRC is valid
--31174-- Reading syms from /lib/libgcc_s.so.1 (0x53bf000)
--31174-- Considering /lib/libgcc_s.so.1 ..
--31174-- .. CRC mismatch (computed 07151771 wanted 3f9779e8)
--31174-- object doesn't have a symbol table
--31174-- Reading syms from /lib/libc-2.11.2.so (0x55d5000)
--31174-- Considering /lib/libc-2.11.2.so ..
--31174-- .. CRC mismatch (computed 21e032ea wanted d5c67601)
--31174-- Considering /usr/lib/debug/lib/libc-2.11.2.so ..
--31174-- .. CRC is valid
--31174-- REDIR: 0x5652600 (__GI_strrchr) redirected to 0x4c25280 (__GI_strrchr)
--31174-- REDIR: 0x5650b40 (__GI_strlen) redirected to 0x4c25810 (__GI_strlen)
--31174-- REDIR: 0x4ef46a0 (operator new(unsigned long)) redirected to 0x4c24d78 (operator new(unsigned long))
--31174-- REDIR: 0x5650b10 (strlen) redirected to 0x4a205ac (_vgnU_ifunc_wrapper)
==31174== WARNING: new redirection conflicts with existing -- ignoring it
--31174-- new: 0x05650b40 (__GI_strlen ) R-> 0x04c257f0 strlen
--31174-- REDIR: 0x5653e70 (mempcpy) redirected to 0x4c26bc0 (mempcpy)
--31174-- REDIR: 0x5654750 (memcpy) redirected to 0x4c25f00 (memcpy)
--31174-- REDIR: 0x564b7e0 (free) redirected to 0x4c24076 (free)
==31174==
==31174== HEAP SUMMARY:
==31174== in use at exit: 20 bytes in 3 blocks
==31174== total heap usage: 3 allocs, 0 frees, 20 bytes allocated
==31174==
==31174== Searching for pointers to 3 not-freed blocks
==31174== Checked 180,104 bytes
==31174==
==31174== 2 bytes in 1 blocks are definitely lost in loss record 2 of 3
==31174== at 0x4C24DFA: operator new(unsigned long) (vg_replace_malloc.c:261)
==31174== by 0x400B17: main (main.cpp:79)
==31174==
==31174== 18 (16 direct, 2 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 3
==31174== at 0x4C24DFA: operator new(unsigned long) (vg_replace_malloc.c:261)
==31174== by 0x400B38: main (main.cpp:80)
==31174==
==31174== LEAK SUMMARY:
==31174== definitely lost: 18 bytes in 2 blocks
==31174== indirectly lost: 2 bytes in 1 blocks
==31174== possibly lost: 0 bytes in 0 blocks
==31174== still reachable: 0 bytes in 0 blocks
==31174== suppressed: 0 bytes in 0 blocks
==31174==
==31174== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 4 from 4)
--31174--
--31174-- used_suppression: 2 dl-hack3-cond-1
--31174-- used_suppression: 2 glibc-2.5.x-on-SUSE-10.2-(PPC)-2a
==31174==
==31174== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 4 from 4)

Здесь мы можем увидеть статистику выделения и высвобождения памяти
==31174== HEAP SUMMARY:
==31174== in use at exit: 20 bytes in 3 blocks
==31174== total heap usage: 3 allocs, 0 frees, 20 bytes allocated
Три раза память была выделена, но ни разу не освобождалась. Чуть далее в выводе программы valgrind мы можем найти информацию немного подробнее.
==31174== 2 bytes in 1 blocks are definitely lost in loss record 2 of 3
==31174== at 0x4C24DFA: operator new(unsigned long) (vg_replace_malloc.c:261)
==31174== by 0x400B17: main (main.cpp:79)
==31174==
==31174== 18 (16 direct, 2 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 3
==31174== at 0x4C24DFA: operator new(unsigned long) (vg_replace_malloc.c:261)
==31174== by 0x400B38: main (main.cpp:80)
Вот тут-то valgrind и сдаёт нас с потрохами, выдавая все наши грехи.

Оптимизация кода

Теперь пришло время задуматься о производительности. Пусть у нас есть такой код
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <sys/time.h>

template<typename Type>
std::vector<Type> & Sort(std::vector<Type> & array)
{
size_t arr_size = array.size();
for(size_t i = 0; i < arr_size; ++i)
{
bool swaped = false;
for(size_t j = 1; j < arr_size; ++j)
{
if(array[j - 1] > array[j])
{
std::swap(array[j - 1], array[j]);
swaped = true;
}
}
if(!swaped)
break;
}
return array;
}

template<typename Type>
class CWriter
{
public:
CWriter(std::ostream & stream) :
mr_stream(stream)
{
}

void operator () (const Type & value)
{
mr_stream << value << std::endl;
}

private:
std::ostream & mr_stream;
};

template<typename Type>
bool WriteArrayToFile(const std::string & filename,
const std::vector<Type> & array)
{
bool result = false;
std::ofstream out(filename.c_str());
if(out.is_open())
{
std::for_each(array.begin(), array.end(), CWriter<Type>(out));
result = true;
out.close();
}
return result;
}

int main(int argc, char ** argv)
{
if(argc < 3)
{
std::cerr << "To few argumentsn";
return 1;
}
size_t array_size = static_cast<size_t>(::atoi(argv[1]));
std::string filename = argv[2];
::srand(static_cast<unsigned int>(::time(0)));
std::vector<int> array;
array.reserve(array_size);

for(size_t i = 0; i < array_size; ++i)
{
array.push_back(::rand());
}

if(! ::WriteArrayToFile(filename, ::Sort(array)))
{
std::cerr << "Error writing the file with name "" <<
filename << ""n";
return 2;
}

return 0;
}
Здесь генерируется массив из n элементов, сортируется и записывается в файл. Если мы его запустим, то увидим картину, не очень-то удовлетваряющую нас -- большие затраты времени. В этом можно убедиться, запустив такую команду
$ time ./test 100000 test.txt

real 0m24.913s
user 0m24.566s
sys 0m0.344s
25 секунд -- это, явно, слишком много. Естественным желанием будет оптимизировать работу программы так, чтобы предельно сократить время её работы. Из данного примера очевидно, что пузырьковая сортировка и является причиной нашего недовольства, но в больших проектах причина может быть не столь очевидной. Давайте сделаем вид, что мы не знаем причину столь затяжного выполнения и попробуем найти её методом профилирования программы. А поможет нам в этом утилита с именем gprof. Подробно о работе с этой утилитой можно прочитать на man-странице проекта opennet.
Для того, чтобы можно было работать с профилировщиком gprof, нужно добавить опцию -pg к команде сборки проекта, а затем собрать проект с отладочными символами. После сборки нужно запустить программу с тем же параметрами, с которыми мы получили неудовлетворительный результат, что приведёт к созданию файла gmon.conf в последнем текущем каталоге программы, а у нас этот каталог не менялся. Запустить программу gprof можно следующим образом
$ gprof ./test > gprof.log
На выходе программа gprof выдаёт очень много информации, поэтому её лучше перенаправить в файл. Теперь нужно открыть этот файл и проанализировать его. Я советую открывать этот файл в текстовом редакторе, поддерживающем подсветку синтаксиса и выбрать режим подсветки C++, так как профиль и граф вызовов содержат много текста на C++. Кроме того, лучше отключить динамический перенос строк. Я приведу только часть простого профиля файла, который у меня получился.
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
55.50 98.49 98.49 1 98.49 154.05 std::vector<int, std::allocator<int> >& Sort<int>(std::vector<int, std::allocator<int> >&)
24.22 141.47 42.99 7769644628 0.00 0.00 std::vector<int, std::allocator<int> >::operator[](unsigned long)
10.77 160.58 19.11 73 0.26 0.26 std::vector<int, std::allocator<int> >::size() const
6.94 172.89 12.31 2507056584 0.00 0.00 void std::swap<int>(int&, int&)
Из приведённых выше строк простого профиля видно, что 55,5% времени программа тратит на сортировку и ещё 24,22% на обращение к элементам вектора. Скорее всего, нам удастся решить обе проблемы, подставив более эффективный алгоритм сортировки. Давайте проверим, заменим сортировку пузырьком сортировкой слияниями.
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <sys/time.h>


template<typename Type>
std::vector<Type> & MergeSort(std::vector<Type> & array)
{
struct CMergeSort
{
void Sort(std::vector<Type> & array)
{
size_t array_size = array.size();
if(array_size <= 1)
return;

typename std::vector<Type>::iterator middle =
array.begin() + static_cast<ptrdiff_t>(array_size) / 2;
std::vector<Type> left(array.begin(), middle);
std::vector<Type> right(middle, array.end());
Sort(left);
Sort(right);
array = Merge(left, right);
}

std::vector<Type> Merge(const std::vector<Type> & left,
const std::vector<Type> & right)
{
std::vector<Type> result;
result.reserve(left.size() + right.size());
for(typename std::vector<Type>::const_iterator l =
left.begin(), r = right.begin();;)
{
if(left.end() == l)
{
typename std::vector<Type>::iterator it =
result.end();
result.insert(it, r, right.end());
break;
}
if(right.end() == r)
{
typename std::vector<Type>::iterator it =
result.end();
result.insert(it, l, left.end());
break;
}
if(*l < *r)
{
result.push_back(*l);
++l;
}
else
{
result.push_back(*r);
++r;
}
}
return result;
}
}; // struct CMergeSort

CMergeSort().Sort(array);
return array;
}

template<typename Type>
class CWriter
{
public:
CWriter(std::ostream & stream) :
mr_stream(stream)
{
}

void operator () (const Type & value)
{
mr_stream << value << std::endl;
}

private:
std::ostream & mr_stream;
};

template<typename Type>
bool WriteArrayToFile(const std::string & filename,
const std::vector<Type> & array)
{
bool result = false;
std::ofstream out(filename.c_str());
if(out.is_open())
{
std::for_each(array.begin(), array.end(), CWriter<Type>(out));
result = true;
out.close();
}
return result;
}

int main(int argc, char ** argv)
{
if(argc < 3)
{
std::cerr << "To few argumentsn";
return 1;
}
size_t array_size = static_cast<size_t>(::atoi(argv[1]));
std::string filename = argv[2];
::srand(static_cast<unsigned int>(::time(0)));
std::vector<int> array;
array.reserve(array_size);

for(size_t i = 0; i < array_size; ++i)
{
array.push_back(::rand());
}

if(! ::WriteArrayToFile(filename, ::MergeSort(array)))
{
std::cerr << "Error writing the file with name "" <<
filename << ""n";
return 2;
}

return 0;
}
Если мы откомпилируем этот код и запустим программу, то получим следующее
$ time ./test 100000 test.txt

real 0m0.437s
user 0m0.076s
sys 0m0.360s
Очевидно, что такие результаты нас устраивают.

---------------
Источники:
Статический анализ кода C++
Профилятор gprof