Битовые операции, преимущества и недостатки

[InterceptorTSK]

Начало см. расширенный бинарный алгоритм.

Какие к черту беззнаковые переменные? Это кое-где не CLS-Compliant, а кое-где этого попросту нет.
Вы совершенно правы, такого рода приведения меня не интересуют, потому как кое-кто на заре эволюции приводил Int к UInt через unbox-box. Как сейчас обстоит ситуация - не знаю. Код написанный с UInt я запарюсь переносить физически на трубку или на соляру. Т.е. привести к UInt, сделать что надо, потом обратно в Int?) Без комментариев. Уважаемый, проведите эксперименты с одим сумматором и с двумя, я ж не против, гляньте разницу.
Господа, был предложен код, где явное преимущество имеют битовые операции в плане выполнения по времени. Код по сути одинаков и JIT его должен соптимизировать, но оптимизация не происходит. Какие могут быть еще вопросы? Хотите оптимизируйте, хотите нет. В любом случае грамотная оптимизация приведет к скорости равной, либо меньшей чем до оптимизации. И не надо мне тыкать JIT-ом. Я его бредовыми инсинуациями наелся. Он делает что хочет и как ему удобнее. Ну и рассмотрите уже простейшую ситуацию: есть код на IL, там есть div, "умный" JIT заменяет div на shift, а это уже дополнительное время.

[Maslov]

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

Press enter...
Fast 82428242 99999
Stpd 82428242 99999
Fast 82118211 99999
Stpd 82548254 99999
Fast 82978297 99999
Stpd 82588258 99999
Fast 83238323 99999
Stpd 83038303 99999
Fast 83148314 99999
Stpd 82798279 99999
Finished...

на одной машине и

Press enter...
Fast 64316431 99999
Stpd 63946394 99999
Fast 63966396 99999
Stpd 63706370 99999
Fast 63996399 99999
Stpd 63476347 99999
Fast 63916391 99999
Stpd 63776377 99999
Fast 63606360 99999
Stpd 63696369 99999
Finished...

на другой

InterceptorTSK в сообщении #325644 писал(а):

Ну пиво пьем, что поделать)

Может, в этом проблема?

[Toucan]

Тема перемещена в Программирование

[InterceptorTSK]

У меня на соседней тачке была идентичная картина. Четыре ядра, одно JIT-оптимизацию проводит, другое делом занято) Это конечно же только предположение, и может быть неверным. Знаю одно, на одном из первых двухъядерных Атлонов (s939), на Соляре x64 и на трубке Sony-Ericsson K-серии оптимизация работает. Повторяюсь еще раз, грамотная оптимизация либо не приведет к увеличению производительности, либо приведет, но уж никак не должна снижать производительность. Попробуйте на других машинах/платформах. Народу много, может кто и отловит разницу)
P.S. Компьютеры не пьют)

-- Вс май 30, 2010 20:06:25 --

Рассмотрите ситуацию с Int64, ну т.е. поменяйте в коде все Int32 на Int64 (кроме последнего, разумеется).

XP 32bit, SP3, FWv3.5, Athlon X2 3800+ (s939)
Press enter...
Fast 351093750 99999
Stpd 3060156250 99999
Fast 351093750 99999
Stpd 3060468750 99999

Кстати, если запустить код на 64битной системе, то есть надежда, что разницы не будет. Граждане! Запустите кому не лень на 64-bit OS! Желательно MS, и фреймворком от них же. Крайне интересен результат.
Ждать 5 циклов не стали, итак все понятно. Знал, что с 64битными числами на 32битных системах все запущено, но не знал, что до такой степени(( Кстати, совершенно забыл сказать, что компилируется все вышесказанное под AnyCPU.
Пойдем накатим) Будем через час-два)

[Circiter]

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

[InterceptorTSK]

Кроссплатформенность? Вы в эту светлую мечту верите?) Подскажите хоть одно реально быстро работающее кроссплатформенное приложение в одном флаконе. Поголовно версии 32/64, либо загрузчики, которые цепляют библиотеки 32/64, в зависимости от битности платформы. Да некоторые платформы имеют вообще фиксированную битность, и вряд ли в ближайшее, да и в отдаленное время будут расширены. По Вашей логике API из-под шарпа не вызывать, ну потому что это небезопасно? Указатели вообще зло? Ну это же не операции языка высокого уровня? Ну что остается, будем юзать высокоуровневый SetPixel) Извините, расскажите это разработчикам того же PhotoShop, или разработчикам игрушек посоветуйте. Плевать они хотели на кроссплатформенность и правильно делают. Ну потому что иначе невывоз( Кто приравнял битовые операции и к чему? На сайтах MS и Sun ничего про это не сказано. Приведите четкий официальный источник, где описываются конкретные случаи губительного воздействия вселенского зла.

[InterceptorTSK]

Кстати, есть еще один момент, вытекающий из общих соображений. JIT роется во всех делителях (а как иначе?) и ищет числа степени два. Таких чисел 63 штуки из диапазона [Int32.MinValue, Int32.MaxValue]. Т.е. пытаясь, по сути, соптимизировать 63 варианта из всевозможных вариантов с огромной кучей нулей. Деление - это зло.

[venco]

Трудно говорить о переносимости с человеком, который, судя по его сообщениям, знает только C# и немного ассемблер.
А ведь есть и такие компиляторы, которые знают про время исполнения разных операций, и умеют, например, деление на 10 заменить умножением.

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

[Zealint]

InterceptorTSK в сообщении #325824 писал(а):

Деление - это зло.

Неправильный вывод. Деление - это деление. а зло - это зло.

[InterceptorTSK]

Абсолютно последователен, потому что точно знаю что сдвинуть и куда. Где Вы видите >> x? Соптимизировать делитель нужно для сдвига, боже, уловите мысль, или в диапазаоне -int, int укладывается больше делителей? Ноль из расчета, разумеется, убираю. Вручную?) Мне этот термин знаком, но я им давно не пользуюсь) Ну потому что природа изобрела женщин, а мужчины изобрели парсеры)
Переносимость не нужна.
Переносимость нужна только на уровне исходников, и не более того, битность идентична.
Почему же ассемблер) Я даже знаю чем в корне отличаются StringBuffer и StringBuilder)))
P.S. Бред

[Circiter]

2InterceptorTSK
Хотя с вами и сложно разговаривать, но я все-таки попробую задать такой наводящий вопрос... Надо полагать, вы предлагаете некую стратегию, не так ли? Судя по всему, вы её себе представляете достаточно четко, так? Другими словами, вы можете формально описать эту стратегию? Да? В таком случае, что мешает вам оформить это формальное описание в виде алгоритма, который будет автоматически оптимизировать программы?

Вот существующие оптимизаторы так и делают!

Другое дело, что JIT-компиляторы не должны заниматься сложной оптимизацией, за них это должен делать первичный транслятор. Здесь я с вами согласен...

[InterceptorTSK]

Стратегии нет. До стратегии далеко.
Судя по чему я что и как представляю?
Формально описать можно все. Другое дело, что 99.9% процентов формальных описаний даже близко не подходят к тому, чтобы работать наиболее быстро. По типу - работает, и ладно.
Стратегия есть, но она, по существу, не касается программирования.
Когда приходит очередной "Алеша" с флешкой и собирается по новой рассчитать очередной ядерный взрыв, ну или чего они там рассчитывают - мне крайне по-барабану, и 50 машин пухнут дней десять, только потому, что другие "Алеши" не в состоянии, например, по-человечески соптимизировать нахождение модуля числа, то становится сначала смешно, а потом грустно. Рано или поздно это надоедает. Вот и приходится извращаться.
Пока ситуация банальна. Есть несколько файликов и парсер. В файлах, например, есть строчки по типу такой:
Ret.Int32 /2 >>1
Парсер цепляет cs или java файлы и тупо их переписывает. Вот собственно и все.
Кстати модуль числа для 32bit находится как ((a >> 31) ^ ((a >> 31) + a)). Продвинутый буржуин писал, что можно обойтись вообще без сумматора, но в это слабо верится, но кто его знает)) Работает где как. Обгоняет стандартный Math.Abs(Int32) приблизительно в 1.7 - 2.5 раза. На трубах рвет стандартный подход в тряпочки.

[meduza]

Я родительсую тему не читал, и эту тоже мельком. Так что извините, если повторюсь или скажу не в тему. Но насчёт "битовой оптимизации" хочу высказать своё ИМХО: она не нужна в 95% случаев. Я сам начинал с ассемблера и после переходя Си и Я.В.У. поначалу тоже злоупотреблял чрезмерной оптимизацией на уровне сдвигов и логических операций, и определение знака произведения через sgn(x)*sgn(y)*sgn(z) казалось кощунством. Но всё прошло. И дошло, что 90% времени занимает выполнения 10% кода. И весь эффект от этой оптимизации сводится на нет. Какой смысл уродовать код всякими ((a >> 31) ^ ((a >> 31) + a)), когда по соседству происходит сортировка пузырьком?

Компьютеры становяться быстрее, компиляторы умнее, изобретаются более совершенные алгоритмы, а люди остаются такими же. Короче:
1) надо писать очевидный, читабельный код, чтобы с первого взгляда стороннему программисту стало ясно, что он делает; (пусть даже и в форме типа sgn(x)*sgn(y)*sgn(z))
2) оптимизировать всегда следует алгоритм, а не его реализацию.

[InterceptorTSK]

Соптимизировать реализацию иногда проще, чем соптимизировать алгоритм, только потому что оптимизация алгоритма почти всегда - нетривиальная задача. Поиск математической оптимизации алгоритма в 95% случаев приводит к увеличению времени выполнения.
Перекапывать чью-то абсолютно читабельную математику в виде sgn(x)*sgn(y)*sgn(z) и искать, на основе этого более быструю математику в java-файле - увольте.
Про ненужность битовых оптимизаций в 95% согласен полностью.
При разумном подходе читабельный код остается в оригинальном виде. Никто его не корежит, и даже не собирается этого делать.
Повторяюсь также:
Нельзя полагаться целиком и полностью на "ум" (читай - по сути - пачку ветвлений) компилятора, заточенных под определенные "действия". Крайне нельзя полагаться на среду исполнения. Она везде разная, и оптимизирует совершенно по-разному (а кое где не оптимизирует вообще).
P.S. Причем здесь модуль числа и сортировка пузырьком?)

[Circiter]

2InterceptorTSK

Цитата:

Причем здесь модуль числа и сортировка пузырьком?)

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