У меня есть сомнения, что возможно изобрести «максимально эффективный алгоритм» копирования для всех вариантов процессора (если посмотреть на разные реализации memcpy то можно слегка устать от разнообразия оптимизаций под разные поколения внутри одной архитектуры x86). Между ядром и физической памятью всякие кэши, таблицы трансляции и прочая. По сути, аппаратная реализация будет вызывать такую же последовательность операций на шине, что и в софтовой реализации.
Подозреваю что мешает общая сложность устройства. Поскольку x86 как бы RISC с CISC интерфейсом, то есть CISC команды транслируются в простые микрооперации, которые исполняются RISC ядром. Но аппаратно реализовать машину, которая REP MOVSB развернёт в соответствующие операции работающие сразу с многими байтами (аналог векторизации) не имеет большого смысла, поскольку оно будет выполняться практически с такой же скоростью как и чисто софтовый аналог (кэширование, префетчинг, предекодинг, предсказание ветвлений, конвееризация доступа к памяти и прочая). Сложность верификации (привет всякие уязвимости и баги) аппаратных реализаций намного выше, чем софтовых, а цена устранения аппаратных ошибок после запуска производства и вовсе космическая (даже при наличии микрокода).
Трудно не согласиться с Хомски, по поводу того, что сегодня «искусственным интеллектом» называют то, что к, собственно, «интеллекту» (в бытовом понимании) имеет весьма отдалённое отношение. Обученная нейронная сеть выступает эквивалентом оптимального фильтра, у которого коэффициенты были «подобраны» на основе входных данных (а не вычислены аналитически, к примеру).
Кажеца на stackoverflow, задавали вопрос типа: «а что если обучить сеть на куче простых чисел, сможет ли она предсказывать, что произвольное число является простым?» (и похакать протоколы использующие «модульную арифметику больших простых» =). Ответ на этот вопрос вполне очевиден.
Это никоим образом, конечно, не говорит о бесполезности такого типа ИИ — он прекрасно применяется в разных областях. Остаётся только процитировать Ноама, что без новых подходов (то есть простым увеличением мощности и быстродействия) не преодолеть ограничений.
Есть, кстати, интересные гипотезы (Пенроуз, Квантовое сознание), что немаловажную роль в процессах мышления в мозге играют квантовые эффекты. Ждём ебилдовмощных квантовых вычислителей, штобы на них помоделировать, вдруг это оно? =)
Писать связно и по-порядку несколько лениво. Но вот ключевые термины и моменты.
CRC является подмножеством циклических кодов (keywords: поля Галуа, коды БЧХ, порождающий полином, синдром, расстояние Хэмминга).
Вероятность не/обнаружения ошибки вычисляется достаточно нетривиально (насколько я знаю на данный момент только брутфорс и товарищ Koopman уже отбрутфорсил много полиномов для разных длин сообщений и расстояний Хэмминга (можно ознакомиться с результатами здесь: users.ece.cmu.edu/~koopman/crc).
*о — это значит полином содержит множитель x+1 (keywords бит чётности) и, следовательно, детектирует все «нечётные ошибки», это когда нечётное количество бит поменяло своё значение.
Из простых рабоче-крестьянских предположений можно рассуждать так: для 16-битного CRC число возможных состояний 2^16 — 1 = 65 535. И, следовательно мы должны обнаруживать однократные ошибки для сообщений длиной 2^16 — 1 — 16 (длина CRC) = 65519 бит. (на самом деле, мы знаем, что нечётные ошибки будут обнаружены при любой длине сообщения). Для ошибок большей кратности можно ожидать что, верхняя граница длины сообщения должна быть такой, чтобы число возможных перестановок ошибочных бит (keywords биноминальный коэффициент) не превышвало число возможных состояний CRC.
Это даёт неплохую оценку, но, как показывает брутфорс эта оценка справедлива только для малых значений расстояний Хэмминга.
Не могу вспомнить источник информации, но насколько я помню, при правильном предсказании ветвления команда Jxx удаляется с конвеера полностью (предсказатель ветвлений работает независимо от конвеера), а CMOVxx выполняется всегда (выполняется цикл записи), условие только выбирает куда записать результат: в точку назначения или в «пустоту».
Почему так сделано — не знаю, но наверняка для этого есть причины. Например, что просто удаляя правильно предсказанную команду Jxx нам не надо учитывать много факторов, мы просто подгружаем в конвеер данные с предполагаемого адреса, а в случае факапа в точке предполагаемого ветвления перезапускаем конвеер (привет Meltdown и Spectre).
А удаление CMOVxx завязано на переименование регистров, отложенные вычисления и Зевс знает какие ещё оптимизации. Видимо оно того не стоит.
Несколько удивительно в таком формате от Александреску. Обычно он предлагает смотреть машинный код (что правильно), видимо тут просто лайт-версия, чтобы не травмировать нежную психику. А то ведь можно упомянуть, что у многих современных архитектур есть conditional-move (на x86, скорее всего, jit заменит ветвления на CMOVxx). Так же известно, что CMOVxx немного медленнее правильно предсказанного ветвления Jxx (по вполне рациональным причинам). И отсюда цифры в -18% и +200% становятся вполне очевидными (и даже предсказуемыми).
Первый скриншот: безуспешно пытался понять, как можно нажать кнопку «Ok» на окне, где есть только "Break", "Continue" и "Ignore".
Если по теме — проблема актуальная, но интрументацией она вроде неплохо решается на этапе отладки. Переполнение стека, на мой взгляд, это логическая ошибка (программист не расчитал нужный размер). Понятно, что в сложных системах эта величина трудно предсказуема, однако это не снимает с разработчика ответственности. Стек это такой же ресурс, как и всё остальное и в эмбедде надо чотко следить за всем.
Обожаю, когда люди «не в теме» переводят статьи с кучей специфических терминов. «Зарядовый насос», «круговой осциллятор», "… уменьшающие движение тока", «кремний на дне», «высокопродуктивный микроскоп» — это победа, ящитаю.
Если операция ввода/вывода была запланирована — её можно отменить вызовом функции CancelIo(). Что хуже, вызвать эту функцию может лишь тот же поток, который запустил первоначальную операцию. Все идеи организации отдельного управляющего потока разбиваются об это ограничение.
Кроме того, даже после вызова CancelIo() мы не можем быть уверены, что операция будет немедленно отменена (возможно, она уже выполняется, использует структуру OVERLAPPED и переданный буфер для чтения/записи).
Ровно так же как и для любых других операций: ждём уведомления.
Разница в типе нотификаций делает возможным (и достаточно тривиальным) эмуляцию IOCP с помощью epoll. Например, проект Wine именно так и делает. Однако, проделать обратное не так просто. Даже если у вас получится — это, вероятно, приведёт к потере производительности.
Тут дело скорее в том, что Overlapped IO само по себе и механизм уведомлений Completion Port более низкоуровневая абстракция, нежли механизмы epoll. Собственно OVL/IOCP суть отражение поведения ядра Windows на юзерспейс.
epoll говорит вам когда дескриптор готов к тому, чтобы с ним можно было что-то сделать — «а сейчас вы можете начать читать данные»
IOCP говорит вам когда запрошенная операция выполнена — «вы просили прочитать данные и вот они прочитаны»
А с записью ситуация зеркальная и не очень понятно, что лучше, что хуже. С epoll() механизм управления буферами и буферизации реализован в ядре и это хорошо, но если вы вдруг завтра придумаете более эффективный способ — то придётся править ядро. А для Windows вы и не сможете поправить ядро. Поэтому вот.
Да я, это, собсно, так, побуквоедствовать.
В доисторической рускоязычной литературе для обозначения регистров часто использовалась аббревиатура СОЗУ (сверхоперативное ЗУ). По сути регистры — это специального вида память, которая адресуется именами регистров (во многих современных архитектурах не мудрствуют и просто называют их r0, r1,… rN). Можно, для накала, рассматривать регистры как кэш управляемый вручную.
На x86 можно написать аналог любой программы, которая использует регистры без использования оных (а вот на load-store архитектуре — не выйдет). Да, ценой быстродействия. Собстно регистровая адресация это всего-лишь способ устранения ботлнека с памятью и ничего более.
Это я к тому, что данные загружаются в регистры не «так или иначе», а для устранения проблем быстродействия связанных с доступом к памяти (как и прозрачные кэши любого уровня).
Но чтобы эти данные как-то изменить, их в начале необходимо загрузить в регистры.
Вообще говоря это неверно для архитектуры x86. Есть команды (методы адресации) которые делают RMW или W напрямую с памятью. К примеру INC mem или MOV/ADD mem, imm
log2(qbrt(99 999 999)) ~ 8.85 = 9 iterations. The binary search performs on result, not an input value. So 9 iterations is enough, i believe.
Кажеца на stackoverflow, задавали вопрос типа: «а что если обучить сеть на куче простых чисел, сможет ли она предсказывать, что произвольное число является простым?» (и похакать протоколы использующие «модульную арифметику больших простых» =). Ответ на этот вопрос вполне очевиден.
Это никоим образом, конечно, не говорит о бесполезности такого типа ИИ — он прекрасно применяется в разных областях. Остаётся только процитировать Ноама, что без новых подходов (то есть простым увеличением мощности и быстродействия) не преодолеть ограничений.
Есть, кстати, интересные гипотезы (Пенроуз, Квантовое сознание), что немаловажную роль в процессах мышления в мозге играют квантовые эффекты. Ждём
ебилдовмощных квантовых вычислителей, штобы на них помоделировать, вдруг это оно? =)CRC является подмножеством циклических кодов (keywords: поля Галуа, коды БЧХ, порождающий полином, синдром, расстояние Хэмминга).
Вероятность не/обнаружения ошибки вычисляется достаточно нетривиально (насколько я знаю на данный момент только брутфорс и товарищ Koopman уже отбрутфорсил много полиномов для разных длин сообщений и расстояний Хэмминга (можно ознакомиться с результатами здесь: users.ece.cmu.edu/~koopman/crc).
Конкретно про 16-битные полиномы: users.ece.cmu.edu/~koopman/crc/crc16.html (в шапке есть ссылка где поясняется, что значат все эти цифры)
Конкретно про CRC-CCITT
(0x8810; 0x11021) <=> (0x8408; 0x10811) {32751,32751} | gold | (*op) CCITT-16
*о — это значит полином содержит множитель x+1 (keywords бит чётности) и, следовательно, детектирует все «нечётные ошибки», это когда нечётное количество бит поменяло своё значение.
Из простых рабоче-крестьянских предположений можно рассуждать так: для 16-битного CRC число возможных состояний 2^16 — 1 = 65 535. И, следовательно мы должны обнаруживать однократные ошибки для сообщений длиной 2^16 — 1 — 16 (длина CRC) = 65519 бит. (на самом деле, мы знаем, что нечётные ошибки будут обнаружены при любой длине сообщения). Для ошибок большей кратности можно ожидать что, верхняя граница длины сообщения должна быть такой, чтобы число возможных перестановок ошибочных бит (keywords биноминальный коэффициент) не превышвало число возможных состояний CRC.
Это даёт неплохую оценку, но, как показывает брутфорс эта оценка справедлива только для малых значений расстояний Хэмминга.
Почему так сделано — не знаю, но наверняка для этого есть причины. Например, что просто удаляя правильно предсказанную команду Jxx нам не надо учитывать много факторов, мы просто подгружаем в конвеер данные с предполагаемого адреса, а в случае факапа в точке предполагаемого ветвления перезапускаем конвеер (привет Meltdown и Spectre).
А удаление CMOVxx завязано на переименование регистров, отложенные вычисления и Зевс знает какие ещё оптимизации. Видимо оно того не стоит.
Если по теме — проблема актуальная, но интрументацией она вроде неплохо решается на этапе отладки. Переполнение стека, на мой взгляд, это логическая ошибка (программист не расчитал нужный размер). Понятно, что в сложных системах эта величина трудно предсказуема, однако это не снимает с разработчика ответственности. Стек это такой же ресурс, как и всё остальное и в эмбедде надо чотко следить за всем.
Ага. То есть Альтера отказалась, а Интел думает иначе.
Ровно так же как и для любых других операций: ждём уведомления.
Тут дело скорее в том, что Overlapped IO само по себе и механизм уведомлений Completion Port более низкоуровневая абстракция, нежли механизмы epoll. Собственно OVL/IOCP суть отражение поведения ядра Windows на юзерспейс.
А с записью ситуация зеркальная и не очень понятно, что лучше, что хуже. С epoll() механизм управления буферами и буферизации реализован в ядре и это хорошо, но если вы вдруг завтра придумаете более эффективный способ — то придётся править ядро. А для Windows вы и не сможете поправить ядро. Поэтому вот.
В доисторической рускоязычной литературе для обозначения регистров часто использовалась аббревиатура СОЗУ (сверхоперативное ЗУ). По сути регистры — это специального вида память, которая адресуется именами регистров (во многих современных архитектурах не мудрствуют и просто называют их r0, r1,… rN). Можно, для накала, рассматривать регистры как кэш управляемый вручную.
На x86 можно написать аналог любой программы, которая использует регистры без использования оных (а вот на load-store архитектуре — не выйдет). Да, ценой быстродействия. Собстно регистровая адресация это всего-лишь способ устранения ботлнека с памятью и ничего более.
Это я к тому, что данные загружаются в регистры не «так или иначе», а для устранения проблем быстродействия связанных с доступом к памяти (как и прозрачные кэши любого уровня).