Pull to refresh

Comments 203

код просто прекрасен :) но не интуитивно понятен.. хотя если человек в уме дворды из шестнадцатиричной системы может переводить в двоичную, то в принципе понятный :))
В данном случае неочевидность алгоритма вполне может быть оправдана эффективностью. Надо лишь добавить комментарий (они для этого и придуманы, а не чтобы выключать отладочные части кода).
А что там переводить то? Каждая позиция в шестнадцатеричном коде соответствует 4-м позициям в двоичном... А это гораздо легче, чем подобные манипуляции, например с переводом в обычный десятиричный.
А на счет комментариев согласен - их вообще всегда лучше делать побольше(естессно не жертвуя потерей качества и не нагромождая код) - ведь самим же потом легче будет разобраться по истечение какого-либо времени.
код просто идеален хотя есть и более эффективные методы на базе lookup таблиц
На самом деле она сдвинута, но по правилам HTML сокращена до 1 пробела.

Не хватает pre.
UFO just landed and posted this here
Очень приятный и понятный код, по крайней мере, если знать, что надо получить. Название функции, конечно, подсказывает её предназначение, но коммента не хватает.

Впрочем, это уже почти идиома, широко известная в узких кругах. Примерно как x^=y^=x^=y (для тех кто в танке, это хитро записанный обмен значений x и y)
Я был в танке, спасибо за изящный кусочек кода!
Я тоже там был, но вас почему-то не видел :)
посмотреть профиль grep0, спасибо.
Ну либо потому, что в танке было темно, либо потому, что это были 2 разных танка.
> x^=y^=x^=y (для тех кто в танке, это хитро записанный обмен значений x и y)
В Си++ это UB, а не обмен значений.
Формально согласен - но я ещё не видел ни одного компилятора, который бы здесь наманьячил.
Скорее всего таких и нет. Сам по себе код, конечно, интересный, но на практике лучше писать
std::swap(x, y);
Это короче, и во сто крат понятней.
а сколько вы знаете highload серверов написанных на плюсах? есть мнение что писать для быстродействия нужно на C используя местами ASM, а плюсы больше для бизнес приложений где важно чтобы куча кетайцов и индеров могла свободно ориентироваться в коде
Есть мнение, что за счёт инлайнов тот же "сорт" работает в Си++ быстрее. Мнение, кстати, не просто "есть", оно проверяется легко.
Это, конечно, частность, но как минимум видно, что Си++ ну не медленнее, если руки из плеч.
Про асм тоже интересно. Много ли человек могут писать на асме лучше, чем генерирует современный компилятор? И сколько будет стоить такой код?
Про бизнес приложения и "куча кетайцов" "свободно ориентироваться" по отношению к Си++ вообще как-то нелепо.

Есть мнение, что писать highload сервера нынче модно на Erlang'е.
Поэтому у Сишников есть макросы для сортировки, и других алгоритмов :)
Но Си++ и правда не может быть медленнее.

После первого highload сервера на эрланге, не связанного с телекоммуникацией, желание напрочь отпало :) но скорость разработки... я даже от себя не ожидал, что можно так быстро на эрланге решать задачи.
А можно подробнее, хотя бы в какой предметной области был сервер? А если вкратце описать основные грабли, то вообще замечательно.
про ASM это вообще заблуждения 90-х годов. Сейчас уже не те процессоры что были раньше, сейчас в процессорах куча конвееров, разных инструкций, плюс многоядерность, сильно сомневаюсь что код написанный на ассемблере будет быстрее кода современного компилятора
>про ASM это вообще заблуждения 90-х годов
не, всё ещё актуально в специфичных узких местах :) как было сказано "используя местами ASM"

>плюс многоядерность
Компилятор распараллеливает ?! :)

>сильно сомневаюсь что код написанный на ассемблере будет быстрее кода современного компилятора
сомневаетесь, потомучто сами не способны? или это где-то кем-то было доказано?
exch x,y
и что тут оптимизировать или распараллеливать?
Да, компилятор, несомненно сможет развернуть цикл, заменить divы на битхаки подобные приведенному в этой статье, но это не отменяет того, что нужно знать специфику компиляторов и процессоров. Конвейеры это конечно круто, но компилятор не сделает за вас эту работу. Чтобы конвейеры использовались нужно написать грамотный код, а грамотный код нужно писать держа в уме таблицы из референса по ASM по операциям, которые могут выполняться параллельно, а также неплохо иметь понятие, каким образом в SMP используются различные уровни кэша, как идет работа с памятью и т.п..

Если написать логику без учета этих многих параметров, то результат может получиться много медленнее несмотря на оптимизацию от компилятора. Это примерно как оптимизировать целочисленную логику под SSE, когда эти же операции выполняются на новых интелах с таким же уровнем параллелилизма, но без затрат на ввод/вывод данных в специальные регистры. Без использования SSE логика даже рассчитанная на параллельные вычисления будет работать быстрее. Чтобы использование SSE (и любой другой SIMD технологии) дало нужные результаты - нужно четко понимать - для чего это используется и в каких случаях можно получить преимущество.

Убеждать против подхода "за счет инлайнов", "сорт в C++" и "быстрее" считаю бессмыссленным. Любое мнение имеет право на жизнь. Если долго повторять себе, то начинаешь в это верить :)

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

