Comments 92
Интересно сравнить какое время получилось бы если хранить таблицу с посчитаными значениями
Не понял вашего вопроса. Ведь в разделе «Предподсчёт» именно это и сделано.
тьфу, оборвался комментарий — с посчитанными значеними для 64битовых без трюка с разбиением на меньшие числа. То есть, так же получалось бы 0.01 как и для чара или больше? Таблица для всех возможных, ясно, не влезет, пусть для какогото диапазона.
Трудно сказать, что будет. Я описал лишь приёмы, работающие со всеми возможными числами каждого диапазона, и то не все возможные комбинации этих приёмов удалось проверить (таких комбинаций будет очень много). А Вы предлагаете некий весьма частный случай задачи, который в общем-то в такой абстрактной постановке не имеет смысла. Я не знаю, что будет, но я в принципе приложил немало усилий, чтобы подобные сравнения каждый мог бы повторить у себя сам.
Поясню один момент, который может быть непонятным сразу. Есть инструкция POPCNT, входящая в состав SSE4.2, которую по-хорошему мне тоже нужно было включить в список тестирования. Однако у меня нет процессора, который поддерживал бы SSE4.2. Сожалею об этом, но ничего поделать не могу.
Стоило бы упомянуть книгу «Hacker's Delight», в которой есть этот и многие другие подобные трюки.
Спасибо за совет, но я не стал давать никаких ссылок, потому что все объяснения в этой статье мои собственные (даже если они вдруг случайно повторяют чьи-то другие варианты объяснений, которых я даже не видел), а сами приёмы я узнавал из совершенно разных мест, которые сейчас и не собрать. Я просто поделился своим опытом.
В указанной Вами книге есть только один трюк для подсчёта единичных битов (боюсь соврать, но в моей редакции есть только параллельное суммирование) и один трюк касательно удаления младшего единичного бита.
В указанной Вами книге есть только один трюк для подсчёта единичных битов (боюсь соврать, но в моей редакции есть только параллельное суммирование) и один трюк касательно удаления младшего единичного бита.
UFO just landed and posted this here
Исходники на Я.Диске — это моветон в 2016-то году. Залейте на гитхаб, будет круто.
За статью респект, очень круто. Кстати, наблюдение — по-моему, вам в карму плюсанули примерно столько же людей, сколько статью:)
За статью респект, очень круто. Кстати, наблюдение — по-моему, вам в карму плюсанули примерно столько же людей, сколько статью:)
Ну там не только исходники, ещё презентация. Я не вижу смысла специально залезать на GitHub, чтобы просто положить 5 файлов и быть в тренде, и не вижу проблемы скачать архив, смотря на него просто как на файл. Спасибо за отзыв :)
У гитхаба по сравнению с просто облачным хранилищем файлов куча преимуществ. Например, вы удалите у себя инфу или переместите её куда-то — в статье останется битая ссылка. Или вы придумаете новый крутой алгоритм — при коммите подписавшиеся увидят это. Также может кто-то ещё дополнить ваши данные пулл-реквестом. Множество других людей, при должном оформлении, сможет увидеть ваши изыскания, даже не зная о существовании хабра. И так далее, и тому подобное. Сплошные плюсы и никаких минусов.
Что ж, спасибо за совет. Я теперь задумался, может мне имело бы смысл создать специальную ветку на GitHub для моих «Бесед о программировании», ведь я постоянно выкладываю учебный материал к ним пока что на Я.Диск. Сейчас я не планировал как-то его развивать, но, возможно, какой-то код будет совершенствоваться и будет иметь смысл делать обновления, а также давать другим что-то туда дописывать. Я подумаю над этим ещё.
В gcc есть функция __builtin_popcount, интересно посмотреть на ее положение в таблице.
Конечно, интересно, но у меня есть подозрение, что там реализован либо вызов POPCNT из SSE4.2, либо (когда данная функция не поддерживается процессором), что-то из моего набора приёмов. Так что она займёт место рядом с какой-то из уже записанных в таблице строк. Буду приятно удивлён, если кто-то обнаружит, что там написано что-то совершенно необычное, у кого есть исходники GCC, можете проверить.
Ну исходники-то не секретны, да. Там табличка
github.com/gcc-mirror/gcc/blob/master/libgcc/libgcc2.c
Осноное всё-таки — это дать возможность вызвать «железную» реализацию, если она есть. Она на каком-нибудь PowerPC появилась в незапамятные годы…
__popcount_tab и сопутствующие функции:github.com/gcc-mirror/gcc/blob/master/libgcc/libgcc2.c
Осноное всё-таки — это дать возможность вызвать «железную» реализацию, если она есть. Она на каком-нибудь PowerPC появилась в незапамятные годы…
POPCNT не будет использоваться, если не указать флаг -msse4.2, что означает либо компиляцию под определённую платформу либо шаманство с weak-функциями и потеря производительности на вызове функции. Если это узкое место, то нужно отдельно компилячить кучу версий — одну для sse4.2, одну для sse4.1… и так до sse2 который гарантированно поддерживается для 64-разрядной архитектуры.
К сожалению представленные на ЯД исходники не позволяют мне проверить все варианты, так как я не понял, что с ними нужно делать. Могу сказать только, что на i5 __builtin_popcount выдаёт 0.1 сек для 100000000 итераций с типом int для sse4.2 и 0.3 сек без него. На Xeon паршивый результат даже с sse4.2 — 0.25, без sse — 2 секунды. На core i7 лучший результат — 0.08 сек. На power хоть и есть инструкция popcntw, но её результат тоже не впечатляет — 0.3 сек.
К сожалению представленные на ЯД исходники не позволяют мне проверить все варианты, так как я не понял, что с ними нужно делать. Могу сказать только, что на i5 __builtin_popcount выдаёт 0.1 сек для 100000000 итераций с типом int для sse4.2 и 0.3 сек без него. На Xeon паршивый результат даже с sse4.2 — 0.25, без sse — 2 секунды. На core i7 лучший результат — 0.08 сек. На power хоть и есть инструкция popcntw, но её результат тоже не впечатляет — 0.3 сек.
Странно, но я постарался в комментариях описать, что делать. В любом случае, в статье написано, что число тестов равно 232.
Порядок действий таков: сначала запускаем «пустой» цикл, который не делает ничего, кроме генерации входного потока из 232 чисел. Например, в моём коде генерация выполняется по формуле n = 19993*n+1, где n имеет размер u32. Начав генерацию от n=0, мы закончим её на n=0, гарантированно пройдя по всем значениям. Измеряем время работы этого пустого цикла.
Затем запускаем этот же цикл, но с вызовом функции подсчёта битов. Измеряем время работы и вычитаем из него время работы пустого цикла — получаем некую оценку на почти чистое время работы функции. Немного грубо, но в пределах получающихся значений времени вполне достаточно для выводов.
Порядок действий таков: сначала запускаем «пустой» цикл, который не делает ничего, кроме генерации входного потока из 232 чисел. Например, в моём коде генерация выполняется по формуле n = 19993*n+1, где n имеет размер u32. Начав генерацию от n=0, мы закончим её на n=0, гарантированно пройдя по всем значениям. Измеряем время работы этого пустого цикла.
Затем запускаем этот же цикл, но с вызовом функции подсчёта битов. Измеряем время работы и вычитаем из него время работы пустого цикла — получаем некую оценку на почти чистое время работы функции. Немного грубо, но в пределах получающихся значений времени вполне достаточно для выводов.
Я немного не об этом. Нельзя загрузить этот код, выполнить make и получить такую же табличку, верно? У меня есть возможность протестировать код на совершенно разных машинах, но нет времени его детально изучать. Но по крайней мере я выяснил, что ваш код считает время пустого цикла:) Быстрый взгляд показывает, что в программе не хватает интерфейса чтобы прогнать все тесты разом.
Именно поэтому код следует выложить на GitHub, так как его ещё дорабатывать и дорабатывать. Чтобы не считать время пустого цикла я использовал разворот цикла на 8, после чего время, затрачиваемое на перебор значений, стало ничтожно мало.
> гарантированно пройдя по всем значениям
А почему цикл от 0 до N не пройдёт гарантированно все значения?
> чтобы компилятор вообще не удалил цикл за ненадобностью
есть volatile.
Но хабр не для Pull Requesto-в. А про гитхаб уже сказали.
Именно поэтому код следует выложить на GitHub, так как его ещё дорабатывать и дорабатывать. Чтобы не считать время пустого цикла я использовал разворот цикла на 8, после чего время, затрачиваемое на перебор значений, стало ничтожно мало.
> гарантированно пройдя по всем значениям
А почему цикл от 0 до N не пройдёт гарантированно все значения?
> чтобы компилятор вообще не удалил цикл за ненадобностью
есть volatile.
Но хабр не для Pull Requesto-в. А про гитхаб уже сказали.
Конечно нельзя так сделать, и не было цели разрабатывать полноценный тестирующий проект, который будет работать у всех и всегда. Раньше я испытывал иллюзии, что это можно сделать, но потом понял, что нельзя. Для измерения процессорного времени использовалась утилита runexe, все измерения проводились вручную. Если ставить целью сделать код, который будет измерять процессорное время на любой машине и везде запускаться, то я затрачу уйму времени.
Цикл от 0 до N не подходит, потому что мне нужен именно хаотичный поток данных (в противном случае алгоритм предподсчёта, возможно, будет работать неадекватно быстро при последовательном обращении к памяти и это не будет отражать ситуацию в реальных проектах).
Разворачивание цикла в моём случае затруднительно, так как процедура тестирования заключается в последовательном откомментировании одной строки за другой и ручной проверки времени работы. Если развернуть цикл, придётся 8 раз откомментировать и комментировать обратно эти же строки.
В целом, я понимаю, чего Вы хотите, но для меня затраты времени на это сейчас будут настолько катастрофическими, что они не оправдают результата.
По поводу GitHub я уже говорил, что подумаю. Нужно разобраться, привыкнуть — это не быстро для меня.
Цикл от 0 до N не подходит, потому что мне нужен именно хаотичный поток данных (в противном случае алгоритм предподсчёта, возможно, будет работать неадекватно быстро при последовательном обращении к памяти и это не будет отражать ситуацию в реальных проектах).
Разворачивание цикла в моём случае затруднительно, так как процедура тестирования заключается в последовательном откомментировании одной строки за другой и ручной проверки времени работы. Если развернуть цикл, придётся 8 раз откомментировать и комментировать обратно эти же строки.
В целом, я понимаю, чего Вы хотите, но для меня затраты времени на это сейчас будут настолько катастрофическими, что они не оправдают результата.
По поводу GitHub я уже говорил, что подумаю. Нужно разобраться, привыкнуть — это не быстро для меня.
Чем
std::chrono::high_resolution_clock::now()плох?
Как он позволяет определить процессорное время? Именно то время, которое процессор тратил только на мою задачу, а не на ещё полсотни процессов в ОС?
Поскольку ваша задача — "горячая", процессор будет занят постоянно. Объем данных у вас велик, так что погрешность можно опустить. Или нет?
Нет, разница между астрономическим временем и процессорным на моей машине могла составлять от 1 до 3 секунд. Для моих измерений это много. Конечно, я мог бы увеличить число тестов раз в 10, но тогда статья вышла бы где-нибудь только к концу февраля :)
Здесь, возможно, стоит раскидать по ядрам. Но это так, лирика.
Я бы раскидал, если бы ОС позволяла это сделать относительно простым методом. В принципе, в идеале надо было вообще запускать компьютер, сразу перехватывать управление, без запуска ОС, и запускать тестирование функций. Это не сложно, в принципе, но не слишком ли много Вы хотите от обычного учебного материала?
Он позволяет прогнать все тесты одним нажатием клавиши.
Что, кроме собственно вашего удобства, позволит каждому желающему прогнать свои тесты, прогнать ваши тесты на своем компьютере и т.д.
Точность теоретически упадет, но думаю не так уж сильно — полсотни процессов в ОС одни и те же.
Что, кроме собственно вашего удобства, позволит каждому желающему прогнать свои тесты, прогнать ваши тесты на своем компьютере и т.д.
Точность теоретически упадет, но думаю не так уж сильно — полсотни процессов в ОС одни и те же.
Может Вы и правы в том, что я мог бы так сделать, но всё-таки я в конце-концов решил, что пусть каждый делает сравнения так, как ему удобно, беря ответственность на себя. Измерять астрономическое время на данном уровне ответственности мне не позволит мой опыт подобной работы и куча граблей на этой почве, поэтому советовать делать то же самое остальным пользователям я бы не стал. Я не вижу проблемы прикрутить упомянутые выше функции, но сам так делать не буду. Всё-таки у меня не готовый продукт, а описание методов. Кто хочет их изучить подробнее по-любому захочет всё переписать и сделать по-своему (по крайней мере, я бы так сделал). Давать что-то, что имеет (по моим представлениям) большой риск не работать или работать неправильно я просто не могу по личным причинам, потому я и ограничился самым простым минимальным кодом. Думаю, тут можно не спорить, ведь я разрешил делать с моим кодом всё, что угодно.
В принципе, можно ещё было бы много недостатков найти в моей работе, но только если забыть о целях. Изначальная цель — показать методы. Сравнение — это просто как бонус. Именно поэтому если кто-то проведёт полноценное сравнение с более научных позиций — это будет заслуживать отдельной хорошей статьи. Такой человек мог бы взять несколько процессоров с разной архитектурой (от настольных ПК до мобильников), несколько ОС, несколько режимов работы компиляторов, написать варианты с использованием POPCNT, создать скрипт, который везде, всегда и у всех будет по нажатию кнопки проводить тестирование и выдавать таблицы с результатом (а также параллельно варить кофе и делать бутерброды), — в общем, полно интересной работы. Я лишь начал тему, но продолжать её можно ещё долго.
В принципе, можно ещё было бы много недостатков найти в моей работе, но только если забыть о целях. Изначальная цель — показать методы. Сравнение — это просто как бонус. Именно поэтому если кто-то проведёт полноценное сравнение с более научных позиций — это будет заслуживать отдельной хорошей статьи. Такой человек мог бы взять несколько процессоров с разной архитектурой (от настольных ПК до мобильников), несколько ОС, несколько режимов работы компиляторов, написать варианты с использованием POPCNT, создать скрипт, который везде, всегда и у всех будет по нажатию кнопки проводить тестирование и выдавать таблицы с результатом (а также параллельно варить кофе и делать бутерброды), — в общем, полно интересной работы. Я лишь начал тему, но продолжать её можно ещё долго.
Пользуясь случаем, сообщу, что runexe по ссылке мертва, а ещё меня терзают смутные сомнения, что я смогу повторить запуск этих тестов, например, на power.
i5 i7 и Xeon — это ничего не значащие маркетинговый названия. Гораздо более информативными были бы указания архитектуры (например, Sandy Bridge или Haswell)
интересно, а нельзя ли использовать флаг четного количества битов в PSW для оптимизации наивного цикла, или цикла с откусыванием единиц?
Надо сделать сопроцессор на FPGA!
Не смешно даже. Обращение к сопроцессору занимает столько времени, что выигрыша никакого не будет, даже если всё будет исполняться за один такт. Такие вещи если и встраивать — то в сам процессор.
P.S. Хотя более сложные вещи реально в FPGA выносят. Но это должно быть что-нибудь как-миниум на несколько тысяч тактов. Иначе смысле нету…
P.S. Хотя более сложные вещи реально в FPGA выносят. Но это должно быть что-нибудь как-миниум на несколько тысяч тактов. Иначе смысле нету…
Ясное дело, что процессор вынужден делать четырёхкратную работу при удвоении входного параметра и даже хорошо, что он справляется всего лишь втрое медленнее.
Там не втрое, там на 70%.
Если кто нибудь прогнал бы тесты на своем компьютере и сравнил бы с POPCNT, я был бы ему благодарен.
К сожалению, компа поддерживающего эту инструкцию под рукой пока нет. Если никто не сподобится, сделаю сам где-то через месяц-полтора.
К сожалению, компа поддерживающего эту инструкцию под рукой пока нет. Если никто не сподобится, сделаю сам где-то через месяц-полтора.
Я тоже был бы рад видеть подобную таблицу с POPCNT. Однако, к сожалению, подобное тестирование занимает очень много времени, человеку, который его проведёт, не стыдно будет написать отдельную статью. Я не запрещаю никому брать и менять свой код по своему усмотрению и с любыми целями. Но и отвечать за него в таком случае не берусь.
Более неочевиден проигрыш второго решения с откусыванием единицы. Вы не приведете ассемблерный листинг циклов наивного решения и с откусыванием для вашего компилятора?
Пожалуйста, но сомневаюсь, что это чем-то поможет. Выкладываю код, который получается для u8 в режиме компиляции x86. Для наивного метода:
Для откусывания единички:
Для u32 для режима x86. Наивный метод:
Откусывание:
Как видите, тут не всё очевидно :)
81078 mov cl, al
8107A and cl, 1
8107D add dl, cl
8107F shr al, 1
81081 jne main+38h (81078h)Для откусывания единички:
281078 lea ecx, [eax-1]
28107B inc dl
28107D and al, cl
28107F jne main+38h (281078h) Для u32 для режима x86. Наивный метод:
2C10A0 mov cl, al
2C10A2 and cl, 1
2C10A5 add dl, cl
2C10A7 shr eax, 1
2C10A9 jne main+60h (2C10A0h)Откусывание:
FB10A0 lea ecx, [eax-1]
FB10A3 inc dl
FB10A5 and eax, ecx
FB10A7 jne main+60h (FB10A0h)Как видите, тут не всё очевидно :)
Я ваш код не смотрел, но ИМХО если код организован, много времени это не займет. Дописать буквально пару строк кода, запустить тестирование, подождать пока оно закончится и опубликовать результаты.
Читайте выше
Для измерения процессорного времени использовалась утилита runexe, все измерения проводились вручную.
процедура тестирования заключается в последовательном откомментировании одной строки за другой и ручной проверки времени работы
Я измеряю именно процессорное время. Автоматизировать это относительно простыми методами я не могу (не потому что не умею, а потому что это долго и менее важно для меня).
Померил для 32битного int — popcnt быстрее самого быстрого варианта с таблицей на 64К в 2 с небольшим раза (на core i5). Всё подряд предлагаемое прогнать нереально:) Ждём когда автор доберётся до гитхаба. Или найти в гугле готовые тесты… Например, вот этот: http://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html
прошу прощения, я абсолютный 0 в программировании на ЯВУ (а статья «не для новичков»), но очень захотелось спросить —
Вроде же у каждого семейства процессоров и даже микроконтроллеров есть «родные» команды арифметического сдвига вправо с флагом переноса, и сложения с этим же флагом, т.е. подсчёт единичек сводится к циклу соответсвующей длины из последовательной пары команд «сдвинуть», «сложить»? Тем более что почти всюду это команды одни из самых простых и быстрых, и к тому же базовые для семейства. т.е. не меняются от версии к версии контроллера или процессора. Просто раз всё равно в статье и комментах речь про компиляции под конкретные процессоры — то насколько хотя бы по порядку величин эти решения медленнее ассемблерных? Или я что-то совсем не правильно понял?
И второй момент — как понимаю у всех тестов низкоуровнего быстродействия результаты буквально кратно меняются в зависимости от того, сидят ли программа и/или её данные в кэше процессора или нет, и соотв это отследить — отдельное мини-исследование — нет ли тут такого момента что измеряются по сути не быстродействие алгоритмов, а просто помещаемость программ или данных в кэш?
Вроде же у каждого семейства процессоров и даже микроконтроллеров есть «родные» команды арифметического сдвига вправо с флагом переноса, и сложения с этим же флагом, т.е. подсчёт единичек сводится к циклу соответсвующей длины из последовательной пары команд «сдвинуть», «сложить»? Тем более что почти всюду это команды одни из самых простых и быстрых, и к тому же базовые для семейства. т.е. не меняются от версии к версии контроллера или процессора. Просто раз всё равно в статье и комментах речь про компиляции под конкретные процессоры — то насколько хотя бы по порядку величин эти решения медленнее ассемблерных? Или я что-то совсем не правильно понял?
И второй момент — как понимаю у всех тестов низкоуровнего быстродействия результаты буквально кратно меняются в зависимости от того, сидят ли программа и/или её данные в кэше процессора или нет, и соотв это отследить — отдельное мини-исследование — нет ли тут такого момента что измеряются по сути не быстродействие алгоритмов, а просто помещаемость программ или данных в кэш?
Наивный метод, который идёт в статье первым, компилируется именно в то, о чём вы пишите — последовательное сложение одного бита за другим. Компилятор генерирует вполне оптимальный код для того кода на ЯВУ, что я дал. Как Вы можете убедиться, это самый медленный алгоритм.
В данном случае всё сидит в кэше, можете не сомневаться.
В данном случае всё сидит в кэше, можете не сомневаться.
Нет, не именно то, это видно по выпрошенным мною у вас листингам. Человек говорит про команду ADC. Что-то наподобие
Т.е. да, все равно по сути длинный "тупой" цикл, но не совсем то же самое.
xor edx, edx
m1:
shl eax,1
jz m2
adc edx, 0
jmp m1
m2:
adc edx, 0
quit:Т.е. да, все равно по сути длинный "тупой" цикл, но не совсем то же самое.
Уверен, что это будет то же самое, а скорее всего даже хуже. Кроме того, это потребует работать с ассемблером, тогда как у меня в планы входило создать только переносимый код, хотя бы на Си. Впрочем, не берусь утверждать что-либо наверняка, любые утверждения требуют доказательств. Но если сравнивать с остальными методами, то цикл по всем битам проиграет однозначно, пусть не на u8, то на более крупных типах точно. Думаю, Вы тоже это понимаете.
Разумеется. И тем не менее, я прогоню цикл с ADC, чисто из любопвтства. Но измерять буду по машинному времени. Да, кстати, я писал вам выше — в статье е вас есть фраза "втрое медленее", там где должно быть "на 70%".
У меня написано правильно. Возможно, вы что-то другое поняли.
Ах, вот оно что. Поскольку написано о режиме x86, мне казалось, что говорится о сравнении с 64 разрядным процессором, мол, при в четверо большем объеме работы (ведь 64 делает за один шаг, для него это естественный объем данных), он проигрывает 64 разрядному втрое. А вы имеете в виду по отношению к 32 битному своему же тесту.
Тогда извините.
Тогда извините.
Да, кстати, вариант с ADC быстрее — на простом тесте 7118,6мс против 8922,6мс
Возможно, это издержки моей выборки исходных данных, потому что метод отсечения единицы отработал еще быстрее — за 5969мс.
Отлично, буду знать :) Вообще, по-хорошему все эти функции можно переписать на ассемблере и они будут работать лучше, если понимать принципы оптимизации, конечно. Только переносимость станет равной почти нулю.
Провел сравнение производительности 2-х функции на Core i7 4770:
Первая использует аппаратную реализацию из SSE4.2.
Вторая комбинацию предрассчитанного массива результатов и SIMD на основе AVX2:
Производительность 1-й — 114 микросекунд на обработку 1 GB, 2-й — 48 ms.
Первая использует аппаратную реализацию из SSE4.2.
#include <intrin.h>
uint64_t BitCount(const uint8_t * src, size_t size)
{
uint64_t sum = 0;
for (size_t i = 0; i < size; i += 8)
sum += __popcnt64(*(uint64_t*)(src + i));
return sum;
}Вторая комбинацию предрассчитанного массива результатов и SIMD на основе AVX2:
#include <immintrin.h>
const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i M = _mm256_set1_epi8(0xF);
const __m256i K = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m256i _sum = _mm256_setzero_si256();
for (size_t i = 0; i < size; i += 32)
{
__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(K, _mm256_and_si256(_src, M))));
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(K, _mm256_and_si256(_mm256_srli_epi16(_src, 4), M))));
}
return _sum.m256i_u64[0] + _sum.m256i_u64[1] + _sum.m256i_u64[2] + _sum.m256i_u64[3];
}Производительность 1-й — 114 микросекунд на обработку 1 GB, 2-й — 48 ms.
Это не вполне честно, но тоже полезно знать.
P.S. Как я понимаю даже обычный SSE на больших объёмах может "уделать" popcnt64? Но только если есть где "развернуться"?
P.S. Как я понимаю даже обычный SSE на больших объёмах может "уделать" popcnt64? Но только если есть где "развернуться"?
Да уделывает в 2 раза (всего на 10% медленнее чем AVX2). Использует SSSE3:
const __m128i Z = _mm_set1_epi8(0x0);
const __m128i M = _mm_set1_epi8(0xF);
const __m128i K = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m128i _sum = _mm_setzero_si128();
for (size_t i = 0; i < size; i += 32)
{
__m128i _src = _mm_loadu_si128((__m128i*)(src + i));
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(K, _mm_and_si128(_src, M))));
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(K, _mm_and_si128(_mm_srli_epi16(_src, 4), M))));
}
return _sum.m128i_u64[0] + _sum.m128i_u64[1];
}Результаты этого теста:
Xeon E5-2680
Bitslice(7) 2493617 us; cnt = 32500610
Bitslice(24) 2209648 us; cnt = 32500610
Lauradoux 1224743 us; cnt = 32500610
SSE2 8-bit 773552 us; cnt = 32500610
SSE2 16-bit 746455 us; cnt = 32500610
SSE2 32-bit 906400 us; cnt = 32500610
SSSE3 500734 us; cnt = 32500610
16-bit LUT 1180070 us; cnt = 32500610
8-bit LUT 1233562 us; cnt = 32500610
gcc popcount 298926 us; cnt = 32500610
gcc popcountll 171961 us; cnt = 32500610
FreeBSD version 1 2614572 us; cnt = 32500610
FreeBSD version 2 1890065 us; cnt = 32500610
Wikipedia #2 1290699 us; cnt = 32500610
Wikipedia #3 882481 us; cnt = 32500610
HAKMEM 169/X11 2994177 us; cnt = 32500610
naive 19328131 us; cnt = 32500610
Wegner/Kernigan 13590515 us; cnt = 32500610
Anderson 5804584 us; cnt = 32500610
8x shift and add 12111373 us; cnt = 32500610
32x shift and add 14550016 us; cnt = 32500610
OpenMP Bitslice(7) 5874879 us; cnt = 32500610
OpenMP Bitslice(24) 83787 us; cnt = 32500610
OpenMP Lauradoux 54328 us; cnt = 32500610
OpenMP SSE2 8-bit 37482 us; cnt = 32500610
OpenMP SSE2 16-bit 39181 us; cnt = 32500610
OpenMP SSE2 32-bit 43241 us; cnt = 32500610
OpenMP SSSE3 31971 us; cnt = 32500610
OpenMP 16-bit LUT 70153 us; cnt = 32500610
OpenMP 8-bit LUT 7236100 us; cnt = 32500610
OpenMP gcc popcount 34359 us; cnt = 32500610
OpenMP gcc popcountll 35332 us; cnt = 32500610
OpenMP FreeBSD version 1 281157 us; cnt = 32500610
OpenMP FreeBSD version 2 198496 us; cnt = 32500610
OpenMP Wikipedia #2 156282 us; cnt = 32500610
OpenMP Wikipedia #3 114159 us; cnt = 32500610
OpenMP HAKMEM 169/X11 230414 us; cnt = 32500610
OpenMP naive 1674378 us; cnt = 32500610
OpenMP Wegner/Kernigan 654721 us; cnt = 32500610
OpenMP Anderson 960991 us; cnt = 32500610
OpenMP 8x shift and add 1583529 us; cnt = 32500610
OpenMP 32x shift and add 957853 us; cnt = 32500610Core i7-3770
Bitslice(7) 620813 us; cnt = 32500610
Bitslice(24) 588943 us; cnt = 32500610
Lauradoux 343854 us; cnt = 32500610
SSE2 8-bit 258616 us; cnt = 32500610
SSE2 16-bit 263849 us; cnt = 32500610
SSE2 32-bit 301500 us; cnt = 32500610
SSSE3 177150 us; cnt = 32500610
16-bit LUT 604952 us; cnt = 32500610
8-bit LUT 857176 us; cnt = 32500610
gcc popcount 234420 us; cnt = 32500610
gcc popcountll 151301 us; cnt = 32500610
FreeBSD version 1 1581670 us; cnt = 32500610
FreeBSD version 2 1112433 us; cnt = 32500610
Wikipedia #2 675289 us; cnt = 32500610
Wikipedia #3 532715 us; cnt = 32500610
HAKMEM 169/X11 1568815 us; cnt = 32500610
naive 12706907 us; cnt = 32500610
Wegner/Kernigan 9730186 us; cnt = 32500610
Anderson 3546174 us; cnt = 32500610
8x shift and add 8769728 us; cnt = 32500610
32x shift and add 10844191 us; cnt = 32500610
OpenMP Bitslice(7) 917011 us; cnt = 32500610
OpenMP Bitslice(24) 721363 us; cnt = 32500610
OpenMP Lauradoux 883048 us; cnt = 32500610
OpenMP SSE2 8-bit 230228 us; cnt = 32500610
OpenMP SSE2 16-bit 117210 us; cnt = 32500610
OpenMP SSE2 32-bit 131941 us; cnt = 32500610
OpenMP SSSE3 248196 us; cnt = 32500610
OpenMP 16-bit LUT 486344 us; cnt = 32500610
OpenMP 8-bit LUT 380845 us; cnt = 32500610
OpenMP gcc popcount 266826 us; cnt = 32500610
OpenMP gcc popcountll 108274 us; cnt = 32500610
OpenMP FreeBSD version 1 839581 us; cnt = 32500610
OpenMP FreeBSD version 2 906064 us; cnt = 32500610
OpenMP Wikipedia #2 918286 us; cnt = 32500610
OpenMP Wikipedia #3 593741 us; cnt = 32500610
OpenMP HAKMEM 169/X11 1054673 us; cnt = 32500610
OpenMP naive 3531085 us; cnt = 32500610
OpenMP Wegner/Kernigan 2340468 us; cnt = 32500610
OpenMP Anderson 1557932 us; cnt = 32500610
OpenMP 8x shift and add 3044832 us; cnt = 32500610
OpenMP 32x shift and add 3624641 us; cnt = 32500610POWER
Bitslice(7) 1360812 us; cnt = 32500610
Bitslice(24) 1271885 us; cnt = 32500610
Lauradoux 447454 us; cnt = 32500610
16-bit LUT 1249726 us; cnt = 32500610
8-bit LUT 2103832 us; cnt = 32500610
gcc popcount 431113 us; cnt = 32500610
gcc popcountll 220803 us; cnt = 32500610
Wikipedia #2 982466 us; cnt = 32500610
Wikipedia #3 763969 us; cnt = 32500610
HAKMEM 169/X11 2067571 us; cnt = 32500610
naive 24156131 us; cnt = 32500610
Wegner/Kernigan 22806373 us; cnt = 32500610
Anderson 3879566 us; cnt = 32500610
OpenMP Bitslice(7) 814847 us; cnt = 32500610
OpenMP Bitslice(24) 112392 us; cnt = 32500610
OpenMP Lauradoux 131094 us; cnt = 32500610
OpenMP 16-bit LUT 120421 us; cnt = 32500610
OpenMP 8-bit LUT 109915 us; cnt = 32500610
OpenMP gcc popcount 142351 us; cnt = 32500610
OpenMP gcc popcountll 154243 us; cnt = 32500610
OpenMP FreeBSD version 1 126954 us; cnt = 32500610
OpenMP FreeBSD version 2 126668 us; cnt = 32500610
OpenMP Wikipedia #2 113159 us; cnt = 32500610
OpenMP Wikipedia #3 122584 us; cnt = 32500610
OpenMP HAKMEM 169/X11 134424 us; cnt = 32500610
OpenMP naive 747296 us; cnt = 32500610
OpenMP Wegner/Kernigan 409483 us; cnt = 32500610
OpenMP Anderson 216775 us; cnt = 32500610
Кстати, а std::bitset count() было бы тоже неплохо посчитать.
Насколько я помню он оптимально выражался в popcnt ну и сделать выводы.
Насколько я помню он оптимально выражался в popcnt ну и сделать выводы.
А вот про подсчет битов: всегда было интересно, почему в сжатом файле примерно одинаковое количество 0 и 1?
Или вот пример создания файлов, которые жмутся на примерно 50%
crfile.sh
---------------------------
test -f ucfile && rm ucfile
touch ucfile
for ((j=1;j<=10000;j++))
do
s=""
for ((i=1;i<=4;i++))
do
x=$((($RANDOM+1)/16384))
test $x -eq 0 && s=«01$s»
test $x -eq 1 && s=«10$s»
done
n=$(echo «obase=10; ibase=2; $s»|bc)
printf "\\$(printf '%03o' "$n")">>ucfile
done
stat -c "%s %n" ucfile
gzip ucfile
stat -c "%s %n" ucfile.gz
gunzip ucfile.gz
7z a ucfile.7z ucfile 2>&1 >/dev/null
stat -c "%s %n" ucfile.7z
rm ucfile.7z
bzip2 ucfile
stat -c "%s %n" ucfile.bz2
bunzip2 ucfile.bz2
---------------------------
sh ./crfile.sh
10000 ucfile
5814 ucfile.gz
5785 ucfile.7z
5185 ucfile.bz2
Или вот пример создания файлов, которые жмутся на примерно 50%
crfile.sh
---------------------------
test -f ucfile && rm ucfile
touch ucfile
for ((j=1;j<=10000;j++))
do
s=""
for ((i=1;i<=4;i++))
do
x=$((($RANDOM+1)/16384))
test $x -eq 0 && s=«01$s»
test $x -eq 1 && s=«10$s»
done
n=$(echo «obase=10; ibase=2; $s»|bc)
printf "\\$(printf '%03o' "$n")">>ucfile
done
stat -c "%s %n" ucfile
gzip ucfile
stat -c "%s %n" ucfile.gz
gunzip ucfile.gz
7z a ucfile.7z ucfile 2>&1 >/dev/null
stat -c "%s %n" ucfile.7z
rm ucfile.7z
bzip2 ucfile
stat -c "%s %n" ucfile.bz2
bunzip2 ucfile.bz2
---------------------------
sh ./crfile.sh
10000 ucfile
5814 ucfile.gz
5785 ucfile.7z
5185 ucfile.bz2
А вот про подсчет битов: всегда было интересно, почему в сжатом файле примерно одинаковое количество 0 и 1?Это далеко не всегда правда. Более того: архиватор, для которого это всегда правда будет, вообще говоря, хуже, чем тот, для которого это может быть неправдой.
Что правда — так это то, что на типичных файлах вы будете получать такой результат. Но это-то как раз понятно: если было бы не так, что было бы достаточно приделать небольшой постобработчик, который бы мог, в типичном случае, сжать файл ещё. Кто бы с этим смирился?
Ну я не пытался утверждать, что это истина. Это всего лишь наблюдение, анализировал биты сжатых файлов. Более того, в сжатых файлах цепочки одинаковых битов становятся длинными. Так почему?
Потому что хороший архиватор выдает "случайный" файл (иначе его можно было бы еще сжать). А в случайном файле обычно 0 и 1 примерно одинаково.
Иными словами, не любую случайную последовательность можно сжать. С этим я согласен, а вот то, что в случайном файле 0 и 1 примерно поровну, это вряд ли.
В "случайном файле" 0 и 1 "примерно" поровну. Посмотрите на Треугольник Паскаля, помедитируйте немного над ним.
Hint: подумайте над тем, сколько существует файлов c нулём единичных битов, с одним, с двумя, без нуликов, с одним нуликом и так далее. Когда поймёте что самая большая вероятность в совсем случайном файле встретить ровно половину нуликов и единичек — продолжайте думать, не останавливайтесь! Возможно рано или поздно поймёте о чём тут люди говорят...
Hint: подумайте над тем, сколько существует файлов c нулём единичных битов, с одним, с двумя, без нуликов, с одним нуликом и так далее. Когда поймёте что самая большая вероятность в совсем случайном файле встретить ровно половину нуликов и единичек — продолжайте думать, не останавливайтесь! Возможно рано или поздно поймёте о чём тут люди говорят...
Конечно, сжать можно любую последовательность (для любого файла можно сделать архиватор, сжимающий этот файл в 1 байт). Нельзя сделать универсальный архиватор, сжимающий любую последовательность.
Если вам неочевидно, что в случайном файле примерно поровну 0 и 1, то вы понимаете под случайным файлом что-то очень странное. Приведите свое определение, что ли.
Если вам неочевидно, что в случайном файле примерно поровну 0 и 1, то вы понимаете под случайным файлом что-то очень странное. Приведите свое определение, что ли.
Про специализированный/универсальный архиватор — да. Под «случайным» файлом Вы имели в виду, наверное, то, что архиватор на выходе выдает файл с псевдослучайной последовательностью? Я не сразу понял. И распределение там биномиальное, p~0,5? М.б. это в виде теоремы оформлено? Если знаете, подскажите, пожалуйста.
У большинства последовательностей число 0 и 1 примерно одинаково. Более формально — доля последовательностей длины n, в которых меньше чем 0.4n (или 0.49999n, неважно) единиц, экспоненциальна мала.
У биномиального распределения при p=0.5 энтропия максимальна — следовательно, если архиватор выдает другое распределение, его вход типично можно сжимать.
У биномиального распределения при p=0.5 энтропия максимальна — следовательно, если архиватор выдает другое распределение, его вход типично можно сжимать.
Ясно. И вот еще, я рассматриваю биты архивного файла. Вижу, что чередующиеся наборы одинаковых битов удлиняются по сравнению с неким произвольным исходным файлом. Может ли быть объяснение этому явлению? Наблюдается для разных архиваторов и разных алгоритмов.
Вообще говоря, если вы действительно находите какую-то алгоритмически выразимую закономерность в результатах работы архиватора — то вы можете его улучшить. Т.к. вряд ли хорошие архиваторы можно улучшить нахаляву, то скорее всего закономерность кажущаяся.
Если нет — предъявите конкретные числа.
Если нет — предъявите конкретные числа.
Хорошие архиваторы с лёгкостью улучшаются нанемного для определённых типов файлов. На этом, чёрт побери, построено вообще всё: если входные данные у вас равновероятны, то построить архиватор вообще нельзя.
Так что для любого, самого-самого лучшего архиватора можно найти какой-то тип файлов, на которых его можно сделать ещё лучше. Как вы сами заметили "для любого файла можно сделать архиватор, сжимающий этот файл в 1 байт" (а почему не 1 бит, кстати?).
Вся проблема обсуждения архиваторов — в этой самой "нечестности": на случайных (совсем случайных… белый шум...) данных никто ничего никогда не сожмёт, всегда нужно как-то отбирать — и вот тут-то собака и порылась. Если зафиксировать, скажем, размер архиватора — тогда можно уже что-то обсуждать… но тоже непросто. Если на каких-то данных архиватор начал выдавать что-то совсем непохожее на белый шум — значит вы задали какой-то тип данных для которых этот архиватор никто не затачивал :-)
Так что для любого, самого-самого лучшего архиватора можно найти какой-то тип файлов, на которых его можно сделать ещё лучше. Как вы сами заметили "для любого файла можно сделать архиватор, сжимающий этот файл в 1 байт" (а почему не 1 бит, кстати?).
Вся проблема обсуждения архиваторов — в этой самой "нечестности": на случайных (совсем случайных… белый шум...) данных никто ничего никогда не сожмёт, всегда нужно как-то отбирать — и вот тут-то собака и порылась. Если зафиксировать, скажем, размер архиватора — тогда можно уже что-то обсуждать… но тоже непросто. Если на каких-то данных архиватор начал выдавать что-то совсем непохожее на белый шум — значит вы задали какой-то тип данных для которых этот архиватор никто не затачивал :-)
Да, естественно можно подобрать данные, на которых архиватор выдаст строку из одних нулей. Но случайно это сделать (или наткнуться на то, что какой-то формат типично приводит к такому результату) — маловероятно.
Не в 1 бит — потому что не бывает файлов в 1 бит.
Вообще есть еще колмогоровский декомпрессор, который "сильно" улучшить нельзя. Правда соответствующий ему архиватор невычислим.
Не в 1 бит — потому что не бывает файлов в 1 бит.
Вообще есть еще колмогоровский декомпрессор, который "сильно" улучшить нельзя. Правда соответствующий ему архиватор невычислим.
Да, естественно можно подобрать данные, на которых архиватор выдаст строку из одних нулей. Но случайно это сделать (или наткнуться на то, что какой-то формат типично приводит к такому результату) — маловероятно.А вот и нет. В большинстве случаев достаточно каких-нибудь тупых последовательностей. Чего-нибудь типа 123456789123456789…
Конечно любой уважающий себя архиватор и так сожмёт такую строку в десятки раз. Но можно-то в 1000, 10000, 1000000 раз… вот только зачем? Часто вы такие файлы сжимаете на практике? Файлы из одних нулей довольно популярны или какие-нибудь N x 0xDEADBEEF (пометка «неиспользуемой» памяти), но более сложные регулярные паттерны встречаются разве только если кто-то хочет «сломать» архиватор специально…
выглядит несколько маньячно :)
размер файла 785816*8=6286528 битов
длина набора одинаковых битов 0, частота
s=2830297
4 55423 т.е. последовательность битов 0000 встречается 55423 раза
3 209814
2 497036
1 985091
длина набора одинаковых битов 1, частота
s=3456231
8 5327 т.е. последовательность битов 11111111 встречается 5327 раз
7 8680
6 23785
5 53878
4 161519
3 139320
2 521863
1 832993
исходный файл, сжатый bz2, размер 390916*8=3127328 битов
сжатый файл, длина набора одинаковых битов 0, частота
s=1555468
26 2
17 1
16 6
15 11
14 29
13 84
12 180
11 405
10 854
9 1707
8 3125
7 5996
6 11862
5 23550
4 47024
3 94969
2 194755
1 404715
сжатый файл, длина набора одинаковых битов 1, частота
s=1571860
935 1 т.е. 1 раз в файле встречается 935 подряд идущих битов = 1
88 1
84 1
71 1
67 2
62 1
61 1
59 1
57 1
51 1
49 1
45 1
44 1
43 6
42 3
41 2
38 2
37 1
35 1
34 1
33 1
30 1
29 2
27 1
26 2
25 5
24 4
23 2
22 5
21 2
20 9
19 14
18 14
17 22
16 26
15 35
14 72
13 89
12 201
11 380
10 582
9 1444
8 2555
7 5339
6 11821
5 24595
4 50123
3 100066
2 195029
1 396805
размер файла 785816*8=6286528 битов
длина набора одинаковых битов 0, частота
s=2830297
4 55423 т.е. последовательность битов 0000 встречается 55423 раза
3 209814
2 497036
1 985091
длина набора одинаковых битов 1, частота
s=3456231
8 5327 т.е. последовательность битов 11111111 встречается 5327 раз
7 8680
6 23785
5 53878
4 161519
3 139320
2 521863
1 832993
исходный файл, сжатый bz2, размер 390916*8=3127328 битов
сжатый файл, длина набора одинаковых битов 0, частота
s=1555468
26 2
17 1
16 6
15 11
14 29
13 84
12 180
11 405
10 854
9 1707
8 3125
7 5996
6 11862
5 23550
4 47024
3 94969
2 194755
1 404715
сжатый файл, длина набора одинаковых битов 1, частота
s=1571860
935 1 т.е. 1 раз в файле встречается 935 подряд идущих битов = 1
88 1
84 1
71 1
67 2
62 1
61 1
59 1
57 1
51 1
49 1
45 1
44 1
43 6
42 3
41 2
38 2
37 1
35 1
34 1
33 1
30 1
29 2
27 1
26 2
25 5
24 4
23 2
22 5
21 2
20 9
19 14
18 14
17 22
16 26
15 35
14 72
13 89
12 201
11 380
10 582
9 1444
8 2555
7 5339
6 11821
5 24595
4 50123
3 100066
2 195029
1 396805
Конечно, сжать можно любую последовательность (для любого файла можно сделать архиватор, сжимающий этот файл в 1 байт).
Предлагаю вам доказать это утверждение и выиграть 50000 евро: http://prize.hutter1.net/
Имелось в виду "каждый конкретный файл". И архив будет не самораспаковывающийся. В том смысле, что у вас будет архиватор размером 100 Мб и архив очень маленького размера.
Там и надо запаковать конкретный файл.
А без ограничения на размер декомпрессора само сжатие смысла не имеет. Можно же полностью файл туда засунуть.
А без ограничения на размер декомпрессора само сжатие смысла не имеет. Можно же полностью файл туда засунуть.
Собственно об том и речь. Любой реальный архиватор затачивается на файлы определённого типа. То есть вплоть до того что в каком-нибудь 7zip'е есть определённые куски файлов определённых форматов, которые он "знает" и потому может особенно хорошо паковать.
Предельный случай — как вы правильно заметили — особого смысла не имеет, но если архиватор у вас один, а файлов определённого типа вам нужно архивировать много (на практике куда как более часто встречающая задача, чем описанный вам challenge), то это — вполне разумное решение.
Предельный случай — как вы правильно заметили — особого смысла не имеет, но если архиватор у вас один, а файлов определённого типа вам нужно архивировать много (на практике куда как более часто встречающая задача, чем описанный вам challenge), то это — вполне разумное решение.
Речь о том, что рассматривать размер сжатых файлов без декомпрессора смысла не имеет, ни в контексте соревнований по сжатию, ни в контексте хранения/передачи файлов. Просто в повседневной жизни объем сжимаемых файлов гораздо больше размера архиватора/деархиватора, а в соревнованиях приходится обговаривать
И в таких условиях (по-моему, достаточно очевидных), "сжать файл до 1 байта" невозможно. На что я и пытался намекнуть
И в таких условиях (по-моему, достаточно очевидных), "сжать файл до 1 байта" невозможно. На что я и пытался намекнуть
Вы сами по своей ссылке хоть ходили?
А вы воюете с ветряными мельницами и выглядите глупо.
The TaskНикто здесь не говорит о "повседневной жизни", или возможности запаковать произвольный файл в один байт. Говорится о том, чтобы запихать конкретный файл целиком в архиватор и далее "запаковывать " его в 1 байт.
Create a compressed version (self-extracting archive) of the 100MB file enwik8
А вы воюете с ветряными мельницами и выглядите глупо.
Ну я считаю, что скопировать файл в другое место и заменить его одним байтом не является сжатием.
Если вы считаете, что это глупо, это конечно ваше право.
Если бы в изначальном комменте было написано "запаковать" в кавычках, я бы прошел мимо.
Если вы считаете, что это глупо, это конечно ваше право.
Если бы в изначальном комменте было написано "запаковать" в кавычках, я бы прошел мимо.
А вы не пробовали читать комментарий полностью прежде чем отвечать?
Там написано "нет архиватора, сжимающего любую последовательность".
Проблема в том, что размер разархиватора зависит от архитектуры, от ОС и т.д.
Как, собственно, вводится колмогоровская сложность — рассматривается фиксированный разархиватор, и берется сложность относительно него (мин. длина архива, который он распаковывает в данное слово). Затем оказывается, что существует "универсальный" разархиватор — который с точностью до константы не хуже любого другого.
Проблема в том, что избавиться от этой константы разумными способами нельзя.
Там написано "нет архиватора, сжимающего любую последовательность".
Проблема в том, что размер разархиватора зависит от архитектуры, от ОС и т.д.
Как, собственно, вводится колмогоровская сложность — рассматривается фиксированный разархиватор, и берется сложность относительно него (мин. длина архива, который он распаковывает в данное слово). Затем оказывается, что существует "универсальный" разархиватор — который с точностью до константы не хуже любого другого.
Проблема в том, что избавиться от этой константы разумными способами нельзя.
Очень круто! Смотрю вы оперируете наверное почти всеми (включая малоизвестные) хаками!
Еще и своих добавили… Вдохновило! (Я тоже =) Вношу лепту:
!Disclaimer! Не бейте, сейчас будет JS. Сями я лишь под МК балуюсь, и тестить не где, да и нет толка от теста в отрыве от собирательного на одной машине.
Оно считает до 16 бит, используя 32х битную арифметику. Соответственно сравнивать его имеет смысл с аналогичным
Кодом из вашей статьи, (как я понимаю этим):
Я уже писал раньше такие штуки. Но сейчас, открыл у вас новый алгебраический хак (в первой строке) и захотел с ним миксануть. Кстати, в конце отдельно выскажу свои мысли по поводу его скрытого потенциала.
Итак вот мой код:
(Тестить бинарником не буду)
Но на примитивных инструкциях примерно можно сравнить на глазок. Все вычисления зависимые (кроме одной инструкции в вашей второй строке). Если считать с конца 3-4-5 строки не содержат скоростных различий и даже (почти) порядка операций. Да у меня IF, но (внимание) у меня вместо этого совсем отсутствует ваша 2я строка…
Это получилось сделать т.к. я на шаг раньше (и в итоге дважды) ухожу в тиражирование.
Однако из-за этого второе тиражирование приходиться делать по-16ти-разрядно, потому результат не может хранить значение больше 15. И это нужно проверять. Хотя на архитектурах с Brunch Prediction это будет вероятно быстрее, чем 4, пусть и простейшие инструкции, пусть одна из них и может попасть под Hyperthreading
Прокомментирую отдельно еще не свойственный для JS imul()
— дело в том, что переполнение при умножении в JS дает (float) Infinity
А используя прием тиражирования бит мне собстеннно абсолютное значение до лампочки. imul() появился как решение и в частности в связи с AsmJS и активной сейчас разработкой WASM. Как заявлено в доке это C-like умножение. (т.е. без неявностей с float'ами)
И теперь еще слово о найденном у вас замечательном арифметическом хаке:
По сути своей такое действие эквивалентно попарному полусумматору:
т.е. можно попарно одновременно получать AND и XOR от групп битов
а эти операции, являются достаточными дляЖигалкина для любых сочетаний…
и еще в сочетании с возможностью не сильно дорого сдвигать их более чем на одну позицию
я подозреваю пригодность этой техники для быстрой криптографии и прочих стремительных, в особенности итеративных алгоритмов… быть может даже на длинной арифметике, ибо есть возможность мульти-одновременно протаскивать группы бит (скользящий накопитель — ядро вычета) на заранее не определенные позиции при итеративном проходе
Еще и своих добавили… Вдохновило! (Я тоже =) Вношу лепту:
!Disclaimer! Не бейте, сейчас будет JS. Сями я лишь под МК балуюсь, и тестить не где, да и нет толка от теста в отрыве от собирательного на одной машине.
Оно считает до 16 бит, используя 32х битную арифметику. Соответственно сравнивать его имеет смысл с аналогичным
Кодом из вашей статьи, (как я понимаю этим):
0 u8 CountOnes5 (u16 n) {
1 n -= (n>>1) & 0x5555;
2 n = ((n>>2) & 0x3333) + (n & 0x3333);
3 n = ((((n>>4) + n) & 0x0F0F) * 0x0101) >> 8;
4 return n; // Здесь происходит неявное обрезание по 8 младшим битам.
5 }Я уже писал раньше такие штуки. Но сейчас, открыл у вас новый алгебраический хак (в первой строке) и захотел с ним миксануть. Кстати, в конце отдельно выскажу свои мысли по поводу его скрытого потенциала.
Итак вот мой код:
0 var popu16=x=>{
1 if(x>=65535)return 16;
2 x-=x>>1&0x5555;
3 x=(x<<14|x)&0x33333333;
4 return Math.imul(x,0x11111111)>>>28;
5 }(Тестить бинарником не буду)
Но на примитивных инструкциях примерно можно сравнить на глазок. Все вычисления зависимые (кроме одной инструкции в вашей второй строке). Если считать с конца 3-4-5 строки не содержат скоростных различий и даже (почти) порядка операций. Да у меня IF, но (внимание) у меня вместо этого совсем отсутствует ваша 2я строка…
Это получилось сделать т.к. я на шаг раньше (и в итоге дважды) ухожу в тиражирование.
Однако из-за этого второе тиражирование приходиться делать по-16ти-разрядно, потому результат не может хранить значение больше 15. И это нужно проверять. Хотя на архитектурах с Brunch Prediction это будет вероятно быстрее, чем 4, пусть и простейшие инструкции, пусть одна из них и может попасть под Hyperthreading
Прокомментирую отдельно еще не свойственный для JS imul()
— дело в том, что переполнение при умножении в JS дает (float) Infinity
А используя прием тиражирования бит мне собстеннно абсолютное значение до лампочки. imul() появился как решение и в частности в связи с AsmJS и активной сейчас разработкой WASM. Как заявлено в доке это C-like умножение. (т.е. без неявностей с float'ами)
И теперь еще слово о найденном у вас замечательном арифметическом хаке:
По сути своей такое действие эквивалентно попарному полусумматору:
// ab - a = a + b //буквы в литералах - это одинаковые битовые разряды
//x-=(x»1& 0b...0101) //многоточия в 0b литералах означают периодическое повторение бит константы
x-=x»1&0x55555555;
// a.b - aa = a + b //точки в литералах - любые сторонние битовые разряды
//x-=(x»2& 0b...001001)*0b...011011;
x-=(x»2& 0x49249249)*0xDB6DB6DB;
// a..b -aaa = a+b
//x-=(x»3& 0b...00010001)*0b...01110111;
x-=(x»3& 0x11111111)*0x77777777; т.е. можно попарно одновременно получать AND и XOR от групп битов
а эти операции, являются достаточными для
и еще в сочетании с возможностью не сильно дорого сдвигать их более чем на одну позицию
я подозреваю пригодность этой техники для быстрой криптографии и прочих стремительных, в особенности итеративных алгоритмов… быть может даже на длинной арифметике, ибо есть возможность мульти-одновременно протаскивать группы бит (скользящий накопитель — ядро вычета) на заранее не определенные позиции при итеративном проходе
Sign up to leave a comment.
Обстоятельно о подсчёте единичных битов