Re[3]: О производительности
От: WolfHound  
Дата: 17.08.09 14:10
Оценка:
Здравствуйте, Nuzhny, Вы писали:

N>Как это делается?

Ну... внимательно смотришь на алгоритм. Определяешь где у некоторого сферического кеша в вакууме(ибо они на разных процессорах ведут себя несколько по разному) будут промахи и переписываешь обращения к памяти так чтобы этих промахов было поменьше.

N>Ммм, например, при какой-либо обработке изображения на 40 Мб.

На обработке изображений у меня этими методами получалось разогнать в 2-3 раза.

N>Разбивать её на блоки меньшие кэша и независимо их обрабатывать? А если независимо нельзя?

А что за алгоритм то? Код показать можешь?
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: О производительности
От: Cadet  
Дата: 17.08.09 14:54
Оценка: :))
Ну где же, где примеры наступления счастья от переписывания всего на С++???
... << RSDN@Home 1.2.0 alpha 4 rev. 1238>>
Re[4]: О производительности
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 17.08.09 16:04
Оценка:
Здравствуйте, WolfHound, Вы писали:

N>>Разбивать её на блоки меньшие кэша и независимо их обрабатывать? А если независимо нельзя?

WH>А что за алгоритм то? Код показать можешь?

У меня изображения в основном 384х288 и интеловская VTune промахов не показывает. Мне просто интересно интересно как такая оптимизация производится: есть готовая методика или просто рекомендации. Для самообразования.
Re[2]: О производительности
От: Sheridan Россия  
Дата: 17.08.09 18:26
Оценка: -1 :)
Приветствую, Cadet, вы писали:

C> Ну где же, где примеры наступления счастья от переписывания всего на С++???

Ну для этого надо учиться и тратить драгоценное время, которое можно потратить на зарабатывание денег.
Поэтому таких примеров не будет.
Хотя... В подпись посмотри
avalon 1.0rc2 rev 300, zlib 1.2.3
build date: 17.08.2009 15:04:24 MSD +04:00
Qt 4.5.2
Matrix has you...
Re[2]: О производительности
От: D. Mon Великобритания http://thedeemon.livejournal.com
Дата: 18.08.09 03:08
Оценка:
Здравствуйте, Cadet, Вы писали:

C>Ну где же, где примеры наступления счастья от переписывания всего на С++???


Есть обратный пример: переписал транслятор с ICFPC'07 с С++ на Окамл без изменений алгоритма, скорость возросла в 10 раз.
Re: О производительности
От: geniepro http://geniepro.livejournal.com/
Дата: 18.08.09 04:34
Оценка:
Здравствуйте, Sheridan, Вы писали:

Пара ускорений в 50 раз:

1. Поиск в таблице dbf (через BDE). Сначала делал фильтрацией, обнаружились тормоза на количествах запросов. Заменил на поиск через процедуру Locate -- поиск в 50 раз ускорился, хотя теперь поиск будет ломаться, если в таблице есть удалёные записи (но это исключено, так что не важно).

2. В одной чужой тулзе, попавшей ко мне на доработку, был алгоритм загрузки данных в список, в котором список постоянно проверялся на наличие в нём загружаемого значения (данные в списке должны быть уникальны). Получилась сложность O(n^2). Вставил в это место временный упорядоченный список, получилось O(n*log n) -- на тех объёмах даных, что там были, ускорение составило более 50 раз.
Re[2]: О производительности
От: geniepro http://geniepro.livejournal.com/
Дата: 18.08.09 05:00
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Оригинальный алгоритм, скачанный с Интернета, работал 6 секунд. После моих модификаций работает 400-500 мсек на 2-ядерной машине и 200-300 — на четырехядерной. По существу я алгоритм не менял, но изменил расположение матрицы в памяти, порядок прохода в ней циклами и добавил многопоточность.


Типа такого было: нашёл простой в применении исходник, реализующий AES-256, так там было два варианта расчётов -- табличный и процедурный. Причём константа, переключающая режим на табличный (BACK_TO_TABLES), была закоментирована. Раскомментировал её -- шифрование/дешифрование ускорилось раз в сто, не меньше...

* Byte-oriented AES-256 implementation.
* All lookup tables replaced with 'on the fly' calculations.
*
* Copyright (c) 2007-2009 Ilya O. Levin, http://www.literatecode.com
* Other contributors: Hal Finney

Вот это вот изменение "All lookup tables replaced with 'on the fly' calculations." и замедлило алгоритмы на два порядка...
Re: О производительности
От: Voblin Россия http://maslyaew.narod.ru/
Дата: 18.08.09 07:52
Оценка: 1 (1)
Здравствуйте, Sheridan, Вы писали:

S>Люди а поделитесь опытом — у кого-ть было когда-ть заметное улучшение производительности софта после какойтотам оптимизации. Интересует именно причина возростания производительности, тоесть изза чего были тормоза и как поправили.


У оптимизации производительности два бога — кэширование и индексирование. Плюс к тому, конечно, есть толпа божков в виде оптимальных алгоритмов.
Кэширование заменяет тяжёлые операции лёгкими, а индексирование превращает O(N) в O(Ln N), O(N*N) в O(N*Ln N) и т.п.

Случаи из практики:
1. (очень давно) В очень тяжёлой расчётной программе вычисление квадратного корня константы было заменено на константу, посчитанную на калькуляторе. Программа заработала быстрее раза в два. Это как частный вариант кэширования.
2. После трёх месяцев накопления данных в базе выполнение запросов стало тормозить нещадно. Поменял в индексе два поля местами. Результат — данные продолжали копиться ещё многие годы, но всё летало как птичка. Это на тему индексирования.

Практически любую программу, оптимизацией которой не занимались специально, долго и вдумчиво, удаётся разогнать по крайней мере раза в два. И попутно понизить класс тормознутости (это самое "О").
Re[2]: О производительности
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 18.08.09 08:00
Оценка:
Здравствуйте, Voblin, Вы писали:

V>Здравствуйте, Sheridan, Вы писали:


S>>Люди а поделитесь опытом — у кого-ть было когда-ть заметное улучшение производительности софта после какойтотам оптимизации. Интересует именно причина возростания производительности, тоесть изза чего были тормоза и как поправили.


V>У оптимизации производительности два бога — кэширование и индексирование. Плюс к тому, конечно, есть толпа божков в виде оптимальных алгоритмов.

V>Кэширование заменяет тяжёлые операции лёгкими, а индексирование превращает O(N) в O(Ln N), O(N*N) в O(N*Ln N) и т.п.

Кеширование данных позволяет приблизить данные, получаемые "издалека", к месту неспосредственного использования данных.
Кеширование результатов вычислений (по науке — мемоизация) позволяет перераспределить сложность алгоритма с времени на память.

И тем и другим кешироанием надо пользоваться с осторожностью. Бывает так что тратится время на кеширование чего-либо, что потом не используется.

ЗЫ. ленивые вычисления позволяют избавить от этой проблемы.
Re[3]: О производительности
От: yumi  
Дата: 18.08.09 08:19
Оценка: +1 :)
Здравствуйте, gandjustas, Вы писали:

G>ЗЫ. ленивые вычисления позволяют избавить от этой проблемы.


Ага, и приносят кучу новых
Lisp is not dead. It’s just the URL that has changed:
http://clojure.org
Re[4]: О производительности
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 18.08.09 08:39
Оценка:
Здравствуйте, yumi, Вы писали:

Y>Здравствуйте, gandjustas, Вы писали:


G>>ЗЫ. ленивые вычисления позволяют избавить от этой проблемы.


Y>Ага, и приносят кучу новых


Каких например?
Re[5]: О производительности
От: yumi  
Дата: 18.08.09 10:32
Оценка: 1 (1) +2
Здравствуйте, gandjustas, Вы писали:

Y>>Ага, и приносят кучу новых


G>Каких например?


Ну например, накопление цепочки не вычисленных операций, которое в самый не подходящий момент начинает вычисляться. Сложность отладки, непредсказуемость. Просто я сейчас как раз таки занимаюсь наоборот, оптимизацией скорости посредством избавления от ленивости.
Lisp is not dead. It’s just the URL that has changed:
http://clojure.org
Уважаемые смеющиеся, а чего смешного я сказал?
От: Sheridan Россия  
Дата: 18.08.09 21:01
Оценка: +1
Помоему очень даже интересный топик получился...
avalon 1.0rc2 rev 300, zlib 1.2.3
build date: 18.08.2009 18:11:54 MSD +04:00
Qt 4.5.2
Matrix has you...
Re: О производительности
От: Flying Dutchman Украина  
Дата: 18.08.09 21:07
Оценка:
Здравствуйте, Sheridan, Вы писали:

S>Приветствую!

S>Люди а поделитесь опытом — у кого-ть было когда-ть заметное улучшение производительности софта после какойтотам оптимизации. Интересует именно причина возростания производительности, тоесть изза чего были тормоза и как поправили.

Вот пример оптимизации кода на C, используемого в управляющей программе реального времени. Задача — оптимизировать следующий код:

sprintf(buffer, "%s%d,%d", "ks", number, state);


где number может принимать значения от 0 до 176, а state — от 0 до 9.

Приведенная ниже программа содержит слабо- и сильнооптимизированный варианты кода и тесты для сравнения их производительности:


/*****************************************************************************
*               includes                                                     *
*****************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

static char *number_list[] =
{
      "0",   "1",   "2",   "3",   "4",   "5",   "6",   "7",   "8",  "9",
     "10",  "11",  "12",  "13",  "14",  "15",  "16",  "17",  "18",  "19",
     "20",  "21",  "22",  "23",  "24",  "25",  "26",  "27",  "28",  "29",
     "30",  "31",  "32",  "33",  "34",  "35",  "36",  "37",  "38",  "39",
     "40",  "41",  "42",  "43",  "44",  "45",  "46",  "47",  "48",  "49",
     "50",  "51",  "52",  "53",  "54",  "55",  "56",  "57",  "58",  "59",
     "60",  "61",  "62",  "63",  "64",  "65",  "66",  "67",  "68",  "69",
     "70",  "71",  "72",  "73",  "74",  "75",  "76",  "77",  "78",  "79",
     "80",  "81",  "82",  "83",  "84",  "85",  "86",  "87",  "88",  "89",
     "90",  "91",  "92",  "93",  "94",  "95",  "96",  "97",  "98",  "99",
    "100", "101", "102", "103", "104", "105", "106", "107", "108", "109",
    "110", "111", "112", "113", "114", "115", "116", "117", "118", "119",
    "120", "121", "122", "123", "124", "125", "126", "127", "128", "129",
    "130", "131", "132", "133", "134", "135", "136", "137", "138", "139",
    "140", "141", "142", "143", "144", "145", "146", "147", "148", "149",
    "150", "151", "152", "153", "154", "155", "156", "157", "158", "159",
    "160", "161", "162", "163", "164", "165", "166", "167", "168", "169",
    "170", "171", "172", "173", "174", "175", "176",
    NULL
};

static void convert1(char* buffer, int number, int state);
static void convert2(char* buffer, int number, int state);
static void convert3(char* buffer, int number, int state);
static void convert_empty(char* buffer, int number, int state);

int main(void) {

    char buffer1[80];
    char buffer2[80];
    char buffer3[80];
    char buffer4[80];
    char control_buffer[80];
    int i;
    const long int repetitions = 10000000;
    time_t begin_time1;
    time_t begin_time2;
    time_t begin_time3;
    time_t begin_time_empty;
    time_t end_time1;
    time_t end_time2;
    time_t end_time3;
    time_t end_time_empty;
    int    time1;
    int    time2;
    int    time3;
    int    empty_time;
    int    number;
    int    state;

    number = 1;
    state  = 2;
    sprintf(control_buffer, "ks%d,%d", number, state);

    /* Control check                                                        */
    convert1(buffer1, number, state);
    assert(strcmp(buffer1, control_buffer) == 0);

    convert2(buffer2, number, state);
    assert(strcmp(buffer2, control_buffer) == 0);

    convert3(buffer3, number, state);
    assert(strcmp(buffer3, control_buffer) == 0);

    /* Time of empty function                                               */
    begin_time_empty = time(0);
    for (i=0; i < repetitions; i++) {
        convert_empty(buffer4, number, state);
    }
    end_time_empty = time(0);
    empty_time = end_time_empty - begin_time_empty;

    /* Time of not optimized function                                       */
    begin_time1 = time(0);
    for (i=0; i < repetitions; i++) {
        convert1(buffer1, number, state);
    }
    end_time1 = time(0);
    time1 = end_time1 - begin_time1;

    /* Time of optimized function                                       */
    begin_time2 = time(0);
    for (i=0; i < repetitions; i++) {
        convert2(buffer2, number, state);
    }
    end_time2 = time(0);
    time2 = end_time2 - begin_time2;

    /* Time of highly optimized function                                 */
    begin_time3 = time(0);
    for (i=0; i < repetitions; i++) {
        convert3(buffer3, number, state);
    }
    end_time3 = time(0);
    time3 = end_time3 - begin_time3;

    time1 -= empty_time;
    time2 -= empty_time;
    time3 -= empty_time;

    printf("Repetitions:      %d\n", repetitions);
    printf("Numbers:          %d %d\n", number, state);
    printf("Empty time:       %d\n", empty_time);
    printf("Not optimized:    %d\n", time1);
    printf("Optimized:        %d\n", time2);
    printf("Highly optimized: %d\n", time3);

    return (0);
}

/*--------------------------------------------------------------------------*/
/*  Not optimized version with sprintf                                      */
/*--------------------------------------------------------------------------*/
static void convert1(char* buffer, int number, int state) {
    sprintf(buffer, "%s%d,%d", "ks", number, state);
}

