Жизнь внутри метода - Философия программирования

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

Pzz>#pragma flame on

Pzz>Напротив. Просто потребность в эффективности программ стала не общепринятой, а нишевой. Когда возникает необходимость спроектировать сервер, обслуживающий большое количество клиентов, или коробочку, выдающую осмысленную производительность на слабом железе, то тут некуда деваться от традиционных представлений о производительности (разве что tradeoff между процессором и памятью заметно сместился в сторону памяти). Ваше поколение оказывается довольно беспомощным при решении такого рода задач, и плохо обучаемым, потому как у вас происходит разрыв шаблона при соприкосновении с реальностью

Боюсь тебя разочаровать, но я таки имею некоторый опыт проектирования серверов, обслуживающих большое количество клиентов.
Скажем так, одна из систем, которую я проектировал, выдерживала впятеро большую нагрузку по клиентам, чем RSDN.RU. И было это почти десять лет назад, на тогдашней аппаратуре. Мое поколение справилось вполне успешно.

Разрыв шаблонов, действительно, произошел. Оказалось, что узкими местами в системе были вовсе не JSP странички. Они-то как раз летали, как трофейный мессершмит.
Сосал почтовый сервер, весь из себя написанный на плюсах и работавший поверх файлухи. (а то! ведь СУБД — это тормоза, они не дают прямого управления IO).
После переписывания на Java, поверх MS SQL, на той же машинке почтовый сервер стал выгребать не 200000 писем в сутки, а 1000000.
Второй боттлнек устранить не удалось: это был Interbase, тоже ясное дело, не на сишарпе писанный. Увы, он никак не хотел жрать больше 1 СPU на четырехпроцессорной машине, и кластеризовываться тоже не умел.

До того проекта я придерживался ровно таких же взглядов, как и Павел Дворкин сейчас. Стандартный набор шаблонов: "Ассемблер порвать невозможно; плюсы — единственный приемлемый язык" и так далее. Разрыв был таким, что я днями смотрел в профайлер и не верил себе.
Ничего, потом всё зажило. Павлу повезло — ему не удалось столкнуться с человеком, который бы столь же наглядно продемонстрировал ему ущербность его взглядов.

Вот, он рядом пишет про сайт microsoft.сom. Ну это же просто праздник какой-то!

Pzz>#pragma flame off

Pzz>У вас на слово "ассемблер" невротическая реакция. Павел не предлагал все писать на ассемблере, или даже что-либо писать на ассемблере, он произнес слово "ассемблер", чтобы очертить некоторый теоретический предел эффективности, достижимой на данном железе.
У меня с реакцией на ассемблер всё в порядке. У меня невротическая реакция как раз на "теоретический предел эффективности", который устроен вовсе не так, как думает Павел. Но объяснить ему это нереально: шаблоны слишком прочны.

... << RSDN@Home 1.2.0 alpha rev. 677>>

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

AVK>Чего воду в ступе толочь? Реализуй описанный алгоритмв императивном стиле, и чтобы распараллеливался, вот мы и посмотрим.

Мне что, делать больше нечего, кроме как вычисление процентов распараллеливать ?

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

S>Сосал почтовый сервер, весь из себя написанный на плюсах и работавший поверх файлухи. (а то! ведь СУБД — это тормоза, они не дают прямого управления IO).
S>После переписывания на Java, поверх MS SQL, на той же машинке почтовый сервер стал выгребать не 200000 писем в сутки, а 1000000.
S>Второй боттлнек устранить не удалось: это был Interbase, тоже ясное дело, не на сишарпе писанный. Увы, он никак не хотел жрать больше 1 СPU на четырехпроцессорной машине, и кластеризовываться тоже не умел.

Не собираюсь оспаривать твои высказывания, но объясни мне, пожалуйста, почему тогда абсолютное большинство десктопного софта, написанного на яве работает в разы медленее, чем его аналоги на C/C++? Почему mcirosoft-овский MSDN работает быстро, а IBM-овская справка (на Java) — из рук вон медленно? Почему та же история повторяется с парочкой OpenOffice/MS Office? UML-рисовалки, это вообще мрак. Если сравнивать Eclipse и MSVC 6.0 — это попросту не смешно. Если ява с такой уверенностью "рвёт" плюсовый код?

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

AVK> Виртовский Оберон модульный, но нифига не ООПнутый

