Zealint 13 фев 2016 в 14:48

Обстоятельно о подсчёте единичных битов

16 мин

100K

Алгоритмы*Программирование*Спортивное программирование*

Туториал

+82

Комментарии 95

Big_Lebowski 13 фев 2016 в 15:19

Интересно сравнить какое время получилось бы если хранить таблицу с посчитаными значениями

Zealint 13 фев 2016 в 15:24

Не понял вашего вопроса. Ведь в разделе «Предподсчёт» именно это и сделано.

Big_Lebowski 13 фев 2016 в 15:42

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

Zealint 13 фев 2016 в 15:53

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

Zealint 13 фев 2016 в 15:59

Поясню один момент, который может быть непонятным сразу. Есть инструкция POPCNT, входящая в состав SSE4.2, которую по-хорошему мне тоже нужно было включить в список тестирования. Однако у меня нет процессора, который поддерживал бы SSE4.2. Сожалею об этом, но ничего поделать не могу.

DeuterideLitium6 6 ноя 2024 в 19:12

У вас тут неправильные прототипы функций. Функции должны эмулировать маш. инструкции, и там должны быть: u8 __popcnt(u8 num), u16 __popcnt(u16 num), u32 __popcnt(u32 num), u64 __popcnt(u64 num)

Посмотрите на команды popcnt для х86, и других процессоров(Alpha, ARM) где есть подобная инструкция. Просто получается лишняя операция return (u8)num; Из-за этого GCC хуже VS мелкософта(там как раз правильный прототип). Тут всё логично, часто подсчитывается массив бит, а не отдельные числа.

Beholder 13 фев 2016 в 16:08

Стоило бы упомянуть книгу «Hacker's Delight», в которой есть этот и многие другие подобные трюки.

Zealint 13 фев 2016 в 16:15

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

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

hellman 13 фев 2016 в 16:40

Тогда ещё graphics.stanford.edu/~seander/bithacks.html

Zealint 13 фев 2016 в 16:48

Да, спасибо, там почти весь набор приёмов, что в статье. Но всё равно «почти» и без пояснений.

НЛО прилетело и опубликовало эту надпись здесь

Pavlusha 14 фев 2016 в 01:04

Не много кривовато описано

НЛО прилетело и опубликовало эту надпись здесь

Vapaamies 15 фев 2016 в 04:05

Аналог popcnt легко реализовать на обычном ассемблере x86, используя bsf и сдвиги.

zagayevskiy 13 фев 2016 в 16:45

Исходники на Я.Диске — это моветон в 2016-то году. Залейте на гитхаб, будет круто.
За статью респект, очень круто. Кстати, наблюдение — по-моему, вам в карму плюсанули примерно столько же людей, сколько статью:)

Zealint 13 фев 2016 в 16:51

Ну там не только исходники, ещё презентация. Я не вижу смысла специально залезать на GitHub, чтобы просто положить 5 файлов и быть в тренде, и не вижу проблемы скачать архив, смотря на него просто как на файл. Спасибо за отзыв :)

zagayevskiy 13 фев 2016 в 17:56

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

Zealint 13 фев 2016 в 18:01

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

mikhaelkh 13 фев 2016 в 18:44

В gcc есть функция __builtin_popcount, интересно посмотреть на ее положение в таблице.

Zealint 13 фев 2016 в 19:39

Конечно, интересно, но у меня есть подозрение, что там реализован либо вызов POPCNT из SSE4.2, либо (когда данная функция не поддерживается процессором), что-то из моего набора приёмов. Так что она займёт место рядом с какой-то из уже записанных в таблице строк. Буду приятно удивлён, если кто-то обнаружит, что там написано что-то совершенно необычное, у кого есть исходники GCC, можете проверить.

khim 13 фев 2016 в 23:17

Ну исходники-то не секретны, да. Там табличка __popcount_tab и сопутствующие функции:
github.com/gcc-mirror/gcc/blob/master/libgcc/libgcc2.c

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

RPG 14 фев 2016 в 00:50

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 сек.