Что же касается C vs C++, то работа под высокой нагрузкой в мультипоточной среде при SMP основанная на сборке мусора ... кхм. Зачем тогда пишут вещи подобные hoard, ведь лучше использовать все стандартное и полагаться на компилятор? :)

Про стандарный сорт ... кхм.
http://research.microsoft.com/barc/sortb…
Некоторый софт доступен даже для скачивания. Можно протестировать :)
Вместе с тем - да, какие-то участки кода будут работать с такой же скоростью, потому что будут компилироваться в одинаковый машинный код.
C++ не урезает возможности языка Си, а добавляет :) Я даже представить себе не могу на основе чего можно сделать вывод что Си++ медленее Си.
Начнем с простого
http://developers.sun.com/solaris/articl…

Попробуйте, как нибудь поинтересоваться, как реализуется обычно сборка мусора для SMP и какие операции нужны, чтобы отслеживать число ссылок.
Обратите внимание на ptmalloc (стандартный аллокатор glibc на базе LEA) vs hoard (нестандартный аллокатор для C++ для SMP).
Никак не могу уловить связи между аллокаторами и C/C++. Я например использую свои аллокаторы, у которых посложнее апи чем стандартные malloc/free, что позволяет мне играться с обрезанием указателей на 64битных до 32бит/использование hugepages и прочие вкусности, которых нет ни в hoard, ни в ptmalloc.
И что за мифическая "обычно сборка мусора для SMP" :) Как сделаешь - так и будет собираться мусор, способов уйма и никак не связана с языком программирования.
Все чтоли? Товарищи, продолжите дискуссию, дюже интересно :)
Примерно как x^=y^=x^=y (для тех кто в танке, это хитро записанный обмен значений x и y)


Это не для тех кто в танке. Это для тех, кто под танком. Вам туда не надо... В результате выполнения этой конструкции может случиться всё, что угодно - хотя обычно компилятор не догадывается соптимизировать это всё до x=0 (но имеет полное право так сделать)...
Изящен то он изящен, вот только медленный :) Есть более быстрые способы обмена, хотя конечно не такие изящные.
public class aaa {

/**
* @param args
*/
public static void main(String[] args) {
int x = 6;
int y =17;
x^=y^=x^=y;

System.out.println("x = "+x+", y= "+y);
}

}


x = 0, y= 6
Спасибо за продемонстрированные грабли. В нормальных процессорах после XOR x,y; XOR y,x; XOR x,y уже нечего оптимизировать, но JVM на нормальные процессоры не похожа. Получается жутковатый байткод с кучей копирований:


6: iload_1
7: iload_2
8: iload_1
9: iload_2
10: ixor
11: dup
12: istore_1
13: ixor
14: dup
15: istore_2
16: ixor
17: istore_1
Это байт код как он исполняется или как он в классфайле? Уверяю вас JIT отлично переведет его в 2 ксора. А если не переведет - это очень плохой JIT
в этом и проблема таких "изящных" приемов. Учитывая, что линкеры, компиляторы, оптимизации прекомпилятора написаны разными людьми по разному. А потом люди удивлятся всплывшим откуда невозмись багам... а потом неделями дебагят "изящные" конструкции типа этой...
Помоему надо первой строкой каждого учебника по програмированию писать правило вывернное годами:
Reading code is more important than writing code
конечно не стоит надеяться что в java будет работать низкоуровневая оптимизация под x86 там ведь результат операции почти всегда уже новый объект
UFO just landed and posted this here
вах) мой первый пост на хабре окажется, видимо, банальным, но все же:

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

В школе одной из первых задач было написать swap(x, y) желательно без использования доп. памяти. Препод ставила 3 тем, кто написал с дополнительной, 4 - тем, кто без дополнительной, и 5 - тем, кто смог объяснить, что без дополнительной памяти - неправильный вариант)
UFO just landed and posted this here
возможно. но кроме практичности есть более важный критерий - корректность. это решение, по-моему, является некорректным. или я неправильно понял задачу - "поменять местами значения двух переменных (объектов? адресов?)"
любой вариант обмена значениями без использования третьей "ячейки" некорректен: представьте, что для обмена передали одно и то же значение.
Вариант x ^= y; y ^= x; x ^= y; работает корректно даже если x == y, представьте себе. А вариант x^=y^=x^=y; является некорректным с точки зрения С++ потому, что переменная изменяется более одного раза между двумя точками следования.

Кстати было бы интересно увидеть доказательство невозможности написать swap (для целых типов) без использования дополнительной памяти. Если вам не сложно, конечно.
Наверное, несложно (я тогда получил 4). Только, чтобы не было недопонимания, укажите прототип требуемой функции.
void swap(int&, int&);

Если не сможете доказать невозможность, найдите хотя бы такую пару чисел, для которых функция, приведенная ниже будет работать неверно.
void swap(int& x, int&y)
{
x ^= y;
y ^= x;
x ^= y;
}
inline было бы неплохо добавить?
Не суть важно в данном случае. Вопрос в возможности/невозможности и корректности/некорректности.
не совсем в числах дело, а в реальном использовании)
например:

int x = 5;
swap(x, x);

на выходе получим, увы, не 5.

конечно, именно так вряд ли кому-то понадобится делать. но при той же сортировке это запросто вылезет
Понятно, я немного по-другому истрактовал вашу фразу «для обмена передали одно и то же значение» :) Вы правы, приведенный мною вариант функции будет работать неправильно в этом случае. Однако swap без дополнительной памяти всё же достижим:
void swap(int& x, int& y)
{
if (x == y) return;
x ^= y;
y ^= x;
x ^= y;
}

Или нет?
да, так все будет работать, т.к. критерий работоспособности обмена - наличие двух разных ячеек памяти. а кроме XOR'a, очевидно, есть континуум различных вариантов.
inline было бы неплохо добавить?
в java есть такая фича, что значение слева от оператора прсваивания сохраняется прежде чем рассчитывается то, что стоит справа от него. поэтому выражение x^=y^=x^=y; некорректно в данном примере. так может быть: x^=y^(y^=x^=y); но все равно имхо этот способ записи ужасен с точки зрения “красоты” кода
UFO just landed and posted this here
Красоту кода немного нарушает неравная длина степеней двойки в десятичной записи.
UFO just landed and posted this here
UFO just landed and posted this here
Зато найти пропущенную скобку проще и ориентироваться в коде легче.
Мне тоже кажется... но не настолько категорично же.
Это просто разные стили программирования.

BSD стиль:
function x()
{
//operator
}

GNU стиль:
function x()
{
//operator
}

K&R стиль:
function x(){
//operator
}
Данная запись на мой вкус лучше всего выглядит так:
procedure hui;
begin
{ code }
end;

;-)))))
не пищите здесь "хуевых" процедур.
тут код на C а не на Pascal
мне кажется, вы не правы. все зависит от code conventions принятых в проекте. как правило переносят на следущую строку - так как в длительной перспективе этот код легче читать. хотя это зависит, повторюсь, от проекта.
UFO just landed and posted this here
UFO just landed and posted this here
Согласен с вами. В данном случае использование asm`а ничем не мотивированно. К тому же код на Си более универсален в плане портирования на другие процессоры, хотя это редко бывает необходимо.
UFO just landed and posted this here
Вам рассказать, что мне хочется сделать с отдельными представителями вида homo sapiens (?), считающих, что их код никогда не придется запускать на процессоре, отличном от x86?

Раскажите - интересно. Почему вдруг я должен тратить моё время на решение ваших проблем? Архитектур в мире существует две с половиной: x86, x86-64 и ARM. Если вы пишете игры - ещё PowerPC. Всё остальное - от лукавого.
UFO just landed and posted this here
Тяжёлые SMP-машины - вымирающий вид (или, скорее сказать, вытесняемый: больше 64-128 ядер SMP малоприменим, а до этого уровня x86 скоро доберётся), если кто-то хочет выкидывать бессмысленную кучу денег на Power, IPF, SPARC и System Z, то он может и на программистов эти деньги потратить - с него не убудет. А писать код, чтобы он, скажем, пережил Big-Endian - это лишние теледвижения. Или вы хотите сказать что писать такой код проще, чем непортируемый?
UFO just landed and posted this here
Представьте себе, SPARC и PA-RISC как раз BE.
О чём и речь :-) Сложно с ними. Да и зачем?

Что касается тяжелых многопроцессорных машин, то SGI-ные NUMA работают в конфигурациях и на 512, и на 2048 ядер.
И много таких машинок они продают? А раз их продаётся с гулькин нос, то и софта под них оптимизированного - кот наплакал. Рано или поздно это направление сдохнет.

Если сделать обвязку для и вариант процессора х86, способные работать в таких конфигурациях, это будет ничуть не дешевле тех машин, о которых мы говорим.
Всё проще: сами эти машинки - вид вымирающий. Продаются они кое-как за счёт тех программ, которые специально для них и писались - ну и используйте там ваш legacy soft! Зачем новый-то под этих динозавров затачивать?
Ну... А как же network order? Если у машины основное назначение tcp/ip-сервером быть, то само taoсp велит использовать машину с BE и оптимизировать соответсвующим образом софт.
На киске собираетесь софт, разработанный каким-то Васей пускать? Уверяю вас: если BE->LE->BE вас тормозит, то ваши задачи оооочень специфические и софт вам нужен не менее специфический... О железяках где кроме поставляющейся с ними прошивки ничего не работает мы не говорим - это отдельная песня. Там даже 4-битные процессоры ещё в ходу - это же не повод на них закладываться при написании библиотек, правда?
>>выкидывать бессмысленную кучу денег на Power, IPF, SPARC и System Z

извините, вы сами-то видели IBM'овские z10? ТТХ читали?
x86(-64) рано или поздно умрет. умрет под грузом всего того говна, которое в него напихали (вроде SSE). он и сейчас-то живет только за счет Windows.
извините, если вдруг задел.
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Всё же это преувеличение. SPARC, PowerPC, MIPS, Itanium никуда ещё не померли и вполне себе живут. При этом живут вполне себе активно и позиции x86-64 (x64) сдавать не собираются. Всё же современный x64 уж черезчур сложный процессор и до электричества жадный. А сложность следствием имеет повышенную багонасыщенность. Так что, я бы не стал хоронить прочие архитектуры - рано ещё. И даже вполне себе может выйти так, что хоронить нам придётся x64, если Microsoft таки не сможет потянуть разработку Windows 10. А даже если и сможет, то нет никаких гарантий, что для Microsoft приоритетной станет платформа xbox. Вобщем, рано хоронить отличные от x64 архитектуры.
При этом живут вполне себе активно и позиции x86-64 (x64) сдавать не собираются.
На каждую машинку не x86-архитектуры приходится с десяток основанных на x86-64.

Desktop? Ну вы сами знаете - ни MIPS, ни Itanium там "не играют". Самый-самый топ? 79.8% занимает x86-64 плюс ещё 2.6% - x86. На долю всех тех, "которые живут вполне себе активно и позиции x86-64 (x64) сдавать не собираются" - 17.6%. Суммарно на всех.

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

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

Смотря что мы называем 'машинкой'. Думается, что в окружающем пространстве процессоров с архитектурой MIPS или SuperH на порядок больше. И это вроде как во вполне себе таких вычислительных устройствах.

TOP 500

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

А первые два места TOP 500 занимают системы на PowerPC. И отрыв значительный.

Desktop

Apple недавно 'купила обратно' P.A. Semi, которая смогла таки сделать очень эффективный PowerPC, и не известно, какие процессоры будут использоваться дальше в desktop'ах от Джобса. Вполне возможно, что реверанс в сторону x64 со стороны Apple был попыткой сманить на Mac OS X новых пользователей, которые бы в последствии стали бы покупать и железо от Яблока. Ну, и нормальный PowerPC они ждали.

Да и xbox с playstation вполне себе в десктоповом режиме могут функционировать. Видео/музыка/интернет поддерживается, а большинству народу большего и не нужно.

И приставкам незачем переходить на x64. Для xbox такой переход выльется в удорожание, потому что Broadway - очень дешёвый процессор с высокой производительностью на ватт. А Cell - слишком другая архитектура, под которую framework от Sony заточен. Да и производительность у него гораздо более высокая в классе игровых и мультимедийных приложений.

Поэтому, я и говорю, что будущее непонятно какое будет.

Единственный козырь у x64 - это совместимость с наследием wintel. Но с развитием всякого .net, web-2.0 и Google, это всё меньший и меньший козырь.

Опять же. AMD считает, что процессоры надо делать неоднородными, а NVIDIA сделала ускоритель, к которому приделан ARM. Intel будет танцевать против этих игроков с Larrabee, который тоже уходит в сторону от x64. Непонятно, как оно будет в будущем.

Да, сейчас x64 являются топовыми, но тут можно вспомнить историю с Alpha, кто его знает, чем это всё продолжится?
Люди, вы о чём? Какие переходы? Какие циклы? Из "K6 optimization manual" (:
mov     edx,esi
shredx,1
andedx,055555555h; (n >> 1) & 0x55555555
subesi,edx; n - ((n >> 1) & 0x55555555)
movedx,esi
shredx,2; n >> 2
andesi,033333333h; n & 0x33333333
andedx,033333333h; (n >> 2) & 0x33333333
addesi,edx; n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
movedx,esi
shredx,4; n >> 4
addedx,esi; n + (n >> 4)
andedx,00F0F0F0Fh; n = (n + (n >> 4) & 0x0F0F0F0F)
imuledx,001010101h; add by multiplying with a "magic number"
shredx,24; shift result into place
UFO just landed and posted this here
Oops. Не обратил внимание что sandycat влево сдвигать предлагал - это я и сам бы хотел увидеть. Может он описался?
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
в SSE4.2 есть popcnt :)
Вместо int должен быть unsigned, в противном случае при отрицательных значениях аргумента вот этот, например, сдвиг вправо
((x & 0xAAAAAAAA) >> 1)
может привести к неверному результату на определнных платформах/компиляторах (бит, отвечающий за знак, не пострадает после применения маски 0xAAAAAAAA).
Вычисляет количество, а возвращает знаковый int. Привязан к размеру int, при этом int не заменен на какой-нибудь int32_t.
я бы для крастоы и читабельности, между символом и скобкой поставил пробел...
по типу:
x = ( x & 0x0000FFFF ) + (( x & 0xFFFF0000 ) >> 16 );
Я когда-то тоже так делал, но перестал из-за причины излишней раздумаемости кода, как мне показалось.
Строка становится длиннее и ее тяжелее читать.
IMO читать, как раз, легче. Хоть строка и длиннее.
Вот мои основные правила, на которые я опираюсь, при написании своего кода (foo-пример на php):

function getones _ (a _ = _ false) _ {

/*
Табулятор 4 (удобно в python) или 6 (удобно в php) пробелов.
Серые подчеркивания символизируют пробел.
*/

таб global $foo, _ $bar; // Это если нужен комментарий

таб if _ (!$a)
табтаб echo 'false';
таб else {
табтаб echo _ ($foo _ === _ $bar ? 'yes' : 'no');
таб }

таб return 1;

}

Иногда делаю так, чтобы удобно было отрезать части кода более одной строки:

/*
$user табтаб = 'root';
$server табта = 'localhost';
/**/

$user табтаб = 'nobody';
$server табта = '192.168.0.2';
/**/

Открывающийся комментарий блокирует нижние строки. Таким образом код не содержит ошибок и для комментирования достаточно переместить один открывающийся /* комментарий. Плюс редактор автоматически равняет строки неравной длины по табам.

И массив оформляю обычно столбиком:

$arr = array (
табтаб 'а',
табтаб 'б',
табтаб 'в'
);

Кажется все... Рад, если кому-то это оказалось полезным.
Почему я не переношу { на новую строку:

  1. Мне искать открывающуюся скобку _не_ легче если она стоит на новой строке: я знаю (for, if, switch, else и что-то наверное упустил) после чего она может стоять, плюс табуляторы тоже хорошо помогают.

  2. Если в редакторе есть возможность сворачивания кода по {}, то без переноса не остается лишней пустой строки:
    function abc () { // Эта останется
    { // А эта уже нет. Зачем?

Однако, скорее всего все зависит от привычки и от того, где вы пишете.
Я пишу в kate под linux со встроеным такстовым редактором по-умолчанию.
вообще фигурные это ужасное "изобретение" - порождает мильён стандартов кодирования, плодит синтаксические инконсистентности и вообще всячески попирает принцип Оккама при кодировании

вот indentation-based синтаксис совсем другое дело (Haskell, Python)..
О, всё моё!

А комментарии-семафоры я делаю следующим образом:
/*
code1
/*/
code2
//*/

для переключения надо добавить слеш в начало первой строки =)
Размер типа int не устанавлен стандартом C++. Размер зависит от реализации. Таким образом этот код не является переносимым, поведение зависит от реализации.

Более того, поведение операции правого сдвига для отрицательных чисел оставлено стандартом на усмотрение разработчиков компиляторов. Действительно, компиляторы от Intel, Microsoft и gcc обрабатывают правый сдвиг для отрицательных чисел по-разному.

Это плохой код.
Плохой не означает (не-)красивый.
Он будет работать только при благоприятном расположении сфер небесных. Какая уж тут красота.
Так это не код - это демонстрация алгоритма :) Так, наверное, надо воспринимать этот кусочек. В реальности надо использовать вариант от khim (развитие основной идеи метода) или встроенные инструкции процессора.
Код прекрасен.

Можно, конечно, поругаться на особенности реализации. Но это поправимо. А идея прекрасна.
Да ладно. Мне больше нравится классическое:

int get_ones_count(uint32_t n) {
  n -= ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n + (n >> 4) & 0x0F0F0F0F);
  n = n * 0x01010101;
  return n >> 24;
}

Ну или если умножения быстрого нет, тогда

int get_ones_count(uint32_t n) {
  n -= ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  n = (n + (n >> 4) & 0x0F0F0F0F);
  n += n >> 8;
  n += n >> 16;
  return n & 0x3F;
}
Первый вариант работает корректно только для n&lt=0xFF. По крайней мере на perl.
Первый вариант отлично работает на всех n. Там недаром сначала идёт умножение n на 0x01010101, а потом уже сдвиг вправо. Результат образуется в разрядах 24..31, а в остальных - мусор.
Ага, сообразил. Надо в perl включить прагму use interger - иначе он из-за переполнения молча конвертирует n в double.

Тогда всё работает корректно, и процентов на 15 быстрее второго варианта... но от tr/unpack всё-равно отстаёт процентов на 50.
Еще можно добавить вариант для 64-х битной машины без сверхбыстрого умножения:
uint get_ones_count(uint64_t x) {
   uint64_t n;
   n = (x >> 1) & 0x7777777777777777;
   x = x - n;
   n = (n >> 1) & 0x7777777777777777;
   x = x - n;
   n = (n >> 1) & 0x7777777777777777;
   x = x - n;
   x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
   x = x + (x >> 8);
   x = x + (x >> 16);
   x = x + (x >> 32);
   return (uint) (x & 0xFF);
}
Ирунда. Ну как может быть красивым чёрно-белый код? Э? Вчерашний день. Да.
Вам, дизайнерам, этого не понять. :D
*безобидная шутка
О! Так я Дизайнер?! Красивое имя!
Так же, как ч/б фильмы Чарли Чаплина уделывают современные голливудские блокбастеры, вместе с их взрывающимися вертолётами.
Вы лишь поменяли систайл на явастайл. не более.
Ну да, по-моему так красивей.
А почему явастайл? Вроде бы это называется паскаль- и камел-стайлом.
Неа. Явастайл будет вот так - int getOnesCount( int x );
А там C# стайл.
Ява-стайл (camel-case) это getOnesCount(...)
а GetOnesCount — это pascal-style.
Кому как. Я функции всегда именую с большой буквы. Переменные с маленькой.
Видимо с Дельфей начинали.
Ну... лицей и первый курс паскаль (не делфи), дальше с++. Я написал всегда? Надо было написать, теперь всегда :)
Лучше бы написать - теперь никогда. :-)
Кстати, этот код отлично оптимизируется для констант. Компилятор сам подставит результат вместо вызова get_ones_count(SOME_PREDEFINED_CONSTANT).
код - ужасен =(
Когда занимался 3D-графикой сказал бы, что код - красив и элегантен, сам так любил писать (думал, что умнее IntelC =) )...
Сейчас на первое место вышли - прозрачность кода и простота восприятия.
Никаких длинных функций и сложных конструкций, никаких магических заклинаний и мантр (хотя, для кого-то шаблоны, boost, ... - что-то вроде сатанинских песнопений =) ).
Время на отладку и построение ментальной модели давно забытого участка кода дороже обходится мнимых эстетических изысков, имхо =)
Ну, наверное, если кто-то пишет такой код - значит ему не пофик, сколько времени будет выполняться его программа. И не надо говорить мне, что, дескать, быстродействие кода давно и абсолютно никого не волнует. Если бы быстродействие никого не волновало, то в новые варианты PowerPC и Intel не добавили бы машинную команду для этого самого подсчета количества единиц. Вера во всемогущество компилятора тоже ни на чем не основана – простой подсчет количества единиц (записанный через тупой цикл) компилятор ни на этот код, ни на использование одной машинной команды САМ не заменит, он ведь искусственным интеллектом не обладает (пока что, во всяком случае).
Он ведь искусственным интеллектом не обладает.
Зато обладает библиотекой шаблонов. Грубо говоря в gcc есть сотни (если не тысячи) иструкций типа "видишь A => пиши B". Никто не мешает и этот цикл туда добавить. Работает на удивление хорошо: оказывается существует куча конструкций, которые встречаются часто и которые почти все программисты пишут неоптимально и одинаково.
Да, это известно - но написание таких шаблонов (с циклами) очень сложная задача и они замедляют работу компилятора, поэтому разработчики GCC пошли по пути добавления встроенной функции __builtin_popcount вместо описания новых преобразований в промежуточном языке.
В свою очередь для программиста это приводит к тому, что приходится писать generic код на plain C типа приведенного Вами под все процессоры, плюс к этому еще и проверять версию GCC на 3.4 и тогда использовать __builtin_popcount. А для старых версий GCC и для других компиляторов приходится использовать вручную написанные ассемблерные вставки или другие builtin функции.
Разумеется, я имею в виду ситуацию, когда кому-то нужно экстраординарное быстродействие при подсчете числа единиц в числе.
Может и красив, но ни разу не практичен. :)
Хотя, что автор понимает под красотой кода?
автор сам не понимает этого до конца). вот и спрашивает))))
Красота в простоте. Преждевременная оптимизация — корень всех зол.

Код не красив.

Тот же
c = x & 1;
while (x >>= 1) c += x & 1;
мне видится гораздо более красивым, если только он не узкое место в программе.
Кстати, советую обратить внимание на книгу Эрика Реймонда "Искусство программирования для Unix", там высказывается и обосновывается, по крайней мере, интересное мнение с точки зрения многолетнего опыта программирования под Unix.
Тогда уж намного лучше
с = 0;
while (x) {
c = c + 1;
x = x & (x - 1);
}
кстати в некоторых случаях этот вариант еще и самый быстрый.
полностью согласен!!!
код Jaguar всего где-то в 2 раза медленнее, но
1) более читабельный, 2) более портируемый
Чисто ради любопытства: что будет если x < 0 ?
Попробуйте ;)
ничего не происходит, зациклился, наверно :)
да, собственно, это уже тонкости: можно перед подсчетом число округлить, или проверить знак и вывести ошибку, или привести тип к unsigned.
если уж говорить только о красоте...

while (x)
    c += x & 1,
    x >> 1;
а ничё, что он не работает?
ой, кажется, я разучился писать программы в голове
Код выглядит конечно забавно, но если б там не было написано что он делает, то я бы не понял, зачем он.
При работе в команде такие вольности не допустимы, имхо.
++++++++++[>+++++++>++++++++++>+++++++++++<<<-]>++.>---.+.>++++<-.<.>-.+.>.>.

Чем не красавец? В исполнении BrainFuck :)
Код пишет HabraHabr. :)

Итересующимся поможет википедия и таблица ASCII.
В таком виде код понятен и легко читается, то есть, он ВНЕШНЕ красиво смотрится. Но как тут верно заметили - для реального проекта этот код недоделанный:
- Нужно использовать беззнаковые целые,
- Следует отвязаться от 32-битной разрядности обычного int и добавить вариант для 64-битных процессоров (который будет иметь несколько иной код, чтобы избежать массового использования длинных целых констант),
- Этот код не оптимизирован и для 32-битной платформы, в нем можно переписать известным образом (с использованием вычитания) первый шаг алгоритма и последние шаги избавить от лишнего маскирования,
- Возможны оптимизации через использование умножения для некоторых архитектур,
- В программе так же хорошо бы предусмотреть подмену этой функции на ассемблерные вставки для конкретных современных процессоров (их новых модификаций), учитывая, что почти все из них (включая последние варианты Intel x86) имеют аппаратную команду для подсчета количества единиц в числе. Если такой код пишется - значит гонятся за быстродействием, а раз так - сам Бог велел использовать аппаратное ускорение возможное на конкретных CPU. :)
Кстати о скорости работы. Все почему-то уверены, что это самый быстрый способ... Возьмём, просто для разнообразия, :) такой классный язык как Perl.

#!/usr/bin/perl
use warnings;
use strict;
use Benchmark qw(:all);

sub get_ones_bitwise {
    my ($x) = @_;
    $x = ($x & 0x55555555) + (($x & 0xAAAAAAAA) >> 1);
    $x = ($x & 0x33333333) + (($x & 0xCCCCCCCC) >> 2);
    $x = ($x & 0x0F0F0F0F) + (($x & 0xF0F0F0F0) >> 4);
    $x = ($x & 0x00FF00FF) + (($x & 0xFF00FF00) >> 8);
    $x = ($x & 0x0000FFFF) + (($x & 0xFFFF0000) >> 16);
    return $x;
}

sub get_ones_tr {
    return sprintf("%016b", shift)=~tr/1//;
}

sub get_ones_unpack {
    return unpack "%32b*", pack "L", shift;
}

our @test = (0,1,3,255,256,1023,1024,0x33333333,0xFFFF0000,0xFFFFFFFF);
@test = (@test) x 100;
cmpthese(1000, {
    bitwise => sub { get_ones_bitwise($_) for @test },
    unpack  => sub { get_ones_unpack($_)  for @test },
    tr      => sub { get_ones_tr($_)      for @test },
});

__END__

         Rate bitwise  unpack      tr
bitwise 532/s      --    -44%    -45%
unpack  952/s     79%      --     -2%
tr      971/s     83%      2%      --

Вот так. Самый быстрый-то, оказывается, tr - которому сам Ларри Уолл велел считать кол-во одинаковых символов в строке. :)
На всякий случай я ещё проверил варианты посмотреть профиль khim: первый работает некорректно на числах больших 0xFF, второй обгоняет вариант топикстартера на 2%, которые погоды не делают.
Хотя со скоростью перебора в while было и так всё понятно, но, до кучи, проверил вариант посмотреть профиль Jaguar и вариант посмотреть профиль sysprg. Первый, вопреки утверждению посмотреть профиль sysprg, немного быстрее. Но в любом случае оба раза в два медленнее исходного варианта топикстартера.

          Rate   while2    while  bitwise bitwise2   unpack       tr
while2   249/s       --      -3%     -52%     -55%     -73%     -74%
while    258/s       4%       --     -51%     -53%     -72%     -73%
bitwise  524/s     110%     103%       --      -5%     -44%     -46%
bitwise2 549/s     120%     113%       5%       --     -41%     -43%
unpack   935/s     275%     262%      79%      70%       --      -3%
tr       962/s     286%     272%      84%      75%       3%       --
При тестировании таких фрагментов важно принимать во внимание конечную цель - зачем этот код используется и что подается ему на вход. Вариант с "x & (x - 1)" хорош тогда и только тогда, когда в числе маленькое количество единиц. В Вашем тесте разницу можно увидеть, если убрать "тяжелые" шаблоны из теста, такие, как 255, 1023 и особенно 0x33333333,0xFFFF0000 и 0xFFFFFFFF. Для них лучшее решение - это вариации . И конечно же самое главное - эти коды не для скриптовых языков (типа perl). Понятное дело, что при использовании perl встроенная функция обгонит все, так как основные накладные расходы в реально хороших вариантах идут на синтаксический анализ и интерпретацию.
Бред. Вы меряете не скорость алгоритмов, а скорость интерпретатора. Пока в perl не будет приличного JIT'а - нужно смириться с тем, что его использование - многократный проигрыш в скорости по сравнению, скажем, с Java...
Я, вероятно, отстал от жизни. Расскажите, пожалуйста, что такое "скорость алгоритма"? :)

Асимптотическая оценка к нашему случаю вроде не относится, а все остальные оценки скорости алгоритма так или иначе базируются на конкретном железе/софте выполняющем этот алгоритм. Например, обсуждая примеры на C/Asm мы исходим из того, что XOR и ветвление процессор выполняет с разной скоростью, и мы знаем что он делает быстрее. В этом плане мой подход ничем не отличается, просто я вместо процессора взял интерпретатор Perl. Более того, он полезен, т.к. я абсолютно уверен что среди читателей этой ветки больше программистов на Perl, чем на Asm. :)
Но вряд ли кто-то в реальной жизни будет считать число единиц в бинарном представлении целого числа на Perl. Много ли Вы вообще знаете задач, где актуальна проблема подсчета количества единиц? Это очень, очень редкие и специфические алгоритмы, самые что ни на есть "ядерные" - к оболочке и скриптам отношения (я думаю) не имеющие. Причем может оказаться, что единицы нужно считать даже не в отдельных числах, а в массивах, и тогда потребуются еще более изощренные вариации алгоритма. Или даже особые структуры данных – например, если нужно считать расстояния по Хеммингу между миллионами битовых векторов. При написании такого "ядерного" кода может оказаться полезным учесть и плотность единиц - например, если ожидается, что они очень редки - использовать цикл, если их сравнительно много - код типа рассмотренного в этой ветке, если процессор имеет соответствующую команду (x86 SSE 4.2, Power5+, Itanium, Alpha EV6+) – то использовать ее...
вообще немного относится. у этого алгоритма O(log n) а у цикла O(n) где n - кол-во битов.
а на примере перла мне кажется неправильно сравнивать. Вернее верно сравнивать алгоритмы с числами и со строками отдельно. Ведь перл все же скриптовый язык.
Скорость алгоритма - это количество элементарных операций. Во всей литературе и всей теории предполагается что элементарные операции выполняются с одинаковой скоростью. Если у вашей машины вдруг появляются какие-то операции, которые работают в тысячу раз быстрее чем операция сложения, то вся теория идёт лесом. Вернее она остаётся верной для чисел типа 10100, но для нормальных диапазонов - она идёт лесом...
Как по мне, так не очень понятно, т.к. что такое 0х я догадался только после прочтения первого комментария.
Ну так это правила языка.
Или вы хотите, чтоб код на всех языках выглядел одинаково понятно без знаний?
автор, видимо, считает, что с С знакомо большинство программистов.

разве он заблуждается?
Может цифры в константы занести чтобы код можно было прочитать?
в этом случае __builtin_popcount будет понятнее :)
и пользуйтесь благами open source :)
src/linux/lib/hweight.c
есть же man на эту тему: http://www.freebsd.org/cgi/man.cgi?query=style&sektion=9&apropos=0&manpath=FreeBSD+6.1-RELEASE - там и описано какой должен быть красивый код.
short int == 2
int == 4
long int = 8
long long int (в C) == 8
Битность процессора совпадает с размером инта.
n-битность процессора означает лишь, что в этом процессоре n-битное слово. Про инты ничего не сказано.
Кто вам сказал? MSVC даже в 64-битном режиме имеет long в 4 байта, а вы - про int...
Ну long всегда 4 насколько помню по спецификации. А вот int не задана. Вот я думаю, 4 или 8 оно.
По "спецификации" short int не менее 16 битов, int не менее 16 битов, long int не менее 32 битов. "Не менее". Почитай стандарт.
Плохо же вы помните спецификацию.
sizeof(char)<=sizeof(short)<=sizeof(int)<=sizeof(long)<=sizeof(long long)
unsigned сhar вмещает в себя числа до 255
unsigned short - до 65535
unsigned int - до 65535
unsigned long - до 4294867295
Всё. Может быть, к примеру, так, что sizeof всех вышеперечисленных типов равен 1 и все они занимают по 8 байт :-)
Я имел в виду, что если процессор n-битный, то в int в C++ n бит.
Неправда, см. выше. Стандарт ничего не говорит про размерность процессора.
Я не указывал на стандарт.
А про какой C++ тогда идёт речь?
Вполне хороший и читаемый код. Я предпочитаю немного другую нотацию вида
abc {
}

и отбивать внутри по TAB ( 8 или 5 пробелов ) - но это мое личное так сказать )

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

Как всегда: производительность * портабельность == константа
По рукам :) С первого взгляда не понятно, что код делает, и нет ни одного комментария.
Кстати, тут говорят, что код линейный, но на самом деле он тоже выполняется за O(количество битов), потому что нам пришлось бы добавлять пропорциональное количество строчек при переходе на другое количество битов.
*O(log(количество битов))
ну, тут могут быть совсем тонкие тонкости типа возможности предсказуемости цикла и его помещаемости в конвейер
Код не красив, так в нём меняется смысл переменной.
Никогда не любил все эти "финты ушами" типа "k = ++p + k++" - после такого очередного "программера" поддерживать проект становиться всё сложнее и сложнее.
Код никогда не бывает красивым. Бывают красивыми только идеи, нашедшие реализацию в коде.
я пришел к такому же выводу)
знаете, в стихах тоже есть идея, и есть форма. вы же не будете утверждать, что красива только идея. тут, мне кажется, тоже самое.
Между поэзией и программированием есть действительно много общего. Это отмечали многие великие умы, такие как Дональд Кнут, Ричард Габриэль и другие.

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

Возвращаясь к теме топика, можно ли судить о красоте кода, предложенного автором, только с позиции формы? Однозначно нет. Не понимая, что собственно в нем происходит (алгоритм), невозможно понять красив он или ужасен. Точно также невозможно судить и красоте стиха, например, если он написан на неизвестном читателю иностранном языке. Можно попытаться прочитать стих, уловить, где в нём рифмы и какой у него ритм. Это и будет форма. Но как бы она ни была прекрасна, белиберда, которая возможно скрывается в этих неродных словах и незнакомых правилах пунктуации, никогда не может считаться поэзией лишь поэтому.
Совершенно верно. Прежде всего красота идей, но не только красота идей.
ИМХО код ужасен, потому что содержит много констант, и как сказал korynd, меняется смысл переменной. Пойдет только с комментарием, как неизбежная оптимизация.
Код действительно красив, но сложноватый. Я просто люблю вычислять такие примеры.
а нельзя понятное и самое очевидное
k = 0;
while (x) { if (x % 2) k++; x /= 2; }
?
Будет работать раз в 10 медленней.
И то. В некоторых алгоритмах это критическое место. Если вам не приходилось считать биты частно, это не означает, что никому не приходилось :)
>интересно почитать мысли на тему красивый/не красивый код

На эту тему есть очень хорошая книга Стив Макконнелл "Совершенный код".
UFO just landed and posted this here
Это что за язык такой?
Важно знать меру и не использовать подобные хаки и оптимизацию там, где они не нужны. Имхо, человек, использующий подобные вещи без необходимости неправильно понимает идеалы программирования.
Гы, а я такой кусок тоже видел в коде. Там комментов не было вообще никаких, а название функции менее очевидное. Пришлось мозг поднапрячь чтоб смысл осилить. Вообще если занешь что должно делаться - то не сложно, а если конечная цель функции неясна, то понять бывает не так просто...
Sign up to leave a comment.

Articles