LINUX.ORG.RU
ФорумTalks

Академические алгоритмы в современном программировании: не маразм ли?

 , , ,


3

2

У меня складывается стойкое ощущение, что использование классических супер-эффективных алгоритмов со всякими чудесными O(n) в современных реалиях, когда серверы со 128-ю процессорными ядрами стали скорее нормой, чем роскошью - в общем, это похоже на маразматическое ретроградство и заскорузлость мозга в принципиальном нежелании критически оценивать свои «бесценные» университетские знания, полученные от людей, не всегда догадывающихся о существовании многопоточности.

На мой взгляд, в современных реалиях наиболее эффективно себя показывают алгоритмы «разделяй и властвуй» наподобие QuickSort'а - т.е. те алгоритмы, которые позволяют разбить выполнение задачи на множество параллельно выполняющихся подзадач. А программистов, не задумывающихся о распараллеливании, синхронизации и склейке результатов - нужно гнать из профессии ссаными тряпками, сколько бы ни было у них гонора в связи с тем, что они всего Кнута выучили наизусть.

Это сугубо моё мнение, которое никому не навязываю, зато предлагаю открытую дискуссию.

★★★★★

Какой вообще смысл заниматься программированием, если компьютеры сами могут все решить?

abraziv_whiskey ★★★★★ ()

Да, сейчас важно умение эффективно распараллелить выполнение задачи, но и без «чудесных O(n)» можно получить маразм, когда распараллевать будут O(n^2), O(n^3) или вообще экспоненциальное что-нибудь вместо O(n).

anonymous_incognito ★★★★★ ()

Ну не совсем так. Я уже приводил пример когда будучи студентом изучал суперкомпьютеры. Препод нам поручил сделать перемножение 2-х матриц. Ну что берем выделяем массивы под MxN и погнали. А я выделил 1 мерный массив. Сделали задачу. А теперь препод говорит А сейчас мы с помощью OpenMP распараллелить её. Раз распараллелили и раз у всех метрики улучшились. А у меня ухудшились. Причем они и худшие были лучше чем в вариантах с MxN. В чем соль? В том, что контроллер памяти и кэш1. И у меня небыло гонки. Чтение происходило последовательно. Никто не соревновался.

Далее на компьютере еще куча задач выполняется. Все орут постоянно - а Python плохо паралелится. Ну и ладно. У меня 4 ядра. На компьютере работает Nginx, PostgreSQL, моя задача и еще ОС. И толку, что у Эрланга например все задачи сами распараллеливаются. Если считать на нем большие куски, то выхлопа 0.

dmxrand ()

Распараллеливать на множетсво потоков говнокода, чтобы что? ахреневали все 128 ядер? эдакий троллинг железа во все поля)

Anoxemian ★★★★★ ()

Параллельные алгоритмы тоже вполне себе исследуются и реализуются, просто в реальности параллельное программирование (за вычетом небольшого количество задач) это 1001 способ выстрелить себе в ногу, а не ускорение.

Evgueni ★★★★★ ()

По-моему, я сейчас прочитал чушь.

Virtuos86 ★★★★★ ()
Ответ на: комментарий от dmxrand

Только на эрланге не пишут верчение матриц и (чему там еще учат в универе, что стоило бы учить в 7-9 классе школы).

svr4 ()

128 ядер в одной машине практически не бывает, если это не лезвия. Обычные материнки под 2011v3 - два сокета.

Спарки 128 физических ядер также не имеют.

svr4 ()

Очередной «я не учился и пришел к успеху» тред?

aiqu6Ait ★★ ()
Ответ на: комментарий от Evgueni

просто в реальности параллельное программирование (за вычетом небольшого количество задач) это 1001 способ выстрелить себе в ногу, а не ускорение.

Это проблема реализации, а не подхода. Нормальный ЯП должен предоставлять возможности для прозрачного распараллеливания без необходимости задумываться о гонках, deadlock'ах и прочей низкоуровневой ерунде. Аналогично должно быть реализовано ускорение выполнения кода на GPU.

Sadler ★★★ ()
Ответ на: комментарий от svr4

Спарки 128 физических ядер также не имеют.

Гуглить Sun Fire 15k («первенец» - всего 112 ядер, если мне не изменяет слероз). А потом Sun Fire 25k и M9000.

MumiyTroll ★★ ()
Ответ на: комментарий от Sadler

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

На данный момент IMHO наиболее оптимальный путь — это распараллеливание на уровне компилятора. Это даст «бесплатные» +10% в скорости программ. По хорошему конечно необходима разработка параллельных алгоритмов (именно теория) под все случаи жизни с оценкой какое они дают преимущество, но IMHO пока нет 1000+ процессоров всегда под рукой оно будет не сильно выигрышно.

Evgueni ★★★★★ ()

Параллельность только повышает требование к качеству алгоритмов. К требованию правильной асимптотики по размерности задачи требуется правильная асимптотика по числу ядер и минимизация последовательной части. Чем больше ядер, тем важнее минимизировать последовательную часть ( https://ru.m.wikipedia.org/wiki/Закон_Амдала ) и операции декомпозиции и сшивки результатов.

YesSSS ★★★ ()

Предлагаешь брать алгоритмы n^2? В чём тут профит? Ну вот возьми 1К данных, на n у меня будет 1K циклов, а на n^2 будешь паралелить 1M? Даже на своих 100 ядрах получишь 10К циклов.

foror ★★★★ ()
Последнее исправление: foror (всего исправлений: 1)
Ответ на: комментарий от Evgueni

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

Выстрелить себе в ногу можно легко и в последовательном программировании, здесь тоже блокировки встречаются сплошь и рядом. Проблема параллельного программирования - только в отладке. Мне, например, из-за этого приходится подробно логировать всё происходящее внутри процессов/потоков до выхода кода в продуктив. Причём очень часто никакими синтетическими тестами невозможно воспроизвести ситуацию, возникающую при эксплуатации - это тоже добавляет проблем.

DRVTiny ★★★★★ ()

Я немного не понял, что именно ты не осилил: сами алгоритмы или университет?

invy ★★★★★ ()
Ответ на: комментарий от YesSSS

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

По-моему актуально только для тех случаев, когда есть некая выдача конечного результата, вынуждающая программу собрать данные со всех порождённых процессов. Если же результат работы параллельного процесса на «принимающей» стороне (тоже распараллеленой) может быть принят сразу - подобной проблемы не возникает.

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

DRVTiny ★★★★★ ()
Последнее исправление: DRVTiny (всего исправлений: 1)

На мой взгляд, в современных реалиях наиболее эффективно себя показывают алгоритмы «разделяй и властвуй» наподобие QuickSort'а

В современных реалиях нужно понимать и как работают алгоритмы и их потребление памяти и процессора, но так-же и хорошо понимать как работает железо, что-бы не нарваться на непонятные проседания производительности. Без понимания алгоритмов можно распараллеллить O(n!) реализацию, эффект параллельности будет нулевой. Без понимания железа можно нарваться .. ну например хотя бы на false sharing, эффект будет тот-же.

qrck ★★ ()
Ответ на: комментарий от qrck

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

DRVTiny ★★★★★ ()

Современные реалии - это одноядерный процессор частотой 560 МГц, память 128 Мбайт, флеш 32 Мбайт. И я руки готов пообрывать тем, кто допускает регрессии и неоптимальные конструкции в основном коде.

Deleted ()

когда серверы со 128-ю процессорными ядрами стали скорее нормой, чем роскошью

Ты похоже не видел задачи, для которых 128 ядер это мало и медленно, и ты думаешь, что это: хреновые алгоритмы, сложная задача или сам дурак.

Artificial_Thought ★★★★ ()
Ответ на: комментарий от DRVTiny

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

qrck ★★ ()

У меня складывается стойкое ощущение, что использование классических супер-эффективных алгоритмов со всякими чудесными O(n) в современных реалиях, когда серверы со 128-ю процессорными ядрами стали скорее нормой, чем роскошью

Вот после таких речей и тормозят мобилочки с 8-ядерными процессорами, тормозит и падает софт на компьютере, бразуер на страничке уровня hello world жрёт больше, чем Crysis на максималках, и т.д.

Quasar ★★★★★ ()
Последнее исправление: Quasar (всего исправлений: 1)
Ответ на: комментарий от DRVTiny

Выстрелить себе в ногу можно легко и в последовательном программировании

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

Проблема параллельного программирования - только в отладке.

Это следствие.

Evgueni ★★★★★ ()
Ответ на: комментарий от dmxrand

dmxrand> Далее на компьютере еще куча задач выполняется. Все орут постоянно - а Python плохо паралелится. Ну и ладно. У меня 4 ядра. На компьютере работает Nginx, PostgreSQL, моя задача и еще ОС. И толку, что у Эрланга например все задачи сами распараллеливаются. Если считать на нем большие куски, то выхлопа 0.

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

Quasar ★★★★★ ()

в современных условиях даже минимальное снижение O() даёт весьма ощутимый в деньгах результат.

многопоточность конечно прикольно и неплохо, но не всё можно распаралелить и не всегда успеть «синхрониовать, и склеить результат».

MKuznetsov ★★★★★ ()
Ответ на: комментарий от svr4

svr4> И давно на них например вебсервер запустили?

А какая разница? Там процессор с огроменной кучей потоков. Свой код писать для этого нужно.

Quasar ★★★★★ ()

ТС, начнём с того, есть ли у тебя ВО, и если есть, то по какой специальности

Harald ★★★★★ ()
Ответ на: комментарий от Evgueni

Нормальный ЯП ничего не знает о задаче для которой всё это делается и я вас уверяю, что в случае параллельного программирования тормоза организовать гораздо проще, чем в случае последовательного.

Поэтому в том же matlab есть for и parfor, array и gpuArray. Выбор всё ещё за разработчиком, наличие удобных средств распараллеливания не отменяет наличия у программиста мозгов и профилировщика.

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

Опять же, об этом должен «думать» компилятор, а не разработчик.

распараллеливание на уровне компилятора

Именно.

Sadler ★★★ ()

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

Простые алгоритмы, занимающее одно ядро, на некоторых задачах могут оказаться быстрее и эффективнее параллельных многоядерных.

Мой вывод: нужно изучать всё и тестировать, собирать информацию по конкретному применению. «Узких мест» может быть навалом, особенно там, где не ожидаешь.

iZEN ★★★★★ ()
Ответ на: комментарий от Quasar

...который годен только для параллельных числодробильных задач и код общего назначения выполняет хуже первопня.

svr4 ()

говно какое-то.

треды, локи, семафоры - это всё отошло в прошлом веке ещё, вместе с юниксом.

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

n_play ()
Ответ на: комментарий от DRVTiny

Проблема параллельного программирования - только в отладке. Мне, например, из-за этого приходится подробно логировать всё происходящее внутри процессов/потоков до выхода кода в продуктив. Причём очень часто никакими синтетическими тестами невозможно воспроизвести ситуацию, возникающую при эксплуатации - это тоже добавляет проблем.

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

kawaii_neko ★★★★ ()

Нет, не маразм. Мало что поменялось реально. Да, вычислительные мощности выросли, но и сложность задач возросла. И тут в общем паритет. Конечно, если речь идёт о какой-нибудь простой оболочке для пользователя + плеер плюс ещё что-нибудь, то мощностей несколько больше, чем нужно. Но опять же, разрешения стали большие, они сами по себе сжирают ресурсы.

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

ixrws ★★★ ()
Ответ на: комментарий от Sadler

Нормальный ЯП должен предоставлять возможности для прозрачного распараллеливания без необходимости задумываться о гонках, deadlock'ах и прочей низкоуровневой ерунде.

А еще лучше быть здоровым и богатым, а не бедным и больным. Боженька требует за халяву платить.

dmxrand ()
Ответ на: комментарий от DRVTiny

Я вас расстрою, но 30 не 30, но 20 лет назад в CS журналы уже не принимали алгоритмы не допускающие распараллеливания.

dmxrand ()
Ответ на: комментарий от Quasar

На локалхосте всегда пофиг, что там и как.

Ну да все на словах Львы Толстые. А потом наблюдаем как создается 100 потоков каждый из которых обрабатывает 1 гиговый кусок и все дохнет. А казалось бы сохрани запросы и обработай их последовательно.

dmxrand ()
Ответ на: комментарий от n_play

асинхронные примитивы

технология 60-тых, между прочим.

aiqu6Ait ★★ ()

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

На мой взгляд, в современных реалиях наиболее эффективно себя показывают алгоритмы «разделяй и властвуй» наподобие QuickSort'а - т.е. те алгоритмы, которые позволяют разбить выполнение задачи на множество параллельно выполняющихся подзадач

Забавно. Что, существует параллельный quicksort?

tailgunner ★★★★★ ()

У меня складывается стойкое ощущение, что использование классических супер-эффективных алгоритмов со всякими чудесными O(n) в современных реалиях, когда серверы со 128-ю процессорными ядрами стали скорее нормой



Но я даже не удосужился погуглить материалы современных ИТ универов на неродном языке, чтобы просветить общественность о реальном положении вещей на рынке НРС.

А я, rtp, так вообще мимо топика крокодил, так даже я догадался что надо сперва гуглить маркетинговые наработки всяких MIT.

Deleted ()

Толсто же. Попробуй еще раз

xnick ()

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

Сколько комплексов...

Solace ★★ ()

наиболее эффективно себя показывают алгоритмы «разделяй и властвуй»

ага, с небольшой паузой на форк-джойн. Но это ладно

в целом пост имхо маразм. если у тебя алгоритм O(e^x), то хоть ты его на 100500 ядер перекинь - вкуснее он пахнуть не станет. на курсере в курсе алгоритмов есть збс примеры этого дела, если их чутка подрихтовать в плане параллельности, то результат все равно тот же будет.

кратко - ты серьезно хочешь сказать что линейный поиск в массиве на 100500 значений, даже если мы его на 128 ядер разобьем, будет быстрее поиска в бинарном дереве на одном ядре? ха!

upcFrost ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.