OSDev

Это ветка дискуссии из соседней темы: Беседа о создании нового языка программирования (с. 9).

Хорошо. Вот один проект FastComputing, он полуживой, так как некому им заниматься, поэтому там сейчас всего 6 задач. Все они простые (не элементарные, а именно простые в моей классификации). Понимание ни одной из этих задач не потребует знаний математики более глубоких, чем дают в 11-м классе общеобразовательной школы с математическим уклоном. Я возьму свои слова обратно относительно программирования на Java, если Вам удастся получить статус Accepted по любым 3-м задачам из 6-ти предложенных. Там в списке компиляторов для отправки решения на проверку можно выбрать Java.

Возможно, для правильной реализации алгоритмов решения некоторых задач (но не для понимания сути самих задач) потребуются знания математики более глубокие, чем даются в школе, но задачи 0 и 2 и 3 и 4 - это must known для любого культурного программиста, поэтому возражения о том, что Вы не владеете математикой не засчитываются. Алгоритмы решения этих задач (которые при руках из плеч можно нормально переписать и сдать в систему) разбросаны по всему интернету. Про задачи 1 и 5 молчу, здесь нужно хорошо владеть теорией матриц и методами динамического программирования по профилю, хотя решение задачи 5 - это классика алгоритмов, но уже совсем не must known, так как реализация динамики в лоб там не пройдёт.

Ну вот, как и ожидалось, сравнение языков подменено предложением поучаствовать в созданном автором темы проекте. За предложение - спасибо, но поучаствовать желания нет. А по подмене понятий поясняю - сравнение производительности (а именно на производительность ориентированы ваши тесты) набора программ возможно ТОЛЬКО при использовании всеми участниками ОДИНАКОВОГО алгоритма. Вы же ни чуть не сомневаясь, предлагаете оценивать мои способности по поиску в сети эффективных алгоритмов, соответствующих тестам на ваших сайтах, со знаниями математиков, заточенными на минимизацию вычислительных затрат. То есть вместо объективного сравнения набора программ в составе системы "Java" против другого набора программ в составе системы "какая вам больше нравится", предлагается поддержать полуживой проект, подменяя предмет оценки из названия темы соревнованием дилетанта с математиками в выборе правильного алгоритма.

И мало того, ваше незнание систем конкурентов С простительно, но если уж вы собрались оценивать алгоритмы по вашим критериям, то хотя бы чисто для себя обратите внимание на такое скромное противоречие - в первой же задачке предлагается использовать до 2 гигабайт памяти, а Java при этом запускается в режиме -Xmx512m -Xms128m. Погуглите (как вы мне предлагаете для поиска алгоритмов), как всё же правильно запускать Java, что бы программе было доступно именно 2 Гб и сразу, а не 128мб сначала и максимум - 512мб. Так же погуглите, сколько бит использует Xeon E5620, а потом проверьте сколькибитная Java установлена на вашем тестовом компьютере. Ни чуть не удивлюсь после показанного выше незнания альтернативных систем, если вы предлагаете всему миру соревноваться с 64-битными вариантами С-кода используя 32-битную Java.

Хотя для меня в принципе интересно познать пределы возможностей Java, поэтому как-нибудь на досуге покопаюсь с перемножением матриц. Но ваш стиль общения - я буду считать вас вменяемым если вы выполните мои желания из прилагаемого "скромного" списка - ни разу не намекает на возможность получить в результате общения с вами сколько-нибудь объективный результат. И да, такой стиль способствует появлению в голове обобщений из серии "куда катится наша наука". Если критерии истины в научном сообществе так беззастенчиво подменяются хорошо если просто непониманием, то такое непонимающее истины сообщество действительно нельзя называть Научным. А если в этой подмене замешана гордыня и самомнение - ну тогда с наукой у нас всё ясно.

Это не мой проект, я только автор идеи.


Если Вам станет легче, я могу сообщить, что для задачи о перемножении матриц подходит обычный блочный метод. Размер блока можно брать от 2 до 160, во всех этих случаях программа, написанная на C++ будет укладываться в отведённое время в 32-битном режиме.


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


Никакой подмены. Просто, как я и ожидал, неопытный в классических задачах Computer Science программист считает свой инструмент подходящим везде, даже в тех сферах, где на порядок более опытный человек ему уже сообщил о невозможности его применения. Java - мёртвый язык для меня и таких как я, если хотите доказать обратное - решите хотя бы три наших тестовых задачи. Ещё раз говорю, что алгоритмы их решения восходят к must known классике, а Ваше невежество в данной области меня не интересует в качестве оправдания. Почему? Потому что Вы имели смелость пропихивать Жабу человеку, который работает в другой сфере программирования и делали это с тем упорством, будто бы разбираетесь в моей области не хуже меня. Ну а раз так, отвечайте за слова, покажите, что Вы компетентны в моей области, либо не влезайте больше с советами к тем людям, которые знают, что говорят на основе своего опыта (а Жабу я лично проверял на подобных задачах - полнейший отстой).