Zealint 14 фев 2016 в 10:08

Странно, но я постарался в комментариях описать, что делать. В любом случае, в статье написано, что число тестов равно 2³².

Порядок действий таков: сначала запускаем «пустой» цикл, который не делает ничего, кроме генерации входного потока из 2³² чисел. Например, в моём коде генерация выполняется по формуле n = 19993*n+1, где n имеет размер u32. Начав генерацию от n=0, мы закончим её на n=0, гарантированно пройдя по всем значениям. Измеряем время работы этого пустого цикла.

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

RPG 14 фев 2016 в 14:18

Я немного не об этом. Нельзя загрузить этот код, выполнить make и получить такую же табличку, верно? У меня есть возможность протестировать код на совершенно разных машинах, но нет времени его детально изучать. Но по крайней мере я выяснил, что ваш код считает время пустого цикла:) Быстрый взгляд показывает, что в программе не хватает интерфейса чтобы прогнать все тесты разом.

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

> гарантированно пройдя по всем значениям

А почему цикл от 0 до N не пройдёт гарантированно все значения?

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

есть volatile.

Но хабр не для Pull Requesto-в. А про гитхаб уже сказали.

Zealint 14 фев 2016 в 16:21

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

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

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

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

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

Randl 15 фев 2016 в 21:17

Чем

std::chrono::high_resolution_clock::now()

плох?

Zealint 15 фев 2016 в 21:32

Как он позволяет определить процессорное время? Именно то время, которое процессор тратил только на мою задачу, а не на ещё полсотни процессов в ОС?

MacIn 15 фев 2016 в 21:35

Поскольку ваша задача — "горячая", процессор будет занят постоянно. Объем данных у вас велик, так что погрешность можно опустить. Или нет?

Zealint 15 фев 2016 в 21:41

Нет, разница между астрономическим временем и процессорным на моей машине могла составлять от 1 до 3 секунд. Для моих измерений это много. Конечно, я мог бы увеличить число тестов раз в 10, но тогда статья вышла бы где-нибудь только к концу февраля :)

MacIn 15 фев 2016 в 21:48

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

Zealint 15 фев 2016 в 22:00

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

MacIn 15 фев 2016 в 22:12

Это не требование к вам, просто мысль вслух.

Randl 15 фев 2016 в 21:42

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

Точность теоретически упадет, но думаю не так уж сильно — полсотни процессов в ОС одни и те же.

Zealint 15 фев 2016 в 21:58

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

В принципе, можно ещё было бы много недостатков найти в моей работе, но только если забыть о целях. Изначальная цель — показать методы. Сравнение — это просто как бонус. Именно поэтому если кто-то проведёт полноценное сравнение с более научных позиций — это будет заслуживать отдельной хорошей статьи. Такой человек мог бы взять несколько процессоров с разной архитектурой (от настольных ПК до мобильников), несколько ОС, несколько режимов работы компиляторов, написать варианты с использованием POPCNT, создать скрипт, который везде, всегда и у всех будет по нажатию кнопки проводить тестирование и выдавать таблицы с результатом (а также параллельно варить кофе и делать бутерброды), — в общем, полно интересной работы. Я лишь начал тему, но продолжать её можно ещё долго.

RPG 15 фев 2016 в 21:47

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

Zealint 15 фев 2016 в 22:04

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

RPG 15 фев 2016 в 22:07

Осталось дождаться, когда Microsoft сделает Windows для power:)

MacIn 15 фев 2016 в 22:11

Есть timeit в Windows Resource Kit. Хотя я не уверен, учитывает ли она время конкретного процесса, или просто измеряет интервал.

encyclopedist 18 фев 2016 в 17:21

i5 i7 и Xeon — это ничего не значащие маркетинговый названия. Гораздо более информативными были бы указания архитектуры (например, Sandy Bridge или Haswell)

gleb_l 14 фев 2016 в 11:14

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

alecv 14 фев 2016 в 18:30

Надо сделать сопроцессор на FPGA!

