Что, господа суровые С++ программисты, поспорим быстродействием с отстойной Джавой? ;)

>> Сергей-4030> Ага. И в два раза медленнее моего.
Lester> ваш тест без -server у меня отрабатывает за 4.3сек, у вас - 2.3сек, значит мои 2 секунды это около 1.05сек на вашем железе, а 0.75 и 1.05 это не в два раза

Нет. "-server" в среднем в три раза быстрее. Поэтому на вашей машине мой тест будет около 4.3/3 = 1.4 сек. против ваших 2 секунд. Впрочем, да, не в два. В полтора.

tarasv> Значит в обеих случаях используется одна и таже оптимизация. Не более того. Я этот оптимизатор не писал но из личной практики древний Ватком в начале 90х прекрасно делала из вот такого
Хех, это очень простой метод оптимизации — называется введение индуктивной переменной. Точнее, индуктивная переменная — это немного другое, но эта получается из него при небольшом размышлении и малой модификации.

Lester> да - я уже понял, что вы правы, собираю родным компилятором из Visual C++ 2005, пробовал mingw - код в два раза медленнее под виндой получается, думаю еще интеловский попробовать

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

>> А с учетом того, что по вашим вычисления Java в два раза медленнее C++, то ваш алгоритм в четыре раза менее эффективен, чем мой
Lester> опять же я сравнивал Java без -server, вы говорите у вас она в три раза быстрее, значит мой алгоритм в 1.43 раза быстрее вашего
Lester> П.С. конечно это все не точно - сейчас поставлю на закачку JDK и сравню
Lester> П.П.С. опс, сорри - получается у нас алгоритмы работают с одинаковой скоростью

Какие-то у вас странные вычисления. На вашей машине мой вариант с "-server" будет предположительно 1.4 секунды. Ваш - 2 секунды. Джава - в два раза медленнее C++ по вашим расчетам. Итого мой алгоритм "чисто" быстрее в 1.4 раза, плюс он преодолевает 2кратные тормоза Java - значит, сам алгоритм эффективней как минимум в 2.8 раз.

Mishka> Тогда могу тебе сказать, что косяк, при котором идёт дебагный код и не идёт оптимальный — это твой. Чаще всего неинициализированная переменная на стеке или выход за пределы.

Exactly.

tarasv>> Значит в обеих случаях используется одна и таже оптимизация. Не более того. Я этот оптимизатор не писал но из личной практики древний Ватком в начале 90х прекрасно делала из вот такого
Mishka> Хех, это очень простой метод оптимизации — называется введение индуктивной переменной. Точнее, индуктивная переменная — это немного другое, но эта получается из него при небольшом размышлении и малой модификации.

Только этот метод оптимизации называется удаление индутивной переменной. Значение i%1000 и есть индуктивная переменная по отнощениею к переменной цикла и ее убирают изменяя инкремент переменной цикла.

ЗЫ MSVC если отловил при компиляции неинициализированную переменную на стеке то в дебаг сборке ставит ассерт с вызовом диалогового окна.

Mishka> Тогда могу тебе сказать, что косяк, при котором идёт дебагный код и не идёт оптимальный — это твой. Чаще всего неинициализированная переменная на стеке или выход за пределы.
Бывает и в самом деле, что глюк компилятора. Я года полтора назад такой словил именно на MSVC++ 2005. Правда, на сишном коде, а не плюсовом. Компилятор доигрался с регистровыми переменными так, что итератор после выхода из цикла имел чёрти какое значение.

ЗЫ там не полная оптимизация была, а просто Release.

tarasv> Только этот метод оптимизации называется удаление индутивной переменной. Значение i%1000 и есть индуктивная переменная по отнощениею к переменной цикла и ее убирают изменяя инкремент переменной цикла.

Не, как раз не удаление, а введение. Удаляется исходная. И заменяется индуктивной, т.е. той, что индуцировалась исходной.

tarasv> ЗЫ MSVC если отловил при компиляции неинициализированную переменную на стеке то в дебаг сборке ставит ассерт с вызовом диалогового окна.

Ну, MSVC ещё и код герерит в дебаговом варианте так, чтобы такую ситуацию распознать. И, если переменная булева, то она точно инициализирована не FALSE. Чаще всего пропуски случаются, когда есть сложный if для инициализации, а потом одну веточку раз и убрал-поправил. Если разрешить все warnings, то такая ситуация отловится, только вот найти среди кучи других её будет очень трудно.

Kernel3> Бывает и в самом деле, что глюк компилятора. Я года полтора назад такой словил именно на MSVC++ 2005. Правда, на сишном коде, а не плюсовом. Компилятор доигрался с регистровыми переменными так, что итератор после выхода из цикла имел чёрти какое значение.

Бывает. Но очень редко. Правда, поэтому у меня SP1 стоит на 2005.

Kernel3> ЗЫ там не полная оптимизация была, а просто Release.
А ты примерчик подкинь. У меня была хрень такая, но позже я обнаружил, что частично вина была моя — программа была в одном месте ill formed. Т.е. он не поругался, но херь погнал конкретную.

tarasv>> Только этот метод оптимизации называется удаление индутивной переменной. Значение i%1000 и есть индуктивная переменная по отнощениею к переменной цикла и ее убирают изменяя инкремент переменной цикла.
Mishka> Не, как раз не удаление, а введение. Удаляется исходная. И заменяется индуктивной, т.е. той, что индуцировалась исходной.

Чтото мне такая арифметика не нравится было две переменных - переменная цикла и индуктивная (неявная в моем примере) от нее. Если метод назвается введение индуктивной переменной то их должно стать три или две (если ввели вместо другой), а осталась одна - переменная цикла, а индктивная от нее исчезла.

И вот в этой статье http://www.ict.edu.ru/ft/004337//p27_37.pdf тоже про удаление индуктивых переменных пишут (в 9й части). Кстати книга Utpal Banerjee в этой статье на почетном первом месте в списке литературы.

Lester>> при росте ограничения растет время работы - следовательно содержимое выполняется
Mishka> Может просто гоняться цикл. Но сравнение всё рано не корректное. Надо такой же код на Джаве писать. Плюс С/С++ или Джавы по сравнению с интерпретатором в том, что они имеет оптимизацию, да и посмотри на то же размещение переменных и обращение к ним. В С/С++ и Джаве это делается раз, а обращение к ним происходит практически статически — смещение относительно регистра стека. А в интерпретаторе — поиск по таблице.

у меня поиск по таблице происходит один раз - потом сразу берется значение по уже найденному индексу

Сергей-4030> Какие-то у вас странные вычисления. На вашей машине мой вариант с "-server" будет предположительно 1.4 секунды. Ваш - 2 секунды. Джава - в два раза медленнее C++ по вашим расчетам. Итого мой алгоритм "чисто" быстрее в 1.4 раза, плюс он преодолевает 2кратные тормоза Java - значит, сам алгоритм эффективней как минимум в 2.8 раз.

> Джава - в два раза медленнее C++ по вашим расчетам

по моим расчетам без -server, если как вы говорите с этим ключом ява в три раза быстрее, то значит Java на этом примере в 1.5 раза быстрее С++, правильно?

П.С. только сейчас ставлю на закачку JDK - инет вчера глючил

Lester> по моим расчетам без -server, если как вы говорите с этим ключом ява в три раза быстрее, то значит Java на этом примере в 1.5 раза быстрее С++, правильно?

Нет, Java, к сожалению, никак не быстрее C++.

tarasv> Чтото мне такая арифметика не нравится было две переменных - переменная цикла и индуктивная (неявная в моем примере) от нее. Если метод назвается введение индуктивной переменной то их должно стать три или две (если ввели вместо другой), а осталась одна - переменная цикла, а индктивная от нее исчезла.

Основная та, которая прописана человеком. Индуктивная та, которая вводится компилятором. Использоваться могут обе, а может только индуктивная. Например:

1. int a[ 5 ];
2. for ( int i = 0; i < 5; ++i )
3.   a[ i ] = 0;

Будет преобразовано в (примерно):

1.    lea ebx,a
2.    mov ecx,5
3. l: mov 0[ebx],0
4.    add ebx,4
5.    loop l

Т.е. хотя команда loop используется, но очень не формально, а вот индуктивная переменная на регистре ebx — в полную. Может получиться и такое:

1.    lea ebx,a
2.    lea ecx,20[ebx]
3.    jmp l:
4. a: mov 0[ebx],0
5.    add ebx,4
6. l: cmp cx,ebx
7.    jl  a

Тут только индуктивная и осталась — ходит напрямую по массиву. А вот в следующем примере уже нужны обе:

1. int a[ 5 ];
2. for ( int i = 0; i < 5; ++i )
3.   a[ i ] = i;

И раскроется это дело во что-то такое:

1.    lea ebx,a
2.    xor ecx,ecx
3.    jmp l:
4. a: mov 0[ebx],ecx
5.    add ebx,4
6.    add ecx,1
7. l: cmp cx,5
8.    jl  a

В том варианте, что ты привёл, произойдёт то, что описано в первой книжке.

tarasv> И вот в этой статье http://www.ict.edu.ru/ft/004337//p27_37.pdf тоже про удаление индуктивых переменных пишут (в 9й части). Кстати книга Utpal Banerjee в этой статье на почетном первом месте в списке литературы.

Может разная немного терминология.

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

Lester>> у меня поиск по таблице происходит один раз - потом сразу берется значение по уже найденному индексу
Mishka> Ты хочешь сказать, что в цикле, когда несколько переменных используются, то ты сразу знаешь всегда их индекс вхождения? Т.е. ты генеришь промежуточный код, а потом его интерпретируешь? А как же тогда подстановки работают?

> Т.е. ты генеришь промежуточный код, а потом его интерпретируешь?

да, и не сомневаюсь, что Сергей тоже - иначе не получить высокое быстродействие

> А как же тогда подстановки работают?

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

Mishka> Бывает. Но очень редко.
Ага. Второго такого случая не припомню.
Mishka> Правда, поэтому у меня SP1 стоит на 2005.
У меня тоже
Mishka> А ты примерчик подкинь. У меня была хрень такая, но позже я обнаружил, что частично вина была моя — программа была в одном месте ill formed. Т.е. он не поругался, но херь погнал конкретную.

1.     for (kbdPortDeviceObject = kbdPortDriverObject->DeviceObject;
2.      kbdPortDeviceObject != NULL;
3.      kbdPortDeviceObject = kbdPortDeviceObject->NextDevice)
4.     {
5.         kbdPortDeviceExtension = kbdPortDeviceObject->DeviceExtension;
6.  
7.         devExt = Devices[DeviceNumber - 1]->DeviceExtension;
8.  
9.     // blah-blah-blah
10.     }

Проблема была с devExt (не итератором - запамятовал). До цикла она не инициализировалась. Devices - некий глобальный массив, DeviceNumber - счётчик, остальные переменнные - локальные.

Сергей-4030> Нет, Java, к сожалению, никак не быстрее C++.

Всегда следует уточнять - какие реализации, на каких задачах и на каком железе А то, вон, у меня было: Я не верю своим глазам! Java быстрее, чем C++???

Да и на http://shootout.alioth.debian.org/gp4/... в одном тесте Java умудрилась обойти G++ (и даже Intel C++: http://shootout.alioth.debian.org/gp4/...)

Кстати, о влиянии -server: http://shootout.alioth.debian.org/gp4/...

tarasv> И вот в этой статье http://www.ict.edu.ru/ft/004337//p27_37.pdf тоже про удаление индуктивых переменных пишут (в 9й части). Кстати книга Utpal Banerjee в этой статье на почетном первом месте в списке литературы.

Таки немного разная терминология. Смотри:

Принцип выявления индуктивных (или «индексных», согласно [1]) переменных основан на ис-
пользовании Def-Use графа [2].

 

Т.е. они называют индуктивной ту, которую Утпал называет индексной. Мы же называли индуктивной ту переменную, которая введена компилятором (индуктирована), а переменную цикла реальную — индексной.

Lester> да, и не сомневаюсь, что Сергей тоже - иначе не получить высокое быстродействие

Оно подходит для всего, кроме подстановок. Тут появляется интерпретирующий элемент. Кстати, изначальное условие точности (не 100 циферок, а того, сколько значащих цифр и правила вычисления точности) сильно усложняют жизнь, т.к. это не просто место в памяти, а целый объект. Что сильно замедляет дело и уже промежуточный код не так сильно помогает.

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

А как тогда будет работать код

1. {
2. a=101E0B2;
3. b=202E0B3;
4. c[a]dfl[b]kj[a][b]=15
5. }

Ты заведёшь столько индексов? А как будешь представлять неплотную матрицу (в данном случае неплотный 4-х местный массив)? Хохма-то в том, что это не массив в определении Татарина, а именно новое имя. И таких квадратных скобочек может быть лимон. Да ещё и, согласно примеру, замена происходит по видимому написанию, а не по величине значения и приведения её к десятичной системе. Обрати внимание, что а имеет значение в десятичной системе, а имя должно быть образовано как c101dfl202kj101202 и эта переменная получает значение 15 с точностью две знаковые цифры. Обрати внимание, что 15.00 и 15.0 разные величины — как указано в спецификации.

Kernel3> Проблема была с devExt (не итератором - запамятовал). До цикла она не инициализировалась. Devices - некий глобальный массив, DeviceNumber - счётчик, остальные переменнные - локальные.
Хых, вообще говоря, и у тебя вариант ill formed программы. Если переменная не инициализированна до цикла, который не может быть вычислен статически (компилятором во время компиляции — сколько итераций), то возможен вариант, когда она вообще не будет инициализирована (а вдруг там сразу NULL?) (не распространаяется на глобальные переменные). Поэтому должно выдаваться сообщение об ошибке или предупреждение (в зависимости от опций компайлера и/или прагм). Вот в этом моменте у них как раз крыша и едет.

Mishka> Кстати, изначальное условие точности (не 100 циферок, а того, сколько значащих цифр и правила вычисления точности) сильно усложняют жизнь, т.к. это не просто место в памяти, а целый объект. Что сильно замедляет дело и уже промежуточный код не так сильно помогает.

Я спрашивал - Сергей написал, что этого не надо делать

Mishka> Ты заведёшь столько индексов?

это отдельный случай - и здесь конечно без поиска не обойтись

Lester> Я спрашивал - Сергей написал, что этого не надо делать

Не надо делать 100, обошлись double. А насчёт вычисления точности — я что-то пропустил? Татарин, Сергей, ау?

Lester> это отдельный случай - и здесь конечно без поиска не обойтись