Далее я буду отвечать только на адекватные попытки продолжения данной темы. Доказывать что-то лично Вам желания больше не имею.

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

Приходит как-то эмбрион на стройку, и говорит:
– Ребята, вы чем гвозди забиваете?
– Молотком. – Отвечают строители.
– А шурупы и саморезы чем крутите?
– Шуруповёртом. – Уже с несколько менее скрываемым раздражением отвечают строители.
– А доски вы, простите, чем пилите? – продолжает спрашивать эмбрион, скрывая улыбку самодовольства.
– Ну пилой, ёпт, тебе чо надо-то, мужик? – Раздражаются строители.
– Я хочу предложить вам все эти действия делать с помощью нового универсального инструмента, который называется «жава»! – Тут эмбрион достал из кармана предмет неопределённой формы, затем продолжил, – обождите, вот сейчас он загрузится... – что-то трещало у него в руках и светилось то в одном, то в другом месте, – ну вот, готово.
– Чо это за по..нь? – Недоумённо вопросили рабочие, не заметив разницы между исходным состоянием предмета и полученным после обещанной загрузки.
– Это жава, она умеет всё, что вы раньше делали разными инструментами. Поначалу может быть немного непривычно, но я вас всех уверяю, что им можно делать всё и повсюду! И знаете, что самое главное? Я стал намного, ну просто-таки намного меньше ошибаться и бить себя по пальцам, когда забиваю гвозди, у меня реже адаптер соскальзывает с шурупа, когда я вкручиваю его в дерево, уже перестал случайно запиливать себе большой палец на левой руке, когда делаю первый пролил в доске.
– Да мы в общем-то подобных ошибок и не делаем.
– Да бросьте, Вы просто не знаете, насколько быстрее вас всех я могу напилить и прибить все эти доски! – Продолжал настаивать эмбрион.
– Спорим, ты гонишь? – изумились рабочие.
– Ну, давайте попробуем, давайте любой гвоздь, я покажу.
– На, держи. – ответил рабочий, бросая эмбриону кровельный гвоздь.
– Эм… ребята, это что? – возмутился эмбрион. – Я полный чайник в строительстве, и вам придётся объяснить мне, с какой стороны держать этот кусок железа и куда вбивать.
– Если ты чайник, х..и ты суда припёрся вообще?
– Я так и знал! Вы специально даёте мне задачу, которую я не могу решить, чтобы потом говорить, что моя жава не имеет перспектив в строительстве!
– Хоршо, не ной, сейчас всё покажу, как мы это делаем. Вот ондулин, вот кладёшь его на обрешётку и нужно, держа гвоздь вот так, – рабочий профессиональным движением приложил руку, - бить по нему молотком вот так, – рабочий точным движением вогнал гвоздь так, что шляпка оказалась в точности посередине верхней части волны листа ондулина, а резиновая прокладка, идеально ровно закрывала отверстие, в которое он вошёл, не помяв при этом мягкую поверхность материала.
– Эмм… – начал эмбрион, – дело в том, что жаву нельзя использовать для таких гвоздей, но можно её ещё доработать, чтобы потом стало можно.
– Ну хорошо, вот иди прибей доску к стене, там берётся обычный гвоздь на 128. – смилостивился уже просто из жалости рабочий.
– Вы плохо знаете жаву, ей нельзя забить сразу гвоздь на 128, но можно взять 4 маленьких по 32!
- Ты опух что-ли? – удивился такой глупости рабочий, – у тебя доска шириной 50, куда ты 32 вобьёшь?
– Ой, можно подумать, что Вам просто лень взять 4 маленьких гвоздя, руки что ли оторвутся?
– Ты не понял, дело не в том, что трудно забить 4 маленьких гвоздя, а в том, что они держать доску не будут!
– Не будут, потому что у Вас руки кривые, а нормально если забить, всё держаться будет, отойди, я тебе покажу.
Тут эмбрион приладил доску к балке, взял 4 гвоздя по 32 и, приложив один, долбанул им своей жавой. Гвоздь вошёл. Затем таким же образом было вбито ещё 3 гвоздя.
– Вот видите? – сказал эмбрион, – всё держ….
Он отпустил руку и доска с грохотом падая ударила эмбриона по ноге.
– ой-ой-ой! – закричал эмбрион, – подлые строители, это подстава, вы специально мне такую доску подложили, чтобы потом говорить, что жава не может забивать гвозди.
– Нет, ты сам сюда пришёл с таким видом, что разбираешься, что делать и как, сам взял доску и уверял нас, что будет держаться. Где тут подстава?
– Ага, главное сказать, что подставы не было и никаких доказательств! Хороши строители!

Рассказ основан на реальных событиях, восстановленных моим воображением по следующим цитатам из соседней темы:









...и многих других.

Очень жизненно!

Напомнило мои разговоры с адептами типовой разработки и быстрых инвестиций: "Чего там делать? Придумал, тяп-ляп набросал прототип, сваял презентацию и иди искать инвестора. Нужно только объяснить, чем твоя разработка лучше других, а твои теории никого не интересуют".

