Вопросы в основном по оптимизации быстродействия.

[Morkonwen]

Здравствуйте, новичок и пишу программу которая будет выполняться несколько дней. никаких понятий сложнее матриц в ней нет, так что хочется сделать ее как можно более быстрой, пусть и в ущерб удобочитаемости. В связи с этим несколько вопросов:
1)Слышал, что обращение к оперативке на порядок дольше, чем обращение к регистрам процессора. Работа с последними возможна на ассемблере. А на с++?
2) вроде бы есть несколько видов оперативной памяти по скорости работы. какие комманды типа сallock позволяют с ними работать?
3)насколько быстро работает reallock и правильно ли я понимаю, что лучше выделять сразу и много, чем немного и по частям?
4) Можно ли быстро узнать размер массива без записывания его размера в другую переменную?

5)Слышал, что вызов функции сам по себе занимает определенное время и в некоторых случаях чтобы этого избежать надо использовать некие макросы. что это значит?

6)я связанные списки делаю так: выделяю массив структур. в структуре две переменные-собственно значение и номер элемента в массиве в котором записан следующий по списку элемент.но ведь, если я понимаю правильно, каждый раз компьютеру приходится вычислять адрес следующего элемента. Как сделать связанный список более естественно, у меня не получается объявить структуру в которой будет указатель на нее же. типа

 typedef struct {

     stru0 *pointer;
     double value;
}stru0;

Заранее спасибо за ответы!

[Carbon]

А у меня всего один вопрос: ваша программа тормозит что ли? Зачем так со скоростью заморачиваться?

[Morkonwen]

Тормозит для нее не тот термин=) просто очень долго выполняется порядка 10-ти дней. и сократить это время хотя бы на пол дня (5%) уже было бы здорово

[pu4koff]

Сообщение от Morkonwen

1)Слышал, что обращение к оперативке на порядок дольше, чем обращение к регистрам процессора. Работа с последними возможна на ассемблере. А на с++?

А на С++ есть встраиваемый асемблер.

Сообщение от Morkonwen

2) вроде бы есть несколько видов оперативной памяти по скорости работы. какие комманды типа сallock позволяют с ними работать?

Есть стек, который быстрее и безопаснее, но его объем ограничен. Есть еще и куча, она медленнее, но зато с объемами попроще.
int i - создаёт переменную на стеке.
int * i = new int; - в куче

Сообщение от Morkonwen

3)насколько быстро работает reallock и правильно ли я понимаю, что лучше выделять сразу и много, чем немного и по частям?

reallock сначала смотрит, можно ли просто правую границу выделенного блока памяти переместить, чтобы увеличить его объем. Если не получится так просто сделать, то выделяется новый блок и в него копируется содержимое текущего блока. На каждый чих делать reallock - не желательно. Лучше с памятью работать как класс vector из стандартной плюсовой библиотеки.

Сообщение от Morkonwen

4) Можно ли быстро узнать размер массива без записывания его размера в другую переменную?

int a[10];
cout << sizeof(a);

Если память под массив выделяется динамически, то уже не всё так просто будет. Проще использовать std::vector

Сообщение от Morkonwen

5)Слышал, что вызов функции сам по себе занимает определенное время и в некоторых случаях чтобы этого избежать надо использовать некие макросы. что это значит?

Макросы обрабатываются препроцессором и вместо их вызова подставляется сам код, т.е. вызова макроса никакого не будет, а программа по сути будет не из функций состоять, а монолит эдакий. Если макрос будет объемным, то объем программы будет нелогично большим. Лучше использовать inline функции.

Сообщение от Morkonwen

6)я связанные списки делаю так: выделяю массив структур. в структуре две переменные-собственно значение и номер элемента в массиве в котором записан следующий по списку элемент.но ведь, если я понимаю правильно, каждый раз компьютеру приходится вычислять адрес следующего элемента. Как сделать связанный список более естественно, у меня не получается объявить структуру в которой будет указатель на нее же. типа

 typedef struct {

     stru0 *pointer;
     double value;
}stru0;

Это у Вас какой-то неправильный массив получается, а не список. Берите готовый std::list или ручками:

struct my_struct
{
  double value;
  my_struct *next;
};

и реализовывать добавление элементов в список и т.д. и т.п.

Вообще преждевременная оптимизация - зло. Сделайте хоть что-то хоть как-то, а уже если будет медленно работать, то искать узкие места в коде и переписывать их на ассемблере или еще какую оптимизацию проводить. На макросах я бы вообще оптимизировать не стал, да и на ассемблере. Судя по вопросам, с асмом не знакомы, а значит лучше оптимизатора код не напишите. Отдайте код компилятору и пусть он с ним делает то, что посчитает нужным. Современные оптимизаторы умеют функции самостоятельно делать inline или оставлять "нормальными" на основе времени исполнения тела функции. В общем, не заморачивайтесь раньше времени.

Сообщение от Morkonwen

Тормозит для нее не тот термин=) просто очень долго выполняется порядка 10-ти дней. и сократить это время хотя бы на пол дня (5%) уже было бы здорово

Уверены, что нужно оптимизировать не алгоритм, а именно доступ к памяти, её выделение и т.п.?

[NiCola999]

это что же за программа такая, что работает 10 дней о_О. Сортировка матриц 1000 на 1000 методом пузырька?))
Простейшие программы выполняются доли секунд, че у вас за прога такая? Интересно посмотреть на исходник. Может там что-то типо
Sleep(900000000); =))

[Carbon]

Если приспичило оптимизировать. То нужно начинать с самого медленного:

1) сеть, операции ввода/вывода, межпроцессовое взаимодействие
2) возможно что-то можно распараллелить
3) оптимизация циклов
4) оптимизация памяти
5) оптимизиция операций

Не надо сразу лезть переписывать на асме. Вы рискуете заниматься секасом неделю и больше. А в итоге прироста в скорости не заметить. Компилятор ведь тоже не пальцем делан. Кстати, покопайтесь в его настройках.
Может как оптимизируете самые тяжёлые участки, остальное уже нафиг не нужны.

Что всё-таки за задача? Что она использует? Может мы чем поможем? Просто вы нам перечислили то, что нужно оптимизировать, если ничего не помогает.

И таки да, может у вас просто алгоритм кривой.

[netrino]

В общем согласен с pu4koff, попробуйте воспользоваться стандартной библиотекой, это будет проще и довольно быстро. Если есть возможность, то в 2010 студии, так как она там получше оптимизирована. Некоторую долю производительности можно выиграть за счёт ключей компилятора, например включить использование SSE. Безусловно компилировать окончательный результат нужно в Release-сборке. Из других оптимизаций, можно вручную разворачивать циклы, ну или писать так, чтобы их хорошо смог развернуть компилятор. Также можете воспользоваться профайлерами, дабы увидеть, на какую часть программы уходит больше всего процессорного времени и максимально оптимизировать этот участок

[Morkonwen]

Сообщение от pu4koff

А на С++ есть встраиваемый асемблер.

Есть стек, который быстрее и безопаснее, но его объем ограничен. Есть еще и куча, она медленнее, но зато с объемами попроще.
int i - создаёт переменную на стеке.
int * i = new int; - в куче

То есть объявление простое и привычное объявление создает переменную сразу в быстрой области памяти? callock насколько я слышал это делает в куче?

Сообщение от pu4koff

int a[10];
cout << sizeof(a);

Если память под массив выделяется динамически, то уже не всё так просто будет. Проще использовать std::vector

Динамически=( пойду читать что такое std::vector. но перед этим, правильно я понимаю, что там его размер храниться в качестве переменной вроде как один из элементов структуры?

Сообщение от pu4koff

struct my_struct
{
  double value;
  my_struct *next;
};

и реализовывать добавление элементов в список и т.д. и т.п.

я бы хотел ручками. а как тогда првильно выделить память и использовать структуры? вот так почему-то нельзя

struct my_struct
{
  double value;
  my_struct *next;
};

my_struct *elem;
my_struct *firstelem=(my_struct *)calloc( sizeof(my_struct),1) ;


*firstelem.value=23.4;

*firstelem.next=(my_struct *)calloc( sizeof(my_struct),1) ;
elem=*firstelem.next;
*elem.value=43.2;

Сообщение от pu4koff

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


Уверены, что нужно оптимизировать не алгоритм, а именно доступ к памяти, её выделение и т.п.?

Да, не знаком с асмом, я не знал, что компиляторы могут код оптимизировать... но в каких пределах? то есть какие простые, но необходимые вещи мне брать на себя? например то, что reallock может иногда перезаписывать весь блок по новой я не знал. Какие общие рекомендации? С оптимизацией я действительно тороплюсь, но просто основная мотивация написания этой программы как раз в том, чтобы она работала быстрее своего аналога.

[Morkonwen]

Опишу подробно задачу, может кто-то и сталкивался и подскажет.
Программа решает 10 000 различных систем уравнений с разряженными матрицами, а потом комбинирует решения. системы имеют вид Ax=kBx, где A и B разряженные матрицы(несиммитричные, но если ij элемент не равен нулю, то и ji тоже не равен нулю, хотя они и различные),x-искомый вектор решение, а k коэффициент, который тоже должен быть таким, чтобы уравнение решалось.
В оригинальной программе (которая работает 10 дней) и k и решение ищутся как то при помощи последовательных приблежений используя умножение вектора на матрицу, что в разряженном случае довольно быстро, но сам поиск занимает жуткие 1.5 минуты каждый раз. мне не нравится эта идея, ведь если бы k было известно, то найти решение и точно можно очень быстро при помощи алгоритма гаусса, в котором, конечно, работа идет только с ненулевыми элементами.

Разряженные матрица храняться в виде массива связанных списков.
Для разряженных матриц можно составить алгоритм гаусса в котором после зануления каждого столбца надо переставлять некоторые строки местами так, чтобы количество образующихся ненулевых элементов после очереднго зануления столбца было минимальным. причем для всех 10000 матриц этот алгоритм один и тот же. составить его надо один единственный раз.

проблема найти k для каждого случая.
я не нашел ничего лучше чем найти определитель от A-kB в виде полинома от k, а потом найти его нули. определитель раскрываю рекурсией - разложением по строке в виде суммы определителей n-1 го порядка .причем каждый раз выбираю такую строку, что бы в ней было поменьше элементов+ надо некоторые результаты запонимать, так как некоторые из подопределителей равны и не стоит их 2 раза вычислять+надо запонимать строки и столбцы, которые вычеркнул так что постоянно есть массивы которые ты все время перезаписываешь, поэтому работа с памятью очень критична. последовательность строк по которым расклыдваешь тоже одна для всех матриц. Вот это меня и привлекает. если получится сделать так, чтобы нахождение k раскрытием определителя + решение алгоритмом гаусса конечной системы будет занимать меньше чем 1.5 минуты, для матриц ранга примерно 10 000 (хотя ненулевых элементов всего лишь 16 в каждой строке), то буду считать миссию выполненой. спасибо за ответы!

[pu4koff]

Операции с матрицами как правило хорошо параллелятся (см. OpenMP)
Так же возможно есть смысл посмотреть на CUDA.
В плане хранения данных я бы не заморачивался и использовал готовые классы из STL (vector, list).
Тут вся загвоздка идёт в алгоритмах поиска решения.
Учитывая, что строки нужно менять местами, то матрицу лучше делать как список строк.
У меня с математикой плохо, поэтому более конкретно тут ничего не скажу. Несколько раз встретилось упоминание о нулевых и ненулевых элементах. Вероятно, тут вырисовывается проверка на равенство нулю. Эта мелочная проверка в цикле вырастает в достаточно высокую лишнюю нагрузку на процессор. Тут уже нужно смотреть как эту проверку можно выкинуть из цикла или вообще, может как-то помечать строки из нулей, если их будет много, чтобы впоследствии не обрабатывать.
В ассемблер даже не лезьте, оптимизатор это сделает лучше, они и циклы умеют разворачивать и много всего интересного.
Я бы сначала реализовал всё как получится, а потом профайлером выискивал узкие места и думал над их оптимизацией.
И посмотрите еще на многообразие алгоритмов сортировки и поиска и преимущества каждого из них. Мне они в своё время достаточно наглядно показали примерный ход мышления в процессе оптимизации алгоритмов.