khim 14 фев 2016 в 19:04

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

P.S. Хотя более сложные вещи реально в FPGA выносят. Но это должно быть что-нибудь как-миниум на несколько тысяч тактов. Иначе смысле нету…

MacIn 15 фев 2016 в 04:41

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

Там не втрое, там на 70%.

Randl 15 фев 2016 в 06:20

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

Zealint 15 фев 2016 в 10:13

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

MacIn 15 фев 2016 в 19:57

Более неочевиден проигрыш второго решения с откусыванием единицы. Вы не приведете ассемблерный листинг циклов наивного решения и с откусыванием для вашего компилятора?

Zealint 15 фев 2016 в 20:28

Пожалуйста, но сомневаюсь, что это чем-то поможет. Выкладываю код, который получается для u8 в режиме компиляции 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)

Как видите, тут не всё очевидно :)

Randl 15 фев 2016 в 20:37

Я ваш код не смотрел, но ИМХО если код организован, много времени это не займет. Дописать буквально пару строк кода, запустить тестирование, подождать пока оно закончится и опубликовать результаты.

zagayevskiy 15 фев 2016 в 21:05

Читайте выше

Для измерения процессорного времени использовалась утилита runexe, все измерения проводились вручную.

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

Zealint 15 фев 2016 в 21:34

Я измеряю именно процессорное время. Автоматизировать это относительно простыми методами я не могу (не потому что не умею, а потому что это долго и менее важно для меня).

RPG 15 фев 2016 в 22:05

Померил для 32битного int — popcnt быстрее самого быстрого варианта с таблицей на 64К в 2 с небольшим раза (на core i5). Всё подряд предлагаемое прогнать нереально:) Ждём когда автор доберётся до гитхаба. Или найти в гугле готовые тесты… Например, вот этот: http://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html

impetus 15 фев 2016 в 08:07

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

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

Zealint 15 фев 2016 в 10:06

Наивный метод, который идёт в статье первым, компилируется именно в то, о чём вы пишите — последовательное сложение одного бита за другим. Компилятор генерирует вполне оптимальный код для того кода на ЯВУ, что я дал. Как Вы можете убедиться, это самый медленный алгоритм.

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

MacIn 15 фев 2016 в 21:21

Нет, не именно то, это видно по выпрошенным мною у вас листингам. Человек говорит про команду ADC. Что-то наподобие

xor edx, edx
m1:
shl eax,1
jz m2
adc edx, 0
jmp m1
m2:
adc edx, 0
quit:

Т.е. да, все равно по сути длинный "тупой" цикл, но не совсем то же самое.

Zealint 15 фев 2016 в 21:39

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

MacIn 15 фев 2016 в 21:46

Разумеется. И тем не менее, я прогоню цикл с ADC, чисто из любопвтства. Но измерять буду по машинному времени. Да, кстати, я писал вам выше — в статье е вас есть фраза "втрое медленее", там где должно быть "на 70%".

Zealint 15 фев 2016 в 22:02

У меня написано правильно. Возможно, вы что-то другое поняли.

MacIn 15 фев 2016 в 22:07

Ах, вот оно что. Поскольку написано о режиме x86, мне казалось, что говорится о сравнении с 64 разрядным процессором, мол, при в четверо большем объеме работы (ведь 64 делает за один шаг, для него это естественный объем данных), он проигрывает 64 разрядному втрое. А вы имеете в виду по отношению к 32 битному своему же тесту.
Тогда извините.

MacIn 15 фев 2016 в 22:17

Да, кстати, вариант с ADC быстрее — на простом тесте 7118,6мс против 8922,6мс

MacIn 15 фев 2016 в 22:27

Возможно, это издержки моей выборки исходных данных, потому что метод отсечения единицы отработал еще быстрее — за 5969мс.

Zealint 15 фев 2016 в 22:28

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

ErmIg 15 фев 2016 в 16:37

Провел сравнение производительности 2-х функции на Core i7 4770:
Первая использует аппаратную реализацию из 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.