ЧСХ, все оппоненты развивали свои проекты исключительно на свои вложения, инвесторов никто привлечь не смог или не захотел.

_________________
Путь успеха Циолковского — правильно умереть

Да сжальтесь вы над бедным программистом, дайте образец на С. В конце концов, ему нужно будет сравнивать скорость с оригиналом. Пусть накодирует, и остынет со спокойной душой. Ассемблерные вставки так уж и быть - разрешены

Простите, а что с чем сравниваем? Жабу с Це или ассемблер с Це? Если вся основная логика программы реализована на ассемблере, то это сравнение именно с ним, а не с жабой или ещё чем.

По сути вопроса нужно сравнивать эффективность компиляторов. Ассемблерные вставки и всяческие intrinsics переводят сравнение в некорректную плоскость. То же самое делают подсказки компилятору о возможности использования различных версий SSE и AVX.

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

Где sum имеет 64 бита, а массивы содержат значения по 32 бита. Для проверки подобной трансляции нет нужды в заумных предложениях тов. Zealint, но можно просто сравнивать производительность С и Java вариантов одного и того же цикла, что крайне просто и наглядно. А если же начать искать самые эффективные алгоритмы перемножения матриц, то корректность сравнения обязательно пострадает, ведь ряд весьма скромных модификаций кода, реализующего один и тот же алгоритм, может привести очень большому проседанию/повышению производительности. Но даже не в этом суть, потому что все более эффективные алгоритмы сводятся к уменьшению количества умножений за счёт количества сложений. И при этом выше показанный код опять таки будет присутствовать, но операций он выполнит на сколько-то процентов меньше. Поэтому тов. Zealint-у стоит обратить на вопросы корректности своё академическое внимание, а то предложит свой сайт в более серьёзно разбирающемся в вопросах сравнения производительности сообществе - будет немного стыдно.

В общем я подобный цикл написал и получил 5.5 тактов на одно умножение и (по видимому) два сложения. То есть я не знаю, какие именно инструкции выдаёт JIT компилятор, но предполагаю, что во первых он не пользуется SSE и AVX (последнего на моём процессоре просто нет), во вторых скорее всего он реализует что-то вроде 32-битного умножения и затем при помощи связки add и adc производит накопление суммы. Регистров вроде должно хватать. Но тем не менее конкретный результат трансляции всё же непонятен, ибо попытки внесения различных модификаций приводили к не совсем очевидным результатам по скорости.

В общем при перемножении матриц размером 5000*5000 получается (расчётное) время чуть больше 340 секунд на Core 2 Duo P7350 2 ГГц, работа на одном ядре. Алгоритм простейший - три вложенных цикла. При переходе на алгоритм Винограда есть надежда опуститься к 170 секундам, при использовании подхода Штрассена вероятно получится немного больше ста секунд (кстати - при росте частоты до 2.4 ГГц Java уложится в отведённое Zealint-ом время). При использовании оптимизации в виде AVX можно получить рост скорости в разы (хотя уже можно воткнуться в предел пропускной способности канала память-процессор). При использовании только SSE рост возможен около 2 раз (хотя далее возможно ещё и параллельное сложение). Собственно именно такие результаты и получены на сайте тов. Zealint - лучшее время в 28 секунда на 2.4 ГГц процессоре наверняка получено с использованием либо intrinsics, либо inline ассемблера.

Вот такие соображения по корректности сравнения Java JIT компилятора с любым имеющимся в природе компилятором С/С++.

Эмбрион, все эти размышления - пустые декларации. На C++ без ассемблера: 6 вложенных циклов (блочный алгоритм, кубическое время счёта), около 80 секунд. Никаких алгоритмов, сложнее кубического не требуется. Если брать SSE, то можно добиться 43 секунд, ещё пока не применяя более сложных алгоритмов. Это если брать 64 бита. При 32 битах также можно написать кубическую версию, которая укладывается во время. Вы продолжаете говорить, что на Java можно чего-то добиться, не понимая реально, чего же всё-таки можно. Решение, которое работает 28 секунд, это алгоритм Винограда-Штрассена, написанный руками из плеч на одной из версий Pascal с ассемблерными вставками (дело в том, что если его написать руками не из плеч, работать будет очень и очень долго, значительно дольше наивной реализации кубического алгоритма).

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


Вообще пофиг : ) Вы не поверите, насколько сильно меня не волнует мнение "более серьёзно разбирающегося в вопросах сравнения производительности сообщества". Особенно если учесть, что это не мой проект : ) Меня волнуют только любые адекватные мнения, которые обычно могут дать люди, имеющие серьёзный и нестандартный опыт. Мнения интернет-хомячков я обычно использую в качестве примеров для своих учеников следующем смысле: "видите, ребята, вот так вот делать нельзя". Вспомните, с чего всё началось: Вы пришли в МОЮ область и намекнули, что язык Java там подходит больше. Я обещал, что ни одну простую (в МОЁМ понимании) задачу Java программист не решит на этом языке. А Вы уходите в сторону, предлагая сравнить два идентичных цикла. Не выйдет.

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