/*--------------------------------------------------------------------------*/
/*  Optimized version                                                       */
/*--------------------------------------------------------------------------*/
static void convert2(char* buffer, int number, int state) {
    strcpy(buffer, "ks");
    strcat(buffer, number_list[number]);
    strcat(buffer, ",");
    strcat(buffer, number_list[state]);
}

/*--------------------------------------------------------------------------*/
/*  Highly optimized version                                                */
/*--------------------------------------------------------------------------*/
static void convert3(char* buffer, int number, int state) {
    static char *numbers = "0123456789";
    char *p_current;
    char *p_from;

    /* Write "ks"                                                           */
    p_current = buffer;
    *p_current = 'k';
    p_current++;
    *p_current = 's';

    /* Write first number using unrolled strcpy                             */
    p_current++;
    for (p_from = number_list[number]; *p_from != '\0'; p_from++) {
        *p_current = *p_from;
        p_current++;
    }

    /* Write comma                                                          */
    /* p_current is already set after the last character of copied string   */
    *p_current = ',';

    /* Write second number                                                   */
    p_current++;
    *p_current = numbers[state];

    /* Write null terminator                                                */
    p_current++;
    *p_current = '\0';
}

/*--------------------------------------------------------------------------*/
/*  Empty function                                                          */
/*--------------------------------------------------------------------------*/
static void convert_empty(char* buffer, int number, int state) {

}

/*****************************************************************************
*               end of file                                                  *
*****************************************************************************/
Re[2]: О производительности
От: Хвост  
Дата: 18.08.09 22:15
Оценка:
Здравствуйте, Flying Dutchman, Вы писали:
если "ks" это фиксированый префикс, то почему бы не залукапить полностью все комбинации? Выйдет меньше чем 16 кб, или ограничения по памяти очень жёсткие (микроконтроллеры)?
People write code, programming languages don't.
Re: Уважаемые смеющиеся, а чего смешного я сказал?
От: Alexander G Украина  
Дата: 18.08.09 22:49
Оценка: 1 (1) +5
Здравствуйте, Sheridan, Вы писали:

S>Помоему очень даже интересный топик получился...


Люди а поделитесь опытом — у кого-ть было когда-ть заметное улучшение производительности софта после какойтотам оптимизации


Это примерно то же, что спросить

Люди, а кто-то из вас использовал вложенные циклы?

Русский военный корабль идёт ко дну!
Re[3]: О производительности
От: Flying Dutchman Украина  
Дата: 18.08.09 23:12
Оценка: :)
Здравствуйте, Хвост, Вы писали:

Х>Здравствуйте, Flying Dutchman, Вы писали:

Х>если "ks" это фиксированый префикс, то почему бы не залукапить полностью все комбинации?

Да, интересная идея — хотя исходники великоваты получатся (хотя можно их, конечно, сгенерироваь автоматически).

X>Выйдет меньше чем 16 кб, или ограничения по памяти очень жёсткие (микроконтроллеры)?


Да нет, у нас использовался процессор Motorola 68000 c 4 или 8 Mb памяти, так что это было бы не критично. В принципе, слабооптимизированная версия нас устроила. Впоследствии даже выяснилось, что даже неоптимизированная версия не сильно влияла на производительность, поскольку этот код использовался достаточно редко (конечно, там была потенциальная опасность из-за того, что функция sprintf производит вызов malloc, но за время долгой эксплуатации программы проблем не было).
Re[2]: О производительности
От: Sinclair Россия https://github.com/evilguest/
Дата: 19.08.09 07:08
Оценка:
Здравствуйте, Flying Dutchman, Вы писали:
Какой-то у вас convert3 многословный.
static void convert3(char* buffer, int number, int state)
{
    static char *numbers = "0123456789";

    char *p_current = buffer;

    *p_current++ = 'k';
    *p_current++ = 's';

    char *p_from = number_list[number];
    while(*pFrom)    
        *p_current++ = *p_from++;

    *p_current++ = ',';

    *p_current++ = numbers[state];

    *p_current++ = '\0';
}
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: Для самообразования — Agner Fog
От: SergeCpp Россия http://zoozahita.ru
Дата: 19.08.09 07:50
Оценка: 18 (2)
N>...просто интересно интересно как такая оптимизация производится: есть готовая методика или просто рекомендации. Для самообразования.

У Agner Fog были?

http://www.agner.org/optimize/#manuals
http://zoozahita.ruБездомные животные Екатеринбурга ищут хозяев
agner fog
Re[6]: Для самообразования — Agner Fog
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 19.08.09 10:19
Оценка:
Здравствуйте, SergeCpp, Вы писали:

SC>У Agner Fog были?


SC>http://www.agner.org/optimize/#manuals


Нет, спасибо.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.