пятница, 10 декабря 2010 г.

std::vector vs plain array

Йоханга.

Сегодня хочу вам немного рассказать о C++. Это мой любимый язык программирования, несмотря на все его достоинства и недостатки (-: .

Часто на просторах интернета, да и не только, я слышу, что раньше трава была зеленее, собаки толще, а С быстрее С++. К примеру, мол, работа с массивами. Доступ по индексу вот в таком коде:

int *arr = new[100];

arr[99] = 1;

Быстрее, чем вот в таком:

std::vector arr(100);

arr[99] = 1;

Предлагаю простой пример. Есть алгоритм, изначально написанный на "чистом С".

По словам автора функции:

Код IDCT в JPEG декодере, мною реализован, работает с матрицами
превращает все элементы matrix из частот в значения цветовых компонент

Вот код:

#define JPEG_COS1 363604
#define JPEG_COS2 342507
#define JPEG_COS3 308248
#define JPEG_SIN1 72325
#define JPEG_SIN2 141871
#define JPEG_SIN3 205965
#define JPEG_SQRT2 185364

static void __fastcall JpegIDCTс(long *matrix)
{
long tmp[64], *ptr1, *ptr2;
long a0, a1, a2, a3, a4, a5, a6, a7;
long b0, b1, b2, b3, b4, b5, b6, b7;
long c0, c1, c2, c3;
long r;
int t;

ptr1 = matrix;
ptr2 = tmp;
t = 8;
while(t--)
{
a0 = *ptr1;
ptr1++;
a4 = *ptr1;
ptr1++;
a2 = *ptr1;
ptr1++;
a6 = *ptr1;
ptr1++;
a1 = *ptr1;
ptr1++;
a5 = *ptr1;
ptr1++;
a3 = *ptr1;
ptr1++;
a7 = *ptr1;
ptr1++;

c0 = (a0 + a1);
c1 = (a0 - a1);
r = JPEG_SIN2 * (a2 + a3);
c2 = (r - (JPEG_SIN2+JPEG_COS2) * a3) >> 18;
c3 = (r - (JPEG_SIN2-JPEG_COS2) * a2) >> 18;
r = JPEG_SIN1 * (a4 + a7);
b4 = (r - (JPEG_SIN1+JPEG_COS1) * a7) >> 18;
b7 = (r - (JPEG_SIN1-JPEG_COS1) * a4) >> 18;
r = JPEG_COS3 * (a5 + a6);
b5 = (r - (JPEG_COS3+JPEG_SIN3) * a6) >> 18;
b6 = (r - (JPEG_COS3-JPEG_SIN3) * a5) >> 18;

a4 = b4 + b5;
a5 = b5 - b4;
a6 = b7 - b6;
a7 = b7 + b6;

b5 = a6 + a5;
b6 = a6 - a5;

a5 = (JPEG_SQRT2*b5) >> 18;
a6 = (JPEG_SQRT2*b6) >> 18;

b0 = c0 + c3;
b1 = c1 + c2;
b2 = c1 - c2;
b3 = c0 - c3;

*ptr2 = (b0 + a7);
ptr2++;
*ptr2 = (b1 + a6);
ptr2++;
*ptr2 = (b2 + a5);
ptr2++;
*ptr2 = (b3 + a4);
ptr2++;
*ptr2 = (b3 - a4);
ptr2++;
*ptr2 = (b2 - a5);
ptr2++;
*ptr2 = (b1 - a6);
ptr2++;
*ptr2 = (b0 - a7);
ptr2++;
}
ptr1 = matrix;
ptr2 = tmp;
t = 8;
while(t--)
{
a0 = ptr2[(0 << a1 =" ptr2[(4" a2 =" ptr2[(2" a3 =" ptr2[(6" a4 =" ptr2[(1" a5 =" ptr2[(5" a6 =" ptr2[(3" a7 =" ptr2[(7" c0 =" (a0" c1 =" (a0" r =" JPEG_SIN2" c2 =" (r">> 18;
c3 = (r - (JPEG_SIN2-JPEG_COS2) * a2) >> 18;
r = JPEG_SIN1 * (a4 + a7);
b4 = (r - (JPEG_SIN1+JPEG_COS1) * a7) >> 18;
b7 = (r - (JPEG_SIN1-JPEG_COS1) * a4) >> 18;
r = JPEG_COS3 * (a5 + a6);
b5 = (r - (JPEG_COS3+JPEG_SIN3) * a6) >> 18;
b6 = (r - (JPEG_COS3-JPEG_SIN3) * a5) >> 18;

a4 = b4 + b5;
a5 = b5 - b4;
a6 = b7 - b6;
a7 = b7 + b6;

b5 = a6 + a5;
b6 = a6 - a5;

a5 = (JPEG_SQRT2*b5) >> 18;
a6 = (JPEG_SQRT2*b6) >> 18;

b0 = c0 + c3;
b1 = c1 + c2;
b2 = c1 - c2;
  b3 = c0 - c3;

ptr1[(0 <<>> 3;

ptr1[(1 <<>> 3;

ptr1[(2 <<>> 3;

ptr1[(3 <<>> 3;

ptr1[(4 <<>> 3;

ptr1[(5 <<>> 3;

ptr1[(6 <<>> 3;

ptr1[(7 <<>> 3;
ptr1++;
ptr2++;
}
}

Достаточно плотная работа с массивом.

Что мы тут имеем? Имеем работу с динамическим массивом, эквивалент которого в С++ это std::vector и статический массив, эквивалента которого в стандартной библиотеке С++ пока что нет, но зато есть эквивалент в бусте: boost::array.

Итак, меняем следующие вещи:

0) Копируем функцию куда-нибудь и называем ее JpegIDCTcpp.

1) Входящий параметр делаем std::vector &

2) Переменную long tmp[64]; меняем на boost::array tmp;

3) Указтель long *ptr1; меняем на std::vector::iterator ptr1;

4) Указатель long *ptr2; меняем на boost::array::iterator ptr2;


Пишем следующий тест:

int main()

{   // First function   Collect v(64);

   unsigned long t1 = millis();

   for ( int i = 0; i <>

  {

    JpegIDCTcpp(v);

  }

  unsigned long t2 = millis();

  std::cout << "vector time = "<< (t2 - t1) <<>

  // Second function

  long * a = new long[64];

  t1 = millis();

  for ( int i = 0; i <>

  {

    JpegIDCTc(a);

  }

  t2 = millis();

  std::cout << "array time = "<< (t2 - t1) <<>

  delete []a;

  return 0;

}

Код был оттестирован двумя компиялторами: GCC и входящим в Microsoft Visual Studio 2008. Сразу оговорюсь, что он тестировался на разных компьютерах, поэтому разбежка между ними получилась ощутимая.

Компилируем в gcc c ключем -O2, запускаем:

vector time = 11595
array time = 11485

Компилируем в gcc c ключем -O3, запускаем:

vector time = 8977
array time = 8998

Компилируем nmake, получаем:

vector time = 11237
array time = 3136

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

#define _SECURE_SCL 0

Итак, результаты трех тестов после отключения проверки индексов в релизе следующие:

1.
vector: 3167
array: 3167

2.
vector: 3136
array: 3182

3.
vector: 3183
array: 3229

Разница во всех примерах находится в пределах погрешности, так что скорость можно считать эквивалентной.

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

В чем мораль? Мораль в том, что при одинаковой скорости выполнения код на С++, с использованием шаблонных классов std::vector и boost::array, а тах же их итераторов, намного безопаснее кода "На чистом С": В дебаге есть проверки выхода за пределы массива, есть контроль за памятью и освобождением ресурсов, удобство работы с вектором ни в какое сравнение не идет с "голым массивом".

Надеюсь, вы сделаете правильный выбор.

Здесь можно скачать весь пример.

Так же можно посмотреть ветвь дискуссии здесь.

среда, 30 июня 2010 г.

Знакомство с erlang.

Что такое erlang? Erlang - это функциональный язык программирования. Вводных статей в интернете полно, как на русском, так и на практически любом другом языке. Можно почитать на википедии, на хабре, на оффсайте. На оффсайте можно скачать виртуальную машину и утилиты для компиляции, редактирование, работы и т.д. Язык кроссплатформенный, так что можно работать в любой системе. Кое-кто называет его "убийцей java".

Язык был разработан и поддерживается компанией Ericsson. Название с одной стороны относится к Датскому математику Agner Krarup Erlang, а с другой стороны к аббревиатуре Ericsson (Ericsson  language).

Отличительной особенностью языка явлется "легковесность" потоков и независимость их друг от друга, благодаря чему можно создавать приложения с большим количеством потоков. Так же существует множество отличий от привычных мне C++, java, C# и т.д. Во-первых, в Ерланге нет объектов в привычном понимании этого слова, зато есть клиент-серверная архитектура, которая позволяет хранить какие-то данные между операциями. Во-вторых, каждая переменная используется всего один раз. Т.е. раз присвоив переменной значение: MyVar=1, больше MyVar менять нельзя. В-третьих, в этом языке нет циклов. Совсем нет циклов. Все циклические операции выполняются при помощи рекурсии. Рекурсия может быть бесконечной, "переполнения стека" она не вызовет. Основными сущностями языка являются "кортежи" и "списки", работа с которыми осуществляется на уровне синтаксиса. Можно много описывать этот любопытный язык, но я рекомендую пройтись по вышеприведенным ссылкам.  Так же на RSDN есть статья, с которой начинал я.

Зачем же мне нужен этот язык? Может показаться, что он слабоприменим. Однако на Ерланге написан мощнейший XMPP-сервер - "ejabberd". Который затыкает за пояс Wildfire, написанный на Java и даже "Jabberd 2", "Jabberd 1.4", написанные на C/C++. Так же существует веб-сервер Yaws, которому apache в разы уступил при нагрузочных тестах. Чат-система Facebook так же построена на erlang (точнее, на ejabberd). Ну и плюс ко всему прочему, мне это просто надо по работе :)

Напоследок хочу показать алгоритм вычисления факториала:

% Это комментарий.  

-module(fact). % Объявление модуля
-export([fac/1]). % Экпортируемая функция

fac(0) -> 1; % Если пытаемся получить факториал нуля, возвращаем 1
fac(N) -> N * fac(N-1). % Рекурсивно считаем факториал, когда N дойдет до 0, вызовется       %функция выше