Здравствуйте, remark, Вы писали:
R>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды.
Если в твоей программе заменить #include <stdlib.h> на #include <cstdlib>, то C++ тоже обгонит Haskell.
Здравствуйте, remark, Вы писали:
R>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды. Так же можно отметить: самая быстрая реализация на Java – 7 сек.; Scala – 15 сек.; Erlang – 111 сек.; Ruby — 131 сек.; Python — 221 сек. Полную таблицу можно видеть здесь.
Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ?
Ок, тогда я могу представить этот бенчмарк как очень синтетический расчитанный на взаимодействие потоков.
Меня настораживает опасность того что этот бенчмарк будет быстрее работать реализованным однопоточно на десктопной машине, я ошибаюсь?
Оченья тяжело следить за гранью когда бенчмарк остается корректным.
P.S. Как насчет тестов с процем с боольшим к-вом ядер , от 8 и более ?
Здравствуйте, CreatorCray, Вы писали:
S>>Мы и так знаем что C\C++ это самые производительные языки. Сию статью надо в другие форумы укладывать :) CC>Ой таки не надо. Тут как раз сидят люди, которые информацию из статьи способны применить на благо. CC>А не дай б-г, эту статью увидят завсегдатаи КСВ
А мы с Шериданом кто? Но мы лучше поругаем MS Windows за кривые способы получения топологии процессоров на очень многопроцессорных системах. ;-)
Здравствуйте, minorlogic, Вы писали: M>Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ? Re[2]: Хамелеоны быстрые и очень быстрые
тут написано почему Erlang столь медленный на этой задаче, если я правильно понял, Erlang создает легковесные потоки, которые прекрасно подходят для распараллелевания вычислений, а здесь ботлнек в доступе к разделяемым ресурсам.
Здравствуйте, Exilian, Вы писали:
E>Здравствуйте, minorlogic, Вы писали: M>>Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ? E>Re[2]: Хамелеоны быстрые и очень быстрые
тут написано почему Erlang столь медленный на этой задаче, если я правильно понял, Erlang создает легковесные потоки, которые прекрасно подходят для распараллелевания вычислений, а здесь ботлнек в доступе к разделяемым ресурсам.
Так это и поражает, легковесные потоки в Эрланге не являются потоками системы, точнее не обязаны ими быть. Поэтому казалось бы что на подобных задачах Эрланг должен как минимум быть удовлетворительным.
Здравствуйте, Roman Odaisky, Вы писали:
CC>>А не дай б-г, эту статью увидят завсегдатаи КСВ RO>А мы с Шериданом кто?
Я про других завсегдатаев. Про тех, у которых любое не негативное упоминание С++ вызывает острую дисфункцию настроения мыслей и обильное разлитие желчи.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, IID, Вы писали:
IID>>А почему бы не использовать posix_memalign ?
R>Спасибо, попробую использовать, если буду делать какие-то патчи. R>Кто-нибудь в курсе, она во всех линуксах по-умолчанию? А то про тестовую машину я узнаю только после попытки сабмита.
R>
Если верить манам, то начиная с версии 2.1.91 glibc, т.е. 2000-2001 года.
Кстати респект за реализацию, и вопрос вдогонку: сильно ли будут отличаться результаты при другой привязке нитей к ядрам, и если так — почему тогда эти две группы ядер не объедены в numa-ноды, для выяснения их структуры есть удобный интерфейс в линуксе. Просто как-то логично привязываться к структуре памяти, а вот к структуре кэшей — imho перебор.
Здравствуйте, YesSSS, Вы писали:
YSS>Если верить манам, то начиная с версии 2.1.91 glibc, т.е. 2000-2001 года.
Спасибо. Может в ближайшем будущем портирую программу на С++, там попробую использовать эти функции.
YSS>Кстати респект за реализацию, и вопрос вдогонку: сильно ли будут отличаться результаты при другой привязке нитей к ядрам,
Изначально моя реализация проводила 2 встречи последовательно, т.е. использовались только 2 ядра. Когда я привязывал потоки к ядрам 0 и 1, время выполнения было 4.8 сек. Когда я привязал потоки к ядрам 0 и 2, время выполнения стало 1.2 сек. Т.е. разница в 4 раза, много это или мало — судите сами.
YSS>и если так — почему тогда эти две группы ядер не объедены в numa-ноды, для выяснения их структуры есть удобный интерфейс в линуксе.
В NUMA узлы они не объединены, т.к. это не NUMA узлы. NUMA узла характеризуются различным временем доступа к памяти, для ядер в составе Q6600 это не так, т.е. время доступа к любой памяти с любого ядра одинакового. Зато отличается стоимость взаимодействия между ядрами. На последних процессорах Intel в составе ядра так же имеются 2 HT потока, это совсем другая песня. Мешать всё это в одну кучу нельзя, т.к. структура системы/связей не однородная. Допустим есть программа, в которой потоки мало взаимодействуют между собой, но зато постоянно работают с различными объектами в памяти; для такой программы необходимо определить структру NUMA узлов, а ядра и HT потоки не интересны. В другой программе потоки постоянно взаимодействуют между собой, и этой программе уже нужно различать ядра. Другая программа производит вычисления и с фиксированной точкой и с плавающей, ей было бы полезно знать какие логические процессоры являются HT потоками-близнецами, а ядра и NUMA узлы ей не нужны.
Почему будет не достаточно введение лишь одной метрики (абстрактной «удалённости» между логическими процессорами)? Традиционная оптимизация для NUMA машин — это создание пулов памяти для каждого NUMA узла. Если мы будем знать только абстрактную удалённость между процессорами, то нам придётся создавать больше пулов, чем это необходимо. Соответственно будет больше потребление памяти и больше издержки на передачу блоков памяти между пулами. Другой пример — программа производит вычисления и с фиксированной точкой и с плавающей, для неё целесообразно проводить разнотипные вычисления на HT потоках-близнецах; если же HT потоков нет в системе, то наоборот сгруппировать вычисления по типу, т.к. однотипные вычисления работают с одними данными (допустим на одном многоядерном процессоре — целочисленные, а на другом — с плавающей точкой). Очевидно, что это не укладывается в модель лишь с одной метрикой удалённости.
YSS>Просто как-то логично привязываться к структуре памяти, а вот к структуре кэшей — imho перебор.
Это зависит.
Во-первых, различие при неправильной привязке я уже озвучил.
Во-вторых, кто-то может вам совершенно законно сказать — просто как-то логично оптимизировать IO, а вот привязываться к структуре памяти — перебор.
С т.з. производительности систему можно представить иерархически (в смысле издержек) следующим образом:
IO (disk/network) ↔ Memory ↔ Cache ↔ Processor
Первая задача при оптимизации — выявить наивысший уровень, который является слабым звеном. Почему наивысший? Потому что там можно получить наибольший выигрыш, или даже правильнее сказать — потому что только там и можно получить хоть какой-то выигрыш. Бессмысленно оптимизировать под процессор (распределение регистров, спец. команды), когда есть проблемы с IO. Бессмысленно оптимизировать требования по пропускной способности кэш↔процессор, когда требования по пропускной способности память↔кэш слишком высоки. Зато для каких-то функций обработки массивов данных самый подходящий уровень оптимизации может быть даже не кэш, а процессор.
В общем, нет такого, что всегда надо оптимизировать Х. Оптимизировать надо то, что является узким местом и за счёт чего можно получить выигрыш. Для данной задачи — это латентность взаимодействия между ядрами.
В-третьих, для некоторых задач/программ привязка к структуре памяти не даст вообще ничего, а привязка к кэшам даст. Т.е. строго говоря тут даже нет строгого отношения "превосходства" между ними, в смысле что вначале надо оптимизировать привязку к памяти и только потом — кэши.
Здравствуйте, Roman Odaisky, Вы писали:
R>>Для этого требуется маунт sysfs, которая по-умолчанию незамаунчена на линуксах.
RO>Странно, еще не видел ни одного линукса без /sys, разве что embedded.
Вот набираю у себя:
[user home]$ cd /sys
[user sys]$ ls
class
[user sys]$
R>>Насколько я знаю, Windows при нумерации логических процессоров всегда следует топологии. Поэтому там просто можно привязывать потоки к процессорам 0 и 1.
RO>Интел: «Affinity mask is a construct of the OS. Within the Microsoft Windows® XP code base, each different OS release may have an internal implementation that tries to optimize thread scheduling by the OS scheduler according to certain hardware configurations that the OS understands as that particular release was designed. To say this simply, the numerical mapping can vary even within an OS family. There is no guarantee, for example, „AffinityMask = 1; Initial APIC = 0“ must be true».
Хммм... даже не знаю, что сказать.
Моё утверждение было основано на том, что я не видел никакой документации от Microsoft на этот счёт, и не видел ни одной машин, которая бы противоречила этому.
Это тоже вроде как информация от Intel, а не от Microsoft. Хотя возможно этот человек имеет доступ к исходным кодам, или получил информацию от Microsoft. В любом случае такую гарантию (что нет никаких гарантий) дать легче всего, но это ещё не говорит, что машины с другой нумерацией процессоров есть.
Хотя там же выше человек приводит:
Windows CPU #0 -> AffinityMask = 1; Initial APIC = 0 ...
Windows CPU #1 -> AffinityMask = 2; Initial APIC = 4 ...
Windows CPU #2 -> AffinityMask = 4; Initial APIC = 12 ...
Windows CPU #3 -> AffinityMask = 8; Initial APIC = 8 ...
Windows CPU #4 -> AffinityMask = 16; Initial APIC = 2 ...
Что видимо есть реальный вывод утилиты на его компьютере...
Здравствуйте, remark, Вы писали:
R>>>Для этого требуется маунт sysfs, которая по-умолчанию незамаунчена на линуксах. R>[user sys]$ ls R>class
Значит, всё же подмонтирована, раз class есть. Посмотри еще вывод mount(1), там точно будет sysfs.
Судя по всему, речь о виртуальной машине, вот почему в /sys только class (хотя там обычно 10 поддиректорий). Так обычно бывает в Virtuozzo/OpenVZ, в то время как Xen предоставляет полномасштабную sysfs.
R>>>Насколько я знаю, Windows при нумерации логических процессоров всегда следует топологии. Поэтому там просто можно привязывать потоки к процессорам 0 и 1. R>Моё утверждение было основано на том, что я не видел никакой документации от Microsoft на этот счёт, и не видел ни одной машин, которая бы противоречила этому.
А если там 256 процессоров, то как они нумеруются? Тем более, ты сам сказал, что никаких гарантий нет, может, на экзотических платформах нумерация и иная.
Здравствуйте, Roman Odaisky, Вы писали:
RO>Здравствуйте, remark, Вы писали:
R>>>>Для этого требуется маунт sysfs, которая по-умолчанию незамаунчена на линуксах. R>>[user sys]$ ls R>>class
RO>Значит, всё же подмонтирована, раз class есть. Посмотри еще вывод mount(1), там точно будет sysfs.
RO>Судя по всему, речь о виртуальной машине, вот почему в /sys только class (хотя там обычно 10 поддиректорий). Так обычно бывает в Virtuozzo/OpenVZ, в то время как Xen предоставляет полномасштабную sysfs.
Да, речь об одной из этих виртуальных машин. Уже повод, что бы пользоваться /proc/cpuinfo.
R>>>>Насколько я знаю, Windows при нумерации логических процессоров всегда следует топологии. Поэтому там просто можно привязывать потоки к процессорам 0 и 1. R>>Моё утверждение было основано на том, что я не видел никакой документации от Microsoft на этот счёт, и не видел ни одной машин, которая бы противоречила этому.
RO>А если там 256 процессоров, то как они нумеруются?
А в чём проблема? От 0 до 255.
RO>Тем более, ты сам сказал, что никаких гарантий нет, может, на экзотических платформах нумерация и иная.
Здравствуйте, remark, Вы писали:
R>Да, речь об одной из этих виртуальных машин. Уже повод, что бы пользоваться /proc/cpuinfo.
В виртуальных машинах как-то не ставится цель выжать еще пару процентов производительности :-)
RO>>А если там 256 процессоров, то как они нумеруются? R>А в чём проблема? От 0 до 255.
Это-то понятно (разве что маску будет сложно уминать в 64-битное битовое поле), а вот в каком порядке пронумеруются — уже другой вопрос.
Здравствуйте, Roman Odaisky, Вы писали:
RO>>>А если там 256 процессоров, то как они нумеруются? R>>А в чём проблема? От 0 до 255.
RO>Это-то понятно (разве что маску будет сложно уминать в 64-битное битовое поле), а вот в каком порядке пронумеруются — уже другой вопрос.
Версии до Windows7 не поддерживают больше 32/64 процессоров. В Windows7 используются т.н. группы процессоров для обхода этого ограничения. Все легаси приложения будут назначены на группу 0, т.е. не будут использовать более 32/64 процессоров. А новые приложения могут использовать все процессоры путём использования пары (группа, маска внутри группы). Как следствие нельзя задать аффинити маску, которая содержит процессоры из разных групп; т.е. процесс/поток можно привязать только к каким-то процессорам внутри одной группы. Количество групп будет минимальным, т.е. если в системе не больше 32/64 процессоров, то группа будет только одна. В Windows7 количество групп ограничено 4-мя, т.е. максимальное кол-во процессоров 256, в следующих версиях максимальное кол-во групп будет увеличено.
Ну а по поводу нумерации, наверное всё же более корректно использовать API для установления топологии, а не зашивать её жёстко. Просто хотелось бы хоть одним глазком поглядеть на такую Windows машину, где нумерация идёт не согласно топологии.
Здравствуйте, igna, Вы писали:
I>Здравствуйте, remark, Вы писали:
R>>На момент сабмита моей реализации самая быстрая реализация была за Haskell'ем с результатом 4.59 секунд, следующая за ней — С++ с результатом 4.74 секунды.
I>Если в твоей программе заменить #include <stdlib.h> на #include <cstdlib>, то C++ тоже обгонит Haskell.
Здравствуйте, minorlogic, Вы писали:
E>>Здравствуйте, minorlogic, Вы писали: M>>>Кстати , какие причины столь тормознутой реализации на Erlang? который вроде и был задуман для таких задач ? E>>Re[2]: Хамелеоны быстрые и очень быстрые
тут написано почему Erlang столь медленный на этой задаче, если я правильно понял, Erlang создает легковесные потоки, которые прекрасно подходят для распараллелевания вычислений, а здесь ботлнек в доступе к разделяемым ресурсам.
M>Так это и поражает, легковесные потоки в Эрланге не являются потоками системы, точнее не обязаны ими быть. Поэтому казалось бы что на подобных задачах Эрланг должен как минимум быть удовлетворительным.
Т.е. проблема не в легковесных потоках, проблема в том, что взаимодействие между действительно параллельными потоками очень дорого в Эрланг. Этому будет подвержена любая программа на Эрланг, в которой процессы более-менее часто взаимодействуют между собой. А это как раз то, к чему призывает философия Эрланг — дескать процессы и обмен сообщениями легковесные, так что используйте их по полной.
Кстати, по поводу "удовлетворительного" результата с легковесными потоками. Моя реализация показывает в такой ситуации 10.4 секунды, но каждое взаимодействие есть честное переключение ядерного потока ОС (при ожидании я всегда делаю sched_yield()). Т.е. "легковесные" Эрланг потоки легче честных ядерных потоков всего на 25%, вот и судите несколько они "легковесные", и насколько разница в 25% может порождать другой стиль программирования.
Здравствуйте, minorlogic, Вы писали:
M>Ок, тогда я могу представить этот бенчмарк как очень синтетический расчитанный на взаимодействие потоков.
Я думаю, что да, такой взгляд вполне законен. Языки соревнуются в возможностях низкоуровневого взаимодействия.
С одной стороны можно сказать, что это и так понятно, что С/C++ обладает самыми развитыми возможностями, а языки типа Ruby вообще не предназначены для этого (никто не будет писать на них ран-таймы других серьёзных языков). Но с другой стороны всё равно полезно увидеть конкретные цифры, а не оперировать эпитетами. По-крайней мере можно дать ответы на 2 вопроса. Первый — некоторые языки предоставляют меньше возможностей (Java/С#), а другие совсем мало (Python), насколько конкретно они медленнее за счёт этого? Второй — некоторые языки предоставляют совсем другие модели программирования и примитивы (Haskell, Erlang), как они (эти другие модели и примитивы) сопоставляются по производительности с С/C++?
M>Меня настораживает опасность того что этот бенчмарк будет быстрее работать реализованным однопоточно на десктопной машине, я ошибаюсь?
Я думаю, что да. Я думаю, что самый быстрый вариант будет реализовать хамелеонов в стиле легковесных потоков, и применить кооперативное планирование, когда поток сам указывает на какой поток переключиться (в стиле fibers Windows), и запустить их на 1 ядерном потоке. Когда первый хамелеон приходит на место встречи, он переключается на произворльного другого; когда второй хамелеон приходит на место встречи, он переключается на первого, что бы завершить встречу. Соотв. никакой синхронизации тут не надо будет вообще.
Но хотя 2 встречи всё равно можно проводить параллельно на 2 ядерных потоках.
M>Оченья тяжело следить за гранью когда бенчмарк остается корректным.
Да, это общая проблема. Бенчмарк сам-то всегда остаётся корректным, проблема в том на сколько, в какой степени и каких ещё задач можно обобщить его результаты.
Но честно говоря, в данном случае меня это не сильно волновало. Я просто ставил цель реализовать задачу так как она поставлена.
M>P.S. Как насчет тестов с процем с боольшим к-вом ядер , от 8 и более ?
Ну на мою реализацию (так же как и на реализацию на Haskell) это никак не повлияет, т.к. она жёстко использует только 2 ядра. Большинство остальных реализаций, которые [пытаются] использовать все ядры будут работать ещё медленнее.
Резонный вопрос — как же для этой задачи получить выгоду от большего числа ядер? Ответ — никак.
