рекомендации по ускорению
От: reseacher2011  
Дата: 25.07.11 12:15
Оценка: -1 :)
Прошу высказаться о возможностях ускорения кода, путем грамотного его написанья для указанных ниже кусков. Т.е. есть ли здесь какие-то приемы, позволяющие получить максимально быструю программу?

void dot_product(const double* x, const double* y, double *scalar){
    *scalar = *x*(*y)+*(x+1)*(*(y+1))+*(x+2)*(*(y+2));
}
void cross_product(const double* x, const double* y, double *vector){
   *vector     =   *(x+1)*(*(y+2)) - *(x+2)*(*(y+1)); 
   *(vector+1) =  - (  *x*(*(y+2)) - *(x+2)*(*y)  );
   *(vector+2) =   *x*(*(y+1))     - *(x+1)*(*y) ; 
}
void module(const double *vect, double *mod){
    *mod = sqrt(pow(*vect,2.)+pow(*(vect+1),2.)+pow(*(vect+2),2.));
}
void dist_segm_point(const double *x, const double *a, const double *b, double *res){
    double dist_ab, proj, r_ab[3], r_ax[3], r_bx[3], tmp_vect[3];
    *r_ab     = *b     - *a;
    *(r_ab+1) = *(b+1) - *(a+1);
    *(r_ab+2) = *(b+2) - *(a+2);
    *r_ax     = *x     - *a;
    *(r_ax+1) = *(x+1) - *(a+1);
    *(r_ax+2) = *(x+2) - *(a+2);
    *r_bx     = *x     - *b;
    *(r_bx+1) = *(x+1) - *(b+1);
    *(r_bx+2) = *(x+2) - *(b+2);
    module(r_ab,&dist_ab);
    dot_product(r_ax,r_ab,&proj);
    proj /= dist_ab;
    if( proj<0 ){
        module(r_ax,res);
    } else if ( proj > dist_ab ){
        module(r_bx,res);
    } else {
       cross_product(r_ab,r_ax,tmp_vect);
       module(tmp_vect,res);
       *res /= dist_ab; 
    }
}

// ...
// эти и другие функции  нужны для  процедуры заполнения матрицы
// и вызываются только в ней:

void matrix_maker( const int n_row, const double* vect_row, const int n_col, const double* vect_col, ... , double* mtx) 
{
   int i,j;
   double xi1,yi1,zi1, ... ; 
   double xj1,yj1,zj1, ...;
   const double* ptr_j;
   for(i=0; i<n_row; ++i) {
       xi1 = *(vect_row++);
       yi1 = *(vect_row++);
       ...
       ptr_j = vect_col;
       for(j=0; j<n_col-1; ++j){
           xj1 = *(ptr_j++);
           yj1 = *(ptr_j++);
           ...
           *(mtx++) = ... ;
..


25.07.11 17:53: Перенесено модератором из 'C/C++' — Odi$$ey
Re: рекомендации по ускорению
От: Vzhyk  
Дата: 25.07.11 12:23
Оценка: +1 -1
25.07.2011 15:15, reseacher2011 пишет:

> Прошу высказаться о возможностях ускорения кода, путем грамотного его

> написанья для указанных ниже кусков. Т.е. есть ли здесь какие-то приемы,
> позволяющие получить максимально быструю программу?
>
> void dot_product(const double* x,const double* y,double *scalar){
> *scalar = *x*(*y)+*(x+1)*(*(y+1))+*(x+2)*(*(y+2));
> }
> void cross_product(const double* x,const double* y,double *vector){
> *vector = *(x+1)*(*(y+2)) — *(x+2)*(*(y+1));
> *(vector+1) = — ( *x*(*(y+2)) — *(x+2)*(*y) );
> *(vector+2) = *x*(*(y+1)) — *(x+1)*(*y) ;
> }
> void module(const double *vect,double *mod){
> *mod = sqrt(pow(*vect,2.)+pow(*(vect+1),2.)+pow(*(vect+2),2.));
Жесть.
Переписал бы ты сначала все нормальным языком, чтобы читать можно было
(не бойся никто твой код не уворует, не надо так его обфусцировать).
А потом запустил бы профилеровщик, посмотрел где и что и почему медленно.
Posted via RSDN NNTP Server 2.1 beta
Re: рекомендации по ускорению
От: Erop Россия  
Дата: 25.07.11 12:32
Оценка: 1 (1) +1 :)
Здравствуйте, reseacher2011, Вы писали:

R>
R>void dot_product(const double* x, const double* y, double *scalar){
R>    *scalar = *x*(*y)+*(x+1)*(*(y+1))+*(x+2)*(*(y+2));
R>}
R>void cross_product(const double* x, const double* y, double *vector){
R>   *vector     =   *(x+1)*(*(y+2)) - *(x+2)*(*(y+1)); 
R>   *(vector+1) =  - (  *x*(*(y+2)) - *(x+2)*(*y)  );
R>   *(vector+2) =   *x*(*(y+1))     - *(x+1)*(*y) ; 
R>}
R>void module(const double *vect, double *mod){
R>    *mod = sqrt(pow(*vect,2.)+pow(*(vect+1),2.)+pow(*(vect+2),2.));
R>}
R>void dist_segm_point(const double *x, const double *a, const double *b, double *res){
R>    double dist_ab, proj, r_ab[3], r_ax[3], r_bx[3], tmp_vect[3];
R>..
R>


1) Сообщу на всякий случай, что double *x и double x[3] в описании ПАРАМЕТРОВ функции ОБОЗНАЧАЮТ ОДНО И ТО ЖЕ
2) Ещё сообщу, что для указателей записи *(x+1) и x[1] ТОЖЕ ЭКВИВАЛЕНТНЫ.

Так что лучше писать ПОНЯТНЕЕ
double dot_product(const double x[], const double y[])
{
    return x[0]*y[0] + x[1]*y[1] + x[2]*y[2];
}


А что касается ускорения, то хорошо бы ПОНЯТНО объяснить, что надо сделать...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: рекомендации по ускорению
От: reseacher2011  
Дата: 25.07.11 12:34
Оценка:
V>Жесть.
V>Переписал бы ты сначала все нормальным языком, чтобы читать можно было
V>(не бойся никто твой код не уворует, не надо так его обфусцировать).

мне нужно на C.
Re: рекомендации по ускорению
От: LaptevVV Россия  
Дата: 25.07.11 12:35
Оценка:
Здравствуйте, reseacher2011, Вы писали:

R>Прошу высказаться о возможностях ускорения кода, путем грамотного его написанья для указанных ниже кусков. Т.е. есть ли здесь какие-то приемы, позволяющие получить максимально быструю программу?


1. Переписать более простым и понятным способом.
2. Посмотреть в сторону OpenMP. Вроде технология специально создавалась под многоядерность.
То, что я читал — довольно просто и понятно. Сам собираюсь пробовать в ближайшее время.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: рекомендации по ускорению
От: Vzhyk  
Дата: 25.07.11 12:43
Оценка: +2
25.07.2011 15:34, reseacher2011 пишет:

> мне нужно на C.

Только у тебя все падежи неправильные. Зачем ты индексацию выкинул?
Пиши нормальным языком x[i].
Posted via RSDN NNTP Server 2.1 beta
Re[2]: рекомендации по ускорению
От: Vzhyk  
Дата: 25.07.11 12:44
Оценка: :)
25.07.2011 15:32, Erop пишет:

>

> 1) Сообщу на всякий случай, что double *x и double x[3] в описании
> ПАРАМЕТРОВ функции ОБОЗНАЧАЮТ ОДНО И ТО ЖЕ
> 2) Ещё сообщу, что для указателей записи *(x+1) и x[1] ТОЖЕ ЭКВИВАЛЕНТНЫ.
>
> Так что лучше писать ПОНЯТНЕЕ
>
> double dot_product(const double x[],const double y[])
> {
> return x[0]*y[0] + x[1]*y[1] + x[2]*y[2];
> }
>
Терпелив ты, однако.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: рекомендации по ускорению
От: reseacher2011  
Дата: 25.07.11 12:45
Оценка:
E>1) Сообщу на всякий случай, что double *x и double x[3] в описании ПАРАМЕТРОВ функции ОБОЗНАЧАЮТ ОДНО И ТО ЖЕ
E>2) Ещё сообщу, что для указателей записи *(x+1) и x[1] ТОЖЕ ЭКВИВАЛЕНТНЫ.
E>Так что лучше писать ПОНЯТНЕЕ


согласен, что x[2] понятнее. Скорость работы *(x+2) и x[2] одинакова?

E>А что касается ускорения, то хорошо бы ПОНЯТНО объяснить, что надо сделать...


требуется написать процедуру, которая быстро заполнить матрицу больших размеров — это matrix_maker. Процедура пишется для numpy/ctypes из-за того, что ее аналог в Питон работает несколько суток.
Re[2]: рекомендации по ускорению
От: Vzhyk  
Дата: 25.07.11 12:46
Оценка: -1
25.07.2011 15:35, LaptevVV пишет:

> 2. Посмотреть в сторону OpenMP. Вроде технология специально создавалась

> под многоядерность.
> То, что я читал — довольно просто и понятно. Сам собираюсь пробовать в
> ближайшее время.
Вообще-то надо четко осознавать где и для чего она нужна, какие вещи
нужно расспараллеливать, а какие нет.
Думаю, к этому автору еще рано идти.
Posted via RSDN NNTP Server 2.1 beta
Re[2]: рекомендации по ускорению
От: reseacher2011  
Дата: 25.07.11 12:52
Оценка:
LVV>1. Переписать более простым и понятным способом.

не нашел ответы на вопросы

1. равны ли в скорости *(x+i) b x[i]?

1.5. при заполнении матрицы все таки использование ++mtx будет быстрее?

2. я думал что module(vector,&scalar) будет быстрее scalar=module(vector)?

может какие приемы есть и где-то хорошо описаны.

LVV>2. Посмотреть в сторону OpenMP. Вроде технология специально создавалась под многоядерность.


расспараллеливание пока не нужно.
Re[3]: рекомендации по ускорению
От: reseacher2011  
Дата: 25.07.11 12:55
Оценка: -1
Здравствуйте, Vzhyk, Вы писали:

V>Вообще-то надо четко осознавать где и для чего она нужна, какие вещи

V>нужно расспараллеливать, а какие нет.
V>Думаю, к этому автору еще рано идти.

я в вопросе написал " о возможностях ускорения кода, путем грамотного его написанья для указанных ниже кусков.", потому что прекрасно знаю о существовании того же OpenMP и в дальнейшем несколькими директивами распараллелю внешний цикл в matrix_maker.


Вы бы по делу что-то сказали.
Re[3]: рекомендации по ускорению
От: LaptevVV Россия  
Дата: 25.07.11 13:07
Оценка: +2
Здравствуйте, reseacher2011, Вы писали:

LVV>>1. Переписать более простым и понятным способом.

R>не нашел ответы на вопросы
R>1. равны ли в скорости *(x+i) b x[i]?
равны
R>1.5. при заполнении матрицы все таки использование ++mtx будет быстрее?
да
R>2. я думал что module(vector,&scalar) будет быстрее scalar=module(vector)?
Нет. Какая разница, что передавать в стек — объект или адрес?
R>может какие приемы есть и где-то хорошо описаны.
Это все — экономия на спичках.
LVV>>2. Посмотреть в сторону OpenMP. Вроде технология специально создавалась под многоядерность.
R>расспараллеливание пока не нужно.
Если матрицы большие, то выигрыш может быть существенным.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[4]: рекомендации по ускорению
От: Vzhyk  
Дата: 25.07.11 13:11
Оценка: +2
25.07.2011 16:07, LaptevVV пишет:

> Если матрицы большие, то выигрыш может быть существенным.

Если матрицы большие то нужно думать о кэшах и скорости памяти.
Posted via RSDN NNTP Server 2.1 beta
Re[4]: рекомендации по ускорению
От: Vzhyk  
Дата: 25.07.11 13:16
Оценка:
25.07.2011 15:55, reseacher2011 пишет:
>
> Вы бы по делу что-то сказали.
Вот по делу:
Переписал бы ты сначала все нормальным языком, чтобы читать можно было.
А потом запустил бы профилеровщик, посмотрел где и что и почему медленно.

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

И потом бы, найдя "бутылочные горлышки" спрашивал бы. А так твой вопрос
выглядит так: "Вот гора нечитаемого кода выполняющего непонять что,
непонять где. Как мне ускорить этого сферического коня в вакууме?"
Posted via RSDN NNTP Server 2.1 beta
Re: рекомендации по ускорению
От: K13 http://akvis.com
Дата: 25.07.11 13:27
Оценка: 1 (1) +1
R>void module(const double *vect, double *mod){
R>    *mod = sqrt(pow(*vect,2.)+pow(*(vect+1),2.)+pow(*(vect+2),2.));
R>}


pow(x,2.) — это специально чтобы подольше считало?
внутри pow(x,a) работает как exp(log(x)*a) — а логарифм и экспонента не самые дешевые операции.
чем помешало vect[0]*vect[0] ?
Re: рекомендации по ускорению
От: minorlogic Украина  
Дата: 25.07.11 13:44
Оценка: +1
Здравствуйте, reseacher2011, Вы писали:

R>Прошу высказаться о возможностях ускорения кода, путем грамотного его написанья для указанных ниже кусков. Т.е. есть ли здесь какие-то приемы, позволяющие получить максимально быструю программу?


1. использовать хороший компилятор для используемой платформы.
2. Использовать быструю библиотеку линейной алгебры. (типа ublas+ATLAS, ublas+Intel MKL, EIGEN "http://eigen.tuxfamily.org/index.php?title=Main_Page")
3. Искать профайлером узкие места.
4. Переписать на С без С++ (just joke)


если есть желание развиваться в этой области
http://www.agner.org/optimize/optimizing_cpp.pdf
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[2]: рекомендации по ускорению
От: reseacher2011  
Дата: 25.07.11 13:46
Оценка: -1 :)
Здравствуйте, Erop, Вы писали:

E>1) Сообщу на всякий случай, что double *x и double x[3] в описании ПАРАМЕТРОВ функции ОБОЗНАЧАЮТ ОДНО И ТО ЖЕ

E>Так что лучше писать ПОНЯТНЕЕ
E>
E>double dot_product(const double x[], const double y[])
E>{
E>    return x[0]*y[0] + x[1]*y[1] + x[2]*y[2];
E>}
E>


Вот она — красота
/* Subroutine int dgesvd_(char *jobu, char *jobvt, integer *m, integer *n, 
        doublereal *a, integer *lda, doublereal *s, doublereal *u, integer *
        ldu, doublereal *vt, integer *ldvt, doublereal *work, integer *lwork, 
        integer *info)
*/

    dgesvd_( &JOBU, &JOBVT, &M, &N, a, &LDA, s, uu, 
          &LDU, vt, &LDVT, wk, &LWORK, &INFO);
Re[3]: рекомендации по ускорению
От: minorlogic Украина  
Дата: 25.07.11 13:53
Оценка:
Здравствуйте, reseacher2011, Вы писали:

LVV>>1. Переписать более простым и понятным способом.


R>не нашел ответы на вопросы


R>1. равны ли в скорости *(x+i) b x[i]?


Смотрите в асемблерный листинг скомпилированного кода.

R>1.5. при заполнении матрицы все таки использование ++mtx будет быстрее?


Смотрите в асемблерный листинг скомпилированного кода.


R>2. я думал что module(vector,&scalar) будет быстрее scalar=module(vector)?


Может быть быстрее , а может не быть. Сильно зависит от компилятора и внутренностей "module"

R>может какие приемы есть и где-то хорошо описаны.


Конечно описаны.
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[3]: рекомендации по ускорению
От: Vzhyk  
Дата: 25.07.11 13:55
Оценка: +1
25.07.2011 16:46, reseacher2011 пишет:

>

> Вот она — красота <http://www.netlib.org/clapack/faq.html&gt;
>
> /* Subroutine int dgesvd_(char *jobu, char *jobvt, integer *m, integer *n,
> doublereal *a, integer *lda, doublereal *s, doublereal *u, integer *
> ldu, doublereal *vt, integer *ldvt, doublereal *work, integer *lwork,
> integer *info)
> */
>
> dgesvd_(&JOBU,&JOBVT,&M,&N, a,&LDA, s, uu,
> &LDU, vt,&LDVT, wk,&LWORK,&INFO);
>

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

З.Ы. Сначала осознай, почему в лапаке такие функции.
Posted via RSDN NNTP Server 2.1 beta
Re: рекомендации по ускорению
От: jazzer Россия Skype: enerjazzer
Дата: 25.07.11 13:58
Оценка: 2 (2)
Здравствуйте, reseacher2011, Вы писали:

R>Прошу высказаться о возможностях ускорения кода, путем грамотного его написанья для указанных ниже кусков. Т.е. есть ли здесь какие-то приемы, позволяющие получить максимально быструю программу?


тут все очень плохо с точки зрения алиасинга.
Компилятор не знает, могут ли разные указатели указывать на одно и то же, и поэтмоу после каждого присваивания будет перечитывать значения из памяти — а вдруг ты туда только что и записал как раз?
Я так понимаю, у тебя невозможно, чтобы аргументы указывали на одну и ту же память, даже со сдвигами.
Тогда используй restrict на всех своих параметрах-указателях.
Также используй локальные переменные — с ними компилятору гораздо легче справляться, так как они точно алиаситься не будут и их можно спокойно по регистрам раскидать:
void cross_product(const double* __restrict__ x, const double* __restrict__  y, double * __restrict__ vector)
{
   const double x0 = x[0], x1 = x[1], x2 = x[2];
   const double y0 = y[0], y1 = y[1], y2 = y[2];

   vector[0] = x1*y2 - x2*y1; 
   vector[1] = x2*y0 - x0*y2;
   vector[2] = x0*y1 - x1*y0; 
}

заодно и код станет понятнее.
Можешь сравнить дизассемблер.

Ну а следующий шаг — это юзать векторные инструкции процессора, например, DPPD для dot_product.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.