Monk
да цель максимальная оптимизация скорости выполнения. Профайлером не пользуюсь. Спасибо за наводку!
касательно памяти: простые функции я не тестировал на прожорливость памяти, т.к. единственная из них которая могла бы жрать много памяти это qsort, который у меня не рекурсивный.
скорость измеряю через цикл т.к. меня интересует не столько скорость самой функцию, а скорость относительно другой (например тот же стандартный strlen)
время выполнения замеряю либо через GetTickCount() либо QueryPerformanceCounter(...) перед циклом скажем в 1000000 итераций и после.
оптимизирую так:
1) алгоритм - самое самое главное (вот например сколько алгоритмов сортировки при этом самый быстрый qsort). Тот-же strlen не на этой станице и на передыдущей - небо и земля
2) использование инлайн функций или кусков кода из макросов (с последними главное не слишком увлекаться в пользу читабельности) чтоб тратить меньше тактов на вызов
3) загонять стековые и локальные переменные в регистры если они часто используются (тоже очень большой прирост в скорости)
4) не использовать знаковые переменные если числа которые будут туда писаться всегда >= 0, тк проц быстрее работает с беззнаковыми числами
5) оптимизация самого компилятора:
..... адресная арифметика например для uint32_t * arr: обращение ко второму uint32_t такое arr[1] быстрее чем явная адресная арифметика
..... раньше я увлекался написание циклов через goto в пользу гибкости, но стандартные циклы while, for быстрее благодаря оптимизации компилятора
6) развёрнутые циклы
7) при необходимости можно для быстоты испльзовать lockup таблицы, как например чаcто делается в том же crc32 а можно и не использовать возвращаясь к первому пункту вот пример:
перевод строки в число здесь
http://stackoverflow.com/a/4351484 через деление и lockup таблицу с символами и вот алгоритм который я использую int32_to_str без таблицы и деления (алгоритм нарыл на
http://fastcode.sourceforge.net/):
тест скорости
Код: Выделить всё
std::string& itostr(int n, std::string& s)
{
if(n==0)
{
s="0";
return s;
}
int sign = -(n<0);
unsigned int val = (n^sign)-sign;
int size;
if(val>=10000)
{
if(val>=10000000)
{
if(val>=1000000000)
size=10;
else if(val>=100000000)
size=9;
else
size=8;
}
else
{
if(val>=1000000)
size=7;
else if(val>=100000)
size=6;
else
size=5;
}
}
else
{
if(val>=100)
{
if(val>=1000)
size=4;
else
size=3;
}
else
{
if(val>=10)
size=2;
else
size=1;
}
}
size -= sign;
s.resize(size);
char* c = &s[0];
if(sign)
*c='-';
c += size-1;
while(val>=100)
{
int pos = val % 100;
val /= 100;
*(short*)(c-1)=*(short*)(digit_pairs+2*pos);
c-=2;
}
while(val>0)
{
*c--='0' + (val % 10);
val /= 10;
}
return s;
}
#include <stdint.h>
#if (INTPTR_MAX == INT32_MAX)
#define THIS_IS_32_BIT_ENVIRONMENT
#elif (INTPTR_MAX == INT64_MAX)
#define THIS_IS_64_BIT_ENVIRONMENT
#else
#error "Environment not 32 or 64-bit!"
#endif
#define _in_
#define _out_
#define MAX_INT32_STR_LEN 11
#define OPPOSITE_SIGN_INT32(v) ((v + (int32_t)0xFFFFFFFF) ^ (int32_t)0xFFFFFFFF)
size_t __fastcall int32_to_str( _in_ const int32_t y, _out_ char * str )
{
register int32_t x = y;
register size_t r_len;
register uint8_t num;
r_len = 0;
if (x < 0)
{
if (x == -2147483648) // --> (x == INT32_MIN)
{
#ifdef THIS_IS_64_BIT_ENVIRONMENT
*((uint64_t *)str) = *((uint64_t *)"-2147483");
*((uint16_t *)(str + 8)) = *((uint16_t *)"64");
*(str + 10) = '8';
#else
*((uint32_t *)(str + 0)) = *((uint32_t *)"-214");
*((uint32_t *)(str + 4)) = *((uint32_t *)"7483");
*((uint16_t *)(str + 8)) = *((uint16_t *)"64");
*(str + 10) = '8';
#endif
return MAX_INT32_STR_LEN;
}
else
{
x = OPPOSITE_SIGN_INT32(x);
*str = '-';
str++;
r_len = 1;
}
}
if (x < 10000)
{
if (x < 100)
{
if (x < 10)
{
r_len += 1;
goto num_9;
}
else
{
r_len += 2;
goto num_8;
}
}
else
{
if (x < 1000)
{
r_len += 3;
goto num_7;
}
else
{
r_len += 4;
goto num_6;
}
}
}
else
{
if (x < 1000000)
{
if (x < 100000)
{
r_len += 5;
goto num_5;
}
else
{
r_len += 6;
goto num_4;
}
}
else
{
if (x < 100000000)
{
if (x < 10000000)
{
r_len += 7;
goto num_3;
}
else
{
r_len += 8;
goto num_2;
}
}
else
{
if (x < 1000000000)
{
r_len += 9;
goto num_1;
}
else
{
r_len += 10;
goto num_0;
}
}
}
}
num_0:
num = '0';
if (x >= 2000000000) {x -= 2000000000; num += 2;}
if (x >= 1000000000) {x -= 1000000000; num += 1;}
*str = num;
str++;
num_1:
num = '0';
if (x >= 800000000) {x -= 800000000; num += 8;}
if (x >= 400000000) {x -= 400000000; num += 4;}
if (x >= 200000000) {x -= 200000000; num += 2;}
if (x >= 100000000) {x -= 100000000; num += 1;}
*str = num;
str++;
num_2:
num = '0';
if (x >= 80000000) {x -= 80000000; num += 8;}
if (x >= 40000000) {x -= 40000000; num += 4;}
if (x >= 20000000) {x -= 20000000; num += 2;}
if (x >= 10000000) {x -= 10000000; num += 1;}
*str = num;
str++;
num_3:
num = '0';
if (x >= 8000000) {x -= 8000000; num += 8;}
if (x >= 4000000) {x -= 4000000; num += 4;}
if (x >= 2000000) {x -= 2000000; num += 2;}
if (x >= 1000000) {x -= 1000000; num += 1;}
*str = num;
str++;
num_4:
num = '0';
if (x >= 800000) {x -= 800000; num += 8;}
if (x >= 400000) {x -= 400000; num += 4;}
if (x >= 200000) {x -= 200000; num += 2;}
if (x >= 100000) {x -= 100000; num += 1;}
*str = num;
str++;
num_5:
num = '0';
if (x >= 80000) {x -= 80000; num += 8;}
if (x >= 40000) {x -= 40000; num += 4;}
if (x >= 20000) {x -= 20000; num += 2;}
if (x >= 10000) {x -= 10000; num += 1;}
*str = num;
str++;
num_6:
num = '0';
if (x >= 8000) {x -= 8000; num += 8;}
if (x >= 4000) {x -= 4000; num += 4;}
if (x >= 2000) {x -= 2000; num += 2;}
if (x >= 1000) {x -= 1000; num += 1;}
*str = num;
str++;
num_7:
num = '0';
if (x >= 800) {x -= 800; num += 8;}
if (x >= 400) {x -= 400; num += 4;}
if (x >= 200) {x -= 200; num += 2;}
if (x >= 100) {x -= 100; num += 1;}
*str = num;
str++;
num_8:
num = '0';
if (x >= 80) {x -= 80; num += 8;}
if (x >= 40) {x -= 40; num += 4;}
if (x >= 20) {x -= 20; num += 2;}
if (x >= 10) {x -= 10; num += 1;}
*str = num;
str++;
num_9:
*str = (char)('0' + x);
return r_len;
}
int main() {
DWORD t = GetTickCount();
char str[MAX_INT32_STR_LEN];
std::string s;
for (DWORD i = 10000000; i > 0; i--){
int32_to_str(-123456789, &str[0]);
//itostr(-123456789, s);
}
printf("%u", GetTickCount()-t);
return 0;
}
результат: int_to_str(...) в два раза быстрее чем itostr(...) благодаря переменным в регистрах, сложению вместо деления, маленькому бинарному поиску в начале для определения количества символов результата и отсутствию цикла
вот и всё что я делаю для оптимизации, ведь если ключевые циклы программы работают максимально быстро и выжимать уже нечего, то и вся программа работает максимально быстро! :)