khim 15 фев 2016 в 17:06

Это не вполне честно, но тоже полезно знать.

P.S. Как я понимаю даже обычный SSE на больших объёмах может "уделать" popcnt64? Но только если есть где "развернуться"?

ErmIg 15 фев 2016 в 17:43

Да уделывает в 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];
}

RPG 15 фев 2016 в 22:39

Результаты этого теста:

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 = 32500610

Core 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 = 32500610

POWER

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

snikulov 16 фев 2016 в 10:50

Кстати, а std::bitset count() было бы тоже неплохо посчитать.
Насколько я помню он оптимально выражался в popcnt ну и сделать выводы.

art0int 16 фев 2016 в 16:08

А вот про подсчет битов: всегда было интересно, почему в сжатом файле примерно одинаковое количество 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

khim 16 фев 2016 в 19:26

А вот про подсчет битов: всегда было интересно, почему в сжатом файле примерно одинаковое количество 0 и 1?

Это далеко не всегда правда. Более того: архиватор, для которого это всегда правда будет, вообще говоря, хуже, чем тот, для которого это может быть неправдой.

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

art0int 16 фев 2016 в 19:46

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

mihaild 16 фев 2016 в 20:01

Потому что хороший архиватор выдает "случайный" файл (иначе его можно было бы еще сжать). А в случайном файле обычно 0 и 1 примерно одинаково.

art0int 16 фев 2016 в 20:37

Иными словами, не любую случайную последовательность можно сжать. С этим я согласен, а вот то, что в случайном файле 0 и 1 примерно поровну, это вряд ли.

khim 16 фев 2016 в 22:53

В "случайном файле" 0 и 1 "примерно" поровну. Посмотрите на Треугольник Паскаля, помедитируйте немного над ним.

Hint: подумайте над тем, сколько существует файлов c нулём единичных битов, с одним, с двумя, без нуликов, с одним нуликом и так далее. Когда поймёте что самая большая вероятность в совсем случайном файле встретить ровно половину нуликов и единичек — продолжайте думать, не останавливайтесь! Возможно рано или поздно поймёте о чём тут люди говорят...

mihaild 17 фев 2016 в 02:57

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

Если вам неочевидно, что в случайном файле примерно поровну 0 и 1, то вы понимаете под случайным файлом что-то очень странное. Приведите свое определение, что ли.

art0int 17 фев 2016 в 06:28

Про специализированный/универсальный архиватор — да. Под «случайным» файлом Вы имели в виду, наверное, то, что архиватор на выходе выдает файл с псевдослучайной последовательностью? Я не сразу понял. И распределение там биномиальное, p~0,5? М.б. это в виде теоремы оформлено? Если знаете, подскажите, пожалуйста.

mihaild 17 фев 2016 в 13:48

У большинства последовательностей число 0 и 1 примерно одинаково. Более формально — доля последовательностей длины n, в которых меньше чем 0.4n (или 0.49999n, неважно) единиц, экспоненциальна мала.
У биномиального распределения при p=0.5 энтропия максимальна — следовательно, если архиватор выдает другое распределение, его вход типично можно сжимать.

art0int 17 фев 2016 в 19:01

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

mihaild 17 фев 2016 в 19:29

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

khim 18 фев 2016 в 00:46

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

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

Вся проблема обсуждения архиваторов — в этой самой "нечестности": на случайных (совсем случайных… белый шум...) данных никто ничего никогда не сожмёт, всегда нужно как-то отбирать — и вот тут-то собака и порылась. Если зафиксировать, скажем, размер архиватора — тогда можно уже что-то обсуждать… но тоже непросто. Если на каких-то данных архиватор начал выдавать что-то совсем непохожее на белый шум — значит вы задали какой-то тип данных для которых этот архиватор никто не затачивал :-)

mihaild 18 фев 2016 в 01:27

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

Не в 1 бит — потому что не бывает файлов в 1 бит.

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

khim 18 фев 2016 в 01:44

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