В смысле? Оберон вполне себе ООП-язык, только ООП там немного низкоуровневый...
Ну так ООПы разные бывают, друг на друга непохожие совсем...

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

G>В смысле? Оберон вполне себе ООП-язык, только ООП там немного низкоуровневый...
G>Ну так ООПы разные бывают, друг на друга непохожие совсем...

Виртовский же это первый оберон, там вроде ООП практически и нет.

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

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

G>>В смысле? Оберон вполне себе ООП-язык, только ООП там немного низкоуровневый...
G>>Ну так ООПы разные бывают, друг на друга непохожие совсем...

FR>Виртовский же это первый оберон, там вроде ООП практически и нет.

Расширяемые записи есть -- вот и основа для ООП. Ну а то, что методы нужно вручную прописывать в процедурные переменные (поля этих записей) -- ну так на то он и "ассемблер ООП"...

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

VD>Ты пойми, люди вроде Дворкина мыслят не так. Они когда пишут код, то представляют его в уже оптимизированном виде. У него не то что списка не будет (это же непроизводительные расходы памяти!). У него и функций в коде не будет. Он просто напишет один огромный "for" в тело которого он зафигачит все свои вычисления.

Вот теперь понятно. Поскольку все это не имеет к моему стилю ни малейшего отношения, остается сделать простейший вывод. Люди вроде тебя сначала придумывают себе некий образ оппонента, причем именно такой образ, который хотелось бы видеть, а потом упорно с этим образом сражаются. С этим образом сражаться проще — он ведь специально для этой цели придуман. Ну а то, что это неэтично — не тебе же говорить об этике!

Не согласен ? Тогда, пожалуйста

1. Приведи , где и когда я говорил, что я вижу код уже в оптимизированном виде. Ссылку!
2. Приведи, где и когда я выступал против списков. Ссылку!
3. Приведи, где и когда я выступал против использования функций. Ссылку!
4. Приведи, где и когда я заявлял, что я все напишу в виде одного огромного for. Ссылку!

Жду. За свои слова надо отвечать — по крайней мере порядочные люди так себя ведут.

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

ГВ>>Не собираюсь оспаривать твои высказывания, но объясни мне, пожалуйста, почему тогда абсолютное большинство десктопного софта, написанного на яве работает в разы медленее, чем его аналоги на C/C++? Почему mcirosoft-овский MSDN работает быстро, а IBM-овская справка (на Java) — из рук вон медленно? Почему та же история повторяется с парочкой OpenOffice/MS Office? UML-рисовалки, это вообще мрак. Если сравнивать Eclipse и MSVC 6.0 — это попросту не смешно. Если ява с такой уверенностью "рвёт" плюсовый код?

WF>Open Office не на Java, если что. C++. Java там так, какие-то плагины, что-ли.

Да, верно. Про openoffice вопрос снимается.

WF>Eclipse просто слишком гибкая и навороченная платформа, да и есть у Java объективные проблемы на десктопе (нет ни кеширования нативного кода, ни AOT, JIT срабатывает не сразу, автоматическая настройка GC как-то неважно работает для монстров типа Eclipse, и.т.д).

Ты хочешь сказать, что это приводит к замедлению где-то на порядок?

WF>Хотя 10 лет назад Java была ещё тормознее.

Это я в курсе.

Здравствуйте, Геннадий Васильев, Вы писали:

WF>>Eclipse просто слишком гибкая и навороченная платформа, да и есть у Java объективные проблемы на десктопе (нет ни кеширования нативного кода, ни AOT, JIT срабатывает не сразу, автоматическая настройка GC как-то неважно работает для монстров типа Eclipse, и.т.д).

ГВ>Ты хочешь сказать, что это приводит к замедлению где-то на порядок?

Думаю, первый пункт — запросто. А это уже не к Java, а к конкретному приложению относится. Например, IBM-овский хелп, насколько мне известно, написан на JSP+JS и поднимает на фоне Tomcat. Да ещё и при первом поиске начинает строить индекс Lucene-ом (или чем-то ещё). Из-за того, что Eclipse расширяем в каждую дырку, а VC 6.0 — нет, да и фич у Eclipse поболее будет. И так далее.

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

G>Расширяемые записи есть -- вот и основа для ООП. Ну а то, что методы нужно вручную прописывать в процедурные переменные (поля этих записей) -- ну так на то он и "ассемблер ООП"...

Ну тогда и в Си есть ООП

Здравствуйте, Геннадий Васильев, Вы писали:

ГВ>Не собираюсь оспаривать твои высказывания, но объясни мне, пожалуйста, почему тогда абсолютное большинство десктопного софта, написанного на яве работает в разы медленее, чем его аналоги на C/C++?
Вкратце: потому, что десктопный софт работает совершенно по-другому, чем серверный.
Более длинно:
1. в серверном коде важнее не responsiveness, а throughput. Задержка реакции в 500 мс для веб-сервера — норма, благодаря тому, что UI обслуживается отдельным агентом на клиентской стороне. В десктопном приложении задержка реакции в 500мс — это ощутимые тормоза.
2. в десктопном коде важную роль играют операции с графикой, а bit-crunching по историческим причинам в управляемых платформах не слишком-то оптимизирован. Это не то чтобы их неотъемлемая особенность, это скорее вопросы приоритетов, выбранных при разработке платформ.

ГВ>Почему mcirosoft-овский MSDN работает быстро, а IBM-овская справка (на Java) — из рук вон медленно? Почему та же история повторяется с парочкой OpenOffice/MS Office? UML-рисовалки, это вообще мрак. Если сравнивать Eclipse и MSVC 6.0 — это попросту не смешно. Если ява с такой уверенностью "рвёт" плюсовый код?
Однако visual studio, несмотря на значительную долю управляемого кода, работает вполне себе приемлемо. Это, грубо говоря, означает, что дело не столько в языке, сколько в прямизне рук разработчика.
Да, это несколько подтачивает тезис о том, что хороший перформанс на средствах высокого уровня достигается меньшей ценой разработки, чем с низким уровнем, но не опровергает его окончательно.

Просто пока что баланс abstraction penalty / abstraction gain в среднем проходит чуть ниже уровня, доступного прикладным программистам управляемых сред. В стародавние времена и C++ безнадежно сливал C по производительности — однако время прошло, и сейчас редкий ассемблерщик порвет плюсы. Точно так же дело обстоит и в управляемых средах: улучшения Execution Runtime позволяют выигрывать всем программам, даже написанным до этих улучшений, и чем более высокоуровневые средства применяются, тем больше будет этот abstraction gain.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Со всем этим можно было бы согласиться, если бы процессор мог непосредственно выполнять код на Хаскеле/C#... Тогда я бы снял свои возражения. А пока что, что там не делай, а закончится все mov, add, jmp и т.д. И вот это есть абсолютный теоретический предел при данном алгоритме, если его идеально эффективно запрограммировать. Улучшить можно, только если алгоритм поменять (или доступ к данным ускорить или распараллелить и т.д.).

Ну прикол-то в том, что если программа сформулирована в терминах mov, add, jmp и т.д, то простор для ее оптимизации крайне мал. Да, процессоры сейчас выжимают максимум из этого, но у них есть существенные ограничения как по ресурсам, которые можно на это потратить, так и по возможным действиям, которые они могут выполнить.

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

Более того, во многих задачах невозможно заранее предложить оптимальное решение в терминах mov, add, jmp и т.д. Просто потому, что еще нет информации о том, в каких условиях будет алгоритм выполняться. Потому, что, к примеру, параллелить на 1 ядре — это гарантированная потеря производительности. И непараллелить при 4 ядрах — тоже гарантированная потеря. А никакого способа автоматически трансформировать mov/add/jmp так, чтобы они были оптимальны для 1/2/4 ядер наука не знает. Зато знает способы делать это в том случае, если программа написана в декларативном стиле.
Ты в курсе, как работают оптимизаторы в современных компиляторах? Именно так и делают: переписывают Control Flow Graph в виде SSA/SSI, то есть практически в функциональном, а потом уже применяют всякие трансформации, учитывая дополнительную информацию.

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

FR>Ну тогда и в Си есть ООП

Ага, и Постгрес с Ораклем — ООБД.

... << RSDN@Home 1.2.0 alpha 4 rev. 1111 on Windows Vista 6.0.6001.65536>>

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Мне что, делать больше нечего, кроме как вычисление процентов распараллеливать ?

Понятно. Тогда получается, что все твои утверждения получается рассматривать только как пустой звук.

... << RSDN@Home 1.2.0 alpha 4 rev. 1111 on Windows Vista 6.0.6001.65536>>

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

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

G>>Расширяемые записи есть -- вот и основа для ООП. Ну а то, что методы нужно вручную прописывать в процедурные переменные (поля этих записей) -- ну так на то он и "ассемблер ООП"...

FR>Ну тогда и в Си есть ООП

В этом случае понятие ООП уж слишком сильно размывается...

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

IT>Я думаю, что у тебя не хватит силёнок даже этот простенький алгоритм эффективно распаралелить. Просто даже в этом не сомневаюсь.

Вообще-то такое называется провокацией

. Ладно. Будем считать, что провокация твоя удалась

Но процентами и провайдерами я все же заниматься не буду. Насколько я понимаю, AsParallel — это из .Net 4.0, так ? Во всяком случае MSDN 2008 о нем молчит. Ну вот, поискал я на Гугле и нашел вот это

http://blogs.msdn.com/pfxteam/archive/2007/12/07/6696413.aspx

Ray Tracer мне изучать недосуг, поэтому я просто распараллелил вычисление сумм красных компонент по столбцам окна. Зачем там эти суммы — а просто, чтобы было что делать

. В остальном же делается именно то, о чем речь идет в этом примере — распараллеливание по кускам по ширине окна

Вот код

struct CHUNK
{
    HDC hdc;
    int xStart, xEnd;
    int nHeight;
};
unsigned* columnSum;
unsigned __stdcall ThreadFunc(void* arg)
{
    CHUNK* pChunk = (CHUNK*) arg;
    int xEnd = pChunk->xEnd;
    int nHeight = pChunk->nHeight;
    HDC hdc = pChunk->hdc;
    for (int x = pChunk->xStart; x <= xEnd; x++)
    {
        unsigned s = 0;
        for ( int y = 0; y < nHeight; y++)
        {
            COLORREF cr = GetPixel(hdc, x, y); // сорри за такое безобразие, конечно
            s+= GetRValue(cr);
        }
        columnSum[x] = s;
    }
    return 0;

}


///... а это где-нибудь для запуска

                RECT r;
                GetClientRect(hWnd, &r);
                int nHeight = r.bottom - r.top;
                int nWidth =  r.right - r.left;
                columnSum = new unsigned[nWidth];

                // без распараллеливания

                DWORD dwTimeStart , dwTimeEnd;

                dwTimeStart = GetTickCount();
                HDC hdc = GetDC(hWnd);
                for ( int x = 0; x < nWidth; x++)
                {
                    unsigned s = 0;
                    for(int y = 0; y < nHeight; y++)
                    {
                        COLORREF cr = GetPixel(hdc, x, y); // сорри за такое безобразие, конечно
                        s+= GetRValue(cr);
                    }
                    columnSum[x] = s;
                }

                dwTimeEnd = GetTickCount();
                nTime1 = dwTimeEnd - dwTimeStart;

            
                // а теперь распараллелим

                SYSTEM_INFO si;
                GetSystemInfo(&si);
                unsigned nProcNumber = si.dwNumberOfProcessors;
                int xChunkWidth = nWidth / nProcNumber;
                CHUNK * pChunks = new CHUNK[nProcNumber];
                HANDLE* hThread = new HANDLE[nProcNumber];
                for ( unsigned i = 0; i < nProcNumber; i++)
                {
                    pChunks[i].nHeight = nHeight;
                    pChunks[i].xStart = xChunkWidth * i;
                    pChunks[i].xEnd = xChunkWidth * (i + 1) - 1;
                    pChunks[i].hdc = hdc;
                }
                pChunks[si.dwNumberOfProcessors - 1].xEnd = nWidth - 1; // спишем на него остаток от деления

                dwTimeStart = GetTickCount();

                for ( unsigned i = 0; i < nProcNumber; i++)
                    hThread[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunc,pChunks +i, 0, NULL);
                WaitForMultipleObjects(nProcNumber, hThread, TRUE, INFINITE);

                dwTimeEnd = GetTickCount();
                nTime2 = dwTimeEnd - dwTimeStart;


                for ( unsigned i = 0; i < nProcNumber; i++)
                    CloseHandle(hThread[i]);
                delete[] pChunks;
                delete[] hThread;
                delete[] columnSum;
                ReleaseDC(hWnd, hdc);

Вот и все. Писал минут 20. Не тестировал всерьез, так как нет времени, так что если есть ошибки — сорри. По этой же причине не сделана обработка ошибок

В релизе на моей машине (AMD Dual 4200+)

nTime1 == 2375
nTime2 = 1593

Не в 2 раза, но время уходит на инициализацию потоков. В реальной задаче я так, конечно, делать не буду — потоки (или пул) будут создаваться один раз, а потом им слаться work item или что-то в этом роде.

А теперь вопросы к тебе.

1. Напиши аналогичное со свои любимым AsParallel, только не вертикальными полосами, а прямоугольно-гнездовыми кусками. Мне, как понимаешь, это на пять минут работы — массив columnSum превратить в двумерный, а в CHUNK вместо nHeight ввести yStart, yEnd.
2. То же самое по диагоналям. Каждый тред занимается своей диагональю, параллельной главной (или побочной)
3. Сделай так, чтобы некоторые из процессоров не использовались этими потоками. Список этих процессоров дан. Мне это ничего не стоит — SetThreadAffinityMask — и все дела.
4. Сделай так, чтобы треды работали в фоне, то есть основной поток имел при этом больший приоритет — его работа для меня более важна, чем это суммирование. Иными словами, если я между

for ( unsigned i = 0; i < nProcNumber; i++)
hThread[i] = (HANDLE)_beginthreadex(NULL, 0, ThreadFunc,pChunks +i, 0, NULL);

и
WaitForMultipleObjects(nProcNumber, hThread, TRUE, INFINITE);

помещу еще некоторый код — должен исполняться он, а не поток — если процессоров не хватает.

5. Ну и напоследок. Сделай так, чтобы эти треды информировали периодически некий третий поток о том, как у них прогресс идет. Для меня тут, конечно, минут на 10 работы — еще один поток надо сделать, причем с петлей сообщений а потом просто PostThreadMessage когда надо.

А пока что мне пора к делу вернуться. Там мне распараллеливание если и поможет, то только при десятке процессоров, а их нет

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

S>Вот в этом месте не понял. Недавно набрел на linq-проект, который прозрачным образом использует индексы на In-memory коллекциях. Вот он, небанальный перебор за счет декларативности программирования. Может, другой пример подберем?

Зачем другой пример? Ты, наверное, меня не до конца понял — я не отрицаю, что можно сделать по-другому. Причем для этого не нужен ни LINQ, ни прочие навороты последних ревизий си-шарпа. Собственно, первое что приходит в голову:

class Item 
{
    Item Next;
}

Уже модель работы с коллекцией изменяется — не будем рассматривать, в какую сторону

Речь-то не о том, как можно сделать, а как обычно делается. Ведь неужели корень зла в том, что в методах пару if-ов используется, и программа партии состоит в том, чтобы заменить эти if-ы на синтаксически что-нибудь другое? Проблема в том, что логика приложений фактически целиком строится на старых приемах и конструкциях, которым уже лет сто в обед. А почему так происходит?

Трактовка 1. "Внешняя" сторона, за которую отвечает ООП, все эти графы, полиморфизмы и прочая вроде как прогрессировала со времен царя гороха, а "внутреняя" нет. Так да здравствует же язык, который предоставляет средства, позволяющие, так сказать, поднять технологический уровень того, что в методах происходит.

Трактовка 2. Да, конечно, императивные конструкции стары. Но все старо в этом мире. Да и сам ООП в общем-то не молодчик. Проблема не в том, что мы в принципе используем эти конструкции, а в том что мы ими злоупотребляем. А почему злоупотребляем? Что мы делаем в этих методах? Пишем хитрые полностью изолированные от всего мира алгоритмы? Фига два. Мы используем "все эти графы, полиморфизмы и прочая". Никаких подозрений не возникает? Так где же у нас root of evil в таком случае?

Собственно, твой пример даже косвенно подтверждает то, о чем я писал.

ЗЫ. Аналогии по просьбе трудящихся не использовал.

... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>

От:	Sinclair	https://github.com/evilguest/
Дата:	28.10.08 05:39
Оценка:	5 (2)

От:	Sinclair	https://github.com/evilguest/
Дата:	28.10.08 05:39
Оценка:	+2

	От:	Pavel Dvorkin
	Дата:	28.10.08 06:15
	Оценка:

От:	Геннадий Васильев	http://www.livejournal.com/users/gesha_x
Дата:	28.10.08 06:15
Оценка:	+3

От:	geniepro	http://geniepro.livejournal.com/
Дата:	28.10.08 06:27
Оценка:

От:	AndrewVK	http://blogs.rsdn.org/avk
Дата:	28.10.08 09:07
Оценка:

	От:	Воронков Василий
	Дата:	28.10.08 10:52
	Оценка: