Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 246
>> если нужно быстродействие, то писать нужно на С
Ах вот оно что. У меня тут тырпрайзное приложение на C# и WPF слегка тормозит, теперь понятно — надо на Си переписывать.
Ах вот оно что. У меня тут тырпрайзное приложение на C# и WPF слегка тормозит, теперь понятно — надо на Си переписывать.
Ну если у вас тормозит UI — замените WPF на что нибудь более низкоуровневое. К слову когда мне нужно быстродействие в части UI — я просто отказываюсь от Binding/Converters/DataTemplates и делаю всё по канонам MVP. Всё ускоряется, хотя условная красота теряется
А если тормозят вычисления (что странно для такого рода приложений) — ну да, создайте DLL написанную на C, вызывайте её через PInvoke, а там примените любые самые мощные оптимизации.
То что вы написали приложение не понимая последствий выбора инструмента — это исключительно ваша ошибка. Ничего смешного тут нет, и ваш сарказм лучше направить в свою сторону.
А если тормозят вычисления (что странно для такого рода приложений) — ну да, создайте DLL написанную на C, вызывайте её через PInvoke, а там примените любые самые мощные оптимизации.
То что вы написали приложение не понимая последствий выбора инструмента — это исключительно ваша ошибка. Ничего смешного тут нет, и ваш сарказм лучше направить в свою сторону.
Что-то хабр превращается в странное место. Ваша ирония не настолько уж и тонка, ан (я ах охренел) сколько минусов.
Пока люди не понюхают разных фруктов, не поучаствуют в проекте, в котором нужно показать OLAP-отчет из трех разных СУБД, расположенных в разных местах на разных каналах — они не поймут, что бывают окружения, в котором хоть на коболе пиши — влияние на быстродействие языка программирования останется чуть меньше нуля.
Мантра «ассеблер быстрее си, си быстрее перла, перл быстрее пейтона» — очень вредна, на самом деле, как любая другая глупость. Ассемблер уже далеко не всегда быстрее си, а пейтон почти никогда не медленнее перла.
Зачем я эти очевидные вещи написал? Ну, я не люблю, когда разумные комментарии (а ваш именно таков) школота активно минусует по принципу «я не понял, но минус поставлю».
Пока люди не понюхают разных фруктов, не поучаствуют в проекте, в котором нужно показать OLAP-отчет из трех разных СУБД, расположенных в разных местах на разных каналах — они не поймут, что бывают окружения, в котором хоть на коболе пиши — влияние на быстродействие языка программирования останется чуть меньше нуля.
Мантра «ассеблер быстрее си, си быстрее перла, перл быстрее пейтона» — очень вредна, на самом деле, как любая другая глупость. Ассемблер уже далеко не всегда быстрее си, а пейтон почти никогда не медленнее перла.
Зачем я эти очевидные вещи написал? Ну, я не люблю, когда разумные комментарии (а ваш именно таков) школота активно минусует по принципу «я не понял, но минус поставлю».
Поясните, пожалуйста, а когда ассемблер медленнее си, если отбросить случаи, когда на ассемблере пишет неуч? Или имелся ввиду всего лишь оптимизирующий компилятор?
К примеру вы можете написать обычный цикл на ассемблере, он скомпилируется как есть: метка → логика → условие → прыжок и вот этот самый прыжок, довольно дорогая операция. На С вы можете написать такой же цикл, но с некоторыми настройками оптимизации, компилятор развернет этот цикл так, что все значения для условия просчитаются на этапе компиляции и перехода как такового просто не будет. Для процессора быстрее идти и выполнять инструкции линейно, а не прыгать по памяти.
Имелось в виду, что разница в производительности между ассемблером и скомпилированным си в настоящее время никогда не бывает узким местом для 99% процентов задач (даже реального времени). Остальной 1% — это хитровывернутая архитектура процессора и/или узкоспециальные алгоритмы, оптимизация которых до сих пор неизвестна компилятору.
Зато используя ассемблер вместо си, есть почти стопроцентный шанс отстрелить самому себе ногу. Для этого не нужно быть неучем. Мне лично не знаком ни один программист, знающий наизусть весь список и способный применить любой алгоритм из перечисленных, причем именно там, где он необходим.
Зато используя ассемблер вместо си, есть почти стопроцентный шанс отстрелить самому себе ногу. Для этого не нужно быть неучем. Мне лично не знаком ни один программист, знающий наизусть весь список и способный применить любой алгоритм из перечисленных, причем именно там, где он необходим.
Эм… Просто, для примера, задача перекодирования числа в строку.
На ассемблере получается на одну операцию деления меньше, чем делает компилятор.
б) задача, типа (short)A=(char)B<<8+(char)C на ассемблере вообще не требует операций сдвига и сложения, а просто три операции mov
А шанс отстрелить себе ногу есть на чем угодно. К примеру, клиент Wurm-online написан на Яве и тормозит даже на моей машине, показывая картинку ХУЖЕ скайрима, который у меня летает. Это, извините меня, даже не отстреленная нога, это прямой хэдшот.
На ассемблере получается на одну операцию деления меньше, чем делает компилятор.
б) задача, типа (short)A=(char)B<<8+(char)C на ассемблере вообще не требует операций сдвига и сложения, а просто три операции mov
А шанс отстрелить себе ногу есть на чем угодно. К примеру, клиент Wurm-online написан на Яве и тормозит даже на моей машине, показывая картинку ХУЖЕ скайрима, который у меня летает. Это, извините меня, даже не отстреленная нога, это прямой хэдшот.
На ассемблере получается на одну операцию деления меньше, чем делает компилятор.
Листинги на ассемблере — ручной и компиляторый (с указанием версии компилятора и опций командной строки) в студию — иначе это набор слов.
б) Теперь можно не только вам сказать «эм...». Я полагаю, что 1%, заботливо выделенный matiouchkine, покрывает такие вот «распространенные» задачи как ствол тысячелетней секвойи спичку (и о да — вы попробуйте докажите, что вам удастся разложить переменные по регистрам так же хорошо, как это сделает компилятор. А то компилятор радостно подвигает и поскладывает на регистрах, а вы свои mov будете из памяти делать)
На самом деле, упаковка байтов в короткие или длинные числа для более эффективной записи в массив или для передачи — вполне нормальный приём при обработке данных. Конечно, вся обработка сырых данных в мире по-прежнему попадает в 1% (по коду), но этот процент довольно важный.
Я попробовал взять код заполнения байтового массива псевдослучайными числами
и откомпилировать его вручную
(чтобы рассмотреть случай нечетной длины пришлось бы добавить еще 5-6 строчек, но на скорость они не влияют).
Выигрыш моего кода по сравнению с С-компилятором (MSVC 10, Full optimization) составил 2.7 раза (на AMD, 32-битная модель), при том, что я даже не пытался оптимизировать код. Что я делаю не так?
Я попробовал взять код заполнения байтового массива псевдослучайными числами
typedef unsigned char byte;
void Fill1(byte *arr,int l){
byte c=1;
for(int i=0;i<l;i++){
c=(byte)(5*c+1);
*arr++=c;
}
}
и откомпилировать его вручную
_Fill4 PROC
; extern "C" void Fill4(byte *arr,int len);
push ebp
mov ebp, esp
push edi
mov edi,[ebp+8]
mov dl,1
mov ecx,[ebp+12]
dec ecx
shr ecx,1
inc ecx
jz $a1
$a2:
lea edx,[edx+4*edx+1]
mov al,dl
lea edx,[edx+4*edx+1]
mov ah,dl
stosw
loop $a2
$a1:
pop edi
pop ebp
ret
_Fill4 ENDP
(чтобы рассмотреть случай нечетной длины пришлось бы добавить еще 5-6 строчек, но на скорость они не влияют).
Выигрыш моего кода по сравнению с С-компилятором (MSVC 10, Full optimization) составил 2.7 раза (на AMD, 32-битная модель), при том, что я даже не пытался оптимизировать код. Что я делаю не так?
Машинный листинг, если интересно:
Да, в моём коде вместо jz следовало бы поставить jle, но я же не буду вызывать его с отрицательной длиной, правда?
?Fill1@@YAXPAEH@Z PROC ; Fill1, COMDAT
push ebp
mov ebp, esp
push esi
mov esi, DWORD PTR _l$[ebp]
mov al, 1
test esi, esi
jle SHORT $LN1@Fill1
mov ecx, DWORD PTR _arr$[ebp]
$LL3@Fill1:
mov dl, al
add dl, dl
add dl, dl
add al, dl
inc al
mov BYTE PTR [ecx], al
inc ecx
dec esi
jne SHORT $LL3@Fill1
$LN1@Fill1:
pop esi
pop ebp
ret 0
?Fill1@@YAXPAEH@Z ENDP
Да, в моём коде вместо jz следовало бы поставить jle, но я же не буду вызывать его с отрицательной длиной, правда?
Мои результаты: асм — 2078, С++ — 2687 (http://pastebin.com/DN1QD1JR). Это хрень, а не выигрыш.
Очень странно, что с полной оптимизацией функция не заинлайнена. Скорее всего или включена отладочная информация, или еще что-то, от чего разница в 2.7 раза, которой у меня нет.
Что делаете не так. Инлайнгинг — первая проблема. Я не говорю о том, что аналог STL, в котором все предикаты и аллокаторы инлайнились бы, на асме не напишешь, его и на С не напишешь. Но даже если сравнивать с С, множество мелких функций компилер заинлайнит, а человек утонет в макросах. А отсутствие лишних прыжков — это хорошо.
Вторая вещь — код слишком простой. Как только нужно будет распределять по регистрам число переменных, большее, чем размер кратковременной памяти (т.е. 7), будет хуже. Как только потребуется знание работы конвеера, чтобы тасовать команды, будет еще хуже. Как только нужно будет получить 200х прирост переносом на GPU — все, код можно выбрасывать совсем. Знать как работает процессор нужно, но для этого заниматься вещами типа этого, а не этой хренью.
У меня на работе асмодельцы заправляют, очень выгодно оправдывать безумные сроки разработки тем, что компилятор хреново компилирует и следует писать прошивки на асме.
Очень странно, что с полной оптимизацией функция не заинлайнена. Скорее всего или включена отладочная информация, или еще что-то, от чего разница в 2.7 раза, которой у меня нет.
Что делаете не так. Инлайнгинг — первая проблема. Я не говорю о том, что аналог STL, в котором все предикаты и аллокаторы инлайнились бы, на асме не напишешь, его и на С не напишешь. Но даже если сравнивать с С, множество мелких функций компилер заинлайнит, а человек утонет в макросах. А отсутствие лишних прыжков — это хорошо.
Вторая вещь — код слишком простой. Как только нужно будет распределять по регистрам число переменных, большее, чем размер кратковременной памяти (т.е. 7), будет хуже. Как только потребуется знание работы конвеера, чтобы тасовать команды, будет еще хуже. Как только нужно будет получить 200х прирост переносом на GPU — все, код можно выбрасывать совсем. Знать как работает процессор нужно, но для этого заниматься вещами типа этого, а не этой хренью.
У меня на работе асмодельцы заправляют, очень выгодно оправдывать безумные сроки разработки тем, что компилятор хреново компилирует и следует писать прошивки на асме.
То, что функция не заинлайнена, не удивительно. Тестирующий вызов выглядел вот так:
и функция передавалась в него в качестве аргумента.
То, что код простой — да, это ограничение. На то, какие функции имеет смысл переписывать, а какие нет. То, что при переходе на другой процессор код придется выбрасывать — несомненно, а кроме того, для переписывания этого кода на другой процессор придется изучить тот процессор очень детально, лучше, чем его знает компилятор. К счастью, эквивалентный сишный код никуда не денется.
То, что так нельзя писать код, использующий классы и структуры — тоже понятно: стоит пошевелить описание, сменить компилятор и т.п. — и адреса полей поедут. Не предназначен этот код для развития, он в некотором смысле одноразовый. Конечно, константы, макросы, и т.п. могут спасти положение (и спасают), но это уже другой уровень разработки.
А 25% выигрыша — не так и мало. Если конкуренты обрабатывают (условно) 10 снимков в секунду, а мы за счет алгоритма можем получить 13, или за счет более слабого процессора увеличить срок работы на батарейке — кому от этого плохо?
void Test(void (*f)(byte *,int)){
for(int i=0;i<40;i+=4) f(A+i,N);
}
и функция передавалась в него в качестве аргумента.
То, что код простой — да, это ограничение. На то, какие функции имеет смысл переписывать, а какие нет. То, что при переходе на другой процессор код придется выбрасывать — несомненно, а кроме того, для переписывания этого кода на другой процессор придется изучить тот процессор очень детально, лучше, чем его знает компилятор. К счастью, эквивалентный сишный код никуда не денется.
То, что так нельзя писать код, использующий классы и структуры — тоже понятно: стоит пошевелить описание, сменить компилятор и т.п. — и адреса полей поедут. Не предназначен этот код для развития, он в некотором смысле одноразовый. Конечно, константы, макросы, и т.п. могут спасти положение (и спасают), но это уже другой уровень разработки.
А 25% выигрыша — не так и мало. Если конкуренты обрабатывают (условно) 10 снимков в секунду, а мы за счет алгоритма можем получить 13, или за счет более слабого процессора увеличить срок работы на батарейке — кому от этого плохо?
Числодробление нельзя не инлайнить. Кому нужен оверхед на кэш-промахи и все эти push epb/mov ebp esp?
25% выигрыша на мелкой функции — хрень. Не бывает бутылочного горлышка такого размера, выполняющегося 100% времени. 30% времени — это 10% прироста. Чтобы получить 25%, придется переписывать намного больше: 20% кода, который выполняется 80% времени. Причем код на асме раздуется как раз раз в 5, и будет 50% кода на С++, 50% на асме. Поддерживать будет замечательно.
И это при условии, что эти 25% будут. Я в этом не уверен. Write-only — понадобился вместо byte short — труба. Инлайнить тяжело. В больших системах большей частью выигрыш идет от кэширования — хэш-таблица на асме? Вообще «я знаю асм лучше компилятора, поэтому я быстрее» — миф. Компилятор не много знает, но он намного быстрее думает и решает. Специально для компиляторов, а не человека, по планете шагает RISC система команд.
В общем, от этого будет плохо и специалисту (не желает меняться в изменившейся обстановке с момента появления RISC), и заказчику (платить за время разработки), и пользователю.
Нормальное решение здесь — увидеть, что по сути предложенный алгоритм является prefix_sum и реализовать (нагуглить) этот отдельный prefix_sum на SSE и, допустим, OpenMP. Или вообще на GPU. В этом случае переносимость будет ограничена сменой либы — будь то TBB, thrust или что-то еще, а за качество низкоуровневого кода будет отвечать сообщество или Intel. В случае чего всегда можно откатиться на std::partial_sum, а можно и написать расчет на кластере. Параллельные примитивы и относительная высокоуровневость С++ дают скорость, а машинным кодам места в бэкендах, и если бэкенды неоптимальные, то лучше помочь миру патчем, а не создавать ad-hoc решения на асме.
25% выигрыша на мелкой функции — хрень. Не бывает бутылочного горлышка такого размера, выполняющегося 100% времени. 30% времени — это 10% прироста. Чтобы получить 25%, придется переписывать намного больше: 20% кода, который выполняется 80% времени. Причем код на асме раздуется как раз раз в 5, и будет 50% кода на С++, 50% на асме. Поддерживать будет замечательно.
И это при условии, что эти 25% будут. Я в этом не уверен. Write-only — понадобился вместо byte short — труба. Инлайнить тяжело. В больших системах большей частью выигрыш идет от кэширования — хэш-таблица на асме? Вообще «я знаю асм лучше компилятора, поэтому я быстрее» — миф. Компилятор не много знает, но он намного быстрее думает и решает. Специально для компиляторов, а не человека, по планете шагает RISC система команд.
В общем, от этого будет плохо и специалисту (не желает меняться в изменившейся обстановке с момента появления RISC), и заказчику (платить за время разработки), и пользователю.
Нормальное решение здесь — увидеть, что по сути предложенный алгоритм является prefix_sum и реализовать (нагуглить) этот отдельный prefix_sum на SSE и, допустим, OpenMP. Или вообще на GPU. В этом случае переносимость будет ограничена сменой либы — будь то TBB, thrust или что-то еще, а за качество низкоуровневого кода будет отвечать сообщество или Intel. В случае чего всегда можно откатиться на std::partial_sum, а можно и написать расчет на кластере. Параллельные примитивы и относительная высокоуровневость С++ дают скорость, а машинным кодам места в бэкендах, и если бэкенды неоптимальные, то лучше помочь миру патчем, а не создавать ad-hoc решения на асме.
Разные бывают горлышки. Одна из моих программ, насколько я помню, 25% времени проводила в цикле длиной 64 байта, выполнявшемся 2 такта. Пришлось хорошо повозиться, чтобы заставить компилятор её так упаковать.
А RISC… ну и что, что RISC. Вот на полке лежит плата с C6455, ждёт свободной минутки. Уж там ассемблер так ассемблер, красивее я со времен PDP11 не видел :)
Но в целом, я согласен. Без необходимости в asm ходить не надо, особенно если это не какие-нибудь прошивки.
Правда, сегодня начальник сказал, что бортовую машину будут брать с процессором не 1.6, а 1.1 ГГц. Так что от меня ждут полуторакратного ускорения кода. На C#. Поразвлекаемся! :-D
А RISC… ну и что, что RISC. Вот на полке лежит плата с C6455, ждёт свободной минутки. Уж там ассемблер так ассемблер, красивее я со времен PDP11 не видел :)
Но в целом, я согласен. Без необходимости в asm ходить не надо, особенно если это не какие-нибудь прошивки.
Правда, сегодня начальник сказал, что бортовую машину будут брать с процессором не 1.6, а 1.1 ГГц. Так что от меня ждут полуторакратного ускорения кода. На C#. Поразвлекаемся! :-D
GCC (4.6.3), кстати, догадался вычислять следующий c с помощью lea, и ему это удается при самом слабом уровне оптимизации (g++ -O1 test.cpp -S -m32 -masm=intel). Каков вклад в обнаруженный прирост производительности принадлежит именно lea — не проверял.
VC написал lea только когда я объявил int c; Почему-то int он умножать на 5 умеет, а unsigned char нет…
Замена сложений на lea дает примерно двукратный выигрыш по скорости.
P.S. Кстати, в сортировке 96-битных чисел мне в итоге удалось обогнать стандартный Sort примерно в 6 раз (оставаясь на C#). Использовал поразрядную сортировку по основанию 256. Эффективная оказалась штука, раньше я её как-то игнорировал.
Замена сложений на lea дает примерно двукратный выигрыш по скорости.
P.S. Кстати, в сортировке 96-битных чисел мне в итоге удалось обогнать стандартный Sort примерно в 6 раз (оставаясь на C#). Использовал поразрядную сортировку по основанию 256. Эффективная оказалась штука, раньше я её как-то игнорировал.
В задаче (б)… вы скобки не забыли? Приоритет у << ниже, чем у +, и компилятор предупреждает о возможной ошибке. И даже если написать a=((char)b<<8)+(char)c; то очень интересно, как вы обойдётесь без сложения…
Забыл. В полпервого ночи не мудрено.
мой код на ассме:{
mov ah,b
mov al,c
mov a,ax
}
Код исходного примера, откомпилированного студией, параметры оптимизации: Ot, Ox:
дизассемблер IDA pro 6.1
{
ldarg.0
ldc.i4 0x100
mul
ldarg.1
add
conv.i2
}
мой код на ассме:{
mov ah,b
mov al,c
mov a,ax
}
Код исходного примера, откомпилированного студией, параметры оптимизации: Ot, Ox:
дизассемблер IDA pro 6.1
{
ldarg.0
ldc.i4 0x100
mul
ldarg.1
add
conv.i2
}
Про ваши примеры тут до меня уже умные люди высказались.
Насчет выстрелов в ногу. У вас какие-то проблемы с логикой. Я утверждал, что в конкретном случае «использования ассемблера вместо си просто ради абстрактного тезиса „ассемблер быстрее“» шанс облажаться почти стопроцентный. Вы сообщаете, что облажаться можно и в других случаях. Ну можно, и к чему это тут? Это как-то опровергает мой тезис, на ваш взгляд?
Насчет выстрелов в ногу. У вас какие-то проблемы с логикой. Я утверждал, что в конкретном случае «использования ассемблера вместо си просто ради абстрактного тезиса „ассемблер быстрее“» шанс облажаться почти стопроцентный. Вы сообщаете, что облажаться можно и в других случаях. Ну можно, и к чему это тут? Это как-то опровергает мой тезис, на ваш взгляд?
У неуча шанс облажаться везде стопроцентный.
Вопрос в том, как трудно отловить ошибку и что нужно оптимизировать.
Вы утверждаете, что оптимизировать ничего не надо, ибо наверняка облажаешься.
Это не так. Компилятор делает УНИВЕРСАЛЬНЫЙ код, а не специализированный.
Вопрос в том, как трудно отловить ошибку и что нужно оптимизировать.
Вы утверждаете, что оптимизировать ничего не надо, ибо наверняка облажаешься.
Это не так. Компилятор делает УНИВЕРСАЛЬНЫЙ код, а не специализированный.
Компилятор делает УНИВЕРСАЛЬНЫЙ код, а не специализированный.
Вы готовы доказать это утверждение для всех компиляторов?
Нет, только про студию и gcc. Есть и специализированные компиляторы.
В любом случае, у того, кто компилирует свою программу вручную, дополнительной информации о данных, которые будут поданы на вход, гораздо больше: здесь число неотрицательное, этот цикл выполнится на менее 4 раз, а здесь число выполнений должно делиться на 8, но может быть нулём… длина этого списка не менее 1… в массиве наверняка есть положительное число, а длина строки не превышает 65535… ну и так далее. Некоторым компиляторам часть этих фактов объяснить можно, и они могут ими даже воспользоваться. Но кое-что наверняка останется за бортом и заставит компилятор делать бессмысленную работу.
Хотя верно и обратное. При глобальной оптимизации компилятор соберет больше инфорамции про контекст, в котором функция вызывается именно в этой программе. И некоторые факты, которые человек учитывать не захочет (что такой-то параметр всегда равен 3 — человек знает, что он скоро исправит его в части вызовов на 13), компилятор заметит и использует для оптимизации «здесь и сейчас».
Хотя верно и обратное. При глобальной оптимизации компилятор соберет больше инфорамции про контекст, в котором функция вызывается именно в этой программе. И некоторые факты, которые человек учитывать не захочет (что такой-то параметр всегда равен 3 — человек знает, что он скоро исправит его в части вызовов на 13), компилятор заметит и использует для оптимизации «здесь и сейчас».
Вы утверждаете, что оптимизировать ничего не надо, ибо наверняка облажаешься.
Я нигде подобной ереси не утверждал. Вам бы чуть подучиться простейшие силлогизмы понимать, а то в ассемблере нынче все крутые.
Имелось в виду, что разница в производительности между ассемблером и скомпилированным си в настоящее время никогда не бывает узким местом для 99% процентов задач. Остальной 1% — это хитровывернутая архитектура процессора и/или узкоспециальные алгоритмы, оптимизация которых до сих пор неизвестна компилятору.
Зато используя ассемблер вместо си, есть почти стопроцентный шанс отстрелить самому себе ногу
_______________________
Читается как:
«в 99% случаев компилятор сделает все сам, а пытаясь использовать асм, вы гарантированно отстрелите себе ногу» => ассемблерные оптимизации лучше не использовать.
Зато используя ассемблер вместо си, есть почти стопроцентный шанс отстрелить самому себе ногу
_______________________
Читается как:
«в 99% случаев компилятор сделает все сам, а пытаясь использовать асм, вы гарантированно отстрелите себе ногу» => ассемблерные оптимизации лучше не использовать.
Я-то наивно полагал, что это читается как «в настоящее время в 99% случаев ассемблерные оптимизации использовать не нужно».
У вас есть примеры на оставшийся один процент, правда, подозреваю, что они чисто академические. Мне приходилось извращаться с ассемблерными вставками ради того, чтобы уместиться в 512КБ. Потом — ради того, чтобы обеспечить поиск по n-арному дереву. Сейчас я не могу придумать не академическую, не супер-узко-специализированную задачу, в которой оптимизация c⇒asm даст хоть какой-то прирост производительности.
На всякий поясню, я не отрицаю возможность добиться прироста, при наличии должной усидчивости. Но рядом всегда окажется что-нибудь наподобие выборки из базы по медленному каналу. И ваши три микросекунды, кроме морального удовлетворения, не дадут ни-че-го.
У вас есть примеры на оставшийся один процент, правда, подозреваю, что они чисто академические. Мне приходилось извращаться с ассемблерными вставками ради того, чтобы уместиться в 512КБ. Потом — ради того, чтобы обеспечить поиск по n-арному дереву. Сейчас я не могу придумать не академическую, не супер-узко-специализированную задачу, в которой оптимизация c⇒asm даст хоть какой-то прирост производительности.
На всякий поясню, я не отрицаю возможность добиться прироста, при наличии должной усидчивости. Но рядом всегда окажется что-нибудь наподобие выборки из базы по медленному каналу. И ваши три микросекунды, кроме морального удовлетворения, не дадут ни-че-го.
Когда вы пишете «в 99% случаев», то что имеется в виду?
99% всех программ (которые могут быть очень разной длины)? Файлов/классов? Функций? Или программистов?
И что понимается под супер-узко-специализированной задачей? Та, у которой будет полтора пользователя? Или такая, которую может написать только супер-узкий специалист? Мне кажется, что все задачи являются достаточно специализированными, даже если они являются частью программ для всеобщего пользования. Иначе эти задачи незачем было бы писать, где-нибудь нашлась бы другая программа, делающая то, что нужно.
99% всех программ (которые могут быть очень разной длины)? Файлов/классов? Функций? Или программистов?
И что понимается под супер-узко-специализированной задачей? Та, у которой будет полтора пользователя? Или такая, которую может написать только супер-узкий специалист? Мне кажется, что все задачи являются достаточно специализированными, даже если они являются частью программ для всеобщего пользования. Иначе эти задачи незачем было бы писать, где-нибудь нашлась бы другая программа, делающая то, что нужно.
Спасибо, я лично не переживаю, -24 говорит о том, что на хабре как миниум n-24 адекватных людей :-). С людьми, у которых в голове эта самая мантра «Си быстрее» без конкретного контекста, диалога обычно не получается.
Подозреваю, что минусы в основном за необоснованную, агрессивную язвительность. Комментарий от niosus не содержал ничего такого, что могло бы вызвать такую реакцию.
Не смешите, когда это на хабре минусовали за агрессивную язвительность?
Фраза:
являет собой идеальный пример бессмысленной абстрактной глупости. Как на нее реагировать? Ну, можно никак. Можно так, как Nagg. Причем последнее, очевидно лучше: людям с не до конца атрофированным мозгом он может помочь сделать первый шаг в постижении следующего уровня компьютерных знаний.
Или вы считаете, что имело смысл расписать очевидное (про ынтырпрайз) на пять страниц с примерами?
Фраза:
если нужно быстродействие, то писать нужно на С
являет собой идеальный пример бессмысленной абстрактной глупости. Как на нее реагировать? Ну, можно никак. Можно так, как Nagg. Причем последнее, очевидно лучше: людям с не до конца атрофированным мозгом он может помочь сделать первый шаг в постижении следующего уровня компьютерных знаний.
Или вы считаете, что имело смысл расписать очевидное (про ынтырпрайз) на пять страниц с примерами?
Если Вы не заметили, статья о скриптовом языке. Если скриптовый язык медленный и нет архитектурных проблем, то вполне логично медленные части писать на низкоуровневом языке. Вот о чём был первый комментарий. К чему Nagg ляпнул про C# — совершенно неясно, поскольку этот язык занимает совершенно другую нишу и используется при решении совершенно других задач.
Статья, на самом деле, о применимости оптимизаций на каждом конкретном уровне, а не только о скриптовых языках.
Если скриптовый язык медленный и нет архитектурных проблем, то вполне логично медленные части писать на низкоуровневом языке.
Даже если забыть, что в статье никто не делал акцент на скриптовых языках, спешу сообщить: время «медленных скриптовых языков» осталось в далеком прошлом. Переписывая бизнес-логику современного приложения на си, программист квалификации ниже Гослинга принесет туда столько проблем, что будет только хуже. Кроме того, потестируйте современные «медленные скриптовые языки», будете приятно удивлены.
Нужно видюху получше, ведь WPF живет на Direct X
:-)
:-)
Была у меня проблема одна: есть файл от exel в котором лежат данные, которые мне нужно преобразовать — в совершенно другой формат(несколько совсем других файлов). Сначала был написан простой макрос на VB — он работал, но я был не доволен, т.к. людям нужно было сказать выполнить макрос и они так и делали да и сам макрос работал несколько секунд. Прошло время, а я почитал про новшества в с++ 11 и решил ради любознательности что-то полезное на нем написать, так и сделал. Маленькая консольная программа, открывает файл распаковывает, тот-же алгоритм что был в VB и записывает новые файлы. Причем программа получилась полностью переносимой, а когда я ее запустил, то она сразу вернула консоль, сначала я решил, что, что-то не работает, но ни одного сообщения об ошибке, проверил — да все работает и работает мгновенно! Пользователи довольны — можно даже не открывать exel, скорость — мгновенная, работает везде, где есть современный компилятор. Вот про что была эта статья.
Автор так и говорит — «если нужно быстродействие, то писать нужно на С, но для начала убедитесь, нужно ли».
Я видел немало систем, которые как разрабатывались на Матлабе, так и в продакшне остались на Матлабе: если какие-то отдельные блоки тормозили, эти блоки переписывались на Си и вызывались из DLL.
Воссоздание готовой системы на С++ и последующая отладка — нешуточная трата времени, и не всегда выгода от такого перфекционизма перевешивает затраты.
Я видел немало систем, которые как разрабатывались на Матлабе, так и в продакшне остались на Матлабе: если какие-то отдельные блоки тормозили, эти блоки переписывались на Си и вызывались из DLL.
Воссоздание готовой системы на С++ и последующая отладка — нешуточная трата времени, и не всегда выгода от такого перфекционизма перевешивает затраты.
Это всё очень хорошо, только:
1. это лень. да, тут нечего скрывать, лишнюю и более тяжёлую работу никто не любит. но это — лень. мастер своего дела такого не допустит. не надо переписывать на ассемблере ненужные куски, да и вообще ассемблер остаётся уделом супер профессионалов — иначе просто не сделать лучше чем компилятор, но допускать траты ресурсов впустую — это лень. никакая мотивация этого не покрывает.
2. даже оптимизируя самые узкие места, практически никогда это дело не доводят до конца — ибо лень. говорят сами себе — это и так нормально. немного соптимизировал и хорошо. на самом деле там конь не валялся и всё тормозит как 10 лет назад. хотя компьютеры стали быстрее в 10-12 раз.
1. это лень. да, тут нечего скрывать, лишнюю и более тяжёлую работу никто не любит. но это — лень. мастер своего дела такого не допустит. не надо переписывать на ассемблере ненужные куски, да и вообще ассемблер остаётся уделом супер профессионалов — иначе просто не сделать лучше чем компилятор, но допускать траты ресурсов впустую — это лень. никакая мотивация этого не покрывает.
2. даже оптимизируя самые узкие места, практически никогда это дело не доводят до конца — ибо лень. говорят сами себе — это и так нормально. немного соптимизировал и хорошо. на самом деле там конь не валялся и всё тормозит как 10 лет назад. хотя компьютеры стали быстрее в 10-12 раз.
Я как раз недавно вспоминал Закон Вирта (Wirth's Law)
Лень двигатель прогресса… В конце концов компьютеры появились благодаря тому, что кому то устало считать на счётах…
Ну а оптимизация доведенная до конца это что? Это невозможно довести до конца. Часто в таких случаях говорят — «нет предела совершенству...»
А лень это часто благо… Именно чужая лень даёт работу нам, программистам… )
Ну а оптимизация доведенная до конца это что? Это невозможно довести до конца. Часто в таких случаях говорят — «нет предела совершенству...»
А лень это часто благо… Именно чужая лень даёт работу нам, программистам… )
Вопрос не в оптимизации до конца. А вообще ставить вопросы оптимизировать или нет не надо. Надо просто делать работу хорошо и код писать оптимально. А не навалаю-ка сейчас по быстрому, потом как-нибудь разберусь. Вот этого потом как-нибудь обычно не случается.
Напомнить, что говорил Кнут про «преждевременную оптимизацию»?
Что оптимизация никогда не бывает преждевременной, поскольку преждевременная оптимизация — это зло, а со злом мы боремся?
Я не говорю, чтобы сразу писать идеал. Но приводить в порядок надо весь код — вот и всё. Так делают мастера своего дела. Остальные могут поступать как хотят. Программист потратит лишний час, а потом пользователи сэкономят дни, компании: киловатты, пластик, магистральные каналы для видео с котиками, co2, деньги в конце концов.
Интересно, что он имеет в виду под «of the time»: время на оптимизацию 3% кода может быть больше, чем на написание остальных 97%. Так что если 3% — это время программиста, которое можно выделить на оптимизацию, дела становятся еще интереснее.
Спасибо, но это не прояснило дела. «Мы должны забыть про микрооптимизации на скажем 97% времени» — означает ли это, что нам можно вспоминать о них только 15 минут в день? Или, например, отводить на микрооптимизацию только последний рабочий день месяца? Или, всё-таки, имеется в виду 3% строчек кода/функций/программ?
Счётные машины появились потому, что считать на счётах всё возрастающее население при переписи становилось всё дольше. А население и экономика всё больше росли. Потому статистические данные всё больше запаздывали. Так что дело не в лени, просто нужно было быстрее считать. А увеличение кол-ва ядер (человеков) уткнулось в те же проблемы, что у любых многоядерных систем.
Думаю, что тут дело не только в лени. Есть еще экономические факторы. Любая компания хочет вложив поменьше, вытащить побольше. Чтобы переписывать все на С++, нужно финансовые затраты. И это часто является решающим фактором.
Согласен с вами. Для прототипа лучше всего подходят языки с динамической типизацией. Они позволяют сконцентрироваться на самой задаче, не отвлекаясь на оптимизации и слежение за типами. Более того, если программа не оперирует огромным количеством данных и не занимается сложными расчётами (хотя тут можно поспорить — например, для питона есть сишные библиотеки для мат-расчётов), то можно программу и не переписывать в дальнейшем.
Зачем делать рефакторинг в прототипе?
Рефакторить его по определению не надо, тем не менее.
Рефакторинг — это изменение кода без изменения функциональности. Зачем что-то менять в прототипе, если это не добавляет функциональность? Это бессмысленная трата ресурсов.
Потому что это позволит добавить еще недостающую функциональность с меньшими затратами.
Далеко не факт. Копипаст обычно быстрее рефакторинга.
Кроме функциональности прототип позволяет промоделировать структуру и взаимосвязи в системе.
Это называется «вертикальный прототип» и смешивать его с горизонтальным не надо.
Копипаст — это болото, в которое опасно далеко заходить.
В прототипе-то? И чем же оно опасно?
А где речь только о горизонтальном?
Нигде. Просто вертикальный тоже пишется один раз, проверяется работоспособность, потом уже пишется нормально — рефакторить тоже негде.
Полностью согласен с вашими замечаниями про рефакторинг в прототипе. Не раз уже замечал, что до того наэкспериментируешься, такого кода нагородишь в прототипе, что дальше экспериментировать просто невозможно. И тогда просто выбора не остается, приходится делать рефакторинг. И чем более высокого уровня язык, тем это быстрее и проще
В сферическом прототипе в вакууме незачем. А в реальном — не стоит заранее отсекать такую возможность.
Я еще раз спрашиваю — зачем?
Затем, что 1) прототип может быть и не выброшен 2) в процессе доработки из-за пренебрежения качеством кода прототип дойдёт до состояния «проще выкинуть и написать с нуля» ещё до завершения прототипирования, что затормозит сам процесс прототипирования.
прототип может быть и не выброшен
Прототипы «на выброс» и «не на выброс» надо строго и жестко разделять с самого начала. И вторых должно быть существенно меньше.
прототип дойдёт до состояния «проще выкинуть и написать с нуля» ещё до завершения прототипирования
Ну и фиг бы с ним. Что быстрее — править прототип или переписывать заново — вопрос сильно отдельный. А вообще просто не надо доводить прототипы до такой сложности, это опасно.
У меня как раз все прекрасно с возможностью легко рефакторить код, чем я и пользуюсь в продуктивном коде.
Я просто не считаю, что выбор технологии для прототипа надо основывать на рефакторинге.
Я просто не считаю, что выбор технологии для прототипа надо основывать на рефакторинге.
Цитата полностью:
Фраза «рефакторить негде» относится к «пишется один раз», и означает что за время написания вертикального прототипа не должно возникать потребность в его рефакторинге.
VS2012 + TFS2012 + Resharper.
Просто вертикальный [прототип] тоже пишется один раз, проверяется работоспособность, потом уже пишется нормально — рефакторить тоже негде.
Фраза «рефакторить негде» относится к «пишется один раз», и означает что за время написания вертикального прототипа не должно возникать потребность в его рефакторинге.
Что за инструменты вы используете в разработке?
VS2012 + TFS2012 + Resharper.
В чем тогда смысл вертикального прототипа?
Смысл вертикального прототипа в том, чтобы проверить работоспособность некоего решения.
И почему у вас прототип не рефакторится, а продуктивный код рефакторится?
Потому что нет смысла рефакторить код, который мы все равно выбросим и перепишем заново.
И причем здесь вертикальный прототип тогда? Зачем он?
Karl Wiegers, Software Requiremens, Second edition, p. 236:
A vertical prototype, also known as a structural prototype or proof of concept, implements a slice of application functionality from the user interface through the technical services layers. A vertical prototype works like the real system is supposed to work because it touches on all levels of the system implementation. Develop a vertical prototype when you’re uncertain whether a proposed architectural approach is feasible and sound, or when you want to optimize algorithms, evaluate a proposed database schema, or test critical timing requirements. To make the results meaningful, vertical prototypes are constructed using production tools in a production-like operating environment.
Относительно вертикального прототипа: он нужен для проверки архитектуры системы, а не «некоего решения».
Архитектура не является неким решением? Интересно.
Если вы не собираетесь его изменять (после выявления недостатков, проблем и т.п.), то отсутствует смысл его делать.
Не факт.
Develop включает рефакторинг, независимо от уровня, на котором проводится этот Developing.
Вы упускаете из поля зрения важную оговорку: «To make the results meaningful, vertical prototypes are constructed using production tools ». Если production tools позволяют рефакторинг — хорошо. Не позволяют — не судьба. Всё. Следовательно, поддержка рефакторинга не может являться ключевым параметром при выборе инструментария для разработки вертикального прототипа. QED.
Конкретно у меня в случае вертикальных прототипов не возникало необходимости их рефакторить, они теряли актуальность раньше.
Так ничто не является ключевым парметром. Зато отдельные параметры ускоряют разработку, а разработка прототипа — тоже разработка, хоть и с другими ограничениями.
В данном случае — является: вертикальный прототип делается теми же инструментами, что и (предполагаемый) продуктив.
Вы не поняли.
Если мы делаем вертикальный прототип, то использование инструментов, совпадающих с продуктивом обязательно. По крайней мере, так утверждает Вигерс, и я не вижу причин с ним не соглашаться.
Если мы делаем вертикальный прототип, то использование инструментов, совпадающих с продуктивом обязательно. По крайней мере, так утверждает Вигерс, и я не вижу причин с ним не соглашаться.
Простите, из чего вы делаете вывод, что фраза про «адекватные результаты» относится только ко второму пункту?
А почему нет? Принцип взаимодействия и структура системы в общем случае не зависит от реализации этого взаимодействия и других технических вещей.
Ну то есть тот факт, что в одном случае система из-за сетевого оверхеда неработоспособна, а в другом — работает, не зависит от реализации сетевого взаимодействия, да? Равно как и то, что WCF (ну например) вот такую аутентификацию умеет, а вот такую — нет, и поэтому здесь каналы должны быть такими, а здесь — нет.
Что он проверяет-то тогда, такой архитектурный прототип?
Из того факта, что я Вигерса цитирую, можно было бы догадаться, что я его читал.
Да, и про эволюционные прототипы тоже.
Сетевое взаимодействие не зависит от инструмента.
То есть если один инструмент использует xml-представление данных, а другой — бинарное, это не влияет на сетевое взаимодействие?
Вероятно, мы по-разному понимаем слова «сетевое взаимодействие».
Использование XML — это архитектурные, а не инструментальные особенности.
Вот проблема наших «инструментов» в том, что они зачастую навязывают архитектурные решения.
Ну вот есть, скажем, WCF. Вполне себе инструмент. Как только мы его выбираем, он навязывает нам определенную группу решений в части организации сервисного взаимодействия (предпочтительные представления данных, предпочтительные техники организации защищенных каналов, etc).
Или вот скажем, MS SQL. Вполне себе инструмент. Но когда мы выбираем, как нам хранить файлы (как часть пользовательских данных) MS SQL (в отличие от других БД) предоставляет нам некоторые возможности, которые сильно влияют на архитектуру решения.
Ну и так далее.
Или вот скажем, MS SQL. Вполне себе инструмент. Но когда мы выбираем, как нам хранить файлы (как часть пользовательских данных) MS SQL (в отличие от других БД) предоставляет нам некоторые возможности, которые сильно влияют на архитектуру решения.
Ну и так далее.
Почему с ног на голову?
Ставятся требования. Выбираются технологии и инструменты. А потом, чтобы удостовериться, что технологии и инструменты удовлетворяют требованиям, строится архитектурный прототип.
Все очень логично.
Ставятся требования. Выбираются технологии и инструменты. А потом, чтобы удостовериться, что технологии и инструменты удовлетворяют требованиям, строится архитектурный прототип.
Все очень логично.
Расшифруйте эту фразу
В требованиях написано «система должна то-то и то-то так-то и так-то».
Мы выбираем инструмент, который может «то» и «так». Ну то есть в его документации написано, что может.
Дальше, если мы документации не верим, мы строим прототип и смотрим, действительно ли будет «то» и «так».
Например «обмениваться сообщениями по защищенному каналу».
Это, несомненно, требование для системы, но, например, в документации на WCF (выше вы не спорили, что это инструмент) вполне себе написано, что он поддерживает secure message channels.
Приблизительно вот здесь. Естественно, не дословно, но дословно никому и не надо.
Нет. Но там написано, что он может их делать. What's your point?
Проблема в том, что вам мало проверить «техническую возможность», вам надо еще удостовериться, что реализация этих вещей в WCF (окей, для HTTPS это еще просто, а вот для WSSecurity — уже нет) совместима с эндпойнтом на другой стороне. А это уже требует построения модели системы хотя бы в участке «та сторона — транспорт — мы». Что и является вертикальным прототипом.
Не всегда получится заранее жёстко разделить прототипы «на выброс» и «не на выброс».
Раз уж говорите, что важно понимать код, то нужно действительно понимать его:
Количество вызовов конструкторов копирования и деструкторов в обоих случаях одиннакого. В случае отсутствия return value optimization, временный объект, как и объект на стеке, будет создан, скопирован в другой временный объект (на время развертывания стека) и уничтожен.
Следующий код был скомпилирован на g++ 4.7.2 с опцией -fno-elide-constructors и в обоих случаях показал по 2 вызова конструктора копирования и деструктора (результат в конце): http://pastebin.com/VSgweiLM
P.S. хотя с эстетической точки зрения я тоже предпочитаю второй вариант
Количество вызовов конструкторов копирования и деструкторов в обоих случаях одиннакого. В случае отсутствия return value optimization, временный объект, как и объект на стеке, будет создан, скопирован в другой временный объект (на время развертывания стека) и уничтожен.
Следующий код был скомпилирован на g++ 4.7.2 с опцией -fno-elide-constructors и в обоих случаях показал по 2 вызова конструктора копирования и деструктора (результат в конце): http://pastebin.com/VSgweiLM
P.S. хотя с эстетической точки зрения я тоже предпочитаю второй вариант
Тема несколько заезженная. Уже даже не холивар.
По сути посыл статьи говорит — мы написали медленный движок, для которого код оптимизировать не имеет смысла. Так что пишите код какой хотите, все равно быстро не получится.
Оба аргумента никудышние. Факт состоит в том что некоторые опреации процессор или движок выполняют быстрее чем другие за счет своей архитектуры (тот же and 1 vs mod 2 ), и если движок VBScript в 2005 не выполнял битовое & на уровне процессора, то да оптимизировать такое действительно не стоит, но тыкать пальцем нужно в сторону программистов движка. Но тут еще можно спорить, стоит полягаться на оптимизации движа или нет
А вот если вызов функции с двумя переменными вызывает задержку в 100 нс и этот факт был доказан и измерян, то НУЖНО следить за переменными, а не дуть щеки, дескать что кто заставлял совать голову в печь, а разработчикам движка НУЖНО засабмитить багрепорт на эту тему
Оба аргумента никудышние. Факт состоит в том что некоторые опреации процессор или движок выполняют быстрее чем другие за счет своей архитектуры (тот же and 1 vs mod 2 ), и если движок VBScript в 2005 не выполнял битовое & на уровне процессора, то да оптимизировать такое действительно не стоит, но тыкать пальцем нужно в сторону программистов движка. Но тут еще можно спорить, стоит полягаться на оптимизации движа или нет
А вот если вызов функции с двумя переменными вызывает задержку в 100 нс и этот факт был доказан и измерян, то НУЖНО следить за переменными, а не дуть щеки, дескать что кто заставлял совать голову в печь, а разработчикам движка НУЖНО засабмитить багрепорт на эту тему
А вот и упомянутые автором «программисты на PDP-11» подоспели :)
Вы наверное хотите потроллить, я вообще то на Java и JavaSctipt пишу, может у вас есть аргумент покрепче?
100 нс — это одна стомиллионная часть секунды. Разработчики движка над таким багом посмеются.
*десятимиллионная
Разработчики посмеются? В 2005ом майкрософт как раз так наплевательски к этому и относился. Видать теперь пришло время, когда это почитается и делается умное лицо что так и нужно.
50 нс прироста на каждую лишнюю переменную означает что когда вас на VBScript в 2005 году заставят отфильтровать таблицу на 10000 строк, и в фильтре у вас будет на две переменных больше чем нужно, вы получите замечательную задержку в 1 секунду. Это все еще выглядит мало?
И между прочим в 2005 году далеко не у всех были PIII на 1GHz
А выбирать инструмент, как некоторые тут советуют, тогда было особо не из чего, доля IE6 тогда было больше 80%. Так что продолжайте в том же духе минусовать, сидя в удобном кресле и дуя щеки
50 нс прироста на каждую лишнюю переменную означает что когда вас на VBScript в 2005 году заставят отфильтровать таблицу на 10000 строк, и в фильтре у вас будет на две переменных больше чем нужно, вы получите замечательную задержку в 1 секунду. Это все еще выглядит мало?
И между прочим в 2005 году далеко не у всех были PIII на 1GHz
А выбирать инструмент, как некоторые тут советуют, тогда было особо не из чего, доля IE6 тогда было больше 80%. Так что продолжайте в том же духе минусовать, сидя в удобном кресле и дуя щеки
50 нс прироста на каждую лишнюю переменную означает что когда вас на VBScript в 2005 году заставят отфильтровать таблицу на 10000 строк, и в фильтре у вас будет на две переменных больше чем нужно, вы получите замечательную задержку в 1 секунду. Это все еще выглядит мало?
Это означает, что инструмент выбран не по месту. Не надо фильтровать на VBS таблицы в десять тысяч строк.
Да, именно это и означает, неистово плюсую за смекалку, вот только в реальном мире это далеко не всегда доступная роскошь — выбирать инструмент разработки, о чем я уже написал, упомянув IE6
А зачем обрабатывать десять тысяч строк на IE6? В 2005-ом году такие операции делали на стороне сервера.
затем что так нписано в ТЗ
С такими ТЗ нужно бороться до последнего, предупреждая о последствиях. После этого не надо писать баги разработчикам VBS, а просто сказать заказчику «вас предупреждали».
не сомневаюсь что вы всегда способны предсказать будущее, всегда рассказываете его своим заказчикам, и они вас при этом всегда понимают
поэтому я просто склоняю голову перед вашим профессионализмом
поэтому я просто склоняю голову перед вашим профессионализмом
При чем тут предсказание будущего? Обычный анализ решения.
потому что, чтобы преупреждать о последствиях, нужно их знать, а вы, как я вижу всегда знаете наперед все последствия или рассчитываете их получить от ближайщего спеца. Мир далеко не так кругл как вы мне тут рисуете.
Да если вы всегда анализируете решение вплоть до производительности функций, мне вас только жаль
Дальше разговвривать не вижу смысла, спорить с вашей оторванной от жизни абстрактной логикой просто бессмысленно
Да если вы всегда анализируете решение вплоть до производительности функций, мне вас только жаль
Дальше разговвривать не вижу смысла, спорить с вашей оторванной от жизни абстрактной логикой просто бессмысленно
когда вас на VBScript в 2005 году заставят отфильтровать таблицу на 10000 строк, и в фильтре у вас будет на две переменных больше чем нужно, вы получите замечательную задержку в 1 секунду. Это все еще выглядит мало?
Смотря с чем сравнить. Если общее время работы на 10000 строк будет больше часа, то 1 секунду просто не заметите.
10000 * 100 нс = 0.001 секунда. Да, это ничтожно мало. Для скриптового языка в 2005-ом году — отличный результат, IMHO. Откуда вы насчитали аж замечательную секунду задержки?
И между прочим в 2005 году далеко не у всех были PIII на 1GHz
В 2005 году я как раз купил себе P4 на 3.8 ГГц, и это в отсталой России-то.
А автор рассказывает о событиях конца 1990-х. В конце 1990-х, собственно, и альтернативы IE не было.
Просто чтоб поставить всё в исторический контекст.
И между прочим в 2005 году далеко не у всех были PIII на 1GHzУ меня в конце 2005 был ноут б/у (у пред.хозяина был с 2002) с Celeron 1,4 GHz.
Вообще-то AMD достигла 1GHz ещё в 2000.
А я так и не понял, почему использование AND вместо MOD даст «некорректный код, и программы не будут работать правильно». Пока компьютеры не перешли на троичную или фибоначчиеву систему счисления, «x&1» и «x%2» будут работать практически одинаково. Более того, у тех, кто пишет (x&1) меньше шансов ошибиться. Я очень часто вижу, как условие нечетности числа записывают в виде x%2==1 :)
P.S. На PDP-11 программировал 2 или 3 года, когда учился.
P.S. На PDP-11 программировал 2 или 3 года, когда учился.
Не смог придумать насчет четности, но замена деления на два сдвигом вправо не работает на отрицательных числах, я думаю он что то такое имел ввиду.
Работает, причем правильно — по-математически, когда [(-3)/2]=-2. А дальше — вопрос, что именно нужно в данной точке программы, математическое или «программистское» деление и взятие остатка.
Деление не «программисткое» а целочисленное, округление должно быть получено отбросом дробной части. А тут получается, что [(-3)/8] = -1, что уже ни математически, ни вообще никак не правильно.
Операции неравнозначны, дают разный результат, этого вполне достаточно.
Операции неравнозначны, дают разный результат, этого вполне достаточно.
Математически, остаток от деления a%b,, должен принадлежать множеству 0..|b|-1. И при этом должно выполняться условие, что (a/b)*b+a%b==a. Поэтому, (-3)%8==5, а (-3)/8==-1 (при целочисленном делении).
http://ru.wikipedia.org/wiki/%D0%9E%D1%81%D1%82%D0%B0%D1%82%D0%BE%D0%BA_%D0%BE%D1%82_%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F
http://ru.wikipedia.org/wiki/%D0%9E%D1%81%D1%82%D0%B0%D1%82%D0%BE%D0%BA_%D0%BE%D1%82_%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F
Сейчас попросил дочку разделить -5 на -3 с остатком — она ответила, не задумываясь: «частное 2, остаток 1». В полном соответствии с определением :)
«Деление с остатком», это как бы не тоже самое. От него получается «неполное частное», оно неотделимо от остатка, чем отличается от обычного порошка частного в делении, которое округляется.
PS И в гугл-калькуляторе, кстати, тоже можно получить отрицательный остаток.
PS И в гугл-калькуляторе, кстати, тоже можно получить отрицательный остаток.
И где же это в математике может потребоваться целочисленное деление с округлением в сторону нуля?
Остаток от 0 до |b|-1 — сколько угодно, в теории чисел и теории групп. Согласованное с ним деление — да, чтобы работала формула деления с остатком (хотя целая часть нужна довольно редко). Деление с округлением до ближайшего целого и согласованный с ним остаток (симметричная модель поля Zp) — бывает (кажется, используется в вычислении квадратичных вычетов). А округления в сторону нуля что-то не припомню.
Остаток от 0 до |b|-1 — сколько угодно, в теории чисел и теории групп. Согласованное с ним деление — да, чтобы работала формула деления с остатком (хотя целая часть нужна довольно редко). Деление с округлением до ближайшего целого и согласованный с ним остаток (симметричная модель поля Zp) — бывает (кажется, используется в вычислении квадратичных вычетов). А округления в сторону нуля что-то не припомню.
Дело не в округлениях. Дело в стремлении математики к двум вещам: обобщению и единству.
В угоду первой были введены и изучены т.н. евклидовы кольца — минимальные по сложности алгебраические структуры, в которых уже можно осмысленно ввести деление с остатком. По ссылке нужно обратить внимание на первую аксиому евклидова кольца (EF1), и сопоставить её с примерами евклидовых колец. Ясно, что евклидова функция в случае кольца целых чисел — модуль, а, скажем, в случае кольца многочленов над полем — их степень. Таким образом, (EF1) требует в случае целых чисел выполнения неравенства |r| < |b|, где r — остаток от деления, b — (ненулевой) делитель. Нетрудно понять, что если остаток ненулевой, возможно две пары (q, r): (q1, r1), (q2, r2), где a = b*q + r, — для каждой пары (a, b), причем |q1 — q2| = 1, |r1 — r2| = b. Обращаю внимание — существование неоднозначности зависит не от знаков делимого и делителя, а от того, делится ли первый на второй нацело.
В угоду второй в теории чисел договорились, что для однозначности выбор всегда будет осуществляться в сторону неотрицательного остатка. Тем не менее, любая формальная система (в том числе, языки программирования), вольна делать это выбор так, как ей покажется удобнее. Вот и, в частности языки, делают это все по-разному.
В угоду первой были введены и изучены т.н. евклидовы кольца — минимальные по сложности алгебраические структуры, в которых уже можно осмысленно ввести деление с остатком. По ссылке нужно обратить внимание на первую аксиому евклидова кольца (EF1), и сопоставить её с примерами евклидовых колец. Ясно, что евклидова функция в случае кольца целых чисел — модуль, а, скажем, в случае кольца многочленов над полем — их степень. Таким образом, (EF1) требует в случае целых чисел выполнения неравенства |r| < |b|, где r — остаток от деления, b — (ненулевой) делитель. Нетрудно понять, что если остаток ненулевой, возможно две пары (q, r): (q1, r1), (q2, r2), где a = b*q + r, — для каждой пары (a, b), причем |q1 — q2| = 1, |r1 — r2| = b. Обращаю внимание — существование неоднозначности зависит не от знаков делимого и делителя, а от того, делится ли первый на второй нацело.
В угоду второй в теории чисел договорились, что для однозначности выбор всегда будет осуществляться в сторону неотрицательного остатка. Тем не менее, любая формальная система (в том числе, языки программирования), вольна делать это выбор так, как ей покажется удобнее. Вот и, в частности языки, делают это все по-разному.
В группах же, должен вас поправить, деление с остатком определено быть не может. Для существования деления с остатком, как я уже говорил, должны выполняться аксиомы евклидова кольца, в том числе, разумеется, кольца. В группе же, для начала, определена только одна операция, а их, очевидно, нужно как минимум две, обозначим их * и +.
Конечное поле Zp является, помимо прочего, кольцом классов вычетов по простому модулю, в котором классы допустимо обозначать по любому представителю. Например, в Z5, [3] = [-2] = [103]. Поэтому выбор какого-то канонического представителя снова таки произволен. Обычно выбирают минимальный неотрицательный.
Более того, в Zp, как и в любом поле, вводить деление с остатком бессмысленно — согласно аксиомам поля, всякий ненулевой элемент Zp имеет обратный, потому деление на ненулевой элемент всегда возможно. Например, в уже упомянутом Z5 [4] / [3] = [3]. Действительно, [4] = [9] = [3*3] = [3]*[3].
Конечное поле Zp является, помимо прочего, кольцом классов вычетов по простому модулю, в котором классы допустимо обозначать по любому представителю. Например, в Z5, [3] = [-2] = [103]. Поэтому выбор какого-то канонического представителя снова таки произволен. Обычно выбирают минимальный неотрицательный.
Более того, в Zp, как и в любом поле, вводить деление с остатком бессмысленно — согласно аксиомам поля, всякий ненулевой элемент Zp имеет обратный, потому деление на ненулевой элемент всегда возможно. Например, в уже упомянутом Z5 [4] / [3] = [3]. Действительно, [4] = [9] = [3*3] = [3]*[3].
Хм… Посмотрел по «своей» же ссылке кольцо на русской википедии, и подумал, что лучше было дать ссылку на английскую: ring
Выбор канонического элемента произволен. Но на то он и канонический, чтобы быть одинаковым для всех элементов класса эквивалентности. Поэтому если они будут принадлежать, скажем, множеству {3-p,4-p,...,2}, то это будет непонятно, но допустимо. А вот если для a>0 представитель окажется положительным, а для a<0 отрицательным, нехорошо получится…
Про деление с остатком в группе я не говорил. Речь шла о теории групп. В частности — о структуре конечной циклической группы, где мы хотим показать, как работает возведение в степень (в том числе отрицательную). И чтобы написать, что (a^k)^m=a^(k*m mod n), нам нужно, чтобы k*m mod n принадлежало множеству 0..n-1 (если мы изначально заали элементы группы как e,a,a^2,...,a^(n-1)).
Про деление с остатком в группе я не говорил. Речь шла о теории групп. В частности — о структуре конечной циклической группы, где мы хотим показать, как работает возведение в степень (в том числе отрицательную). И чтобы написать, что (a^k)^m=a^(k*m mod n), нам нужно, чтобы k*m mod n принадлежало множеству 0..n-1 (если мы изначально заали элементы группы как e,a,a^2,...,a^(n-1)).
Я не очень понял, что вы имели в виду в первом абзаце. Если вы по-прежнему о математике и о свойствах полей Zp, элемент a — это элемент фактора Z по идеалу, порожденному p (чем и является Zp), то есть, класс эквивалентности, «представитель» — элемент кольца Z, являющийся представителем класса a, то должен заметить, что Zp — конечное поле, конечные поля неупорядочиваемы (Finite fields cannot be ordered), потому представители, конечно, могут быть положительными и отрицательными, ибо они из Z, где естественный порядок не только линейный (кстати, под "<" вы какой порядок имели в виду?), но и полный (well order), но вот записи a<0 и a>0 (считая 0 удобным обозначением [0]) абсолютно бессмысленны.
Нет, не нужно. В общем случае, остатков r таких, что k*m = q*n + r, может быть два, r1 и r2, причем |r1 — r2| = n. Для определенности будем считать, что r1 < r2. Пусть теперь g (в вашем примере фигурировал снова под именем a) — образующий циклической группы порядка n. Тогда:
g^r1 = g^r1 * e = g^r1 * g^n = g^(r1 + n) = g^r2.
И чтобы написать, что (a^k)^m=a^(k*m mod n), нам нужно, чтобы k*m mod n принадлежало множеству 0..n-1 (если мы изначально заали элементы группы как e,a,a^2,...,a^(n-1)).
Нет, не нужно. В общем случае, остатков r таких, что k*m = q*n + r, может быть два, r1 и r2, причем |r1 — r2| = n. Для определенности будем считать, что r1 < r2. Пусть теперь g (в вашем примере фигурировал снова под именем a) — образующий циклической группы порядка n. Тогда:
g^r1 = g^r1 * e = g^r1 * g^n = g^(r1 + n) = g^r2.
1) В первом абзаце я пытался найти канонический элемент класса вычетов по модулю p, содержащего заданное целое число a (для которого выражение a>0 имеет смысл, поскольку целые числа упорядочены). Канонический элемент нужен для того, чтобы по двум произвольным объектам определить, принадлежат ли они одному классу эквивалентности. Если операция mod возвращает (как принято в математике) число от 0 до p-1, то я могу использовать её в качестве способа опеределения канонического элемента, для объекта x канонический элемент в его классе вычетов по модулю n — это x mod n. Операцию % из языков программирования я для этой цели использовать не могу: числа -11 и 24 по модулю 7 дали бы разные «канонические элементы» (-4 и 3 соответственно), несмотря на то, что они принадлежат одному классу вычетов. Для этой математической задачи операция % не годится.
2) Первая фраза в описании структуры циклической группы с образующей a порядка n: группа состоит из n элементов: e, a, a^2, ..., a^(n-1). Других элементов в ней ней. Далее мы определяем элемент, обратный a^k (как a^((-k) mod n) и произведение элементов a^k и a^m: это a^((k+m) mod n). Пока всё хорошо: элементы, которые мы получили в результате, принадлежат исходному перечислению. Если мы определим операцию возведения в степень, как (a^k)^m=a^((k*m) mod n), то опять всё в порядке — элемент в списке есть. Если же мы вместо mod воспользуемся операцией %, то получим, что при n=8,k=3, m=-5: ((a^3)^(-5))=a^((3*(-5))%8) = a^(-7). Такого элемента в исходном перечислении элемнтов группы нет. Конечно, мы знаем, что a^(-7)=a, но тогда придётся говорить, что некоторые элементы имеют по два эквивалентных обозначения, которые равноправно могут использоваться в формулах… неудобно. Операция mod всё же лучше.
Так где же в математике используется компьютерное вычисление остатка? Или компьютерное деление нацело (вместо привычного [a/b])? Да, в одном из доказательств евклидовости кольца Z (индукцией по |a|) оно возникает. Но там есть и другие, более прямые доказательства…
2) Первая фраза в описании структуры циклической группы с образующей a порядка n: группа состоит из n элементов: e, a, a^2, ..., a^(n-1). Других элементов в ней ней. Далее мы определяем элемент, обратный a^k (как a^((-k) mod n) и произведение элементов a^k и a^m: это a^((k+m) mod n). Пока всё хорошо: элементы, которые мы получили в результате, принадлежат исходному перечислению. Если мы определим операцию возведения в степень, как (a^k)^m=a^((k*m) mod n), то опять всё в порядке — элемент в списке есть. Если же мы вместо mod воспользуемся операцией %, то получим, что при n=8,k=3, m=-5: ((a^3)^(-5))=a^((3*(-5))%8) = a^(-7). Такого элемента в исходном перечислении элемнтов группы нет. Конечно, мы знаем, что a^(-7)=a, но тогда придётся говорить, что некоторые элементы имеют по два эквивалентных обозначения, которые равноправно могут использоваться в формулах… неудобно. Операция mod всё же лучше.
Так где же в математике используется компьютерное вычисление остатка? Или компьютерное деление нацело (вместо привычного [a/b])? Да, в одном из доказательств евклидовости кольца Z (индукцией по |a|) оно возникает. Но там есть и другие, более прямые доказательства…
Я не совсем понял, откуда из воздуха взялся критерий «должно где то в математике использоваться». Кстати, интересно, а округление вообще в математике где то используется?
Согласно стандарта(гугл сказал) для целых чисел знак правого слеша означает деление с отбросом дробной части. Кому и как более привычно представлять себе этот слеш — не имеет значения. Где то в обсуждении произошла подмена деления на деление с остатком. Две разных операций. Вот там где эта подмена произошла, там и бага этого треда.
Согласно стандарта(гугл сказал) для целых чисел знак правого слеша означает деление с отбросом дробной части. Кому и как более привычно представлять себе этот слеш — не имеет значения. Где то в обсуждении произошла подмена деления на деление с остатком. Две разных операций. Вот там где эта подмена произошла, там и бага этого треда.
Началось с вот этой фразы:
Что такое «целочисленное деление», если оно не из языков программирования и не деление с остатком? Согласно стандарта чего? В стандартах некоторых языков программирования это так, вот я и назвал его «программистским». А вы что имели в виду?
Деление не «программистское» а целочисленное, округление должно быть получено отбросом дробной части. А тут получается, что [(-3)/8] = -1, что уже ни математически, ни вообще никак не правильно.
Что такое «целочисленное деление», если оно не из языков программирования и не деление с остатком? Согласно стандарта чего? В стандартах некоторых языков программирования это так, вот я и назвал его «программистским». А вы что имели в виду?
Нет, началось не с этой фразы, началось с того, что замена деления на два сдвигом вправо представляет собой некорректный код, ибо не работает на отрицательных числах. Не работает, потому что, как выяснилось, результатом выполнения получается «деление с остатком». Другая операция. Для деления (-3)/8 = -(3/8). А для деления с остатком — нет. Более того, как вот говорит ramntry деление с остатком это не операция вообще, а уравнение. С двумя решениями, одно из которых отсекается искусственным требованиям о положительности остатка. И кстати, если уж ссылаться на википедию, в ней также написано, что делить с остатком можно только целое на натуральное. То бишь на отрицательное уже нельзя делить. В отличие от обычного деления. Я так полагаю где то неточность.
Целочисленное деление — это из вариаций русского перевода вот этой фразы «quotient with any fractional part discarded». Частное с отброшенной дробной частью. Ну да, можно назвать это «программистским делением», если так хочется.
Не в математике, но в счете денег вполне себе используется, и задолго до программирования использовалось.
PS поскольку речь идет об оптимизации некоей операции в коде, то о стандарте этого кода, ISO C соответствующий. Было бы странно искать это где то еще.
Целочисленное деление — это из вариаций русского перевода вот этой фразы «quotient with any fractional part discarded». Частное с отброшенной дробной частью. Ну да, можно назвать это «программистским делением», если так хочется.
Не в математике, но в счете денег вполне себе используется, и задолго до программирования использовалось.
PS поскольку речь идет об оптимизации некоей операции в коде, то о стандарте этого кода, ISO C соответствующий. Было бы странно искать это где то еще.
Любопытно. Русская статья о «делении с остатком» переводит на английскую «Modulo operation», где сказано «In mathematics the result of the modulo operation is the remainder of the Euclidean division», а в определении этого «Euclidean division» условия b>0 уже нет, есть только b!=0. И остаток они хотят от 0 до |b|-1.
«замена деления на два сдвигом вправо представляет собой некорректный код» — всё равно не убедили. Во-первых, «замена» представляет собой не код, а преобразование программы. Да, это преобразование неэквивалентно, так как операции разные. Иногда оно превращает корректную программу в некорректную. Иногда, наверное, наоборот (я приводил пример для остатка — когда писали (a%2)==1, его перевод в (a&2)==1 исправил бы ошибку). Чаще тот, кто делает такую замену, знает, что он делает, но, конечно, неожиданности возможны (например, цикл while(a>>=1); может не закончиться, в отличие от while(a/=2); ). Так что почему «их программы не будут работать правильно», для меня по-прежнему загадка.
«замена деления на два сдвигом вправо представляет собой некорректный код» — всё равно не убедили. Во-первых, «замена» представляет собой не код, а преобразование программы. Да, это преобразование неэквивалентно, так как операции разные. Иногда оно превращает корректную программу в некорректную. Иногда, наверное, наоборот (я приводил пример для остатка — когда писали (a%2)==1, его перевод в (a&2)==1 исправил бы ошибку). Чаще тот, кто делает такую замену, знает, что он делает, но, конечно, неожиданности возможны (например, цикл while(a>>=1); может не закончиться, в отличие от while(a/=2); ). Так что почему «их программы не будут работать правильно», для меня по-прежнему загадка.
1. Я специально оговорился: «если вы по-прежнему о математике». В математическом контексте выглядит обескураживающим появление в тексте символа % в смысле «компьютерного вычисления остатка» (не говоря уже о том, что совершенно непонятно, что вы имеете в виду. C и python вычисляют остатки по-разному — например). Одновременно становится неясно, что вы понимаете под mod — то ли снова что-то компьютерное, то ли математическое… А если математическое, то что именно? В записи a ≡ b (mod n) — mod(1) — не знак операции, а а часть абстрактного символа, обозначающего равенство классов: [a]n = [b]n. Если очень хочется мыслить mod как операцию в этом контексте, то вернее считать, что mod(2) возвращает класс эквивалентности, чем считать, что mod возвращает некоторый представитель этого класса. Если вы под mod(3) подразумеваете операцию взятия остатка от деления, то я уже объяснял, почему она неоднозначна — и почему эта однозначность ничему особенно не мешает.
2. С тем, что в компьютерных вычислениях принято и удобно выяснять принадлежность двух элементов к одному множеству из системы непересекающиеся множеств с помощью их фиксированных представителей я, безусловно, соглашусь. Вспомним хотя бы систему непересекающихся множеств.
3. С тем, что операция % в варианте C — это не mod(2) не согласится невозможно.
Так что ваш пост целиком говорит не о математике, а об… этакой возможной реализации некоторых математических понятий в рамках компьютерных вычислений — и о том, насколько удобно или неудобно с этой целью использовать некоторые операторы некоторого конкретного языка программирования. Так что получилась вещь, старая как мир — я об одном, вы о другом.
2. С тем, что в компьютерных вычислениях принято и удобно выяснять принадлежность двух элементов к одному множеству из системы непересекающиеся множеств с помощью их фиксированных представителей я, безусловно, соглашусь. Вспомним хотя бы систему непересекающихся множеств.
3. С тем, что операция % в варианте C — это не mod(2) не согласится невозможно.
Так что ваш пост целиком говорит не о математике, а об… этакой возможной реализации некоторых математических понятий в рамках компьютерных вычислений — и о том, насколько удобно или неудобно с этой целью использовать некоторые операторы некоторого конкретного языка программирования. Так что получилась вещь, старая как мир — я об одном, вы о другом.
Да, еще один момент. Кажется, мне не удалось донести важную вещь: на кольце классов вычетов по модулю n нельзя ввести порядок (an ordered ring that is not trivial is infinite). Нельзя — значит, никак нельзя. И даже так: «зафиксируем способ выбора в каждом классе некоторого его представителя. Так как на представителях можно ввести порядок, то можно, таким образом, ввести порядок и на самих классах». Это неверно. Вы получите порядок на кольце вычетов как на множестве, а не как на кольце. Кстати, если рассматривать компьютерную целочисленную арифметику с математических позиций, то в ней все события разворачиваются (обычно) в кольце классов вычетов по модулю 2n, где n > 1. Потому с математической точки зрения такая операция, как < в, скажем, C, определенная для типа, скажем, int, не является отношением линейного порядка, как хотелось бы. С программисткой же точки зрения фраза «в C невозможно сравнить два значения типа int» неверна — лишний довод в пользу того, что не надо математику и компьютерные вычисления валить в одну кучу. А если это нужно сделать — то нужно быть предельно, порой параноидально, аккуратным и обговаривать абсолютно всё. Иначе сколь бы правильные вещи вы не думали, они не будут правильно записаны и правильно поняты другими.
Потому с математической точки зрения такая операция, как < в, скажем, C, определенная для типа, скажем, int, не является отношением линейного порядка, как хотелось бы.
отношением линейного порядка на кольце вычетов, я имел в виду, конечно.
А где вы увидели порядок на классах вычетов? С нулем у меня сравнивались исключительно целые числа. И из фразы «найти канонический элемент класса вычетов по модулю p, содержащего заданное целое число a» сделать вывод, что a — это класс вычетов, довольно сложно.
Для «линейного порядка», насколько я понимаю, требуется рефлексивность, так что операция < и в математическом кольце Z не будет операцией линейного порядка. Надо брать <=. И такая операция на типе int (и на всех других, где она определена), таки даст линейный порядок (как на множестве).
А то, что int не образует упорядоченное кольцо (и даже группу по сложению) — что ж, такая судьба. Нет у нас пока бесконечной памяти. То, что x>=y и x-y>=0 — разные вещи, думаю, все знают.
Для «линейного порядка», насколько я понимаю, требуется рефлексивность, так что операция < и в математическом кольце Z не будет операцией линейного порядка. Надо брать <=. И такая операция на типе int (и на всех других, где она определена), таки даст линейный порядок (как на множестве).
А то, что int не образует упорядоченное кольцо (и даже группу по сложению) — что ж, такая судьба. Нет у нас пока бесконечной памяти. То, что x>=y и x-y>=0 — разные вещи, думаю, все знают.
из фразы «А вот если для a>0 представитель окажется положительным, а для a<0 отрицательным, нехорошо получится…» сложно заключить, что a — это представитель. Гораздо проще заключить, что a — класс. Я уже осознал, что вы имели в виду — но нужно почти читать мысли, чтобы понять, что у вас такое a, которое еще и через каждый абцаз меняет свой смысл.
Замечание про < и <= верное, спасибо.
Конечно.
Замечание про < и <= верное, спасибо.
таки даст линейный порядок (как на множестве).
Конечно.
Кстати, к слову о канонических представителях и сишной арифметике. Мы тут с вами как-то увлеклись и не заметили следующего: если договориться в качестве канонического представителя брать минимальный элемент из неотрицательных (я о кольцах Z/(n), конечно), то выйдет, что в каком-то смысле сам диапазон значений сишного int являет собой не канонический случай. Ведь там есть, например, -1 (здесь и далее жирным — значения типа сишного int), то есть, мы со своей перспективы будем говорить, что сишный int «записывает» класс числа -1 как [-1]232. Но мы договорились обозначать класс числа -1 как [-1 + 232]232. Так что даже с самых дурацких позиций обижаться на сишный % за то, что -3 % 2 == 1 — ложь, странно. Подсовываем оператору представитель класса из Z/(232) в неканонической форме (-3), а хотим, чтобы он вернул нам представитель класса, в данном случае, из Z/(2), записанный в канонической (относительно Z/(232)).
Проблема решается довольно тривиально. Видимо, уже заметили, что -1 + 232 (здесь и далее курсивом — значения типа сишного unsigned), может быть получен из -1 приведением типа в сишном стиле, благо отрицательные числа хранятся в дополнительном коде.
На моей машине (x86_64, linux, gcc 4.7.2) приведенный ниже код работает без срабатывания assert'ов (кстати говоря, те самые явные сишные преобразования типов и не понадобились даже):
Для решения грандиозной проблемы несостоятельности символа % понадобилось лишь добавить еще один символ — u :)
Но рекомендовать такое к широкому использованию я отчего-то не стал бы.
Проблема решается довольно тривиально. Видимо, уже заметили, что -1 + 232 (здесь и далее курсивом — значения типа сишного unsigned), может быть получен из -1 приведением типа в сишном стиле, благо отрицательные числа хранятся в дополнительном коде.
На моей машине (x86_64, linux, gcc 4.7.2) приведенный ниже код работает без срабатывания assert'ов (кстати говоря, те самые явные сишные преобразования типов и не понадобились даже):
Скрытый текст
#include <assert.h>
int main()
{
int a = 5;
int b = 13;
int c = -3;
assert(a % 8u == b % 8u);
assert(a % 8u == c % 8u);
assert(b % 8u == c % 8u);
return 0;
}
Для решения грандиозной проблемы несостоятельности символа % понадобилось лишь добавить еще один символ — u :)
Но рекомендовать такое к широкому использованию я отчего-то не стал бы.
К сожалению, такое работает только для классов по модулю какой-нибудь степени двойки. В остальных отрицательные int «переедут» в чужой класс.
Да, в «евклидовом» смысле int неканонический. Его можно было бы рассматривать как канонический симметричный набор представителей, но соответствующей операции mod (дающей ответ от -n/2 до (n-1)/2), по-видимому, нет ни в одном языке (кроме операции mod0 в каком-то Scheme R6RS). Что-то вроде (a%n+(n>>1))%n-(n>>1). Ужас…
На страничке en.wikipedia.org/wiki/Modulo_operation написано, как mod вычисляется в разных языках. Присутствует по меньшей мере 6 вариантов (включая «Implementation dependent» для некоторых C и C++ :) )
Да, в «евклидовом» смысле int неканонический. Его можно было бы рассматривать как канонический симметричный набор представителей, но соответствующей операции mod (дающей ответ от -n/2 до (n-1)/2), по-видимому, нет ни в одном языке (кроме операции mod0 в каком-то Scheme R6RS). Что-то вроде (a%n+(n>>1))%n-(n>>1). Ужас…
На страничке en.wikipedia.org/wiki/Modulo_operation написано, как mod вычисляется в разных языках. Присутствует по меньшей мере 6 вариантов (включая «Implementation dependent» для некоторых C и C++ :) )
Работает, только округление происходит в большую сторону, а не в меньшую (как с положительными числами).
Сдвига вправо есть два — знаковый и беззнаконвый. Для отрицательных чисел знаковый сдвиг сохраняет старший бит и дублирует его во младшие, что даёт желаемый результат.
В таких языках как Java, есть соответствующие операторы ">>" и ">>>", а в C# знаковый сдвиг выполняется для типов данных, которые могут быть отрицательны (short, int, long), а беззнаковый — для остальных (byte, ushort, uint, ulong).
Сдвига вправо есть два — знаковый и беззнаконвый. Для отрицательных чисел знаковый сдвиг сохраняет старший бит и дублирует его во младшие, что даёт желаемый результат.
В таких языках как Java, есть соответствующие операторы ">>" и ">>>", а в C# знаковый сдвиг выполняется для типов данных, которые могут быть отрицательны (short, int, long), а беззнаковый — для остальных (byte, ushort, uint, ulong).
Наоборот — округление всегда происходит в меньшую сторону (а не в большую, как деление для отрицательных).
Хотя, возможно, мы имеем в виду разные процессоры.
Хотя, возможно, мы имеем в виду разные процессоры.
Имеется в виду округление в большую сторону по абсолютному значению. А так, округление всегда в меньшую сторону.
int v1 = -11;
(v1 >> 1) = -6;
int v2 = 11;
(v2 >> 1) = 5;
Abs(v1) > Abs(v2)
int v1 = -11;
(v1 >> 1) = -6;
int v2 = 11;
(v2 >> 1) = 5;
Abs(v1) > Abs(v2)
и чем некорректна проверка числа на нечетность с помощью x%2==1?
На отрицательных нечетных числах она выдаст false, там x%2==-1. Если проверять с помощью %, то надо сравнивать с нулём.
да, верно, не подумал почему-то. Ситуацию усугубляет то, что результат 1) зависит от языка (в python, например, на отрицательных числах результат 1, в си — действительно -1), 2) зависит от типа x (знаковый/беззнаковый, в первую очередь). Не знаю, зависит ли результат от аппаратной платформы в С/С++, к своему стыду. Полагаться на единство, разумеется, не стоит. Но знать, могут ли быть различия на практике было бы интересно.
Мне кажется, программа должна отражать намерения программиста, а не инструкции для машины.
Если по смыслу проверяется чётность, проверять %
Если по смыслу проверяется значение младшего бита, проверять &
Когда код осмысленный и прозрачный, а не составлен из хакерских заклинаний — тогда логические ошибки в этом коде сами бросаются в глаза.
Мне кажется, Эрик имел в виду именно это.
Если по смыслу проверяется чётность, проверять %
Если по смыслу проверяется значение младшего бита, проверять &
Когда код осмысленный и прозрачный, а не составлен из хакерских заклинаний — тогда логические ошибки в этом коде сами бросаются в глаза.
Мне кажется, Эрик имел в виду именно это.
Лайки лайками, но хочется сказать открыто: спасибо за правильные мысли, выраженные правильными словами. Обеими руками за.
Такие мысли толкают людей на создание более высокоуровневых языков, отходя дальше от ассемблера. Будем надеятся, что когда-то будут платформы, где можно ввести детальную спецификацию, а код будет уже сам генерироваться наилучшим способом. Тогда задача разработки будет сводится к уточнению и изменению спецификации, которая лучше всего отображает суть проблемы.
На PDP-11 программировал 2 или 3 года, когда учился.Считаю, что это необходимая школа, да;-)
Очень правильная статья! В первую очередь — выбор подходящего инструмента. Только потом всё остальное. Меня скукоживает, когда я слышу что-то в духе: «Фейсбук и Википедия написаны на PHP, поэтому для разработки высоконагруженного сайта буду использовать его; Фейсбук не может ошибаться. А чтобы всё работало быстро — буду избегать использования итераторов и прочего бесполезного синтаксического сахара, который временами в 1.5 раза медленнее».
Помню, как меня активно по-хабровому «не любили» (да и сейчас наверняка нарвусь) за высказвание мнения, что сильное беспокойство о производительности PHP — это повод посмотрерть в сторону хотя бы C#/Java. И особенно, когда беспокойство выливается в позывы превратить нормальный читаемый код в непонятно что, а от использования удобных фич языка и сторонних библиотек «приходится» отказываться.
Сам пишу на C#, PHP, JS, временами на C++, Python и прочих языках. Язык и прочие инструменты всегда выбираю осознанно, а не «потому что в прошлый раз на нём писал». Поэтому в ситуации, когда хочется избавиться от лишней переменной, обычно не оказываюсь. Признаюсь, иногда возникают неестественные позывы заменить «lock» или скидывание задачи в ui диспетчер на «что-нибудь побыстрее», но я пересиливаю такие позывы.
P.S. Лучше бы курсивом, а не цветом выделяли. В глазах пестрит, и всё время возникают позывы нажать на ссылку.
Помню, как меня активно по-хабровому «не любили» (да и сейчас наверняка нарвусь) за высказвание мнения, что сильное беспокойство о производительности PHP — это повод посмотрерть в сторону хотя бы C#/Java. И особенно, когда беспокойство выливается в позывы превратить нормальный читаемый код в непонятно что, а от использования удобных фич языка и сторонних библиотек «приходится» отказываться.
Сам пишу на C#, PHP, JS, временами на C++, Python и прочих языках. Язык и прочие инструменты всегда выбираю осознанно, а не «потому что в прошлый раз на нём писал». Поэтому в ситуации, когда хочется избавиться от лишней переменной, обычно не оказываюсь. Признаюсь, иногда возникают неестественные позывы заменить «lock» или скидывание задачи в ui диспетчер на «что-нибудь побыстрее», но я пересиливаю такие позывы.
P.S. Лучше бы курсивом, а не цветом выделяли. В глазах пестрит, и всё время возникают позывы нажать на ссылку.
Эрик как всегда четко и по сути говорит. Статья смак. И советы относятся не только к конкретным языкам, а и вообще к разработке.
Гы, меня прикалывает что человек, проработавший в софтверной фирме программистом кучу лет разговаривает и очень похоже что и думает об оптимизации на уровне любителей. И еще дает при этом вредные советы. И еще более прикалывает что это распространяется в сети как некие откровения.
Не надо искать ничего по коду. Надо замерять и анализировать результат профилировщика. Если нет нормального инструмента — надо его как-то эмулировать. Но ни в коем случае не стоит что-то там искать по коду, если вы не профи в оптимизации и шаблонные проблемы вы действительно находите беглым взглядом.
Не надо искать ничего по коду. Надо замерять и анализировать результат профилировщика. Если нет нормального инструмента — надо его как-то эмулировать. Но ни в коем случае не стоит что-то там искать по коду, если вы не профи в оптимизации и шаблонные проблемы вы действительно находите беглым взглядом.
> Меня вовсе не волнует машинный код, исполняемый файл для меня «чёрный ящик»
Я бы выбрал даже несуществующий вариант: главное для меня — читаемость и сопровождаемость кода, к черту оптимизацию, которая ухудшает сопровождаемость хоть на йоту.
Я бы выбрал даже несуществующий вариант: главное для меня — читаемость и сопровождаемость кода, к черту оптимизацию, которая ухудшает сопровождаемость хоть на йоту.
Поддерживаю — мир компьютеров и программирования на столько сложен, отнимает просто массу, тонны времени, бесконечное количество книг, алгоритмов, паттернов, с разработчиками микрософта спорят, корпорации спорят между собой. XDA форум думает быстрее разработчиков Android и прочие вещи.
Сделать идеально невозмонно, потому что идеальность ощущение правоты кода. И оно у каждого индивидуальное на основе опыта. Пусть программа чуть больше тормозит но она гарантированно сможет развиваться влево и вправо.
Сделать идеально невозмонно, потому что идеальность ощущение правоты кода. И оно у каждого индивидуальное на основе опыта. Пусть программа чуть больше тормозит но она гарантированно сможет развиваться влево и вправо.
Только мне фиолетовый цвет шрифта тут режет глазки? Плюс еще мое «суперское» сглаживание на линуксе…
А как я бросался оптимизировать php заменой кавычек и использованием сдвигов. У меня были скрипты, которые отрабатывали неимоверно быстро, и скрипты, в которых неправильный запрос sql занимал пару секунд.
Но вот на огромных массивах данных действительно приходится думать о мелочах, которые дают выигрыш на 100000 итерациях в пару-тройку критичных для результата минут. Только в вебе этого действительно никому не надо и затраты на такое никогда не окупятся.
Но вот на огромных массивах данных действительно приходится думать о мелочах, которые дают выигрыш на 100000 итерациях в пару-тройку критичных для результата минут. Только в вебе этого действительно никому не надо и затраты на такое никогда не окупятся.
В огромных массивах данных больший прирост даст многопоточность и какая-нибудь пакетная обработка.
К сожалению, в огромных массивах данных доступные терафлопсы иногда заканчиваются слишком рано, а результата все равно ждать приходится слишком долго.
По этому параллельность параллельностью, но и локальные оптимизации с учетом возможностей современных процессоров никто не отменяет. Да, для одноразовых задач может быть и имеет смысл положиться только на компилятор, но для многоразовых иногда эффективнее воспользоваться знаниями живого программиста по оптимизации под систему (например, далеко не всю векторизацию кода компиляторы смогут сделать автоматически, а выполняться векторизованный код будет чаще всего быстрее).
По этому параллельность параллельностью, но и локальные оптимизации с учетом возможностей современных процессоров никто не отменяет. Да, для одноразовых задач может быть и имеет смысл положиться только на компилятор, но для многоразовых иногда эффективнее воспользоваться знаниями живого программиста по оптимизации под систему (например, далеко не всю векторизацию кода компиляторы смогут сделать автоматически, а выполняться векторизованный код будет чаще всего быстрее).
Конечно же вы не имели в виду, что надо тратить день на «максимальную оптимизацию без потери читабельности» функции, которая выполняется один раз, и занимает 0.0000000001% от общего времени выполнения программы. Ведь так?
Неочевидный пример. Функция, которая выполняется один раз, может заниматься тем, что подготавливать данные для остальной программы в наиболее эффективном для использования виде. И на её оптимизацию (которая измеряется в эффективности использования этих данных) вполне можно потратить не один день.
Можете понимать мои слова как угодно, игнорировать контекст, внезапно вводить всё новые и новые виды оптимизаций, функций, программ и даже времени, но я всё равно не буду писать сухим юридическим языком, уточняя каждое понятие, а в конце обязательно словарик. Мне жаль своё время :)
Речь шла об оптимизации кода, не вижу причин зачем это понимать, как оптимизацию данных.
Речь шла об оптимизации кода, не вижу причин зачем это понимать, как оптимизацию данных.
Об оптимизации кода одной отдельно взятой функции, причем имелось в виду исключительно время её исполнения? Тогда смысла оптимизировать, конечно, не очень много. Но зачем загонять себя в такие рамки? Функция это часть программы, и работа над ней запросто может ускорить программу в целом, даже если время работы этой функции увеличится. Вы не будете считать такую ситуацию «оптимизацией»?
Могу сказать про недавний опыт.
Мы переписывали движок баннерокрутилки, полученный от коллег. Наш хороший разработчик переписал все на ООП PHP. Мы пытались что-то оптимизировать, но оно даже под абешкой не взлетало (50 запросов в секунду должно плевать с одного сервака, получали 99% fails).
В конце-концов в результате оптимизаций на профайлинге стала очевидность важности правильной архитектуры. Ниже этапы оптимизации и вывод.
1. Сначала убрали лишнее ООП. Помогло, не сильно
2. Увидели, что крутые ООП-оболочки над БД сильно тормозят. Переписали на голом PDO
3. Но и голое PDO стало тормозить. 90% времени съедает, 400 мс.
4. По моему предложению перенесли логику в БД. Так как там была операция в цикле и ряд запросов.
5. Сначала хранимки в БД написали " в лоб" — циклы и тд. Помогло, не сильно — 50% не работало под нагрузкой.
6. С участием нашего DBA, выдающего специалиста, переделали циклы в хранимке на язык реляционной БД — в один запрос, убрали временные таблицы из логики, и так далее.
7. В итоге менее 10% фейлов, и система стала жить на нагрузке.
Вывод — правильная архитектура решает, правильный выбор инструментов для размещения логики того или иного вида.
А вовсе не тупые оптимизации, вроде давайте заменим двойные кавычки на одинарные, или там заменим кусок сишного кода на ассемблер. А умные, которые неразрывно связаны с проникновением в предметную область задачи и понимания условий, в которых приложение будет работать.
Мы переписывали движок баннерокрутилки, полученный от коллег. Наш хороший разработчик переписал все на ООП PHP. Мы пытались что-то оптимизировать, но оно даже под абешкой не взлетало (50 запросов в секунду должно плевать с одного сервака, получали 99% fails).
В конце-концов в результате оптимизаций на профайлинге стала очевидность важности правильной архитектуры. Ниже этапы оптимизации и вывод.
1. Сначала убрали лишнее ООП. Помогло, не сильно
2. Увидели, что крутые ООП-оболочки над БД сильно тормозят. Переписали на голом PDO
3. Но и голое PDO стало тормозить. 90% времени съедает, 400 мс.
4. По моему предложению перенесли логику в БД. Так как там была операция в цикле и ряд запросов.
5. Сначала хранимки в БД написали " в лоб" — циклы и тд. Помогло, не сильно — 50% не работало под нагрузкой.
6. С участием нашего DBA, выдающего специалиста, переделали циклы в хранимке на язык реляционной БД — в один запрос, убрали временные таблицы из логики, и так далее.
7. В итоге менее 10% фейлов, и система стала жить на нагрузке.
Вывод — правильная архитектура решает, правильный выбор инструментов для размещения логики того или иного вида.
А вовсе не тупые оптимизации, вроде давайте заменим двойные кавычки на одинарные, или там заменим кусок сишного кода на ассемблер. А умные, которые неразрывно связаны с проникновением в предметную область задачи и понимания условий, в которых приложение будет работать.
Хороший пример оптимизации под конкретные требования, которые привели к использованию соответствующих задаче инструментов. Хотя для баннерокрутилки, я думаю, гадая на кофейной гуще, хватило бы и более простых решений, нежели разнесение логики на разные уровни. К примеру кэширование и переход на фастцги.
Насчёт пунктов 4-6: помню, заменил хранимку в ORACLE на хитрый запрос с хитрой обработкой его результатов на клиенте, заработало быстрее.
Мне показалось что опрос слабо коррелирует со статьей. В статье изложен несколько довольно разумных советов по расстановке приоритетов при оптимизации производительности, а в опрос сведен к попытке поиздеваться над теми кто оптимизирует байты и циклы где это не нужно.
Эта статья видимо ответ на дискуссию про производительность в другой статье про Дум3. Там вопрос остановился на том насколько важно для программиста понимать производительность тех строк кода, которые он пишет. На С/С++ на мой взгляд это часто означает примерное понимание того какие машинные инструкции будут сгенерированы, как устроены виртуальные функции, как обрабатываются исключения, итд. На Java, C# есть свои ловушки и лучшие практики.
Если так рассуждать то и писать хороший код тоже не «критически важно», достаточно уметь быдлокодить чтобы решать какие-то проблемы и зарабатывать деньги. Однако возьмем ли мы на работу С# программиста с опытом 3-5 лет, который не знает сложность алгоритма для вставки в тот или иной контейнер? Или если Senior C++ на собеседование не расскажет как устроены виртуальные функции?
На мой взгляд понимание работы с производительностью связано с професионализмом разработчика и это также тесно связано с умением писать «правильный» код. Это не означает что надо писать крипто код с ассемблерными вставками по всей программе, например С-шный код в ядре линукс вполне читаемый и при хорошо этом оптимизирован с учетом производительности.
Эта статья видимо ответ на дискуссию про производительность в другой статье про Дум3. Там вопрос остановился на том насколько важно для программиста понимать производительность тех строк кода, которые он пишет. На С/С++ на мой взгляд это часто означает примерное понимание того какие машинные инструкции будут сгенерированы, как устроены виртуальные функции, как обрабатываются исключения, итд. На Java, C# есть свои ловушки и лучшие практики.
Не просто «в принципе неплохо», а «замечательно и весьма полезно» — лишних знаний вообще не бывает.
Но не «критически важно».
Если так рассуждать то и писать хороший код тоже не «критически важно», достаточно уметь быдлокодить чтобы решать какие-то проблемы и зарабатывать деньги. Однако возьмем ли мы на работу С# программиста с опытом 3-5 лет, который не знает сложность алгоритма для вставки в тот или иной контейнер? Или если Senior C++ на собеседование не расскажет как устроены виртуальные функции?
На мой взгляд понимание работы с производительностью связано с професионализмом разработчика и это также тесно связано с умением писать «правильный» код. Это не означает что надо писать крипто код с ассемблерными вставками по всей программе, например С-шный код в ядре линукс вполне читаемый и при хорошо этом оптимизирован с учетом производительности.
Вы путаете «ловушки и лучше практики» из совершенно разных областей.
Сложность алгоритмов и семантика виртуальных функций — абстракции, вечные и неустаревающие, и именно ими программист должен владеть и руководствоваться.
Но их знание никоим боком не связано с «пониманием того, какие машинные инструкции будут сгенерированы».
Низкоуровневые трюки типа «and быстрее чем mod» или «виртуальные функции реализуются таблицей указателей, которую можно пойти и подредактировать прямо в памяти, чтобы создать quick-and-dirty субкласс» — это совсем другое. Это бывает полезно, но чаще у охотников поковыряться в битах получается непонятный и неподдерживаемый код, о чём Эрик и пишет.
Сложность алгоритмов и семантика виртуальных функций — абстракции, вечные и неустаревающие, и именно ими программист должен владеть и руководствоваться.
Но их знание никоим боком не связано с «пониманием того, какие машинные инструкции будут сгенерированы».
Низкоуровневые трюки типа «and быстрее чем mod» или «виртуальные функции реализуются таблицей указателей, которую можно пойти и подредактировать прямо в памяти, чтобы создать quick-and-dirty субкласс» — это совсем другое. Это бывает полезно, но чаще у охотников поковыряться в битах получается непонятный и неподдерживаемый код, о чём Эрик и пишет.
Ну я точно не призывал использовать знания для создания хаков вроде правки таблицы виртуальных функций на лету или каких-то семантически неверных замен.
Я вижу в вашем описание хороший принцип, что в общем случае не нужно управлять кодогенерацией прописывая кривой код на более высоком уровне. Но жить целиком в стране эльфов, которой является спецификация языка тоже не стоит, надо примерно представлять чем оплачиваются все эти чудеса волшебной страны.
Я вижу в вашем описание хороший принцип, что в общем случае не нужно управлять кодогенерацией прописывая кривой код на более высоком уровне. Но жить целиком в стране эльфов, которой является спецификация языка тоже не стоит, надо примерно представлять чем оплачиваются все эти чудеса волшебной страны.
Удивлен результатом опроса, если честно. Думал, что многие немного слукавят при выбора варианта ответа)
Слукавят в какую сторону???
Это был универсальный комментарий к любому опросу. Осторожно! может спровоцировать флеймвар.
на 1-2 пункта повыше
Но зачем? Наоборот, сейчас люди гордятся, что они умеют оперировать абстракциями вышего уровня, и поэтому никакой ассемблер им не нужен. Как и видно по комментариям в этой и смежных темах.
Да и 36% программистов, которых заботит ассемблерный листинг их программы, это в наше время довольно много. Так что, возможно, что многие хоть на пункт, но слукавили. Особенно подозрительным выглядит соотношение 9%/4%. Сейчас ведь и для микроконтроллеров в основном пишут на С, не так ли?
Да и 36% программистов, которых заботит ассемблерный листинг их программы, это в наше время довольно много. Так что, возможно, что многие хоть на пункт, но слукавили. Особенно подозрительным выглядит соотношение 9%/4%. Сейчас ведь и для микроконтроллеров в основном пишут на С, не так ли?
Что такое ЯНУ и ЯВУ?
Жесть! Сколько споров и на какие темы… Это всё из-за топика о производительности приложений. Тут уже можно создавать отдельные топики по математике, проектированию приложений, методикам разработки, и пр. Хоть бери текст из комментариев — и статья готова =)
У вас заголовок статьи в стиле Йоды магистра:) Чем хуже вариант «Насколько плохим должен быть код»?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Насколько плохим код должен быть?