Я хотел бы спросить, есть ли более быстрый способ сделать мое преобразование звука, чем путем повторения всех значений один за другим и деления их на 32768.
void CAudioDataItem::Convert(const vector<int>&uIntegers, vector<double> &uDoubles)
{
for ( int i = 0; i <=uIntegers.size()-1;i++)
{
uDoubles[i] = uIntegers[i] / 32768.0;
}
}
Мой подход работает отлично, но это может быть быстрее. Однако я не нашел способ ускорить его.
Спасибо за помощь!
Если ваш массив достаточно велик, возможно, стоит распараллелить это для цикла. OpenMP parallel for - это то, что я буду использовать.
Тогда функция будет:
void CAudioDataItem::Convert(const vector<int>&uIntegers, vector<double> &uDoubles)
{
#pragma omp parallel for
for (int i = 0; i < uIntegers.size(); i++)
{
uDoubles[i] = uIntegers[i] / 32768.0;
}
}
с gcc вам нужно передать -fopenmp при компиляции для pragma, который будет использоваться, на MSVC это /openmp. Поскольку нерестовые потоки имеют заметные накладные расходы, это будет только быстрее, если вы обрабатываете большие массивы, YMMV.
Для максимальной скорости вы хотите конвертировать более одного значения на каждую итерацию цикла. Самый простой способ сделать это - с SIMD. Вот примерно, как вы это сделали бы с SSE2:
void CAudioDataItem::Convert(const vector<int>&uIntegers, vector<double> &uDoubles)
{
__m128d scale = _mm_set_pd( 1.0 / 32768.0, 1.0 / 32768.0 );
int i = 0;
for ( ; i < uIntegers.size() - 3; i += 4)
{
__m128i x = _mm_loadu_si128(&uIntegers[i]);
__m128i y = _mm_shuffle_epi32(x, _MM_SHUFFLE(2,3,0,0) );
__m128d dx = _mm_cvtepi32_pd(x);
__m128d dy = _mm_cvtepi32_pd(y);
dx = _mm_mul_pd(dx, scale);
dy = _mm_mul_pd(dy, scale);
_mm_storeu_pd(dx, &uDoubles[i]);
_mm_storeu_pd(dy, &uDoubles[i + 2]);
}
// Finish off the last 0-3 elements the slow way
for ( ; i < uIntegers.size(); i ++)
{
uDoubles[i] = uIntegers[i] / 32768.0;
}
}
Мы обрабатываем четыре целых числа для каждой итерации цикла. Поскольку мы можем разместить только два двойника в регистрах, там дублируется работа, но дополнительное разворачивание поможет производительности, если массивы не являются крошечными.
Изменение типов данных на более мелкие (например, короткие и плавающие) также должно способствовать повышению производительности, поскольку они сокращают пропускную способность памяти, и вы можете поместить четыре поплавка в регистр SSE. Для аудиоданных вам не нужна точность двойной.
Обратите внимание, что я использовал неуравновешенные нагрузки и магазины. Выровненные будут немного быстрее, если данные фактически выровнены (что не будет по умолчанию, и трудно сделать материал выровненным внутри std::vector).
Ваша функция сильно параллелизуема. На современном процессоре Intel существуют три независимых способа распараллеливания: уровень обучения parallelism (ILP), уровень потока parallelism (TLP) и SIMD. Я смог использовать все три, чтобы получить большие повышения в вашей функции. Результаты зависят от компилятора. Повышение намного меньше, чем использование GCC, поскольку оно уже векторизует функцию. См. Таблицу цифр ниже.
Однако основным ограничивающим фактором в вашей функции является то, что сложность времени - это только O (n), и поэтому происходит резкое падение эффективности, когда размер массива, который вы используете, пересекает каждый уровень кеша граница. Если вы посмотрите, например, при большом плотном матричном умножении (GEMM), это операция O (n ^ 3), поэтому, если все правильно (с использованием, например, черепичной петли), иерархия кэша не проблема: вы можете приблизиться к максимуму flops/s даже для очень больших матриц (что, по-видимому, указывает на то, что GEMM является одним из тех, кого думает Intel, когда они проектируют CPU). Способ исправить это в вашем случае - найти способ выполнить вашу функцию в блоке кеша L1 сразу после/до того, как вы выполните более сложную операцию (например, это будет как O (n ^ 2)), а затем перейдите к другому L1. Конечно, я не знаю, что вы делаете, поэтому я не могу этого сделать.
ILP частично выполняется для вас аппаратным обеспечением ЦП. Однако часто несущие зависимости цикла ограничивают ILP, поэтому часто помогают разворачивать петли, чтобы в полной мере использовать ILP. Для TLP я использую OpenMP, а для SIMD я использовал AVX (однако приведенный ниже код работает и для SSE). Я использовал 32-батную выровненную память и убедился, что массив был кратным 8, так что никакой очистки не было.
Вот результаты из 64-битной версии Visual Studio 2012 с AVX и OpenMP (конечно, режим выпуска) SandyBridge EP 4 ядра (8 потоков HW) @3,6 ГГц. Переменная n - это количество элементов. Я повторяю функцию несколько раз, поэтому общее время включает это. Функция convert_vec4_unroll2_openmp дает наилучшие результаты, кроме области L1. Вы также можете очистить, что эффективность значительно снижается при каждом переходе на новый уровень кеша, но даже для основной памяти это еще лучше.
l1 chache, n 2752, repeat 300000
covert time 1.34, error 0.000000
convert_vec4 time 0.16, error 0.000000
convert_vec4_unroll2 time 0.16, error 0.000000
convert_vec4_unroll2_openmp time 0.31, error 0.000000
l2 chache, n 21856, repeat 30000
covert time 1.14, error 0.000000
convert_vec4 time 0.24, error 0.000000
convert_vec4_unroll2 time 0.24, error 0.000000
convert_vec4_unroll2_openmp time 0.12, error 0.000000
l3 chache, n 699072, repeat 1000
covert time 1.23, error 0.000000
convert_vec4 time 0.44, error 0.000000
convert_vec4_unroll2 time 0.45, error 0.000000
convert_vec4_unroll2_openmp time 0.14, error 0.000000
main memory , n 8738144, repeat 100
covert time 1.56, error 0.000000
convert_vec4 time 0.95, error 0.000000
convert_vec4_unroll2 time 0.89, error 0.000000
convert_vec4_unroll2_openmp time 0.51, error 0.000000
Результаты с g++ foo.cpp -mavx -fopenmp -ffast-math -O3 на i5-3317 (мост плюща) @2,4 ГГц 2 ядра (4 потока HW). GCC, кажется, векторизует это, и единственное преимущество от OpenMP (которое, однако, дает худший результат в области L1).
l1 chache, n 2752, repeat 300000
covert time 0.26, error 0.000000
convert_vec4 time 0.22, error 0.000000
convert_vec4_unroll2 time 0.21, error 0.000000
convert_vec4_unroll2_openmp time 0.46, error 0.000000
l2 chache, n 21856, repeat 30000
covert time 0.28, error 0.000000
convert_vec4 time 0.27, error 0.000000
convert_vec4_unroll2 time 0.27, error 0.000000
convert_vec4_unroll2_openmp time 0.20, error 0.000000
l3 chache, n 699072, repeat 1000
covert time 0.80, error 0.000000
convert_vec4 time 0.80, error 0.000000
convert_vec4_unroll2 time 0.80, error 0.000000
convert_vec4_unroll2_openmp time 0.83, error 0.000000
main memory chache, n 8738144, repeat 100
covert time 1.10, error 0.000000
convert_vec4 time 1.10, error 0.000000
convert_vec4_unroll2 time 1.10, error 0.000000
convert_vec4_unroll2_openmp time 1.00, error 0.000000
Вот код. Я использую vectorclass http://www.agner.org/optimize/vectorclass.zip для выполнения SIMD. Это будет использовать либо AVX для записи 4 двухлокальных за один раз, либо SSE, чтобы сразу записать 2 удвоения.
#include <stdlib.h>
#include <stdio.h>
#include <omp.h>
#include "vectorclass.h"
void convert(const int *uIntegers, double *uDoubles, const int n) {
for ( int i = 0; i<n; i++) {
uDoubles[i] = uIntegers[i] / 32768.0;
}
}
void convert_vec4(const int *uIntegers, double *uDoubles, const int n) {
Vec4d div = 1.0/32768;
for ( int i = 0; i<n; i+=4) {
Vec4i u4i = Vec4i().load(&uIntegers[i]);
Vec4d u4d = to_double(u4i);
u4d*=div;
u4d.store(&uDoubles[i]);
}
}
void convert_vec4_unroll2(const int *uIntegers, double *uDoubles, const int n) {
Vec4d div = 1.0/32768;
for ( int i = 0; i<n; i+=8) {
Vec4i u4i_v1 = Vec4i().load(&uIntegers[i]);
Vec4d u4d_v1 = to_double(u4i_v1);
u4d_v1*=div;
u4d_v1.store(&uDoubles[i]);
Vec4i u4i_v2 = Vec4i().load(&uIntegers[i+4]);
Vec4d u4d_v2 = to_double(u4i_v2);
u4d_v2*=div;
u4d_v2.store(&uDoubles[i+4]);
}
}
void convert_vec4_openmp(const int *uIntegers, double *uDoubles, const int n) {
#pragma omp parallel for
for ( int i = 0; i<n; i+=4) {
Vec4i u4i = Vec4i().load(&uIntegers[i]);
Vec4d u4d = to_double(u4i);
u4d/=32768.0;
u4d.store(&uDoubles[i]);
}
}
void convert_vec4_unroll2_openmp(const int *uIntegers, double *uDoubles, const int n) {
Vec4d div = 1.0/32768;
#pragma omp parallel for
for ( int i = 0; i<n; i+=8) {
Vec4i u4i_v1 = Vec4i().load(&uIntegers[i]);
Vec4d u4d_v1 = to_double(u4i_v1);
u4d_v1*=div;
u4d_v1.store(&uDoubles[i]);
Vec4i u4i_v2 = Vec4i().load(&uIntegers[i+4]);
Vec4d u4d_v2 = to_double(u4i_v2);
u4d_v2*=div;
u4d_v2.store(&uDoubles[i+4]);
}
}
double compare(double *a, double *b, const int n) {
double diff = 0.0;
for(int i=0; i<n; i++) {
double tmp = a[i] - b[i];
//printf("%d %f %f \n", i, a[i], b[i]);
if(tmp<0) tmp*=-1;
diff += tmp;
}
return diff;
}
void loop(const int n, const int repeat, const int ifunc) {
void (*fp[4])(const int *uIntegers, double *uDoubles, const int n);
int *a = (int*)_mm_malloc(sizeof(int)* n, 32);
double *b1_cmp = (double*)_mm_malloc(sizeof(double)*n, 32);
double *b1 = (double*)_mm_malloc(sizeof(double)*n, 32);
double dtime;
const char *fp_str[] = {
"covert",
"convert_vec4",
"convert_vec4_unroll2",
"convert_vec4_unroll2_openmp",
};
for(int i=0; i<n; i++) {
a[i] = rand()*RAND_MAX;
}
fp[0] = convert;
fp[1] = convert_vec4;
fp[2] = convert_vec4_unroll2;
fp[3] = convert_vec4_unroll2_openmp;
convert(a, b1_cmp, n);
dtime = omp_get_wtime();
for(int i=0; i<repeat; i++) {
fp[ifunc](a, b1, n);
}
dtime = omp_get_wtime() - dtime;
printf("\t%s time %.2f, error %f\n", fp_str[ifunc], dtime, compare(b1_cmp,b1,n));
_mm_free(a);
_mm_free(b1_cmp);
_mm_free(b1);
}
int main() {
double dtime;
int l1 = (32*1024)/(sizeof(int) + sizeof(double));
int l2 = (256*1024)/(sizeof(int) + sizeof(double));
int l3 = (8*1024*1024)/(sizeof(int) + sizeof(double));
int lx = (100*1024*1024)/(sizeof(int) + sizeof(double));
int n[] = {l1, l2, l3, lx};
int repeat[] = {300000, 30000, 1000, 100};
const char *cache_str[] = {"l1", "l2", "l3", "main memory"};
for(int c=0; c<4; c++ ) {
int lda = ((n[c]+7) & -8); //make sure array is a multiple of 8
printf("%s chache, n %d\n", cache_str[c], lda);
for(int i=0; i<4; i++) {
loop(lda, repeat[c], i);
} printf("\n");
}
}
Наконец, любой, кто прочитал это далеко и чувствует, как напоминать мне, что мой код больше похож на C, чем на С++, прочитайте это сначала, прежде чем вы решите прокомментировать http://www.stroustrup.com/sibling_rivalry.pdf
Вы также можете попробовать:
uDoubles[i] = ldexp((double)uIntegers[i], -15);
Изменить:. См. ответ Адама выше для версии с использованием встроенных функций SSE. Лучше, чем я здесь...
Чтобы сделать это более полезным, давайте посмотрим на код, сгенерированный компилятором. Я использую gcc 4.8.0 и да, стоит проверить ваш конкретный компилятор (версию), так как есть довольно значительные различия в выходе, например, gcc 4.4, 4.8, clang 3.2 или Intel icc.
Ваш оригинал, используя g++ -O8 -msse4.2 ..., преобразуется в следующий цикл:
.L2:
cvtsi2sd (%rcx,%rax,4), %xmm0
mulsd %xmm1, %xmm0
addl $1, %edx
movsd %xmm0, (%rsi,%rax,8)
movslq %edx, %rax
cmpq %rdi, %rax
jbe .L2
где %xmm1 содержит 1.0/32768.0, поэтому компилятор автоматически превращает деление в умножение на обратное.
С другой стороны, используя g++ -msse4.2 -O8 -funroll-loops ..., код, созданный для цикла, значительно изменяется:
[ ... ]
leaq -1(%rax), %rdi
movq %rdi, %r8
andl $7, %r8d
je .L3
[ ... insert a duff device here, up to 6 * 2 conversions ... ]
jmp .L3
.p2align 4,,10
.p2align 3
.L39:
leaq 2(%rsi), %r11
cvtsi2sd (%rdx,%r10,4), %xmm9
mulsd %xmm0, %xmm9
leaq 5(%rsi), %r9
leaq 3(%rsi), %rax
leaq 4(%rsi), %r8
cvtsi2sd (%rdx,%r11,4), %xmm10
mulsd %xmm0, %xmm10
cvtsi2sd (%rdx,%rax,4), %xmm11
cvtsi2sd (%rdx,%r8,4), %xmm12
cvtsi2sd (%rdx,%r9,4), %xmm13
movsd %xmm9, (%rcx,%r10,8)
leaq 6(%rsi), %r10
mulsd %xmm0, %xmm11
mulsd %xmm0, %xmm12
movsd %xmm10, (%rcx,%r11,8)
leaq 7(%rsi), %r11
mulsd %xmm0, %xmm13
cvtsi2sd (%rdx,%r10,4), %xmm14
mulsd %xmm0, %xmm14
cvtsi2sd (%rdx,%r11,4), %xmm15
mulsd %xmm0, %xmm15
movsd %xmm11, (%rcx,%rax,8)
movsd %xmm12, (%rcx,%r8,8)
movsd %xmm13, (%rcx,%r9,8)
leaq 8(%rsi), %r9
movsd %xmm14, (%rcx,%r10,8)
movsd %xmm15, (%rcx,%r11,8)
movq %r9, %rsi
.L3:
cvtsi2sd (%rdx,%r9,4), %xmm8
mulsd %xmm0, %xmm8
leaq 1(%rsi), %r10
cmpq %rdi, %r10
movsd %xmm8, (%rcx,%r9,8)
jbe .L39
[ ... out ... ]
Таким образом, он блокирует операции вверх, но все равно преобразует одно значение по времени.
Если вы измените исходный цикл для работы с несколькими элементами на итерацию:
size_t i;
for (i = 0; i < uIntegers.size() - 3; i += 4)
{
uDoubles[i] = uIntegers[i] / 32768.0;
uDoubles[i+1] = uIntegers[i+1] / 32768.0;
uDoubles[i+2] = uIntegers[i+2] / 32768.0;
uDoubles[i+3] = uIntegers[i+3] / 32768.0;
}
for (; i < uIntegers.size(); i++)
uDoubles[i] = uIntegers[i] / 32768.0;
компилятор gcc -msse4.2 -O8 ... (т.е. даже без запроса разворачивания), идентифицирует потенциал использования CVTDQ2PD/MULPD, а ядро цикла будет:
.p2align 4,,10
.p2align 3
.L4:
movdqu (%rcx), %xmm0
addq $16, %rcx
cvtdq2pd %xmm0, %xmm1
pshufd $238, %xmm0, %xmm0
mulpd %xmm2, %xmm1
cvtdq2pd %xmm0, %xmm0
mulpd %xmm2, %xmm0
movlpd %xmm1, (%rdx,%rax,8)
movhpd %xmm1, 8(%rdx,%rax,8)
movlpd %xmm0, 16(%rdx,%rax,8)
movhpd %xmm0, 24(%rdx,%rax,8)
addq $4, %rax
cmpq %r8, %rax
jb .L4
cmpq %rdi, %rax
jae .L29
[ ... duff device style for the "tail" ... ]
.L29:
rep ret
т.е. теперь компилятор распознает возможность поместить два double на регистр SSE и выполнить параллельное умножение/преобразование. Это довольно близко к коду, который генерирует версия встроенного ASA.
Итоговый код (я показал только около 1/6 его) намного сложнее, чем "прямые" свойства, из-за того, что, как уже упоминалось, компилятор пытается добавить/добавить unaligned/not -block-multiple "heads" и "tail" для цикла. Это во многом зависит от средних/ожидаемых размеров ваших векторов, будет ли это выгодно или нет; для "общего" случая (векторы, более чем в два раза превышающие размер блока, обработанного "самым внутренним" циклом), это поможет.
Результат этого упражнения в основном... что, если вы принуждаете (по параметрам/оптимизации компилятора) или намекаете (слегка переставляя код) свой компилятор, чтобы делать правильные вещи, то для этого конкретного типа копии /convert, он содержит код, который не будет сильно отличаться от написанных вручную.
Заключительный эксперимент... сделайте код:
static double c(int x) { return x / 32768.0; }
void Convert(const std::vector<int>& uIntegers, std::vector<double>& uDoubles)
{
std::transform(uIntegers.begin(), uIntegers.end(), uDoubles.begin(), c);
}
и (для наиболее удобного для чтения сборки, на этот раз с использованием gcc 4.4 с gcc -O8 -msse4.2 ...) сгенерированный цикл ядра сборки (опять же, бит до/после):
.p2align 4,,10
.p2align 3
.L8:
movdqu (%r9,%rax), %xmm0
addq $1, %rcx
cvtdq2pd %xmm0, %xmm1
pshufd $238, %xmm0, %xmm0
mulpd %xmm2, %xmm1
cvtdq2pd %xmm0, %xmm0
mulpd %xmm2, %xmm0
movapd %xmm1, (%rsi,%rax,2)
movapd %xmm0, 16(%rsi,%rax,2)
addq $16, %rax
cmpq %rcx, %rdi
ja .L8
cmpq %rbx, %rbp
leaq (%r11,%rbx,4), %r11
leaq (%rdx,%rbx,8), %rdx
je .L10
[ ... ]
.L10:
[ ... ]
ret
С этим, что мы узнаем? Если вы хотите использовать С++, действительно используйте С++; -)
Позвольте мне попробовать другой способ:
Если умножение с точки зрения инструкций сборки значительно лучше, тогда это должно гарантировать, что оно будет умножено.
void CAudioDataItem::Convert(const vector<int>&uIntegers, vector<double> &uDoubles)
{
for ( int i = 0; i <=uIntegers.size()-1;i++)
{
uDoubles[i] = uIntegers[i] * 0.000030517578125;
}
}