А вот и нет. В большинстве случаев достаточно каких-нибудь тупых последовательностей. Чего-нибудь типа 123456789123456789…

Конечно любой уважающий себя архиватор и так сожмёт такую строку в десятки раз. Но можно-то в 1000, 10000, 1000000 раз… вот только зачем? Часто вы такие файлы сжимаете на практике? Файлы из одних нулей довольно популярны или какие-нибудь N x 0xDEADBEEF (пометка «неиспользуемой» памяти), но более сложные регулярные паттерны встречаются разве только если кто-то хочет «сломать» архиватор специально…

mihaild 18 фев 2016 в 18:09

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

art0int 18 фев 2016 в 10:25

выглядит несколько маньячно :)
размер файла 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

mihaild 18 фев 2016 в 18:10

Вы же понимаете, что это невозможно прочитать?

art0int 18 фев 2016 в 20:41

Думаю, что прочитать можно, но сделать это непросто.

Randl 5 мар 2016 в 15:01

Конечно, сжать можно любую последовательность (для любого файла можно сделать архиватор, сжимающий этот файл в 1 байт).

Предлагаю вам доказать это утверждение и выиграть 50000 евро: http://prize.hutter1.net/

zagayevskiy 5 мар 2016 в 15:20

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

Randl 5 мар 2016 в 20:45

Там и надо запаковать конкретный файл.
А без ограничения на размер декомпрессора само сжатие смысла не имеет. Можно же полностью файл туда засунуть.

khim 5 мар 2016 в 22:49

Собственно об том и речь. Любой реальный архиватор затачивается на файлы определённого типа. То есть вплоть до того что в каком-нибудь 7zip'е есть определённые куски файлов определённых форматов, которые он "знает" и потому может особенно хорошо паковать.

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

Randl 6 мар 2016 в 08:06

Речь о том, что рассматривать размер сжатых файлов без декомпрессора смысла не имеет, ни в контексте соревнований по сжатию, ни в контексте хранения/передачи файлов. Просто в повседневной жизни объем сжимаемых файлов гораздо больше размера архиватора/деархиватора, а в соревнованиях приходится обговаривать
И в таких условиях (по-моему, достаточно очевидных), "сжать файл до 1 байта" невозможно. На что я и пытался намекнуть

zagayevskiy 6 мар 2016 в 11:06

Вы сами по своей ссылке хоть ходили?

The Task
Create a compressed version (self-extracting archive) of the 100MB file enwik8

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

А вы воюете с ветряными мельницами и выглядите глупо.

Randl 6 мар 2016 в 15:06

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

mihaild 7 мар 2016 в 00:21

А вы не пробовали читать комментарий полностью прежде чем отвечать?
Там написано "нет архиватора, сжимающего любую последовательность".
Проблема в том, что размер разархиватора зависит от архитектуры, от ОС и т.д.

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

impfromliga 18 фев 2019 в 23:02

Очень круто! Смотрю вы оперируете наверное почти всеми (включая малоизвестные) хаками!
Еще и своих добавили… Вдохновило! (Я тоже =) Вношу лепту:

!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 от групп битов
а эти операции, являются достаточными для ~~Жигалкина~~ для любых сочетаний…

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

aabzel 18 мая в 00:50

Как в Excel подсчитать количество единичных битов в десятичном числе

kinh 18 мая в 01:22

Навскидку такой способ: нужна таблица в 2 колонки. Допустим, в ячейку A1 записываем число, которое нужно проанализировать, в ячейку A2 пишем формулу =ОКРВНИЗ(A1/2;1) это будет сдвигать вправо на 1 бит вышестоящее число. В ячейку B2 пишем =ЕСЛИ(ЕНЕЧЁТ(A1);1;0) это будет возвращать 1, если число слева на строку выше заканчивалось на единичный бит, и 0 в противном случае. Протягиваем эти колонки вниз, например, на 32 или 64 строки - в зависимости от размерности числа, и находим сумму значений правой колонки.
Я не знаток Excel - это просто первое, что в голову пришло.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий