LINUX.ORG.RU

Новая самая быстрая реализация QuickSort на AVX2

 ,


2

6

Вышла железная сортировка для целых чисел максимально полно использующая расширение процессоров x86 AVX2. На данный момент это самая быстрая сортировка вообще. Так же автор щепетильно подошел к вопросу формальной верификации алгоритма. Доступна версия для int32, но по заверениям автора алгоритм легко перенести на другие битности. Особо отмечено что алгоритм можно использовать в криптографических приложениях.

Также автор обещает порт на ARM NEON

>>> Подробности

★★★★

Проверено: jollheef ()
Последнее исправление: Deleted (всего исправлений: 3)

Ответ на: комментарий от steemandlinux

Что именно майниш и как? Я посмотрю твой говнокод.

anonymous
()
Ответ на: комментарий от LjubaSherif

Ты просто завидуешь. Кто тебе мешает поучаствовать раз ты такой умный? Сделал бы себе имя среди серьёзных людишек на раз.

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

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

Какое имя есть у этих людишек? Это нонеймы с помойки, которые просиживают жопу за еду и едят по воле хозяина. Нахрен мне эта помойка?

К тому же, это удел мартых прыгать и жопой крутить, подобное поведение недостойно тех, кто хоть каплю себя уважает. Если ты настолько мусор, что единственное, что ты можешь сделать - это пустить пыль в глаза домохозяек, то ты расписался в своей некомпетентности. Сим ты сказал «я ничего объективно полезного сделать не могу - мой потолок впаривать домохозяйкам всякое дерьмо».

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

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

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

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

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

anonymous
()
Ответ на: комментарий от Thero

мы вроде говорим о наступающей постквантовой эпохе..

Зачем вы постоянно повторяете левые базворды? Никакая квартовая эпоха не имеет никакого отношения к теме.

Это банальные тезисы секты таймингатаки.

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

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

LjubaSherif
()
Ответ на: комментарий от anonymous

Хватит кривляться, выпендрёжник.

Амёба целиком и полностью обделалась и решила в очередной раз проигнорировать свой предыдущий кукаретинг и насрать нового?

Так и скажи что криптография и проблемы квантовых вычислений это

Это так мило, когда ламерок открыл ссылку и увидел там два базворда «квантовый» и «криптография» и начал их повторять, только вот всё, что идёт дальше - не имеет никакого отношения ни к «квантовый», ни к «криптографии».

не твой дошкольный уровень минимального байтоёбства с воспроизводимыми на одном субсете аппаратной платформы эффектами.

Самое интересное то, что дошколёнок не имеет никакого отношения ни к первому, ни ко второму, но почему-то явно кукарекает.

Это так смешно, когда домохозяйка начинает что-то вещать об уровне, производительности, платформе. Твои призвание - полы мыть, вот и мой. Зачем кукарекаешь о чём-то, что находится за рамками твоего восприятия?

А самое интересное то, что «постквантумных» балаболов в 10раз больше даже и как-то странно получается. В то, что проще - умеют меньше, нежели в то, что сложнее. Вот ведь незадача.

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

Ты — грязь, чувак пишущий эти алгоритмы нет. Ты хуже чем грязь, ты ничто. Тебя не существует. Что тут обсуждать? Слишком много слов.

Вот тот чувак кстати, если ты не знаешь, кто это https://en.wikipedia.org/wiki/Daniel_J._Bernstein

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

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

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

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

А так, уязвимые алгоритмы весьма выгодны с точки зрения правительства и есть люди не согласные с подобным. Можно совершенно спокойно исходить из предположения, что противники — низкопробные «пропагандоны», действующие в чужих интересах.

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

На что только люди не пойдут ради денег. Ничего святого.

anonymous
()
Ответ на: комментарий от LjubaSherif

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

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

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

В этом и проблема, ты даже не читаешь то, что линкуешь.

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

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

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

Существует - разрешение измерений. Вся эта макулатура ссылается на микро-эффекты, для получения которых нужны измерения времени с разрешением в наносекунды. А рамках удалённого доступа ЧИСТО ФИЗИЧЕСКИ нельзя получить разрешение большее, нежели в миллисекунды. Таким образом до того момента как ты научишься предавать информацию хотя-бы с на 3(реально 6) порядка большей скоростью, нежели световая - ни о каких тайминг-атаках и речи быть не может, даже теоретически.

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

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

удалённого доступа ЧИСТО

нуну.

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

anonymous
()
Ответ на: комментарий от LjubaSherif

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

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

Не нужно сливаться с темы, я упомянул спектр выше. Почему вы все такие? Зачем ты мне пишешь рандомные фразы и прочую шаблонную херню. Ты мне нормально отвечай, либо признавайся, что балабол. Что же ты постоянно свои тезисы забываешь, а мои игнорируешь?

Кстати, спектр множит твои потуги на ноль, целиком и полностью. Я выше об этом писал. Методика эксплойта 1в1 повторяет тайминг-атаку. И тут мы видим фундаментальную разницу. Методика достижения цели одна, теоретической базе 20лет в одном случае, пару дней в другом. Эксплойт в первом случае не родился за двадцать лет НИ ОДИН, а во втором за пару часов и не один.

Разреши это явное противоречие - как так получилось? К тому же, почему тайминг-ламерки не запилили удалённый эксплойт? Это же основное их пугало - где оно?

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

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

Очередная шаблонная херня, ведь догматы есть у тебя и я их показал. Ты не ни одного моего не показал. К тому же, все мои тезы имеют обоснования, а твои потуги это нытьё вида «ааа, я не знаю как ответить», «ааа, мне нечего ответить - напишу шаблонную херню про догматы», «ааааа, я нихрена не понимаю - буду повторять услышанные где-то базворды и авось меня за умного поискают» - нет, не посчитают.

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

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

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

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

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

P.P.S я возможно упустил некоторые ваши домыслы и агрессивно-провокационные вопросы из-за предварительной фильтрации.

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

нужно пояснить о том что спектр был предсказан до того как запилили первую реализацию спекулятивного исполнения?

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

Есть теоретическая база любой уязвимости, и к спектру никакого отношения никакое «спекулятивное выполнение» отношения не имеет. Не нужно повторять базворды из интернета, повторю в десятый раз. Если очень просто - люди поняли, что наружу торчат некие побочные эффекты того самого исполнения. Далее люди научились их использовать. Самое спекулятивное исполнение не предполагает(прямо) ничего из этого.

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

что у нас нет никаких данных о том реальна угроза тайминг атак или это полная чушь?

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

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

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

Я уже в который раз слышу повторение одной и той же ахинеи, которую я уже давно помножил на ноль.

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

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

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

djbsort по заявлениям автора этим требованиям соответствует.

Ты несёшь полную херню, ты выше писал:

изменит подходы к обработке информации способами которые мы не можем однозначно предсказать.

Если ты не можешь что-то предсказать - как ты определит соответствие? Правильно - никак. Это херня.

вы считаете автор воюет с квантовыми мельницами?

Я не считаю - это так и есть. Есть два возможных варианта. А) автор набивает себе очки на хайповом дерьме. б) автор просто написал это пункт для того, чтобы от него просто отстали эти ламерки со своим дерьмом. В пользу этого говорит и то, что он написал про пост-квантовый мир, а далее написал про тайминг-атаки.

И да, автор прав. Его сортировка(как и любая другая) действительно неуязвима к тайминг-атакам, а знаешь почему? Потому что их нет.

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

Я уже это доказал. Я по умолчанию прав, пока адепты этой секты не докажут иное. А они не докажут это никак и никогда, ведь это противоречит базовым свойствам этой реальности.

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

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

P.P.S я возможно упустил некоторые ваши домыслы и агрессивно-провокационные вопросы из-за предварительной фильтрации.

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

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

Хмм тогда почему все 100 лет знали о спектрах, и я помню обсуждения и активное использование схожих уязвимостей ещё в 90х, но не использовали? Я вот тоже не понимаю с чего такой интерес, это всё было известно очень давно и всем было насрать. Можно предположить, что это как-то связано с облаками и сменой поколений.

Уязвимость крипты тут менее мифическая, очень больно будет всем как только появятся алгоритмы приносящие достаточные результаты (а у кого будет доступ к ним и технологии? хинт: не у тебя).

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

Вполне вероятно что это вообще был бэкдор и люди «в теме» успешно его использовали, находили же неизвестные команды процессора и странные необъяснимые эффекты. Которые добавляют в errata, однако более вероятно что всё запланировано. Тут вопрос, ошибка это или бэкдор? Я склоняюсь к последнему.

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

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

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

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

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

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

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

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

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

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

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

Наверное считали что слишком сложно и архитектурозависимо.

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

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

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

Ну это альтернативная ветка развития,не могу сказать, насколько успешная, жидкоазотники вон уже 50 кубитов вместе собрали и заставили работать.

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

Я по умолчанию прав, пока адепты этой секты не докажут иное. А они не докажут это никак и никогда, ведь это противоречит базовым свойствам этой реальности.

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

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

SMT не имеет никакой фактической ценности по части загрузки чего бы то ни было

Современные процессоры умеют out-of-order execution, то есть переставлять инструкции местами, сохраняя зависимости внутри CFG. Поток исполнения может заблокироваться, если для выполнения следующего блока инструкций нужен результат от предыдущего, который ещё не готов. Сама суть исполняемой на потоке задачи может быть такова, что не представляется возможным утилизировать все исполнительные блоки ядра. Тут и пригождается SMT — можно утилизировать ресурсы ядра полнее, запустив второй поток, пока первый занят ожиданием результата.

Другой (положительный для производительности) эффект SMT — «аппаратное» переключение контекста между hyperthreading siblings сильно дешевле, чем переключение контекста между процессами ОС.

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

Эти потуги. Ты неправ не потому, что ты неправ априори. Ты балабол, а балабол априори неправ.

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

LjubaSherif
()
Ответ на: комментарий от kmeaw

Современные процессоры умеют out-of-order execution, то есть переставлять инструкции местами, сохраняя зависимости внутри CFG.

Полная херня. Никто и нигде никакие инструкции не переставляет - это допущение для дошколят, которое ты пытаешься ретранслировать из интернета.

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

Опять же, херня. Никакого одного и вообще потока инструкций в рамках ОоО нет.

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

Таких не бывает, а если и бывают - им SMT никак не поможет.

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

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

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

Да ты явно одарён, если поток занять ожиданием результата - зачем нужен OoO? Правильно - ничем. Это проблема твоих детсадовских представлений, которые не имеют никакого отношения к реальности.

Другой (положительный для производительности) эффект SMT — «аппаратное» переключение контекста между hyperthreading siblings сильно дешевле, чем переключение контекста между процессами ОС.

Чего? Как всё запущено. Переключение процессов существует в рамках ОС и никакого отношения к SMT не имеют. Это внешняя относительно процессора логика. Процессор никак не может ничего с ней поделать.

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

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

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

У современных интелов SMT на стероидах так-то, ос не может предсказать где он смержит и оптимизирует. По этой же причине можно получить 130% производительности вместо теоретических менее 100. Что-то реальность расходится с твоими теориями, или ты о чём-то другом?

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

Ты пишешь какую-то херню. Ты просто выкрикиваешь рандомные фразы из которых ничего не следует.

У современных интелов SMT на стероидах так-то, ос не может предсказать где он смержит и оптимизирует.

Вот что из этого следует? В чём эти стероиды заключаются, причём тут вообще ОС? ОС никогда и нигде не знает о том, как исполняются её потоки. Вне зависимости от того, какое там SMT - на стероидах, либо нет.

По этой же причине можно получить 130% производительности вместо теоретических менее 100.

Вот опять херня, получить 130% относительно чего? В чём? Очередные детсадовские рассуждения.

Эти потуги из разряда - на моих гипертредах синхронизация работает быстрее. И толку с этого? Это изначально проблема твоего говнокода и никакого отношения к теме не имеет. Мы обсуждаем свойства реальности, а не свойства какого-то дерьма. В рамках дерьма может быть всё что угодно, может 100500 тредов на 10 ядрах работать лучше, а может и 10 на 100500 ядрах. Но из этого ничего не следует и ничего не значат.

Что-то реальность расходится с твоими теориями, или ты о чём-то другом?

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

SMT физически не может дать больше, чем один поток, ведь он исполняется в рамках того самого одного потока. Это как говорить о том, что «моё авто-распараллеливание на два потока даёт на одноядерной системе(без SMT) больше производительности». Этого физически быть не может, ведь ОС всё равно ведёт твои два потока к одному.

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

Самый популярный пример я уже разобрал. Синхронизация. Только проблема знаешь в чём? Ты не сравниваешь синхронизацию между одни ядро и двумя SMT-тердами. Ты сравниваешь её между двумя SMT-ядрами и двумя обычными. Ты нарушаешь условие сравнения, но ты не понимаешь этого. И в этом твоя(и не только) проблема.

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

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

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

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

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

Внимание вопрос - зачем ты пытаешься съехать на какие-то там рассуждения про новое/старое, если ты не знаешь это новое?

Опять же, ты пытаешься манипулировать. Никто не отрицал твоё учение - я лишь его критиковал, задавая тебе(его адепту) вопросы. Вопросы относительно его применимости к реальности. Ведь ты говоришь о какой-то секте не как о чём-то новом/левом, а как о то, на что мне нужно смотреть и что мне нужно учитывать. Ты претендуешь на применимость своего учения в рамках далеко за рамками твоей секты.

И ты считаешь, что ты не должен обосновывать его применимость? И тебе говорили именно об этом, и только об этом. Само по себе твоё учение никого не интересует, а я не обязан принимать твоё учение лишь потому, что оно «новое»(на самом деле это дерьмо мамонта, просто для вас, домохозяек, хайп дошел только сейчас).

Ты немного перепутал, ты решил, что твои «философские» рассуждения и апелляции к логике - будет играть за тебя, даже если ты не знаешь предмета. И действительно - они бы сработали, против рядового балабола, даже если они знает какой-то предмет.

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

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

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

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

SMT физически не может дать больше, чем один поток, ведь он исполняется в рамках того самого одного потока.

Для начала, написать код, который сможет задействовать все ФУ современного процессора - это весьма сложная задача. Некоторые считают, что это вообще невозможно. Помимо этого, сами алгоритмы могут не позволить этого сделать, размер ROB-а ведь ограничен.

Ну, и про микроархитектуры IBM-овских POWER8 и POWER9 тебе, царь, не помешало бы что-то почитать. «Ядро против ядра» эти процессоры конкретно дрючат штеудовские Xeon-ы, именно за счёт большого количества ФУ и широкого SMT.

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

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

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

Насколько слышал, smt на паверах маразматический.

Это фанаты штеуда распускают слухи (ибо некоторые из них заинтересованы материально). Всё с Power-ами нормально, и стоят они сейчас дешевле штеудов.
Для серверных нагрузок, для которых и предназначены POWER-ы, много ядер(SMT потоков) это хорошо . Это для десктопов, рабочих станций и HPC однопоточная производительность часто бывает предпочтительнее.

В Power-ах, кстати, есть такая фишка, что они могут динамично изменять количество SMT потоков на ядро. Безо всяких перезагрузок, как у Штеуда, а прямо на лету.

anonymous
()
Ответ на: комментарий от LjubaSherif

> out-of-order execution, то есть переставлять инструкции местами, сохраняя зависимости внутри CFG

Полная херня. Никто и нигде никакие инструкции не переставляет.

А что тогда делает OoO? Может ли вычислительное ядро выполнить несколько инструкций за один такт, если мы этого явным образом не просим (ISA не VLIW)? Что будет, если в потоке инструкций встретися такая, результат (эффект) исполнения которой зависит от внешнего по отношению к ядру устройства?

> … суть исполняемой на потоке задачи … не … утилизировать все … блоки

Таких не бывает, а если и бывают - им SMT никак не поможет.

Почти любая задача, которая состоит из итераций, меняющих состояние так, что каждая последующая зависит от предыдущей (то есть не поддаётся параллелизации). Пример: посчитать MD5 от сообщения размером больше 512 бит. Пока не обработаем первые 512 бит, следующие 512 обработать не сможем, так как состояние MD5 для них ещё неизвестно.

У Haswell есть по крайней мере 4 ALU и 2 load/store units. Одна итерация внутреннего цикла MD5 не использует их все одновременно.

если поток занять ожиданием результата - зачем нужен OoO?

Чтобы догрузить ядро чем-то ещё. Пока блоки ядра заняты одной задачей, другие можно занять другой.

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

Пусть у нас есть два вычислительно-тяжёлых процесса A и B.

Сначала запустим их на CPU с одним ядром без SMT под многозадачной ОС. Работает процесс A, приходит прерывание от таймера, тратим такты на переключение контекста между A и ядром, затем на переключение контекста между ядром и B — A, B и ядро конкурируют хотя бы за регистры, поэтому нужно делать load/store.

Теперь всё то же самое, но с SMT. Мы можем (с точки зрения ядра ОС) запустить A на thread0, а B на thread1. Конечно же, на самом деле они не будут выполняться одновременно. Но переключаться между ними будет уже не ОС, а сам CPU. В итоге выполняется меньше кода (не нужен context switcher ОС), не делаются лишние load/store.

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

А что тогда делает OoO?

Я дал более-менее полное описание выше.

Может ли вычислительное ядро выполнить несколько инструкций за один такт, если мы этого явным образом не просим (ISA не VLIW)?

Дело не в «инструкций за такт» - ОоО нужно не только для этого, «любая» операция пайплайновая и никакими «одним тактов» не измеряется.

Что будет, если в потоке инструкций встретися такая, результат (эффект) исполнения которой зависит от внешнего по отношению к ядру устройства?

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

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

У тебя фундаментальная дыра в восприятии, ты почему-то решил, что один поток - это один поток. Это нихрена не так.

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

У Haswell есть по крайней мере 4 ALU и 2 load/store units. Одна итерация внутреннего цикла MD5 не использует их все одновременно.

И тут у тебя фундаментальная дыра в восприятии. Юниты - это только мала часть параллельности ядра. Существуют как минимум пайплайн, а так же симды. К тому же в хасвеле не 2 load/store units.

Даже если бы там был один «load/store units», то в любом случае нужно ОоО для его загрузки, ведь операция исполняется, допустим, 5 тактов, то нужно минимум 5 параллельных операций для загрузки одного «юнита».

Чтобы догрузить ядро чем-то ещё. Пока блоки ядра заняты одной задачей, другие можно занять другой.

Ты сам себе противоречишь.

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

Всё куда интереснее.

Сначала запустим их на CPU с одним ядром без SMT под многозадачной ОС. Работает процесс A, приходит прерывание от таймера, тратим такты на переключение контекста между A и ядром, затем на переключение контекста между ядром и B — A, B и ядро конкурируют хотя бы за регистры, поэтому нужно делать load/store.

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

Опять же, полная херня - никакие твои днищенские х86-регистры не имеют отношения к load/store.

Теперь всё то же самое, но с SMT. Мы можем (с точки зрения ядра ОС) запустить A на thread0, а B на thread1. Конечно же, на самом деле они не будут выполняться одновременно. Но переключаться между ними будет уже не ОС, а сам CPU. В итоге выполняется меньше кода (не нужен context switcher ОС), не делаются лишние load/store.

Полная херня, таски итак будут переключатся - никто и нигде не выделяет таскам ядра монопольно. Про load/store - полная херня.

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

> Что будет, если в потоке инструкций встретися такая, результат (эффект) исполнения которой зависит от внешнего по отношению к ядру устройства?

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

По какому принципу?

> > если поток занять ожиданием результата - зачем нужен OoO?

> Чтобы догрузить ядро чем-то ещё. Пока блоки ядра заняты одной задачей, другие можно занять другой.

Ты сам себе противоречишь.

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

add ecx, ebx
in dx, al
shr esi, 2

Если не будет OoO, то во время выполнения in мы будем вынуждены гнать пустышки (bubble) по пайплайну вместо выполнения полезной работы.

В чём противоречие? И зачем же на самом деле нужен OoO?

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

Для этого надо написать однопоточную программу, вычисляющую несколько md5 одновременно на одном ядре.

Если у нас будет гипотетическая ОС, знающая абсолютно всё про исполняющиеся процессы, используемой в машине процессор и умеющая перекомпилировать код за нулевое время, то SMT перестанет быть нужным — захотел пользователь считать две штуки md5 параллельно, ОС взяла и слила две задачи в одну, да так, что они в одно ядро поместились.

Пока же такой ОС нет, и эту работу выполняет CPU. SMT позволяет ОС предоставить процессору две задачи md5 вместо одной.

> Поток исполнения может заблокироваться, если для выполнения следующего блока инструкций нужен результат от предыдущего, который ещё не готов.

Всё куда интереснее.

Как же?

Опять же, полная херня - никакие твои днищенские х86-регистры не имеют отношения к load/store.

А где же ОС тогда хранит контекст процесса, и как можно восстановить/сохранить его без load/store?

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

Я не утверждаю, что переключений совсем не будет. Но их будет меньше.

переключение тасков происходит настолько редко

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

Твоё представление о том, как происходит процесс вычислений в современных CPU явно отличается от моего. Где я могу ознакомиться с тем, как всё устроено на самом деле?

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

По какому принципу?

Описано выше.

В моём представлении, OoO нужен для того, чтобы не гнать впустую пайплайн

У тебя уже откуда-то взялся пайплайн, которого раньше не было? А взялся он потому, что я о нём тебе рассказал?

когда нам неизвестен результат одной инструкции в середине потока инструкций.

Тебе дали две твоих цитаты, которые противоречат друг друга.

Если не будет OoO, то во время выполнения in мы будем вынуждены гнать пустышки (bubble) по пайплайну вместо выполнения полезной работы.

Никто не сравнивает наличие и отсутствие ОоО. К чему и зачем ты это пишешь?

В чём противоречие? И зачем же на самом деле нужен OoO?

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

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

Вот то, что противоречило, а не то, что ты там цитировал.

Для этого надо написать однопоточную программу, вычисляющую несколько md5 одновременно на одном ядре.

И? Тебе кто-то говорил о том, что не нужно? Либо что? К чему эти откровения?

Если у нас будет гипотетическая ОС, знающая абсолютно всё про исполняющиеся процессы, используемой в машине процессор и умеющая перекомпилировать код за нулевое время, то SMT перестанет быть нужным — захотел пользователь считать две штуки md5 параллельно, ОС взяла и слила две задачи в одну, да так, что они в одно ядро поместились.

Причём тут твоя гипотетическая ОС? Тебе кто-то говорил о том, что рядовое дерьмо будет работать так же? Нет. Нормальный код никуда не надо сливать. А про то, что SMT - это костыль, который позволяет ускорять дерьмо - я уже писал.

Пока же такой ОС нет, и эту работу выполняет CPU. SMT позволяет ОС предоставить процессору две задачи md5 вместо одной.

Я уже писал зачем и для чего нужно SMT, ничего нового ты не написал.

Как же?

Уже было описано выше.

А где же ОС тогда хранит контекст процесса, и как можно восстановить/сохранить его без load/store?

Ты не говорил о контексте, о контексте было отдельно и я отдельно же ответил. Ты пытался там намекать на «больше регистров - быстрее работает». Именно на это я отвечал.

Я не утверждаю, что переключений совсем не будет. Но их будет меньше.

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

Твоё представление о том, как происходит процесс вычислений в современных CPU явно отличается от моего. Где я могу ознакомиться с тем, как всё устроено на самом деле?

Есть базовый мануал от интела, а дальше уже твой личный опыт. Начать стоит с этого.

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

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

В случае с OoO ожидание остановит поток тогда, когда не осталось ни одной инструкции, эффект от которой не зависит от того результата, который мы ожидаем.

И? Тебе кто-то говорил о том, что не нужно? Либо что? К чему эти откровения?

Похоже я начал понимать, к чему ты.

Всё наше обсуждение началось с того, что ты считаешь, что

SMT - это костыль, который позволяет ускорять дерьмо

а я с этим не могу полностью согласиться (считаю, что SMT хоть и костыль, но полезный).

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

1) один экземпляр этой задачи нельзя ускорить с помощью SMT;

2) для любого количества одновременно запущенных экземпляров этой задачи справедливо утверждение, что с SMT wall clock time будет не меньше, чем без SMT;

3) включение SMT не помогает выполнить какой-либо (возможно дерьмовый) код с любой ненулевой производительностью без ущерба для производительности твоей задачи.

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

Если ты считаешь эту задачу дерьмовой, то либо объясни почему, либо дай определение дерьмовости.

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

В случае с OoO ожидание остановит поток тогда, когда не осталось ни одной инструкции, эффект от которой не зависит от того результата, который мы ожидаем.

Манёвры, такие манёвры. Я тебе дал твою цитату, а ты про неё забыл и выдал новую, которая ещё хуже. В стране эльфов у тебя там будет так, как ты написал.

Всё наше обсуждение началось с того, что ты считаешь, что

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

1) один экземпляр этой задачи нельзя ускорить с помощью SMT;

Очевидно, что любая нормально реализованная задача.

2) для любого количества одновременно запущенных экземпляров этой задачи справедливо утверждение, что с SMT wall clock time будет не меньше, чем без SMT;

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

3) включение SMT не помогает выполнить какой-либо (возможно дерьмовый) код с любой ненулевой производительностью без ущерба для производительности твоей задачи.

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

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

И, к чему ты пишешь эту детсадовскую херню? Я уже на это отвечал.

Если ты считаешь эту задачу дерьмовой, то либо объясни почему, либо дай определение дерьмовости.

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

Определение дерьмовости очевидно - любой код с низким уровнем параллелизма уровня инструкций.

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

Определение дерьмовости очевидно - любой код с низким уровнем параллелизма уровня инструкций.

Внезапно, есть не код, а алгоритмы, на которых в принципе невозможно получить высокий ILP на современных процессорах с их ограничениями (размер instruction window, например).
И данные для обработки могут поступать последовательно, маленькими порциями, без возможности их буферизирования (потоковая обработка с высокими требованиями по времени обработки. Т.е. ты не можешь сложить в буфер несколько пакетов данных и затем обработать их параллельно, ибо требования по QoS. Результат нужно быстро выплюнуть для каждого мелкого входного пакета, а не дожидаться, когда их накопился несколько штук, чтоб это распараллелить).

anonymous
()
Ответ на: комментарий от LjubaSherif

Шото даже не знаю. Твой манямирок не совсем отражает действительность? На практике SMT принесёт пользу на интеле весьма редко, это говнище ещё то. Но эмм, если не из чего выбирать, на ряде задач можно поиметь профит. Что-то уровня кодирования x264 и прочее такое дерьмо. Вебня опять же. Там не все блоки задействуются, экономить можно сколько угодно. И не весь код будешь писать лично ты и не всегда идеально. Но код херня, это лишь малая часть.

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

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

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

Внезапно, есть не код, а алгоритмы, на которых в принципе невозможно получить высокий ILP на современных процессорах с их ограничениями (размер instruction window, например).

Ты ничего не получишь и в ситуации с SMT. Опять же, несёшь херню. Какие-то алгоритмы параллелят только колхозники. Поэтому, абсолютно насрать на то, какой там у тебя алгоритм - всегда можно запустить два, параллельно. А когда нельзя - ты не получишь никакого профита и от SMT/MT, повторю второй раз.

И данные для обработки могут поступать последовательно, маленькими порциями

Проблема твоего колхоза, SMT никак не поможет.

без возможности их буферизирования (потоковая обработка с высокими требованиями по времени обработки.

Перепутал колхоз, современные процессоры не про летенси.

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

Могу, ты пишешь отборную херню. Любая обработка в любом колхозном api буфиризована, а ничего, кроме колзоз-апи у колхозников нет.

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

Опять же, если пакеты независимы - последовательность не противоречит параллельности и никакая буферизация не обязательна. Если у тебя есть зависимости - ты уже прокукарекался с буферизацией.

ибо требования по QoS.

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

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

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

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

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