Что тут не понятного? ФЯ по Гапертону (и тебе, в общем-то) это запрет на модификацию переменных. А это деградация функциональности и больше ничто. Этот запрет не даст никаких приемущество с точки зрения реализации алгоритмов. Никакие паттерн-матчинги от этого не зависят. Никакие функции высшего порядка тоже. Это просто запрет ради запрета. Он яко бы должен привести к гипотетическому упрощению программирования. Но по жизни, как говорится рулят, ковровые бомбордировки и танковые клинья и еще этот, как его? А, гриб Сарумяна. То есть рулят отладчики, IDE, визуальные дизайнеры и т.п.
...
И вообще, большой вопрос что считать функциональным, а что императивным. Лично я считаю фунциональным стиль программирования в котором программист старается использовть вычисление выражений вместо выполнения инструкций. Гапертон же тут рядом заявил, что если в программе используется модификация переменных, то это уже "императивщина" (таки оскорбление какое-то ).
Так вот можно без проблем писать очень компактный и выразительный код во всю используя модификацию переменных. И программа от этого сложнее не или непонятнее не станет. Так что если определять ФП как это делает Гапертон, то ФП вообще мало чего дает.
...
L> Это новый взгляд на проблему и именно с этой точки зрения я рассматриваю оспариваемый тезис. Собственно мое мнение можно читать как "объектно ориентированный взгляд на проблему имеет оверхед по сравнению с функциональным".
А я считаю это мнение заблуждением. Ну, что же поделаешь?
VD>>А каковы тогда критерии отнесения чего-то к ООП или императивному программированию (ИП)? Ведь ООП код может быть функциональным по сути, а может быть императивным. Как же быть?
L>Что такое функциональный ООП? Это использование ОО и функциональщины в одном флаконе? Если да, то нам не о чем спорить.
Тут г. Гапертон выразил мысль, что главное в ФП это "immutability". А используя ООП я могу сделать класс immutable или mutable. Отличный пример реализация класса строк в std::C++ и в Яве. Пользуясь определением Гапертона, я выбирая реализацию класса делаю выбор между императивным и функциональным дизайном. Так?
Re: Immutable data structures are the way of the future in C
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, nikov, Вы писали:
N>>Eric Lippert, один из разработчиков C#, пишет в своем блоге.
N>>
N>>Immutable data structures are the way of the future in C#.
VD>Интересно, когда я говорил о том же саом, то тут меня чуть ли не закевали.
Нет, ну согласись, что у тебя тут сложилась репутация ктулху, просыпающегося от любого ключевого слова немерла. А когда ктулху просыпается — его ведь мочат все, кому не лень...
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Gaperton, Вы писали:
G>>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. S>Погоди, тут я чего-то не понимаю. Мы говорим про thread context switch или про что? S>Переключение потока, вроде бы, тоже не сахар. Поскольку у потока как минимум свой стек, переключение нарушит локальность и с высокой вероятностью приведет к сбросу кэша. А это опять сбегать в основную память.
Нет, речь, разумеется, не о переключении контекста. Аппаратный мультатрединг работает так.
У тебя в одном процессорном ядре есть, допустим, один конвейр и кластер арифметики, но 4 независимых копии регистрового файла, и четыре независимых program counter. Конвейр ядра при этом крайне простой — он может выдавать одну инструкцию за такт. На каждый такт ядро выбирает инструкцию по другому program counter. Таким образом, у тебя 4 независимых потока выполнения, переключающихся на каждом такте по кругу, без какого-либо оверхэда — выглядит это для софта как 4 независимых ядра, на самом же деле аппаратно это одно ядро. При этом, потоки могут быть в двух состояниях — готовы к выполнению, и не готовы к выполнению. Поток не готов к выполнению, если он ждет какого-нибудь события, в частности (но не исчерпывающе):
1) Завершения конвейеризованной арифметической операции, например целочесленного умножения или деления, или операции с плавающей запятой.
2) Ждет, пока завершится операция с памятью при случае промаха в кэш.
3) Ждет когда прочухает синхронизация.
По кругу переключаются только готовые к выполнению потоки.
Зачем так делать? Затем, что данная схема позволяет очень дешевым образом по сравнению с суперскалярными процессорами поддерживать исполнительный конвейр ядра в наполненном состоянии, и эффективно бороться с задержками в интерфейсе с памятью. Промах в кэш уже не так страшен — размер кэша уже не так критичен для производительности как при суперскалярном дизайне, поэтому размер кэшей L1 можно уменьшить. Задержки при обращении в память уже не так критичны — поэтому можно совершенно спокойно делать объединенный кэш L2. Всю цепочку обращения к памяти можно удлиннить и конвейеризовать — и все будет в порядке, чтобы компенсировать негативное влияние задержки достаточно увеличить количество аппаратных потоков.
Второй положительный момент — и это используется в ниагаре 2 — увеличив количество потоков можно хорошо загрузить конвейеризованную плавающую запятую. Вторая ниагара — один из самых быстрых процов в мире на данный момент.
Третий положительный момент — при таком дизайне существенно сокращается площадь кристалла для одного ядра, и их можно засунуть в кристалл МНОГО. Все анонсированные процы всех производителей, в которых большое количество ядер, будут по принципам архитектуры и свойствам напоминать Ниагару. А именно — очень простые ядра single-issue, с большим количеством аппаратных потоков. Почитай вот это
и вот это http://en.wikipedia.org/wiki/UltraSparc_T1
G>>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. S>Чего-то я фундаментально не понимаю.
А теперь?
Re[6]: Immutable data structures are the way of the future i
Здравствуйте, CreatorCray, Вы писали:
И что? Счастье-то где?
Поясняю: иммутабельность ценна не сама по себе, а множеством классных последствий, которые она обеспечивает. В частности, потокобезопасностью по низкой цене.
А здесь мы что имеем? Нельзя одновременно делать Push в двух разных потоках, потому что оба должны потрогать счетчик сцылок. Это очень плохо отразится на NUMA.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: Immutable data structures are the way of the future i
[]
VD>const же в С++ — это, как говорится, "почти ничто". Это атрибут переменной (о const на фунции вообще не говорим, так как это из другой оперы), который ко всему прочему элементарно обойти. Сделать какие либо оптимизации на основании знания о const-стантности или как-то другим образом использовать это явление скажем при многопоточном программировании нельзя.
Вполне себе можно. Компайлер может оптимайзить "настоящие" константы.
[]
Immutable data structures are the way of the future in C#
G>Третий положительный момент — при таком дизайне существенно сокращается площадь кристалла для одного ядра, и их можно засунуть в кристалл МНОГО. Все анонсированные процы всех производителей, в которых большое количество ядер, будут по принципам архитектуры и свойствам напоминать Ниагару. А именно — очень простые ядра single-issue, с большим количеством аппаратных потоков.
Чуть подробнее о том, почему будут делать именно так.
Для начала — простой принцип, позволяющий сравнивать разные архитектуры.
1) Как вычисляется пиковая производительность процессора. Во-первых, интересны в этом деле полезные операции, то есть арифметика. С этим все просто — это тактовая частота умноженная на количество всех АЛУ на кристалле, которые могут работать в параллель.
2) Реальная производительность определяется процентом загрузки АЛУ (опять же — потому, что нас интересуют только полезные операции). Процессорное ядро, кэша, интерфейс с памятью — это обвязка, случащая цели эффективно нагрузить АЛУ полезными операциями. Простои АЛУ должны быть минимизированы, идеально — АЛУ должно выдавать результат на каждом такте.
3) Внимание — самое интересное. Какая архитектура будет лучше? Та, которая при минимальной площади сможет нагрузить АЛУ по максимуму. Почему так? Потому что кристаллы имеют ограниченную площадь (она связана с ценой и процентом выхода годных), и чем больше [хорошо нагруженных АЛУ мы туда поместим, тем больше будет реальная производительность. Поэтому, лучшей будет та архитектура, которая при прочих равных будет давать меньшую площадь управления и обвязки вокруг АЛУ. Это автоматически означает большую производительность процессора.
Традиционно до последнего времени это решалось подъемом тактовой частоты (за счет углубления конвейра процессора и улучшения техпроцесса) и суперскалярным выполнением (возможностью выдавать несколько инструкций на АЛУ (или, если точнее, кластер арифметики) одновременно за один такт. В чем тут проблема? Для того, чтобы заполнять дырки в конвейре при промахе в кэш, надо иметь
1) большой размер кэша инструкций и большое "окно просмотра", в котором мы ищем независимые по регистрам инструкции, фактически восстанавливая граф зависимостей по регистрам. Процессор параллелит вашу программу на лету — современные процы имеют пять каналов арифметики, то есть умеют выдавать до 5 инструкций за такт.
2) Внеочередное выполнение инструкций. Инструкции должны выдаваться на АЛУ в порядке готовности аргументов, а не в том порядке, в котором они идут в программе.
Внеочередное выполнение, которое позволяет компенсировать задержки, создает массу неочевидных на первый взгляд технических проблем — например, точная обработка исключений, дорогое переключение контекста, неупорядоченная запись в память (это, в принципе, хорошо с одной стороны, но это выходит боком при синхронизации параллельных процессов).
Далее — чем быстрее становится процессор, тем больше будет разница в быстродействии процессора и внешней памяти. Память то у нас быстрая, но у нее офигенная латентность по выполнению запросов. Поэтому, приходится увеличивать размеры кэшей и окон просмотра. Короче говоря, управление процессора при росте проиводительности становится все сложнее и сложнее, оно пухнет, и занимает все больше площади.
Сан пошел другим путем. Как решить проблемы высокой латентности памяти, и при этом максимально упростить управление и обвязку? Выход — аппаратная многопоточность. Полный отказ от суперскаляра. Максимально простое управление — как в микропроцах начала 90-х годов. Такой подход позволяет увеличить относительную площадь АЛУ к управлению и обвязке на кристалле, одновременно — снизить требования к размеру кэшей, снизить энергопотребление и тактовые частоты, и в результате снять с кристалла той же площади существенно больше полезных операций в секунду. Короче, такой подход решает практически все проблемы. Только он позволяет иметь на кристалле в районе десятка процессоных ядер (видимых софту как сотня, потому что в каждом из них десяток аппаратных тредов). Но создает новую — придется научиться писать сильно параллельные программы. Но придется привыкать — данная архитектура является оптимумом с точки зрения разработчиков микросхем. Ничего лучше по удельной производительности на квадратный миллиметр человечество пока не придумало.
Хотя, есть еще reconfugurable computing, находящийся в данный момент в зачаточном состоянии — он выстреллит лет через 7-10.
И еще есть stream computing, который, на самом деле уже здесь. nVidia уже продает Tesla — суперкомпьтеры построенные на потоковой модели, ну и Cell тут припоминали под видом nccNUMA, а на самом деле Cell конечно же тоже заточен на потоковую обработку. Stream computing имеет хороший шанс попасть в мйнстрим уже в течении 2-3 лет. Это радикально другая парадигма программирования, там вообще надо по другому писать.
Средства параллельного программирования должны быть радикально упрощены. Что и произойдет в ближайшем будущем — мы сейчас находимся в переломной точке.
А вы, пнимаешь, хромой гепертрединг у P4 вспоминаете. Да технологии суперкомпьютеров 20-летней давности. Времена, когда передовые идеи опробировались на суперкомпьютерах безвозвратно ушли. Сейчас основным источником идей являются 3D видеоускорители, сделавшие за последние 10 лет прорыв в удельной производительности на миллиметр кристалла (stream computing). Еще один прорыв удалось сделать Sun — сейчас в интелах и АМД лихорадчно изучают дизайн Ниагары, выложенный под GPL. Процессоры будущего не будут иметь ничего общего со старыми суперкопьютерами. Они будут проще архитектурно, и будут совершенно по другому программится.
Re[4]: Immutable data structures are the way of the future i
Здравствуйте, CreatorCray, Вы писали: CC>Т.е. immutable это неснимаемый const для данных? так?
Я не помню семантику const для нестатических полей. Она проинициализировать поле в конструкторе позволяет?
Если да — то всё более-менее в порядке, это оно. Более-менее потому, что без GC эта штука практически бесполезна.
Я имею в виду экономию памяти за счет раздельного владения. В статье речь идет о структуре ImmutableStack, которая ведет себя достаточно забавным образом: у нее Push и Pop делаются за время O(1), и при этом обладают неразрушающей семантикой.
На первый взгляд, такую же структуру реализовать на С++ легко. Увы — если место размещения оператора new совершенно очевидно, то оператор delete совершенно неясно когда вызывать.
Если мы породили из одного стека несколько различных стеков, то их общий "хвост" должен жить до тех пор, пока жив хоть кто-то из них.
На С++ это достижимо только путем подсчета ссылок, но для него нужно заводить счетчик, и структура сразу же перестанет быть иммутабельной.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[6]: Immutable data structures are the way of the future i
Здравствуйте, Константин Л., Вы писали:
КЛ>Вполне себе можно. Компайлер может оптимайзить "настоящие" константы.
Резюме
Вера в то,что ключевое слово const помогает компилятору генерировать более качественный код, очень распространена. Да, const действительно хорошая вещь, но основная цель данной задачи — показать, что предназначено это ключевое слово в первую очередь для человека, а не для компиляторов или оптимизаторов..
Когда речь идет о написании безопасного кода, const — отличный инструмент, который позволяет программистам писать более безопасный код с дополнительными проверками компилятором. Но когда речь идет об оптимизации, то const остается в принципе полезным инструментом, поскольку позволяет проектировщикам классов лучше выполнять оптимизацию вручную; но генерировать лучший код компиляторам оно помогает в гораздо меньшей степени.
ASIDE: Immutable data structures are the way of the future in C#. It is much easier to reason about a data structure if you know that it will never change. Since they cannot be modified, they are automatically threadsafe. Since they cannot be modified, you can maintain a stack of past “snapshots” of the structure, and suddenly undo-redo implementations become trivial. On the down side, they do tend to chew up memory, but hey, that’s what garbage collection was invented for, so don’t sweat it. I’ll be talking more about programming using immutable data structures in this space over the next few months.
Чего, собственно, хотелось бы и в Java. И что, в принципе, тоже обосновано. Давно уже читал статью, но насколько помню, там та же аргументация: Теория и практика Java: Изменять или не изменять? Неизменяемые объекты могут значительно облегчить вашу жизнь. Уже сейчас в Eclipse чистильщик исходного кода по умолчанию автоматически расставляет атрибут неизменяемости переменной или поля класса (модификатор final) везде, где встречает сущность по факту используемую как неизменяемую; в итоге смотришь, количество immutable-переменных значительно превышает количество mutable. Встает законный вопрос: почему по умолчанию все изменяемо, может сделать наоборот: по умолчанию сущности неизменяемые, а если очень уж нужно, указывай специальным модификатором — как, к примеру, сделано в Nemerle/Scala.
Re[8]: Immutable data structures are the way of the future i
Здравствуйте, Константин Л., Вы писали: КЛ>Не понял про вред. Или ты в свете immutability?
Да. Понимаешь, тут некоторые участники дискуссии путают отсутствие зависимостей, гарантированное отсутствием модификаций, со словом сonst. Если я на сарае напишу const, это не сделает лежащие в нем дрова неизменяемыми.
Это то же самое, что полагать, что маскировка обращения к глобальной переменной за доступом к приватному нестатическому члену класса избавит от проблем. Типа раз мы в коде пишем this->setMap(...), то всё уже в порядке, хоть этот setMap по прежнему пишет в static CMap* g_map.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Gaperton, Вы писали: G>>Кстати, не объяснишь мне, какой такой всем очевидный вред есть от mutable? G>>И каким именно образом он у нас "для обмана трудящихся масс" предназначен? S>Поясняю еще раз: преимущества в многоядерной среде есть не у константных, а у иммутабельных структур. У некоторых людей при взгляде на ключевое слово const может возникнуть иллюзия того, что соответствующий метод не нуждается в синхронизации. Ан нет — внутри него есть модификация mutable.
Поясняешь? У некоторых людей? Если метод нуждается в синхронизации, то она будет у него внутри. И он будет помечен комментарием как thredsafe. Снаружи ты синхронизацию все равно не навесишь, ее надо внутрь прятать. Это раз.
Вот это — то, что на самом деле в скором будущем обеспечит преимущество в многоядерной среде. А "иммутабельные" структуры — лоховство. У тебя на одной иммутабельной очереди, которая реально полезна для синхронизации и передачи данных в отличии от стека, которая называется Okasaki Queue и чуточку более сложна чем лоховской стек, и над которой ты думать отказался, оверхэд будет в разы по сравнению с нормальной лок-фри реализацией очереди, не говоря уже о худшем случае ( О(N) она в худшем случае дает, у нее только среднее O(1) ).
Так что хватит "обманывать трудящиеся массы".
G>>ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете. S>Никакой константной семантики у него нету.
Есть у нее "чистая" семантика. Поди людям в декларативном программировании объясни, что чистой семантики здесь нет . Увидишь, что будет.
G>>Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику. S>Откуда взялась чистая семантика в коде, который меняет глобальное состояние? Для чистой семантики вам, функциональщикам, придется передавать (seed, state) в каждый вызов.
Ты нас, функциональщиков, функционалить не учи . Для чистой семантики нам, функциональщикам, достаточно не заботится о порядке вызовов, и иметь "прозрачность по ссылкам". Что в данном случае дает случайная семантика самой функции.
S>Иначе вы будете обязаны выполнять синхронизацию внутри этого "чистого" метода. А то значения, случайно генерящиеся в параллельно исполняемых потоках, будут волшебным образом коррелировать. Если об этом знать, то можно сразу выделить по генератору на поток, и избежать race condition. Но ключевое слово const прячет он нас mutable природу этого генератора, и мы удивляемся, почему это у нас четыре ядра пашут не быстрее двух.
Знаешь, я могу в TLS состояние этой штуки хранить, вообще-то. Так, к слову. И будут у меня четыре ядра пахать как надо, ага.
А ты, прежде чем говорить об "иммутабельных структурах", для начала почитал бы хотя бы про окасаки кью. Чтобы знать, о чем говоришь, и представлять, на какой именно performance penalty ты налетишь при их применении. Также, тебе, и автору этой вашей статьи, не помешало бы знать, что без "ленивых вычислений" реализуется эффективно очень небольшой класс "иммутабельных структур", которого особливо для работы не хватит. Упражнения для мозга полезны — почитай диссертацию Окасаки. А именно, ничего, кроме деревянного дерева да очереди (и то и другое с хорошим оверхэдом, да и то — требует специально заточенного аллокатора для хорошей работы, в котором еще надо будет те же самые проблемы синхронизации половить, о которых ты забыл) ты по большому счету не сделаешь.
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
На посмотри.
G>>Обратите внимание на пример номер 2. Мы делаем чистую функцию — которая вычисляет некоторое значение без побочных эффектов — не меняя состояние системы (т.е. ее возвращаемое значение целиком и полностью определяется значениями ее аргументов). Мы разумеется сразу помечаем ее как const. Но она однако тормозит иногда, при некоторых сочетаниях параметров, и мы решаем всунуть внутрь ея кэш. Который, разумеется, будет у нас mutable. При этом, семантика нашей функции останется "чистой", все в порядке. S>Хороший пример. С кэшем опять то же самое — скрытое состояние, которое нужно синхронизовывать. Вы выполняете запись в структуру, и либо там стоит InterlockedExchange, либо у вас начинаются проблемы с нарушением целостности.
А если у меня внутри локфри-структура данных для кэша, что тогда?
G>>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет. S>InterlockedIncrement все еще на пару порядков медленнее обычного инкремента.
Рекомендую прекратить вводить "трудящиеся массы" в смущение. Это одна процессорная инструкция, которая в случае нескольких ядер на общем кэше (например, как в проце XBox360) не имеет никакого оверхэда. В случае, если кэшей несколько (их в реальности будет мало — разработчики процов стараются их объединять) то тогда надо будет слазить в соседний кэш. Это не более чем несколько накладных тактов. Фигня полная, учитывая, что современные процы либо суперскалярные, либо мультитредные (на фоне этой операции они преспокойно продолжат свою работу, либо текущего, либо очередного треда). Так что не надо пугать людей зазря.
Для "трудящихся масс" — делаем быстрый атомарный счетчик на x86. http://www.codemaestro.com/reviews/review00000104.html
S>Кстати, не все примитивы синхронизации требуют режима ядра. Захват critical section традиционно строится на interlocked операциях в user mode.
Конечно, дык как мы выяснили можно и вообще без них .
Re[2]: Immutable data structures are the way of the future i
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, nikov, Вы писали:
N>>
N>>Immutable data structures are the way of the future in C#.
CC>Я туплю или это аналог const из С++?
Нет, т.к. конст в плюсах обходится (слабая там типизация, увы), да и это модификатор данных, в плюсах же и кода тоже. Т.е. смысл хоть и похожий, но несколько разный.
Re[4]: Immutable data structures are the way of the future i
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, Курилка, Вы писали:
CC>>>Я туплю или это аналог const из С++? К>>Нет, т.к. конст в плюсах обходится (слабая там типизация, увы), да и это модификатор данных, в плюсах же и кода тоже. Т.е. смысл хоть и похожий, но несколько разный. CC>Т.е. immutable это неснимаемый const для данных? так?
Типа того. Имеется ввиду, что компилятор может полагаться на неизменяемость, что открывает простор для оптимизаций.
Re[8]: Immutable data structures are the way of the future i
Здравствуйте, Gaperton, Вы писали: G>Ничего страшного мы тут не имеем. G>1) У тебя разных счетчиков ссылок столько, сколько разных элементов в структуре данных — коллизий будет немного.
Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука. G>Реально — трогает разделяемые данные другой поток ровно один раз — при первой модификации стека. И все.
Это почему еще? Напоминаю, что из одного стека можно получмть сколько угодно стеков. G>И далеко не факт, что налетит на коллизию. Не слишком страшно, правда? Тем более, что в случае NUMA тебе надо по-любому очень аккуратно к распараллеливанию подходить, выделяя слабосвязные по данным фрагменты. Скажем, ты уверен, что общий хип будет вообще хорошо рабоать при NUMA?
Скажем, я уверен, что здесь можно использовать heap-per-thread. Тогда создание нового стека вообще не будет использовать никакую синхронизацию. G>2) От хотя бы однобитного счетчика ссылок вряд-ли кто откажется в данной ситуации — уж очень он здорово поправляет здоровье отца русской демократии — сильно разгружается GC.
Совершенно не представляю себе, чем бы здесь помог однобитный счетчик ссылок.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[6]: Immutable data structures are the way of the future i
Здравствуйте, Gaperton, Вы писали: G>Это полная фигня.
Можно раскрыть это утверждение? Я не понял, к чему именно относилось "фигня" и что она означает. G> Попробуй лучше сделать ImmutableQueue. И чтобы push и pop было за О(1). Хорошее управжнение для мозга, ну, и изобретешь заново Okasaki Queue — тоже дело. .
Я не ощущаю какой-то потребности в упражнениях для мозга.
G>На второй взгляд, такую же структуру на С++ так же легко, как и на первый. Эта структура делается однонаправленным списком. Хвост которого может указывать на начало или середину другого списка.
Это очевидно, потому что именно это описано в статье. G>В узлах делаешь счетчик ссылок. И все.
Совершенно верно — "и всё". И теряем возможность создавать списки без блокировок. G>Можно делать хитрее — для экономии памяти применять однобитныесчетчики ссылок — техника оптимизации, которая применялась еще в древних лисп-машинах.
А можно мне рассказать про эти однобитные щетчики ссылок, и как они помогут выполнять детерминистическое освобождение памяти? G>Ага. И что интересно — циклов нет, обрати внимание.
И? G>Ну, и это можно делать, конечно же, не только подсчетом ссылок. Можно тупо аллокатор перекрыть, и вообще сделать для них честный GC. Это раз.
Честный GC? В С++? Вручную? Нет, это конечно возможно; но я бы так делать не стал. Дешевле использовать пригодную для этого платформу. G>Как раз на С++ структура и не перестанет быть иммутабельной, если завести mutable счетчик ссылок. mutable как раз для таких ситуаций и предназначен, и никакого вреда кроме пользы от него не будет. Это, собственно, два.
Не надо путать божий дар с яичницей. mutable предназначен для обмана трудящихся масс, и вред от него очевиден. Процессор обмануть не удастся — для него нет ни mutable ни const; а есть жосткая реальность — необходимость синхронизации счетчика ссылок, который вы заботливо впендюрили.
Однобитный счетчик синхронизовывать не обязательно, но он всё равно требует GC. G>Ну и три. Функциональное программирование, я вижу, идет в массы семимильными шагами. Скоро, глядишь — через годик, заговорят об Окасаки, ленивых конструкторах, и бесконечных структурах данных. Любопытно.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: Immutable data structures are the way of the future i
Здравствуйте, CreatorCray, Вы писали:
CC>Обоснуй плз, ибо выше по ветке выяснили, что таки да, аналог const для данных.
Дык, я больше поприкалываться над постоновкой вопроса хотел. Как говорится, что спросил, то получил.
Что же по делу, то тебе уже тут отвечали, но если хочешь, то могу попробовать донести эти мисли более доходчиво.
Неизменяемость о которой идет речь — это свойство объектов (можно даже сказать класса объектов). Более того — это свойство о котором есть (должна быть) информация в метаданных, а стало быть, это свойство о котором знает рантайм (CLR, например). Причем свойство это неприложное, т.е. его нельзя обойти.
Это позволяет рантайму и компиляторам выполнять разного рода оптимизации и во многих случаях получать более простые решения. Например, их можно безопастно разделять между разными потоками при этом не делая ни каких блокировок.
const же в С++ — это, как говорится, "почти ничто". Это атрибут переменной (о const на фунции вообще не говорим, так как это из другой оперы), который ко всему прочему элементарно обойти. Сделать какие либо оптимизации на основании знания о const-стантности или как-то другим образом использовать это явление скажем при многопоточном программировании нельзя. Это всего лишь некое средство программрования в духе С++. В С++ оно несомнее позволяет избежать некоторых ошибок, но к сожалению, глобальных выгод не дает.
Собственно концепция незименяемых переменных в ФЯ (ФЯ потому что в С++ константность можно обойти и она немного другая) в купе с неизменяемыми объектами (о чем тут шла речь) являются взаимодополняемыми (а не замещающими). С++ же просто скверно спроектированный язык в котором интересные идеи, которые автор пытался привнести в язык, нивелируются откровенно слабой базовой подготовкой автора и стремлением скрестить езжа с ужом (С-шные анохранизмы с идеями вроде типобезопасности).
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Sinclair, Вы писали:
S>Не надо путать божий дар с яичницей. mutable предназначен для обмана трудящихся масс, и вред от него очевиден. Процессор обмануть не удастся — для него нет ни mutable ни const; а есть жосткая реальность — необходимость синхронизации счетчика ссылок, который вы заботливо впендюрили.
Кстати, не объяснишь мне, какой такой всем очевидный вред есть от mutable? И каким именно образом он у нас "для обмана трудящихся масс" предназначен?
ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете. Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику.
Обратите внимание на пример номер 2. Мы делаем чистую функцию — которая вычисляет некоторое значение без побочных эффектов — не меняя состояние системы (т.е. ее возвращаемое значение целиком и полностью определяется значениями ее аргументов). Мы разумеется сразу помечаем ее как const. Но она однако тормозит иногда, при некоторых сочетаниях параметров, и мы решаем всунуть внутрь ея кэш. Который, разумеется, будет у нас mutable. При этом, семантика нашей функции останется "чистой", все в порядке.
Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.
Бенчмарки SPEC составлены из реальных программ. Так всегда было, и так всегда будет. Это не синтетика. Они более объективны, чем запуск программы Х дядей васей.
G>>Что-то я не понимаю, а чем то отличается от обычной памяти в любом современно многоядерном проце? У тебя и в ниагаре есть общая память, но доступ к ней тоже тебует дополнительных действий. Тот же самый MEMBAR надо выставить. Можешь и не высталвять пожалуйста. Когерентность кэшей L1 практически нигде автоматом не поддерживается, знаешь ли, это технически сложно, и дает большую просадку даже для двух ядер. Везде надо специальные инструкции выдавать. C>nccNUMA отличается тем, что у нас явно выделена локальная память. Причем есть возможности ее явно синхронизировать с "общей" памятью. Точнее, "общая" память формируется из локальной памяти каждого ядра.
C>Соответственно, работа по поддержанию когерентности уже ложится на программиста.
У нас 8 ядер, у каждого из ни локальный L1 кэш, который будет синхронизоваться с общим кэшом L2 только при указании программистом инструкций типа MEMBAR. Еще раз повторю вопрос — в чем разница?
C>>>Ты закон Мура помнишь? По прогнозам, он будет работать до 2015 года минимум. Если взять сегодняшний Core Quatro, то к 2015 он как раз станет где-то Core 64 просто благодаря увеличению плотности. Ну а дальше возможно будут многослойные ядра и прочая магия. G>>Закон мура перестал работать примерно в 2003 году. Я еще полтора года назад в свои презентации графики вставлял, которые это показывают. Посмотри на графики роста тактовой частоты и как они кореллируют с техпроцессом — не растет уже тактовая частота, проблемы с этим. Не заметил, что частоты у процов понизились? C>Ай-ай-ай. В законе Мура нет ничего про тактовую частоту, а есть про плотность транзисторов. В первом приближении можно считать, что можно наращивать количество ядер пропорционально количеству транзисторов.
Законов Мура несколько штук. Его относят и к тактовой частоте — до 2003 года он соблюдался.
G>>Core 64 ты утончением техпроцесса не получишь. Можешь просто посчитать, насколькр больше таких ядер влезет на техпроцесс 20нм, если сейчас core 2 duo делается на 65 нм. Мало запихать в один кристалл много ядер. Надо решать проблемы общего доступа к памяти (количество ног у микросхем не подчиняется закону мура, извини), суметь накормить данными эти ядра, и решить вопросы синхронизации. Суперскалярные процы типа Core Duo будут иметь большие проблемы при увеличении количества ядер. C>Почему-то мне кажется, что инженеры в Intel'е найдут решения этих проблем. Есть у меня вот такая железная уверенность, ну может будет не 64-ядерный, а 32-ядерный Core 32.
C>Собственно, четырехсокетный сервер с Core 2 Quadro уже дает нам 16 ядер.
Речь, разумеется, идет о количестве ядер на одном кристалле. А так можно договориться и о том, что 10 стоек по 10 материнских плат уде дают нам 100 ядер.
G>>Во первых, ты не прав. out-of-order совершенно не нужен при многопоточном дизайне проца — они будут только мешать друг другу и не будет никакой пользы. Это взаимоисключающие вещи, поэтому собственно гипертрединг и сосет. Суперскаларное выполнение при этом вводить вполне можно (выполнять подряд идущие инструкции впараллель) — но инструкции переупорядочивать глупость. C>КАК еще ты добьешся увеличения однопоточной производительности?
Все способы повысить однопоточную производительность двадцать раз за последние 20 лет перепробованны и известны:
1) Увеличить количество инструкций, выполняемых за такт, и параллелить программу на лету (суперскаляр). Сдерживающие факторы — многопортовый несинтезируемый регистровый файл, площадь которого квадратично зависит от количества портов, и который дизайнят в транзисторах. Промахи в кэш и блокировки лечатся увеличением кэша, увеличением окна просмотра (дорогая схема с элементами ассоциативной памяти, которая к тому же жрет энергию и греется), а также добавлением out-of-order execution который позволяет арифметике накладываться на ожидающие событий команды, а также арифметика может обгонять друг-друга чтобы равномерно нагрузить кластер АЛУ (что вызывает жопу при точной обработке исключений, и тянет за собой переименование регистров = увеличение количества физических регистров + дорогая ассоциативная схема переименования + байпас надо тянуть — а он жрет площадь также квадратичным образом от количества регистров и количества каналов арифметики). Далее — ты наверно в курсе, что память у нас виртуальная, и надо транслировать адреса из виртуальных в физические. Так вот, очень интересные штуки появляются, когда это принимаешь во внимание (в учебниках такие тонкости не пишут). У тебя каждая инструкция load и store может выбросить exception, что режет паралеллим в наивных реализации суперскаляра. Чтобы с этим бороться, вводят раннее вычисление физических адресов и кэш TLB.
Короче, в суперскалярных процах крайне тяжело сделать реально большое количество инструкций за такт. Чем больше каналов арифметики, тем больше нужно кэшей, окна просмотра, тем выше площадь байпасов и регистрового файла, и тем больше получается задержка в управлении. Площадь проца растет примерно квадратично от количества каналов в суперскаляре.
2) Увеличить тактовую частоту. Есть один-единственный надежный способ это сделать — углубить конвейр. Будем грется и энергию жрать, но перформанс выжмем. Однако, толку в этом будет ноль, если не поддерживать этот длинный конвейр в наполненном состоянии. А это на однопоточной программе — challenge. Вот тут и начинаются танцы с бубном. Огромные таблицы и навороченные алгоритмы предсказания переходов. Обязательный out-of-order. Еще больше глубина окна просмотра — сотни инструкций будем просматривать на предмет выполнения впараллель, не дай бог конвейр собьется. Спекулятивное выполнение на удачу замутим — если чо отменим выполнение инструкций. Разумеется, надо опять кэш раздуть — а то плохо будет, промахи в кэш сведут нам на дерьмо длинный конвейр.
Короче, подъем тактовой частоты на одном потоке тоже дорогого стоит. И реально — ты со всеми этими фокусами затрахаешься загрузку конвейров даже в районе 50% поддерживать. Реальная производительность будет от пиковой в несколько раз отличаться.
Есть конечно еще VLIW — который казалось бы решает кучу проблем. На бумаге в основном. Там получается огромный регистровый файл, чудовищный по размерам байпас без которого вливу ваще никак, длиннющие связи, и как результат — низкие частоты. И тоже нефиговая площадь. Единственное серьезное преимущество VLIW на практике — низкое энергопотребление. А жопа вся там из-за того, что обращения в память должны быть с детерминированными задержками — компилятро должен их рассчитать статически. Если это не соблюдается (хрена лысого это будет на современной памяти типа DDR соблюдаться, она по логическому устройству сложнее жестких дисков), то весь красивый VLIW начинает сосать. В результате — VLIW массово применяется только для сигнальной обработки — работает на внутреннем буфере микросхемы.
Вот так. Аппаратый мультитрединг — решает эти проблемы. Главная фишка в нем, разумеется — это полная и безоговорочная победа над высокой латентностью памяти. Его можно комбинировать с суперскалярным выполнением, скажем, двух инструкций, идущих подряд, это нормально. А вот out of order тут уже лишний. Почему так. Допустим у тебя 8 аппаратных потоков. Все эти 8 команд — уже независимы по регистрам — они работают на разных регистровых файлах, их можно выполнять впараллель при условии задействования разных каналов АЛУ. Тебя не волнует, в каком порядке они пойдут по конвейру — да в любом (попробуй добавить сюда в уме out-of-order, и спроектируй простой проц, посмотри, что получится и что ты от того выиграешь. По другому ты не поймешь). Если одна из этих 8 команд зависнет на ожидании — конвейр не встанет, следующие инструкции будут братся из других потоков и подаваться в конвейр. Все — конвейр у тебя наполнен — безо всяких окон просмотра, внеочередного и спекулятивного выполнения. Предсказывать переходы можно, но так как нам не страшен промах предсказания (конвейр не остановится), то можно с тем же успехом и не предсказывать. Не нужна таблица предсказаний. А вот конвейр мы реально нагрузим процентов на 80%, и при этом полностью задействуем широкий канал с памятью — нам теперь не нужны большие кэша для этого, плевать нам на промахи.
И так далее. Если ты посмотришь внимательно на ход рассуждений, то поймешь, что в любом подходе есть несколько ключевых решений, которые тянут за собой кучу мелких. Вот они, основные. 1) Аппаратное динамическое распараллеливание потока по зависимостям команд по регистрам (классический суперскаляр). 2) Явное распараллеливание на аппаратные потоки (мультитред). 3) Статическое распараллеливание компилятором (VLIW). Вокруг одного из того ты строишь архитектуру, и как только начинаешь, дальнейшие варианты действий у тебя предопределены — ты выбираешь из небольшого числа вариантов.
G>>К сожалению, для того, чтобы это объяснить, мне придется целую статью здесь написать, начав издалека, с устройства типового суперскалярного проца и типичных проблем, которые там возникают. А на это у меня нет ни времени ни сил. Могу порекомендовать книгу Танненбаума по архитектуре ЭВМ — лучшее введение в вопрос для программистов. C>Я примерно представляю как работают предикторы, спекулятивное исполнение и т.п.
Этого мало. Чтобы понимать, почему делается так или иначе, надо хотя бы в общих чертах уметь проектировать процы, и представлять себе реальные проблемы. Общего представления об отдельных алгоритмах и механизмах недостаточно, надо понимать причины design decisions, и как эти механизмы стыкуются между собой.
Я вот очень примерно, в общих чертах, представляю себе, как работает суперскалярный проц, потому что у нас был НИР "исследование возможностей создания суперскалярного процессора с системой команд MIPS I", в ходе которого была разработана потактовая поведенческая модель проца, на которой мы последствия нескольких десятков разных архитектурных ходов изучили — какая фича как работает и как именно влияет на производительность. thesz ее писал на Хаскеле, если интересно. Кстати, похвастаюсь — наш проц на моделировании выдавал 3,3 реальные инструкции за такт при выполнении DCT из декодирования H.264, при четырех каналах арифметики. Так-то вот. Но делать мы его все равно не стали (и слава богу). 17-портовый регистровый файл — это вам не шутки. Да и производительность проседает, стоит добавить юзерский режим и TLB. А начнешь навороты наворачивать, чтобы ситуацию выправить — так у него площадь попрет сразу (и так в самой скромной конфигурации был не меньше 5 мм2 без кэшей — сравни с 2-3 мм2 площади single-issue multithreaded MIPS34K)
G>>Обрати внимание, как устроен проц XBox 360 — предназначенный для наиболее требовательных "настольных" приложений — компьютерных игр. in-order execution + 3 ядра + аппаратная многопоточность (по 2 потока на ядро), общий кэш L2. Итого — 6 аппаратных потоков. Потому что делать так — дешевле, чем суперскаляр. Производительность одного потока там примерно 20% от скорости core duo. И ничего — в майкрософт выбрали такой дизайн, хотя вполне могли опять заказать проц интелу, как для первого XBox. C>Ну так я не спорю, что оно им так дешевле получилось — разработчикам-то особого выбора нет. А если бы у покупателей был выбор что взять: крутой параллельный процессор или крутой однопоточный — это был бы другой вопрос.
Покупателю пофиг, какой там проц. А программерам аппаратчики выбора не оставляют, извини. Будем писать массово параллельные программы.
Здравствуйте, Курилка, Вы писали:
C>>Можно чуть дальше в прошлое на Cray'и с их кучей fine-grained барьеров посмотреть (могу найти PDFку с описанием). Не секрет, что настольные PC примерно на 20 лет отстают от суперкомпьютеров. Так что, скоро nccNUMA будет дальше появляться. К>Было бы интересно посмотреть пдфку http://crtc.wm.edu/paper/eorm07.pdf и еще одна есть, сейчас постараюсь найти.
Здравствуйте, Курилка, Вы писали:
К>Здравствуйте, Gaperton, Вы писали:
G>>... out-of-order совершенно не нужен при многопоточном дизайне проца — они будут только мешать друг другу и не будет никакой пользы. Это взаимоисключающие вещи, поэтому собственно гипертрединг и сосет. Суперскаларное выполнение при этом вводить вполне можно (выполнять подряд идущие инструкции впараллель) — но инструкции переупорядочивать глупость. К сожалению, для того, чтобы это объяснить, мне придется целую статью здесь написать, начав издалека, с устройства типового суперскалярного проца и типичных проблем, которые там возникают. А на это у меня нет ни времени ни сил. Могу порекомендовать книгу Танненбаума по архитектуре ЭВМ — лучшее введение в вопрос для программистов.
К>Ты вот эту книжку имеешь в виду?
Ну то прям жостко как-то. Не. Ничего из того, что трудно купить, достать, прочитать и понять.
Вот это — не танненбаум, существенно менее попсово — эту книгу писали аппаратчики. Вот это, пожалуй, по детальности изложения — оптимум для программиста, который хочет глубоко понять принципы аппаратного дизайна, но при этом не собирается переквалифицироваться в RTL-инженера. http://www.ozon.ru/context/detail/id/1374858/
Re[5]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
S>На С++ это достижимо только путем подсчета ссылок, но для него нужно заводить счетчик, и структура сразу же перестанет быть иммутабельной.
mutable int m_refCount;
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[6]: Immutable data structures are the way of the future i
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, Sinclair, Вы писали:
S>>На С++ это достижимо только путем подсчета ссылок, но для него нужно заводить счетчик, и структура сразу же перестанет быть иммутабельной. CC>
CC>mutable int m_refCount;
CC>
Напомнило про "рыбу второй свежести"
Re: Immutable data structures are the way of the future in C
[]
G>Как раз на С++ структура и не перестанет быть иммутабельной, если завести mutable счетчик ссылок. mutable как раз для таких ситуаций и предназначен, и никакого вреда кроме пользы от него не будет. Это, собственно, два.
Простите, но mutable всего-лишь позволяет изменять поля объекта в const-методах. Откуда тут immutability?
[]
Re[3]: Immutable data structures are the way of the future i
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Нет, ну согласись, что у тебя тут сложилась репутация ктулху, просыпающегося от любого ключевого слова немерла. А когда ктулху просыпается — его ведь мочат все, кому не лень...
Во-первых, у меня тут бессмертие.
Во-вторых, ключевого слова не было.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Immutable data structures are the way of the future i
Здравствуйте, VladD2, Вы писали:
CC>>Я туплю или это аналог const из С++? VD>Тупишь .
Обоснуй плз, ибо выше по ветке выяснили, что таки да, аналог const для данных.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[5]: Immutable data structures are the way of the future i
> CC>>>Я туплю или это аналог const из С++? > VD>>Тупишь . > CC>Обоснуй плз, ибо выше по ветке выяснили, что таки да, аналог const для данных. > > Утверждение того, что в const-поле класса таки-можно что-либо записать вне конструктора класса не достаточно для обоснования?
Конечно, не достаточно. Снятие константности с const полей ведет к UB, т.е. компилятору явно разрешается полагаться на неснимаемость константности с данных. Другое дело, что с алиасов константность снимать разрешено, что делает практически невозможным применение оптимизаций, основанных на константности.
> Во-вторых, речь идёт об immutable-типах. Разве в С++ есть const-классы?
const A и просто A с точки зрения компилятора — разные типы.
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Re: Immutable data structures are the way of the future in C
Здравствуйте, Константин Л., Вы писали:
КЛ>Вполне себе можно. Компайлер может оптимайзить "настоящие" константы.
Это те которые заданы на этапе компиляции?
Так это ерунда.
Их только ленивый не оптимизирует.
Тут речь идет о структурах данных которые один раз на этапе исполнения создаются и больше никогда и ни при каких условиях не меняются.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[9]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Константин Л., Вы писали: КЛ>>Не понял про вред. Или ты в свете immutability? S>Да. Понимаешь, тут некоторые участники дискуссии путают отсутствие зависимостей, гарантированное отсутствием модификаций, со словом сonst. Если я на сарае напишу const, это не сделает лежащие в нем дрова неизменяемыми.
Синклер, я ничего не путаю. Не знаю как ты на сарае там консты пишешь, но когда Я ПИШУ const, то я уж забочусь о том, чтобы семантика операций была константной на самом деле.
S>Это то же самое, что полагать, что маскировка обращения к глобальной переменной за доступом к приватному нестатическому члену класса избавит от проблем. Типа раз мы в коде пишем this->setMap(...), то всё уже в порядке, хоть этот setMap по прежнему пишет в static CMap* g_map.
Ты просто не понимаешь, о чем я. Бывает.
Re[11]: Immutable data structures are the way of the future
Здравствуйте, Sinclair, Вы писали:
G>>В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус. S>Это всего лишь оптимизация GC. Без GC этот счетчик не работает.
Кстати, достаточно известная оптимизация. Называется (неудивительно) one-bit reference counting: http://citeseer.ist.psu.edu/130110.html
А вообще, RC как оптимизация GC вообще не помешал бы.
Sapienti sat!
Re[9]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
G>>Ничего страшного мы тут не имеем. G>>1) У тебя разных счетчиков ссылок столько, сколько разных элементов в структуре данных — коллизий будет немного. S>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука.
Ну не совсем так — есть wait-free алгоритмы, позволяющие не блокировать читающие потоки во время мутации коллекций и т.п.
Sapienti sat!
Re[11]: Immutable data structures are the way of the future
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Gaperton, Вы писали:
S>>>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука. G>>Ну, в реальности, положим, тебе надо не lock/free, а InterlockedIncrement сделать, а это, насколько я помню, одна ассемблерная инструкция. S>Количество инструкций != количеству тактов.
Фундаментальная истина, не поспоришь, особенно для процов x86 . Может быть, ты знаешь, сколько конкретнонакладных тактов будет на инструкцию XADD, через которую делается этот инкремент, а? А я тебе скажу. Если ядра работают на общем кэше — то ноль. Если на нескольких раздельных — то плюс несколько тактов слазить в соседний кэш (не будет их там больше двух), на что ядро преспокойно наложит выполнение следующих операций — зависимостей по регистрам от этого XADD у нас нет. Или выполнение следующего аппаратного треда. Случай промаха в кэш мы не рассматриваем — я надеюсь, ты понимаешь почему? Потому что в этом случае эта операция займет ровно столько же времени, сколько и обычный инкремент, на фоне-то доступа во внешний DDR.
G>>При первой модификации стека отдельным потоком. Надо на реальные кейсы смотреть. Приведи реальный пример использования, при котором получается сколько угодно. Мне кажется, на практике будет немного "стеков". S>Ты статью читал? Там же А* реализуется. Стеков будет столько, сколько выходов из клетки.
Ладно, уговорил. Почитаю статью.
S>>>Скажем, я уверен, что здесь можно использовать heap-per-thread. Тогда создание нового стека вообще не будет использовать никакую синхронизацию. G>>Конечно. В этом случае тебе правда весь стек откопировать придется сразу, что не хорошо. S>Нет, не надо. Никакой проблемы ссылаться из одного хипа в другой нету. Возможно, будут особенности с cache locality, но их, скорее всего, можно побороть грамотным выравниванием.
А управлять ссылками между хипами кто будет? Пушкин А.С.? И каким образом мы это будем делать, не мог бы ты пояснить? Уж не ссылки ли на хипы ты собрался считать (что совершенно то же, только вид сбоку)?
G>>В С++ ты вообще можешь честный GC закрутить на элементах стека, кстати, полностью перекрыв аллокацию для объектов класса стек. S>Свой скепсис по поводу честного GC в С++ я уже высказывал.
Ну тогда придумай, как будешь считать ссылки между разными хипами.
S>>>Совершенно не представляю себе, чем бы здесь помог однобитный счетчик ссылок. G>>Это не так просто представить сразу — надо для начала представить себе как устроен этот стек. Однобитные счетчики ссылок позволят тебе отличать ситуацию, когда на объект наброшена одна ссылка, от ситуаций, когда ссылок много. В первом случае, который наиболее част для элементов однонаправленных списков, на которых и будет реализован твой стек, однобитные ссылки позволяют удалять длинные цепочки не привлекая GC. G>>В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус. S>Это всего лишь оптимизация GC. Без GC этот счетчик не работает.
Надо ли понимать этот твой ответ так, что ты понял, что такое однобитный счетчик ссылок? Разумеется это оптимизация. И не "всего лишь", а "хорошая" оптимизация. Я тебе это с самого начала и сказал.
2) От хотя бы однобитного счетчика ссылок вряд-ли кто откажется в данной ситуации — уж очень он здорово поправляет здоровье отца русской демократии — сильно разгружается GC.
По существу вопроса возражения есть?
Re[12]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>Фундаментальная истина, не поспоришь, особенно для процов x86 . Может быть, ты знаешь, сколько конкретнонакладных тактов будет на инструкцию XADD, через которую делается этот инкремент, а? А я тебе скажу. Если ядра работают на общем кэше — то ноль.
А если не работают?
Подумай о nccNUMA
Sapienti sat!
Re[4]: Immutable data structures are the way of the future i
VD>Случаем — нет.
VD>Ты то ли плохо понимашь чем отличаются неизменяемые струтуры данных от полного не использования состояния в программах, то ли не понимаешь, что наличие неизменяемых струтур не отменяет наличие изменяемых.
Э-э-э... Это сложно как-то очень. Это типа как "пчелы против меда" штоли?
Re[16]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. Каждый отдельный поток протормозит, но вместе они нагрузят одно ядро на процентов 70-80. При поддержке аппаратной многопоточности вполне реально сделать объединенный кэш L2 — пусть он будет высоколатентный — это не важно, с латентностью и задержками эффективно борется аппаратная многопоточность.
Только вот куча задач у нас реально однопоточна — поэтому жуткие замедления на синхронизации будут убивать производительность. А если выкидывать все примитивы синхронизации — то тогда получаем и полную невозможность использовать многопоточность.
Причем, это не теория — а вполне себе реальная практика с HyperThreading'овыми CPU. Там как раз та же ситуация, но по другой причине — длинный pipeline делал синхронизацию очень дорогой, и в качестве метода борьбы использовали переключение потоков. В результате, очень часто получали ЗАМЕДЛЕНИЕ вместо ускорения.
G>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
Ок, против моей любимой валюты — отсканированых $100
C>>Более того, скорее всего будут еще и механизмы, позволяющие разбивать набор процессоров на группы, чтобы барьер в одной группе не останавливал остальные процессоры. В общем, как раз все будет устроено как в некоторых суперкомпьютерах G>Зачем так делать, если можно увеличить количество аппаратных потоков, и сделать высоколатентный, но централизованный кэш L2.
См. выше.
Здравствуйте, Cyberax, Вы писали:
C>>>Так вот только сами по себе ядра в SPARC'ах никогда особым быстродейтвием не отличались. Для массивно-параллельных задач типа жуткого сервера с кучей потоков — оно рулит, но вот матетематика с числодробилками на нем часто сосет. G>>Первая ниагара имеет одно FPU на восемь ядер, она не для числодробления презназначена, а для enterprise servers. А вот вторая ниагара (ultrasparc t2) на плавающей запятой порвет все xeon-ы и core duo на кровавые ошметки — там у каждого из ядер свое FPU. C>Я имею в виду целочисленные задачи. Как результат — не рвет на всех задачах. Сказывается примитивность отдельно взятого ядра — достаточно чтобы в вычислении были непараллелизуемые участки, и производительность уходит в пол.
Ну, батенька, параллелить же надо. Понятно что отдельное ядро там тупое до безобразия — в этом вся и штука.
C>>>Я сейчас как раз работаю (удаленно) с машинкой с UltraSparc T1 (на днях должны UltraSparc T2 привезти — жду с нетерпением). Сервера на нем вообще просто великолепно работают, а та же перекомпиляция ядра — медленнее, чем на моей скромной домашней Core 2 Duo машине. G>>Ничего удивительного тут нет. Во первых, "скромный" core 2 duo — самый совершенный суперскалярный (рассчитанный на однопоточные приложения) проц за всю историю человечества. Перекомпиляция ядра — однопоточное приложение. UltraSparc T1 предназначен для эффективного выполнения параллельных программ. C>Перекомпиляция ядра — параллельный процесс (make -jN, где N — количество параллельных задач, встроено в сам make). На моем Core 2 Duo максимум производительности у меня при N=3, на T1 — при N=6. Тем не менее, все равно Core 2 Duo работает быстрее.
На шести параллельных задачах t1 никак не сможет обогнать core 2 duo — это технически невозможно. Почему он медленнее на 32-х, или хотя бы восьми? Задачи то совершенно независимы.
G>>О чем ты? Нет никаких таких суперкомпьютеров. Все суперкомпьтеры давным давно, уже лет 10 как минимум, собираются на мэйнстримовых микропроцессорах (стойки соедняются через merynet или infiniband), Крэй сто лет назад раззорился и был выкуплен силикон графиксом, и делает свои сервера на Оптеронах. Это уже давно не так. Даже мйнфреймы сейчас работают на кастомизированной версии проца Power 5 с микропрограмной поддержкой. На этот старый crap 20-летней давности уже сейчас никто не смотрит. Основных направлений исследований по данной теме сейчас четыре. C>Кстати, ты про суперкомпьютерные кластеры очень хорошо напомнил — это как раз nccNUMA, точнее NORMA (No Remote Memory Access). Там обращение к памяти соседнего узла стоит очень дорого — поэтому даже и не пытаются заниматься фигней вроде автоматической когенрентности памяти, а сразу используют явную передачу сообщений.
Ну если ты считаешь передачу сообщений nccNUMA, то тогда я с тобой соглашусь. Асинхронные сообщения — это хорошо и удобно, ничего против не имею. Только необходимости применять это внутри кристалла пока вроде как нет — и так пока справляются. Ты в кристалл все равно слишком много ядер не засунешь — коммерческая площадь кристалла не зависит от применяемого техпроцесса, и составляет около 200 мм2 плюс-минус 50 — если экстремальные случаи не рассматривать.
Далее — одно простое 64-битное процессорное ядро вместе со скромным кэшом L1 будет занимать примерно 8-15 мм2 на техпроцессе 0,09 в зависимости от наворотов, тут ты ничего не сделаешь. Я говорю о реально простом ядре, без векторных операций типа SSE, и без особо навороченной плавающей запятой. Дальше — считай. Половину кристалла можно будет отдать под кэш, плюс потребуется сложный многопоточный контроллер памяти и внутрикристальный коммутатор. Реальное количество ядер на кристалле будет около 10 штук плюс-минус, на тонких техпроцессах будет максимум 16 ядер. С таким количеством ядер на кристалле вполне хватит аппаратной многопоточности — вводить nccNUMA внутри кристалла смысла особого нет.
Re: Immutable data structures are the way of the future in C
Здравствуйте, Курилка, Вы писали:
CC>>Я туплю или это аналог const из С++? К>Нет, т.к. конст в плюсах обходится (слабая там типизация, увы), да и это модификатор данных, в плюсах же и кода тоже. Т.е. смысл хоть и похожий, но несколько разный.
Т.е. immutable это неснимаемый const для данных? так?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[4]: Immutable data structures are the way of the future i
Здравствуйте, Курилка, Вы писали:
К>Здравствуйте, CreatorCray, Вы писали:
CC>>Т.е. immutable это неснимаемый const для данных? так?
К>Ну по сути да, где-то так. Правда ещё гарантии побольше, чем в случае плюсов.
Хотя блин, масло маслянное получилось, если он неснимаемый, то это и есть жёсткая гарантия
Re[5]: Immutable data structures are the way of the future i
Здравствуйте, Курилка, Вы писали:
К>Ну по сути да, где-то так. Правда ещё гарантии побольше, чем в случае плюсов.
Ну про гарантии мне не надо рассказывать
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[2]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, CreatorCray, Вы писали: CC>>Т.е. immutable это неснимаемый const для данных? так? S>Я не помню семантику const для нестатических полей. Она проинициализировать поле в конструкторе позволяет? S>Если да — то всё более-менее в порядке, это оно. S>Более-менее потому, что без GC эта штука практически бесполезна. S>Я имею в виду экономию памяти за счет раздельного владения. В статье речь идет о структуре ImmutableStack, которая ведет себя достаточно забавным образом: у нее Push и Pop делаются за время O(1), и при этом обладают неразрушающей семантикой.
Это полная фигня. Попробуй лучше сделать ImmutableQueue. И чтобы push и pop было за О(1). Хорошее управжнение для мозга, ну, и изобретешь заново Okasaki Queue — тоже дело. .
S>На первый взгляд, такую же структуру реализовать на С++ легко. Увы — если место размещения оператора new совершенно очевидно, то оператор delete совершенно неясно когда вызывать.
На второй взгляд, такую же структуру на С++ так же легко, как и на первый. Эта структура делается однонаправленным списком. Хвост которого может указывать на начало или середину другого списка. В узлах делаешь счетчик ссылок. И все. Можно делать хитрее — для экономии памяти применять однобитныесчетчики ссылок — техника оптимизации, которая применялась еще в древних лисп-машинах.
S>Если мы породили из одного стека несколько различных стеков, то их общий "хвост" должен жить до тех пор, пока жив хоть кто-то из них. S>На С++ это достижимо только путем подсчета ссылок, но для него нужно заводить счетчик, и структура сразу же перестанет быть иммутабельной.
Ага. И что интересно — циклов нет, обрати внимание. Ну, и это можно делать, конечно же, не только подсчетом ссылок. Можно тупо аллокатор перекрыть, и вообще сделать для них честный GC. Это раз.
Как раз на С++ структура и не перестанет быть иммутабельной, если завести mutable счетчик ссылок. mutable как раз для таких ситуаций и предназначен, и никакого вреда кроме пользы от него не будет. Это, собственно, два.
Ну и три. Функциональное программирование, я вижу, идет в массы семимильными шагами. Скоро, глядишь — через годик, заговорят об Окасаки, ленивых конструкторах, и бесконечных структурах данных. Любопытно.
Re[7]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, CreatorCray, Вы писали: S>И что? Счастье-то где? S>Поясняю: иммутабельность ценна не сама по себе, а множеством классных последствий, которые она обеспечивает. В частности, потокобезопасностью по низкой цене. S>А здесь мы что имеем? Нельзя одновременно делать Push в двух разных потоках, потому что оба должны потрогать счетчик сцылок. Это очень плохо отразится на NUMA.
Ничего страшного мы тут не имеем.
1) У тебя разных счетчиков ссылок столько, сколько разных элементов в структуре данных — коллизий будет немного. Реально — трогает разделяемые данные другой поток ровно один раз — при первой модификации стека. И все. И далеко не факт, что налетит на коллизию. Не слишком страшно, правда? Тем более, что в случае NUMA тебе надо по-любому очень аккуратно к распараллеливанию подходить, выделяя слабосвязные по данным фрагменты. Скажем, ты уверен, что общий хип будет вообще хорошо рабоать при NUMA?
2) От хотя бы однобитного счетчика ссылок вряд-ли кто откажется в данной ситуации — уж очень он здорово поправляет здоровье отца русской демократии — сильно разгружается GC.
Re[7]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
S>И что? Счастье-то где? S>Поясняю: иммутабельность ценна не сама по себе, а множеством классных последствий, которые она обеспечивает. В частности, потокобезопасностью по низкой цене.
Дык понятно, что они как раз именно этих последствий добиваются. Будет долгий процесс в стиле МС по переходу на функциональщинку. Лет эдак через 10 мы ощитим от этого отдачу .
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Immutable data structures are the way of the future i
Здравствуйте, VladD2, Вы писали:
VD>Во-первых, у меня тут бессмертие.
Только тебе еще успеть надо, агент написать. Чтобы он и после тебя тут всех мочил. А можно и не после; написал агент, запустил, откинулся на спинку кресла, а он мочит, мочит...
Re[5]: Immutable data structures are the way of the future i
Здравствуйте, igna, Вы писали:
VD>>Во-первых, у меня тут бессмертие.
I>Только тебе еще успеть надо, агент написать. Чтобы он и после тебя тут всех мочил. А можно и не после; написал агент, запустил, откинулся на спинку кресла, а он мочит, мочит...
А зачем не? См. пункт 1.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Immutable data structures are the way of the future i
Здравствуйте, CreatorCray, Вы писали:
CC>>>Я туплю или это аналог const из С++? VD>>Тупишь . CC>Обоснуй плз, ибо выше по ветке выяснили, что таки да, аналог const для данных.
Утверждение того, что в const-поле класса таки-можно что-либо записать вне конструктора класса не достаточно для обоснования?
Во-вторых, речь идёт об immutable-типах. Разве в С++ есть const-классы?
... << RSDN@Home 1.2.0 alpha rev. 717>>
Help will always be given at Hogwarts to those who ask for it.
Re: Immutable data structures are the way of the future in C
Очень мне это напоминает "с больной головы на здоровую". Помню как в C++ вводили inline чтобы помочь компилятору принять решение о встраивомости. До этого были register и т.п.
Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[2]: Immutable data structures are the way of the future i
Здравствуйте, minorlogic, Вы писали:
M>Очень мне это напоминает "с больной головы на здоровую". Помню как в C++ вводили inline чтобы помочь компилятору принять решение о встраивомости. До этого были register и т.п.
M>Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?
Имхо некорректная аналогия: понимание того, что mutability вещь чаще всего вредная, по сути нуждается в некоем принуждении (как в том же немерле принудительно надо добавлять mutable, насколько я помню). inline/register являются по сути premature optimization, а вот программу написанную со сплошными mutable переменными запросто в программу на immutable переменных переписать вряд ли получится, т.к. чаще всего даже алгоритмы меняются (начиная с цилков/рекусии в ИЯ/ФЯ). Правда чётких доказательств этого у меня нет, поэтому можно считать лишь субъективным мнением.
Re[9]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Gaperton, Вы писали: G>>Ничего страшного мы тут не имеем. G>>1) У тебя разных счетчиков ссылок столько, сколько разных элементов в структуре данных — коллизий будет немного. S>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука.
Ну, в реальности, положим, тебе надо не lock/free, а InterlockedIncrement сделать, а это, насколько я помню, одна ассемблерная инструкция.
G>>Реально — трогает разделяемые данные другой поток ровно один раз — при первой модификации стека. И все. S>Это почему еще? Напоминаю, что из одного стека можно получмть сколько угодно стеков.
При первой модификации стека отдельным потоком. Надо на реальные кейсы смотреть. Приведи реальный пример использования, при котором получается сколько угодно. Мне кажется, на практике будет немного "стеков".
G>>И далеко не факт, что налетит на коллизию. Не слишком страшно, правда? Тем более, что в случае NUMA тебе надо по-любому очень аккуратно к распараллеливанию подходить, выделяя слабосвязные по данным фрагменты. Скажем, ты уверен, что общий хип будет вообще хорошо рабоать при NUMA? S>Скажем, я уверен, что здесь можно использовать heap-per-thread. Тогда создание нового стека вообще не будет использовать никакую синхронизацию.
Конечно. В этом случае тебе правда весь стек откопировать придется сразу, что не хорошо. В С++ ты вообще можешь честный GC закрутить на элементах стека, кстати, полностью перекрыв аллокацию для объектов класса стек.
G>>2) От хотя бы однобитного счетчика ссылок вряд-ли кто откажется в данной ситуации — уж очень он здорово поправляет здоровье отца русской демократии — сильно разгружается GC. S>Совершенно не представляю себе, чем бы здесь помог однобитный счетчик ссылок.
Это не так просто представить сразу — надо для начала представить себе как устроен этот стек. Однобитные счетчики ссылок позволят тебе отличать ситуацию, когда на объект наброшена одна ссылка, от ситуаций, когда ссылок много. В первом случае, который наиболее част для элементов однонаправленных списков, на которых и будет реализован твой стек, однобитные ссылки позволяют удалять длинные цепочки не привлекая GC. В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус.
Re[7]: Immutable data structures are the way of the future i
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Gaperton, Вы писали: G>>Это полная фигня. S>Можно раскрыть это утверждение? Я не понял, к чему именно относилось "фигня" и что она означает.
К простоте реализации иммутабельного стека, сравнительно, например, с queue. Иммутабельный стек — полная фигня. Если ты не будешь отвечать подстрочником, на каждое предложение, а будешь отвечать на абзац целиком, который есть законченная мысль, то понять к чему это относится будет гораздо проще.
G>> Попробуй лучше сделать ImmutableQueue. И чтобы push и pop было за О(1). Хорошее управжнение для мозга, ну, и изобретешь заново Okasaki Queue — тоже дело. . S>Я не ощущаю какой-то потребности в упражнениях для мозга.
Напрасно, это бы помогло тебе понять, что ImmutableStack полная фигня. Но не ощущаешь, так не ощущаешь, ради бога.
G>>На второй взгляд, такую же структуру на С++ так же легко, как и на первый. Эта структура делается однонаправленным списком. Хвост которого может указывать на начало или середину другого списка. S>Это очевидно, потому что именно это описано в статье.
Это очевидно независимо от того, что именно написано в статье . Я ее, например, не читал. Не интересно.
G>>В узлах делаешь счетчик ссылок. И все. S>Совершенно верно — "и всё". И теряем возможность создавать списки без блокировок. G>>Можно делать хитрее — для экономии памяти применять однобитныесчетчики ссылок — техника оптимизации, которая применялась еще в древних лисп-машинах. S>А можно мне рассказать про эти однобитные щетчики ссылок, и как они помогут выполнять детерминистическое освобождение памяти?
Почитай про них в сети. Я, видишь-ли, что-то тоже какой-то потребности рассказывать вдруг ощущать перестал.
G>>Как раз на С++ структура и не перестанет быть иммутабельной, если завести mutable счетчик ссылок. mutable как раз для таких ситуаций и предназначен, и никакого вреда кроме пользы от него не будет. Это, собственно, два. S>Не надо путать божий дар с яичницей. mutable предназначен для обмана трудящихся масс, и вред от него очевиден. Процессор обмануть не удастся — для него нет ни mutable ни const; а есть жосткая реальность — необходимость синхронизации счетчика ссылок, который вы заботливо впендюрили.
InterlockedIncrement и InterlockedDecrement. http://www.yandex.ru/yandsearch?text=InterlockedIncrement+%E8%ED%F1%F2%F0%F3%EA%F6%E8%FF&rpt=rad
Почитай про эту "жосткую реальность", реальность надо знать в лицо, даже если это всего-навсего одна инструкция x86. Нормальные пацаны пользуются этими примитивами, и ничего не "синхронизуют". Mutable же нужен для обмана компилятора.
S>Однобитный счетчик синхронизовывать не обязательно, но он всё равно требует GC.
Требует или GC, или полноценного счетчика ссылок. Это оптимизация. Ты про него уже прочитал, видимо, или раньше знал — эт хорошо. Значит, понимаешь, о чем я говорю.
Re[2]: Immutable data structures are the way of the future i
Здравствуйте, minorlogic, Вы писали:
M>Очень мне это напоминает "с больной головы на здоровую". Помню как в C++ вводили inline чтобы помочь компилятору принять решение о встраивомости. До этого были register и т.п.
M>Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?
Immutable cтруктуры по-другому монтируются. И операции над ними по-другому реализуются. См., например, Окасаки.
Re[2]: Immutable data structures are the way of the future i
Здравствуйте, minorlogic, Вы писали:
M>Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?
В случае среды Net — такое невозможно. Невозможно предсказать как будет использоваться тот или иной метод класса, учитывая то что в момент компиляции на уровне C# известен только код сборки, на уровне JIT — глобальный анализ невозможен поскольку компилируется только вызванная процедура и ее зависимости.
Re[6]: Immutable data structures are the way of the future i
Здравствуйте, Константин Л., Вы писали:
КЛ>Здравствуйте, VladD2, Вы писали:
КЛ>[]
VD>>const же в С++ — это, как говорится, "почти ничто". Это атрибут переменной (о const на фунции вообще не говорим, так как это из другой оперы), который ко всему прочему элементарно обойти. Сделать какие либо оптимизации на основании знания о const-стантности или как-то другим образом использовать это явление скажем при многопоточном программировании нельзя.
КЛ>Вполне себе можно. Компайлер может оптимайзить "настоящие" константы.
Другое дело, что для immutable type'ов это намного проще
КЛ>[]
[]
G>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.
1. Interlocked не так дешев, как кажется.
2. mutexes не так дороги, как кажутся (e.g. CRITICAL_SECTION)
3. Sinclair говорит о том, что и без Interlocked можно легко обойтись
Re[10]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
S>>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука. G>Ну, в реальности, положим, тебе надо не lock/free, а InterlockedIncrement сделать, а это, насколько я помню, одна ассемблерная инструкция.
Количество инструкций != количеству тактов.
G>При первой модификации стека отдельным потоком. Надо на реальные кейсы смотреть. Приведи реальный пример использования, при котором получается сколько угодно. Мне кажется, на практике будет немного "стеков".
Ты статью читал? Там же А* реализуется. Стеков будет столько, сколько выходов из клетки.
S>>Скажем, я уверен, что здесь можно использовать heap-per-thread. Тогда создание нового стека вообще не будет использовать никакую синхронизацию. G>Конечно. В этом случае тебе правда весь стек откопировать придется сразу, что не хорошо.
Нет, не надо. Никакой проблемы ссылаться из одного хипа в другой нету. Возможно, будут особенности с cache locality, но их, скорее всего, можно побороть грамотным выравниванием. G>В С++ ты вообще можешь честный GC закрутить на элементах стека, кстати, полностью перекрыв аллокацию для объектов класса стек.
Свой скепсис по поводу честного GC в С++ я уже высказывал.
S>>Совершенно не представляю себе, чем бы здесь помог однобитный счетчик ссылок. G>Это не так просто представить сразу — надо для начала представить себе как устроен этот стек. Однобитные счетчики ссылок позволят тебе отличать ситуацию, когда на объект наброшена одна ссылка, от ситуаций, когда ссылок много. В первом случае, который наиболее част для элементов однонаправленных списков, на которых и будет реализован твой стек, однобитные ссылки позволяют удалять длинные цепочки не привлекая GC. G>В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус.
Это всего лишь оптимизация GC. Без GC этот счетчик не работает.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Gaperton, Вы писали: G>Кстати, не объяснишь мне, какой такой всем очевидный вред есть от mutable? G>И каким именно образом он у нас "для обмана трудящихся масс" предназначен?
Поясняю еще раз: преимущества в многоядерной среде есть не у константных, а у иммутабельных структур. У некоторых людей при взгляде на ключевое слово const может возникнуть иллюзия того, что соответствующий метод не нуждается в синхронизации. Ан нет — внутри него есть модификация mutable.
G>ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете.
Никакой константной семантики у него нету. G>Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику.
Откуда взялась чистая семантика в коде, который меняет глобальное состояние? Для чистой семантики вам, функциональщикам, придется передавать (seed, state) в каждый вызов.
Иначе вы будете обязаны выполнять синхронизацию внутри этого "чистого" метода. А то значения, случайно генерящиеся в параллельно исполняемых потоках, будут волшебным образом коррелировать. Если об этом знать, то можно сразу выделить по генератору на поток, и избежать race condition. Но ключевое слово const прячет он нас mutable природу этого генератора, и мы удивляемся, почему это у нас четыре ядра пашут не быстрее двух.
G>Обратите внимание на пример номер 2. Мы делаем чистую функцию — которая вычисляет некоторое значение без побочных эффектов — не меняя состояние системы (т.е. ее возвращаемое значение целиком и полностью определяется значениями ее аргументов). Мы разумеется сразу помечаем ее как const. Но она однако тормозит иногда, при некоторых сочетаниях параметров, и мы решаем всунуть внутрь ея кэш. Который, разумеется, будет у нас mutable. При этом, семантика нашей функции останется "чистой", все в порядке.
Хороший пример. С кэшем опять то же самое — скрытое состояние, которое нужно синхронизовывать. Вы выполняете запись в структуру, и либо там стоит InterlockedExchange, либо у вас начинаются проблемы с нарушением целостности.
G>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.
InterlockedIncrement все еще на пару порядков медленнее обычного инкремента. Кстати, не все примитивы синхронизации требуют режима ядра. Захват critical section традиционно строится на interlocked операциях в user mode.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
G>>ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете. S>Никакой константной семантики у него нету. G>>Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику. S>Откуда взялась чистая семантика в коде, который меняет глобальное состояние? Для чистой семантики вам, функциональщикам, придется передавать (seed, state) в каждый вызов. S>Иначе вы будете обязаны выполнять синхронизацию внутри этого "чистого" метода. А то значения, случайно генерящиеся в параллельно исполняемых потоках, будут волшебным образом коррелировать. Если об этом знать, то можно сразу выделить по генератору на поток, и избежать race condition. Но ключевое слово const прячет он нас mutable природу этого генератора, и мы удивляемся, почему это у нас четыре ядра пашут не быстрее двух.
хочется еще добавить, относительно данного конкретного примера, со своей точки зрения.. бог бы с ней со скоростью, но тут вылезет еще одна проблема, связанная с тем, что ф-ия get_rnd_value() изменяет внутреннее состояние нашего "генератора случайных чисел". Связана эта проблема с воспроизводимостью результатов. Т.е. в ряде наших, например, задач (исследования распределений статистик различных критериев методом монте-карло) бывает важно, что установливая один и то же seed для генератора на выходе мы получаем одинаковые результаты. А в случае разделения такого нашего генератора разными потоками воспроизводимость мы потерям, т.к. помимо seed на результаты влияет очередность обращений потоков к этому генератору -- а она в общем случае может изменяться в определенных пределах. Был бы он immutable -- не было бы этой проблемы (хотя immutable генератор псевдослучайных величин это само по себе достаточно загадочно)) ).
Здравствуйте, inko, Вы писали:
I>хочется еще добавить, относительно данного конкретного примера, со своей точки зрения.. бог бы с ней со скоростью, но тут вылезет еще одна проблема, связанная с тем, что ф-ия get_rnd_value() изменяет внутреннее состояние нашего "генератора случайных чисел". Связана эта проблема с воспроизводимостью результатов. Т.е. в ряде наших, например, задач (исследования распределений статистик различных критериев методом монте-карло) бывает важно, что установливая один и то же seed для генератора на выходе мы получаем одинаковые результаты. А в случае разделения такого нашего генератора разными потоками воспроизводимость мы потерям, т.к. помимо seed на результаты влияет очередность обращений потоков к этому генератору -- а она в общем случае может изменяться в определенных пределах. Был бы он immutable -- не было бы этой проблемы (хотя immutable генератор псевдослучайных величин это само по себе достаточно загадочно)) ).
В случае его использования разными потоками надо хранить его состояние в Thread Local Storage. И все будет хорошо. "Чистый" он, "чистый", как слеза младенца. Несмотря на mutable внутри.
Здравствуйте, Константин Л., Вы писали:
КЛ>Здравствуйте, Gaperton, Вы писали:
КЛ>[]
G>>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.
КЛ>1. Interlocked не так дешев, как кажется.
Откуда ты знаешь, насколько именно дешев он мне кажется? Знаешь точно, насколько он дешев — скажи. Не знаешь — зачем пугаться самому и пугать других?
КЛ>2. mutexes не так дороги, как кажутся (e.g. CRITICAL_SECTION)
То же самое. Есть что конкретно сказать касательно производительности — давай. То что критическая секция дешевле мьютекса — я в курсе.
КЛ>3. Sinclair говорит о том, что и без Interlocked можно легко обойтись
Ну, и где именно он об этом говорит? Я вообще достаточно внимательно читаю те посты, на которые отвечаю.
Re: Immutable data structures are the way of the future in C
Здравствуйте, nikov, Вы писали:
N>Eric Lippert, один из разработчиков C#, пишет в своем блоге.
N>
N>Immutable data structures are the way of the future in C#.
Типа Америку открыл, блин... И пример у него надуманный. Вот вполне реальная задачка: есть два потока, один пишет данные в очередь, другой их изымает из этой очереди. Запросто все делается без синхронизаций, и по нашим замерам получали итоговое ускорение более чем в 5 раз.
Re[13]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
G>>Фундаментальная истина, не поспоришь, особенно для процов x86 . Может быть, ты знаешь, сколько конкретнонакладных тактов будет на инструкцию XADD, через которую делается этот инкремент, а? А я тебе скажу. Если ядра работают на общем кэше — то ноль. C>А если не работают?
Ну, кстати, я оказался не совсем прав. Картину несколько портят раздельные кэша L1 для каждого из ядер — в них надо убить значения счетчика. Вторая проблема — в разделяемом кэше L2 у нас данные хранятся широкими строками. Все это — источник тормозов. Вот как оно на самом деле:
Xbox 360 Performance
The performance of synchronization instructions and functions on Xbox 360 will vary depending on what other code is running. Acquiring locks will take much longer if another thread currently owns the lock. InterlockedIncrement and critical section operations will take much longer if other threads are writing to the same cache line. The contents of the store queues can also affect performance. Therefore, all of these numbers are just approximations, generated from very simple tests:
lwsync was measured as taking 33-48 cycles.
InterlockedIncrement was measured as taking 225-260 cycles. (казалось бы, медленно, но дело в том, что в PowerPC на это уходит три инструкции, и в этот момент проц не простаивает, а моментально переключается на другой аппаратный тред, так что на практике все хорошо)
Acquiring or releasing a critical section was measured as taking about 345 cycles.
Acquiring or releasing a mutex was measured as taking about 2350 cycles.
Windows Performance
The performance of synchronization instructions and functions on Windows vary widely depending on the processor type and configuration, and on what other code is running. Multi-core and multi-socket systems often take longer to execute synchronizing instructions. Acquiring locks take much longer if another thread currently owns the lock. However, even some measurements generated from very simple tests are helpful:
MemoryBarrier was measured as taking 20-90 cycles. InterlockedIncrement was measured as taking 36-90 cycles. (Wintel рулит! Реально быстрый интерлокед инеремент, на который наложатся следующие инструкции, так как Core Duo — суперскалярный проц)
Acquiring or releasing a critical section was measured as taking 40-100 cycles.
Acquiring or releasing a mutex was measured as taking about 750-2500 cycles.
C>Подумай о nccNUMA
Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру.
Кстати, о неблокирющих структурах и микро-параллелизме на С++. Программерам на С++ ничего руками делать не надо. Все укадено до нас. http://threadingbuildingblocks.org/
Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор. Работает быстрее, программится проще. Вот пример — они параллелят DES. Имеют почти линейную масштабируемость. http://www.devx.com/go-parallel/Article/34951
Re[14]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
C>>Подумай о nccNUMA G>Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру.
Ну... Если посмотреть под определенным углом и Cell можно считать nccNUMA. И вообще, я тебе гарантирую, что nccNUMA обязательно будет — так как барьеры и полная когенертность кэшей будет непомерно дорогой на процессорах с 80 ядрами.
Более того, скорее всего будут еще и механизмы, позволяющие разбивать набор процессоров на группы, чтобы барьер в одной группе не останавливал остальные процессоры. В общем, как раз все будет устроено как в некоторых суперкомпьютерах
G>Кстати, о неблокирющих структурах и микро-параллелизме на С++. Программерам на С++ ничего руками делать не надо. Все укадено до нас. G>http://threadingbuildingblocks.org/ G>Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор.
Аллокатор там отстойный HOARD лучше, смотрел я TBB уже. Вообще, в Java есть подобный аналог (в стандартной библиотеке с JDK1.5) — набор классов в java.util.concurrent.
Sapienti sat!
Re[14]: Immutable data structures are the way of the future
> http://threadingbuildingblocks.org/ > Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор. Работает быстрее, программится проще. Вот пример — они параллелят DES. Имеют почти линейную масштабируемость. > http://www.devx.com/go-parallel/Article/34951
А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать.
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Re[15]: Immutable data structures are the way of the future
Здравствуйте, Sergey, Вы писали: S>А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать.
Ну, вообще народ говорит, что шансов на дальнейшее расслабление модели не так уж и много. В следующей версии CLR планируют ужесточить модель памяти, т.к. в настоящем виде она слишком relaxed и требует, вообще говоря, параноидального стиля программирования.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: Immutable data structures are the way of the future i
Ты то ли плохо понимашь чем отличаются неизменяемые струтуры данных от полного не использования состояния в программах, то ли не понимаешь, что наличие неизменяемых струтур не отменяет наличие изменяемых.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[16]: Immutable data structures are the way of the future
> S>А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать. > Ну, вообще народ говорит, что шансов на дальнейшее расслабление модели не так уж и много.
А что за народ, из интел или из амд?
> В следующей версии CLR планируют ужесточить модель памяти, т.к. в настоящем виде она слишком relaxed и требует, вообще говоря, параноидального стиля программирования.
А CLR то тут причем? Мы ж конкретно за Intel® Threading Building Blocks перетираем.
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Re[15]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
C>>>Подумай о nccNUMA G>>Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру. C>Ну... Если посмотреть под определенным углом и Cell можно считать nccNUMA. И вообще, я тебе гарантирую, что nccNUMA обязательно будет — так как барьеры и полная когенертность кэшей будет непомерно дорогой на процессорах с 80 ядрами.
Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. Каждый отдельный поток протормозит, но вместе они нагрузят одно ядро на процентов 70-80. При поддержке аппаратной многопоточности вполне реально сделать объединенный кэш L2 — пусть он будет высоколатентный — это не важно, с латентностью и задержками эффективно борется аппаратная многопоточность.
Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
C>Более того, скорее всего будут еще и механизмы, позволяющие разбивать набор процессоров на группы, чтобы барьер в одной группе не останавливал остальные процессоры. В общем, как раз все будет устроено как в некоторых суперкомпьютерах
Зачем так делать, если можно увеличить количество аппаратных потоков, и сделать высоколатентный, но централизованный кэш L2.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
C>>>Подумай о nccNUMA G>>Зачем? Вот когда какой-нить производитель процов анонсирует разработку системы nccNUMA, тогда и подумаю. А пока имеем, что имеем — симметричные многоядерные системы. Суперкомпьютеры я в рассчет не беру. C>Ну... Если посмотреть под определенным углом и Cell можно считать nccNUMA. И вообще, я тебе гарантирую, что nccNUMA обязательно будет — так как барьеры и полная когенертность кэшей будет непомерно дорогой на процессорах с 80 ядрами.
Кроме того. Если ты глянешь на архитектуру UltraSPARC T1 (а это первый из сильно многоядерных процов), то можно обратить внимание, что он не выполняет переупорядочивания записей (из-за которого возникает недетский геморрой и тормоза при синхронизации). Total Store Order там — это кроме прочего еще и снижает количество требуемых инструкций для синхронизации. И один кэш L2 на 8 ядер, зацепленный за коммутатор кроссбар. Это все в сумме означает мегадешевый interlocked increment (он из-за Relaxed Store Order такой дорогой у intel и ibm, собственно), и удешевление остальных примитивов синхронизации.
UltraSPARC T1 has two varieties of instructions for synchronization: memory
barriers and flush. The following memory barrier instructions ensure that any load,
store, or atomic memory operation issued after it take effect after all memory
operations issued before it:
■ MEMBAR with mmask{1} = 1 (MEMBAR #StoreLoad)
■ MEMBAR with cmask{1} = 1 (MEMBAR #MemIssue)
■ MEMBAR with cmask{2} = 1 MEMBAR #Sync)
All other types of membar instructions are treated as NOPs, since they are implied
by the TSO memory ordering protocol followed by UltraSPARC T1.
Кроме того, он выполняет переключение потока при синхронизации, накладывая на нее выполнение другого потока — о чем я и говорил. Поэтому задержка на синхронизации вобще не важна — throughput процессорного ядра она не уменьшит.
Multithreading
In UltraSPARC T1, execution is switched in round-robin fashion every cycle among
the strands that are ready to issue another instruction. Context switching is built into
the UltraSPARC T1 pipeline and takes place during the SWITCH stage, thus contexts
are switched each cycle with no pipeline stall penalty.
The following instructions change a strand from a ready-to-issue state to a not-
ready-to-issue state, until hardware determines that their input/execution
requirements can be satisfied:
■ All branches (including CALL, JMPL, etc.)
■ All VIS instructions
■ All floating point (FPops)
■ All WRPR, WR, WRHPR
■ All RDPR, RD, RDHPR
■ SAVE(D), RESTORE(D), RETURN, FLUSHW (all register management)
■ All MUL and DIV
■ MULSCC
■ MEMBAR #Sync, MEMBAR #StoreLoad, MEMBAR #MemIssue
■ FLUSH
■ All loads
■ All floating-point memory operations
■ All memory operations to alternate space
■ All atomics load-store operations
■ Prefetch
Здравствуйте, Sergey, Вы писали:
>> http://threadingbuildingblocks.org/ >> Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор. Работает быстрее, программится проще. Вот пример — они параллелят DES. Имеют почти линейную масштабируемость. >> http://www.devx.com/go-parallel/Article/34951
S>А потом вашу программу запустят на каком-нибудь очередном процессоре AMD, и вдруг окажется, что у него чуть более relaxed модель памяти, чем у процессоров intel... Лично мне стремно такую библиотеку использовать.
Не окажется. Должно быть нормально. Эта либа, кстати, портирована и на PowerPC. На AMD она, естественно, тоже работает.
И как правильно говорит товарищ Синклер, в будущем, при росте количества ядер, модель памяти будет скорее строже, чем наоборот. В Ниагаре сановской вообще TSO.
Здравствуйте, Gaperton, Вы писали:
G>Кроме того. Если ты глянешь на архитектуру UltraSPARC T1 (а это первый из сильно многоядерных процов), то можно обратить внимание, что он не выполняет переупорядочивания записей (из-за которого возникает недетский геморрой и тормоза при синхронизации). Total Store Order там — это кроме прочего еще и снижает количество требуемых инструкций для синхронизации. И один кэш L2 на 8 ядер, зацепленный за коммутатор кроссбар. Это все в сумме означает мегадешевый interlocked increment (он из-за Relaxed Store Order такой дорогой у intel и ibm, собственно), и удешевление остальных примитивов синхронизации.
Так вот только сами по себе ядра в SPARC'ах никогда особым быстродейтвием не отличались. Для массивно-параллельных задач типа жуткого сервера с кучей потоков — оно рулит, но вот матетематика с числодробилками на нем часто сосет.
Я сейчас как раз работаю (удаленно) с машинкой с UltraSparc T1 (на днях должны UltraSparc T2 привезти — жду с нетерпением). Сервера на нем вообще просто великолепно работают, а та же перекомпиляция ядра — медленнее, чем на моей скромной домашней Core 2 Duo машине.
G>Кроме того, он выполняет переключение потока при синхронизации, накладывая на нее выполнение другого потока — о чем я и говорил. Поэтому задержка на синхронизации вобще не важна — throughput процессорного ядра она не уменьшит.
Ну это сказки — на практике будет cache thrashing, уже наблюдали такое с HyperThreading. Хотя как оптимизация — действительно работает неплохо.
G>Именно таким образом будут выглядеть процы ближайшего будущего, дружище. Вот оно, будущее. Все просто, и никаких извратов. G>http://opensparc-t1.sunsource.net/specs/UST1-UASuppl-current-draft-HP-EXT.pdf
Можно чуть дальше в прошлое на Cray'и с их кучей fine-grained барьеров посмотреть (могу найти PDFку с описанием). Не секрет, что настольные PC примерно на 20 лет отстают от суперкомпьютеров. Так что, скоро nccNUMA будет дальше появляться.
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
G>>Именно таким образом будут выглядеть процы ближайшего будущего, дружище. Вот оно, будущее. Все просто, и никаких извратов. G>>http://opensparc-t1.sunsource.net/specs/UST1-UASuppl-current-draft-HP-EXT.pdf C>Можно чуть дальше в прошлое на Cray'и с их кучей fine-grained барьеров посмотреть (могу найти PDFку с описанием). Не секрет, что настольные PC примерно на 20 лет отстают от суперкомпьютеров. Так что, скоро nccNUMA будет дальше появляться.
Было бы интересно посмотреть пдфку
Re[16]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток.
Погоди, тут я чего-то не понимаю. Мы говорим про thread context switch или про что?
Переключение потока, вроде бы, тоже не сахар. Поскольку у потока как минимум свой стек, переключение нарушит локальность и с высокой вероятностью приведет к сбросу кэша. А это опять сбегать в основную память.
G>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу.
Чего-то я фундаментально не понимаю.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[17]: Immutable data structures are the way of the future
Здравствуйте, Sinclair, Вы писали:
G>>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. S>Погоди, тут я чего-то не понимаю. Мы говорим про thread context switch или про что?
Ага.
S>Переключение потока, вроде бы, тоже не сахар. Поскольку у потока как минимум свой стек, переключение нарушит локальность и с высокой вероятностью приведет к сбросу кэша. А это опять сбегать в основную память.
Это решается созданием нескольких кэшей — по штуке на поток. Хотя, AFAIR, в P4 только L1 переключался.
Sapienti sat!
Re[18]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали: C>Это решается созданием нескольких кэшей — по штуке на поток. Хотя, AFAIR, в P4 только L1 переключался.
8-0 Это как? У нас в системе живет несколько тысяч (если не десятков тысяч) потоков. Сколько-сколько кэшей мы собираемся создать???
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[19]: Immutable data structures are the way of the future
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Cyberax, Вы писали: C>>Это решается созданием нескольких кэшей — по штуке на поток. Хотя, AFAIR, в P4 только L1 переключался. S>8-0 Это как? У нас в системе живет несколько тысяч (если не десятков тысяч) потоков. Сколько-сколько кэшей мы собираемся создать???
Два на одно вычислительное ядро Для ОС одно физическое ядро будет видно как два логических CPU.
Sapienti sat!
Re[17]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
G>>Вас всех совершенно напрасно волнуют задержки синхронизации. Ответ на эти проблемы у производителей сейчас простой — аппаратная многопоточность. Черт с ней, большой задержкой на операцию — в это время запускается другой аппаратный поток. Каждый отдельный поток протормозит, но вместе они нагрузят одно ядро на процентов 70-80. При поддержке аппаратной многопоточности вполне реально сделать объединенный кэш L2 — пусть он будет высоколатентный — это не важно, с латентностью и задержками эффективно борется аппаратная многопоточность. C>Только вот куча задач у нас реально однопоточна — поэтому жуткие замедления на синхронизации будут убивать производительность. А если выкидывать все примитивы синхронизации — то тогда получаем и полную невозможность использовать многопоточность.
Ты подумай над тем, что ты сказал Если у тебя куча задач однопоточна — то в них нечего синхронизировать, и не будет жутких заедлений на синхронизации. Если у тебя задача сильно многопоточна, и эта куча потоков нагружает ядро процентов на 80% — то эта куча потоков в совокупности будет работать настолько быстро, насколько возможно, и не важно, какая задержка синхронизации будет на каждом из потоков.
C>Причем, это не теория — а вполне себе реальная практика с HyperThreading'овыми CPU.
HyperThreading — крайне неудачная технология, которая имеет мало общего с современной аппаратной многопоточностью. Аппаратные потоки в ниагаре и в процах интела, которые готовятся к выпуску, совсем другие. Так что эта "практика" никак не соотносится с "теорией".
Нормальльная, настоящая практика — это работа Ниагары, доступ к которой у тебя как ты пишешь есть.
C>Там как раз та же ситуация, но по другой причине — длинный pipeline делал синхронизацию очень дорогой, и в качестве метода борьбы использовали переключение потоков. В результате, очень часто получали ЗАМЕДЛЕНИЕ вместо ускорения.
Длинный пайплайн — проблема архитектуры P4. В современных многопоточных процах конвейр короткий. В ниагаре если мне не изменяет память всего 7 стадий конвейра. И аппаратные потоки там совсем другие.
C>>>Более того, скорее всего будут еще и механизмы, позволяющие разбивать набор процессоров на группы, чтобы барьер в одной группе не останавливал остальные процессоры. В общем, как раз все будет устроено как в некоторых суперкомпьютерах G>>Зачем так делать, если можно увеличить количество аппаратных потоков, и сделать высоколатентный, но централизованный кэш L2. C>См. выше.
Не аргумент ИМХО. Аппелировать к гипертредингу — некорректно.
Re[18]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
C>>Только вот куча задач у нас реально однопоточна — поэтому жуткие замедления на синхронизации будут убивать производительность. А если выкидывать все примитивы синхронизации — то тогда получаем и полную невозможность использовать многопоточность. G>Ты подумай над тем, что ты сказал Если у тебя куча задач однопоточна — то в них нечего синхронизировать, и не будет жутких заедлений на синхронизации.
Дело в том, что множество задач — преимущественно однопоточны. Самый тупой пример — GUI с worker-thread'ами для длительных задач.
C>>Причем, это не теория — а вполне себе реальная практика с HyperThreading'овыми CPU. G>HyperThreading — крайне неудачная технология, которая имеет мало общего с современной аппаратной многопоточностью. Аппаратные потоки в ниагаре и в процах интела, которые готовятся к выпуску, совсем другие. Так что эта "практика" никак не соотносится с "теорией".
Чем они другие?
G>Нормальльная, настоящая практика — это работа Ниагары, доступ к которой у тебя как ты пишешь есть.
А в чем у нас там будут фундаментальные различия?
C>>Там как раз та же ситуация, но по другой причине — длинный pipeline делал синхронизацию очень дорогой, и в качестве метода борьбы использовали переключение потоков. В результате, очень часто получали ЗАМЕДЛЕНИЕ вместо ускорения. G>Длинный пайплайн — проблема архитектуры P4. В современных многопоточных процах конвейр короткий. В ниагаре если мне не изменяет память всего 7 стадий конвейра. И аппаратные потоки там совсем другие.
Длинный пайплайн, в данном случае, это просто причина подобного эффекта. В 80-процессорной машине у нас будут задержки из-за необходимости обеспечения когерентности, а в P4 были задержки из-за срывов pipeline'а.
C>>См. выше. G>Не аргумент ИМХО. Аппелировать к гипертредингу — некорректно.
Это тот же самый механизм, придуманый для лечения подобных же эффектов. Так что, ИМХО, вполне корректно.
Sapienti sat!
Re[19]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
C>>>Только вот куча задач у нас реально однопоточна — поэтому жуткие замедления на синхронизации будут убивать производительность. А если выкидывать все примитивы синхронизации — то тогда получаем и полную невозможность использовать многопоточность. G>>Ты подумай над тем, что ты сказал Если у тебя куча задач однопоточна — то в них нечего синхронизировать, и не будет жутких заедлений на синхронизации. C>Дело в том, что множество задач — преимущественно однопоточны. Самый тупой пример — GUI с worker-thread'ами для длительных задач.
Суть дела это не меняет — в преимущественно однопоточной задаче не будет жутких замедлений на синхронизации, за преимущественно отсутствием таковой. В случае гуя так это вообще пофигу — там человек не заметит никаких задержек даже на тысячу тактов.
C>>>Причем, это не теория — а вполне себе реальная практика с HyperThreading'овыми CPU. G>>HyperThreading — крайне неудачная технология, которая имеет мало общего с современной аппаратной многопоточностью. Аппаратные потоки в ниагаре и в процах интела, которые готовятся к выпуску, совсем другие. Так что эта "практика" никак не соотносится с "теорией". C>Чем они другие?
Тем, что в ниагаре потоки переключаются каждый такт, их много на одно ядро, и основная их задача — борьба с задержками при обращении в память. И они с этой задачей великолепно справляются, так как вокруг этой идеи спроектирована вся Ниагара.
У пня — длинный конвейр и суперскалярное выполнение. Его несчастных два аппаратных потока переключаются не каждый такт (иначе суперскаляр не будет работать), переключение их дороже чем в ниагаре, и это, с одной стороны, никак не помогает в борьбе с задержками при обращении к памяти, более того — усугубляет проблему вытеснением данных из кэшей — два аппаратных суперскалярных потока работая подолгу конкурируют за один разделяемый кэш мешая друг другу, а кэш в силу их суперскалярности для них как воздух — их производительность очень критична к хитам в кэш.
В результате, суперскалярному пню этот гипертрединг — как собаке пятая нога, толку от него практически ноль. А в дизайне Ниагары наоборот — никакого суперскаляра, очень простые ядра, и все построено вокруг аппаратных потоков — поэтому в Ниагаре этих ядер 8 штук, а аппаратных потоков 32. А в пне — одно ядро, и два потока. Разницу в цифрах чувствуешь? Глядя на одни цифры уже можно понять, насколько это разные технологии.
Взять синхронизацию — в ниагаре у тебя TSO, в P4 у тебя ацкое переупорядочивание записей (что дает дикий оверхэд на синхронизацию). Отличий дофига — нет в мире более разных процов, чем Ниагара и P4. Между ними вообще общего ничего нет.
G>>Нормальльная, настоящая практика — это работа Ниагары, доступ к которой у тебя как ты пишешь есть. C>А в чем у нас там будут фундаментальные различия?
См выше.
C>>>Там как раз та же ситуация, но по другой причине — длинный pipeline делал синхронизацию очень дорогой, и в качестве метода борьбы использовали переключение потоков. В результате, очень часто получали ЗАМЕДЛЕНИЕ вместо ускорения. G>>Длинный пайплайн — проблема архитектуры P4. В современных многопоточных процах конвейр короткий. В ниагаре если мне не изменяет память всего 7 стадий конвейра. И аппаратные потоки там совсем другие. C>Длинный пайплайн, в данном случае, это просто причина подобного эффекта. В 80-процессорной машине у нас будут задержки из-за необходимости обеспечения когерентности, а в P4 были задержки из-за срывов pipeline'а.
Когерентность обойдется гораздо дешевле при дизайне а-ля Ниагара, и Ниагара устроена так, чтобы задержки были пофигу. Ты вообще читал мои объяснения про аппаратную многопоточность? Для кого пишу, блин?
G>>Не аргумент ИМХО. Аппелировать к гипертредингу — некорректно. C>Это тот же самый механизм, придуманый для лечения подобных же эффектов. Так что, ИМХО, вполне корректно.
Похожий механизм (общее там только то, что и там и там два контекста выполнения аппаратно хранятся, все остальное — различия), работающий в совершенно другом контексте, решающий другие проблемы, и создающий новые проблемы. Так что некорректно совершенно.
Re[20]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Sinclair, Вы писали:
S>>Здравствуйте, Cyberax, Вы писали: C>>>Это решается созданием нескольких кэшей — по штуке на поток. Хотя, AFAIR, в P4 только L1 переключался. S>>8-0 Это как? У нас в системе живет несколько тысяч (если не десятков тысяч) потоков. Сколько-сколько кэшей мы собираемся создать??? C>Два на одно вычислительное ядро Для ОС одно физическое ядро будет видно как два логических CPU.
Ты чо Синклера пугаешь? Какие нафиг два кэша на одно ядро? Ты так собрался бороться с вытеснением данных из кэша штоли? Так это проще делается — аппаратные потоки переключаются каждый такт, и все. Как и сделано в Ниагаре. Чтобы снять вопросы об эффективности такого подхода — в Ниагаре размеры кэшей L1 меньше, чем у любого из современных серверных процов, и при этом
At the time of its release in December of 2005, a single chip, eight core, 32-thread, 1.2 GHz UltraSPARC T1 server performed similarly to a two-socket, four-core, eight-thread, 1.9 GHz IBM POWER5 server, performed similarly to a four socket, eight-core, sixteen-thread 3.0 GHz Intel Xeon "Paxville MP" server, and exceeded the performance of a four socket, four-core, four-thead 1.6 GHz Intel Itanium server. Arguably, this made the UltraSPARC T1 the world's most powerful general-purpose commercial server processors, when considering multithreaded commercial workloads.
Re[18]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
G>>Кроме того. Если ты глянешь на архитектуру UltraSPARC T1 (а это первый из сильно многоядерных процов), то можно обратить внимание, что он не выполняет переупорядочивания записей (из-за которого возникает недетский геморрой и тормоза при синхронизации). Total Store Order там — это кроме прочего еще и снижает количество требуемых инструкций для синхронизации. И один кэш L2 на 8 ядер, зацепленный за коммутатор кроссбар. Это все в сумме означает мегадешевый interlocked increment (он из-за Relaxed Store Order такой дорогой у intel и ibm, собственно), и удешевление остальных примитивов синхронизации. C>Так вот только сами по себе ядра в SPARC'ах никогда особым быстродейтвием не отличались. Для массивно-параллельных задач типа жуткого сервера с кучей потоков — оно рулит, но вот матетематика с числодробилками на нем часто сосет.
Первая ниагара имеет одно FPU на восемь ядер, она не для числодробления презназначена, а для enterprise servers. А вот вторая ниагара (ultrasparc t2) на плавающей запятой порвет все xeon-ы и core duo на кровавые ошметки — там у каждого из ядер свое FPU.
C>Я сейчас как раз работаю (удаленно) с машинкой с UltraSparc T1 (на днях должны UltraSparc T2 привезти — жду с нетерпением). Сервера на нем вообще просто великолепно работают, а та же перекомпиляция ядра — медленнее, чем на моей скромной домашней Core 2 Duo машине.
Ничего удивительного тут нет. Во первых, "скромный" core 2 duo — самый совершенный суперскалярный (рассчитанный на однопоточные приложения) проц за всю историю человечества. Перекомпиляция ядра — однопоточное приложение. UltraSparc T1 предназначен для эффективного выполнения параллельных программ. При частоте 1.2 Мгц эффективная частота одного виртуального проца будет 300 Мгц. Так как он single issue — то он работает чуть ли не медленнее второго пня. Однако, скажем, mysql запущенный на ультраспарке и хорошо нагруженный запросами обойдет твой коре дуо раз в десять.
Далее. Если ты воспользуешься параллельным билдом — есть такие средства, то твой коре дуо также начнет сосать.
G>>Кроме того, он выполняет переключение потока при синхронизации, накладывая на нее выполнение другого потока — о чем я и говорил. Поэтому задержка на синхронизации вобще не важна — throughput процессорного ядра она не уменьшит. C>Ну это сказки — на практике будет cache thrashing, уже наблюдали такое с HyperThreading. Хотя как оптимизация — действительно работает неплохо.
Это реальность. А гипетрединг — относится к аппаратной многопоточности ниагары как наручные часы к многоквартирному дому. Посмотри бенчмарки — Ниагара самый быстрый проц в мире на целочисленных операциях, и кэша у нег меньше. А вторая ниагара — самый быстрый проц на плавающей запятой. http://rsdn.ru/forum/message/2697806.1.aspx
G>>Именно таким образом будут выглядеть процы ближайшего будущего, дружище. Вот оно, будущее. Все просто, и никаких извратов. G>>http://opensparc-t1.sunsource.net/specs/UST1-UASuppl-current-draft-HP-EXT.pdf C>Можно чуть дальше в прошлое на Cray'и с их кучей fine-grained барьеров посмотреть (могу найти PDFку с описанием). Не секрет, что настольные PC примерно на 20 лет отстают от суперкомпьютеров. Так что, скоро nccNUMA будет дальше появляться.
О чем ты? Нет никаких таких суперкомпьютеров. Все суперкомпьтеры давным давно, уже лет 10 как минимум, собираются на мэйнстримовых микропроцессорах (стойки соедняются через merynet или infiniband), Крэй сто лет назад раззорился и был выкуплен силикон графиксом, и делает свои сервера на Оптеронах. Это уже давно не так. Даже мйнфреймы сейчас работают на кастомизированной версии проца Power 5 с микропрограмной поддержкой. На этот старый crap 20-летней давности уже сейчас никто не смотрит. Основных направлений исследований по данной теме сейчас четыре.
1) fine-grain hardware multithreading.
2) stream processing (суперкопьютеры 20-летней давности сосут — идеи идут от современных 3D ускорителей, совершивших технологический прорыв)
3) reconfigurable computing (идеи идут от FPGA — совершивших технологический прорыв)
4) Перспективные модели параллельного программирования и их аппаратная поддерджка (transactional memory, kernel-stream model, lock-free datastructures, etc)
Здравствуйте, Gaperton, Вы писали:
C>>Два на одно вычислительное ядро Для ОС одно физическое ядро будет видно как два логических CPU. G>Ты чо Синклера пугаешь? Какие нафиг два кэша на одно ядро?
Я про P4 говорил.
Sapienti sat!
Re[22]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>Здравствуйте, Gaperton, Вы писали:
C>>>Два на одно вычислительное ядро Для ОС одно физическое ядро будет видно как два логических CPU. G>>Ты чо Синклера пугаешь? Какие нафиг два кэша на одно ядро? C>Я про P4 говорил.
Ну тогда извини .
Re[20]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
C>>Дело в том, что множество задач — преимущественно однопоточны. Самый тупой пример — GUI с worker-thread'ами для длительных задач. G>Суть дела это не меняет — в преимущественно однопоточной задаче не будет жутких замедлений на синхронизации, за преимущественно отсутствием таковой. В случае гуя так это вообще пофигу — там человек не заметит никаких задержек даже на тысячу тактов.
Фига, будет. Банальные мутирующие строки будут требовать захватывать мьютекс при каждом обращении (или заставлять пользователя вручную проверять, что работа со строками прикрыта каким-то мьютексом). Так как мы не знаем точно, есть ли у нас в данный момент конкуррентный поток (и пофиг, что в большинстве случаев его не будет).
Ты еще учти, что скорее всего не удастся сохранить производительность текущих процессоров при записи в память при увеличении количества ядер. На Sparc'е с его 32 (AFAIR) регистрами это еще не так плохо, а вот на x86 — будет очень даже заметно.
C>>Чем они другие? G>Тем, что в ниагаре потоки переключаются каждый такт, их много на одно ядро, и основная их задача — борьба с задержками при обращении в память. И они с этой задачей великолепно справляются, так как вокруг этой идеи спроектирована вся Ниагара.
Переключение каждый такт — это непринципиально.
G>У пня — длинный конвейр и суперскалярное выполнение. Его несчастных два аппаратных потока переключаются не каждый такт (иначе суперскаляр не будет работать), переключение их дороже чем в ниагаре, и это, с одной стороны, никак не помогает в борьбе с задержками при обращении к памяти, более того — усугубляет проблему вытеснением данных из кэшей — два аппаратных суперскалярных потока работая подолгу конкурируют за один разделяемый кэш мешая друг другу, а кэш в силу их суперскалярности для них как воздух — их производительность очень критична к хитам в кэш.
В P4 оно тоже используется для борьбы с задержками при промахе по кэшу (и срывами pipeline'а) — у каждого логического ядра свой L1-кэш.
G>В результате, суперскалярному пню этот гипертрединг — как собаке пятая нога, толку от него практически ноль. А в дизайне Ниагары наоборот — никакого суперскаляра, очень простые ядра, и все построено вокруг аппаратных потоков — поэтому в Ниагаре этих ядер 8 штук, а аппаратных потоков 32. А в пне — одно ядро, и два потока. Разницу в цифрах чувствуешь? Глядя на одни цифры уже можно понять, насколько это разные технологии.
Ты на цену посмотри еще Понятно, что T1 — это процессор для больших серверов, а P4 — десктопный. Поэтому и такая разница в количестве ядер.
C>>Длинный пайплайн, в данном случае, это просто причина подобного эффекта. В 80-процессорной машине у нас будут задержки из-за необходимости обеспечения когерентности, а в P4 были задержки из-за срывов pipeline'а. G>Когерентность обойдется гораздо дешевле при дизайне а-ля Ниагара, и Ниагара устроена так, чтобы задержки были пофигу. Ты вообще читал мои объяснения про аппаратную многопоточность? Для кого пишу, блин?
Читаю. Кстати, ты еще учти, что во время выполнения Interlocked — у тебя ВСЕ ядра будут курить бамбук при попытках обращения к памяти (шина-то блокирована, однако).
Здравствуйте, Gaperton, Вы писали:
C>>Так вот только сами по себе ядра в SPARC'ах никогда особым быстродейтвием не отличались. Для массивно-параллельных задач типа жуткого сервера с кучей потоков — оно рулит, но вот матетематика с числодробилками на нем часто сосет. G>Первая ниагара имеет одно FPU на восемь ядер, она не для числодробления презназначена, а для enterprise servers. А вот вторая ниагара (ultrasparc t2) на плавающей запятой порвет все xeon-ы и core duo на кровавые ошметки — там у каждого из ядер свое FPU.
Я имею в виду целочисленные задачи. Как результат — не рвет на всех задачах. Сказывается примитивность отдельно взятого ядра — достаточно чтобы в вычислении были непараллелизуемые участки, и производительность уходит в пол.
C>>Я сейчас как раз работаю (удаленно) с машинкой с UltraSparc T1 (на днях должны UltraSparc T2 привезти — жду с нетерпением). Сервера на нем вообще просто великолепно работают, а та же перекомпиляция ядра — медленнее, чем на моей скромной домашней Core 2 Duo машине. G>Ничего удивительного тут нет. Во первых, "скромный" core 2 duo — самый совершенный суперскалярный (рассчитанный на однопоточные приложения) проц за всю историю человечества. Перекомпиляция ядра — однопоточное приложение. UltraSparc T1 предназначен для эффективного выполнения параллельных программ.
Перекомпиляция ядра — параллельный процесс (make -jN, где N — количество параллельных задач, встроено в сам make). На моем Core 2 Duo максимум производительности у меня при N=3, на T1 — при N=6. Тем не менее, все равно Core 2 Duo работает быстрее.
G>О чем ты? Нет никаких таких суперкомпьютеров. Все суперкомпьтеры давным давно, уже лет 10 как минимум, собираются на мэйнстримовых микропроцессорах (стойки соедняются через merynet или infiniband), Крэй сто лет назад раззорился и был выкуплен силикон графиксом, и делает свои сервера на Оптеронах. Это уже давно не так. Даже мйнфреймы сейчас работают на кастомизированной версии проца Power 5 с микропрограмной поддержкой. На этот старый crap 20-летней давности уже сейчас никто не смотрит. Основных направлений исследований по данной теме сейчас четыре.
Кстати, ты про суперкомпьютерные кластеры очень хорошо напомнил — это как раз nccNUMA, точнее NORMA (No Remote Memory Access). Там обращение к памяти соседнего узла стоит очень дорого — поэтому даже и не пытаются заниматься фигней вроде автоматической когенрентности памяти, а сразу используют явную передачу сообщений.
Sapienti sat!
Re[21]: Immutable data structures are the way of the future
Здравствуйте, Cyberax, Вы писали:
C>>>Дело в том, что множество задач — преимущественно однопоточны. Самый тупой пример — GUI с worker-thread'ами для длительных задач. G>>Суть дела это не меняет — в преимущественно однопоточной задаче не будет жутких замедлений на синхронизации, за преимущественно отсутствием таковой. В случае гуя так это вообще пофигу — там человек не заметит никаких задержек даже на тысячу тактов. C>Фига, будет. Банальные мутирующие строки будут требовать захватывать мьютекс при каждом обращении (или заставлять пользователя вручную проверять, что работа со строками прикрыта каким-то мьютексом). Так как мы не знаем точно, есть ли у нас в данный момент конкуррентный поток (и пофиг, что в большинстве случаев его не будет).
Мутирующие строки — это не мьютекс, а легковесная критическая секция в юзер-моде. Которая 1) будет быстрее, чем в x86 из-за total store order, 2) будет быстрее, чем откопировать строку, и 2) на захват которой наложится один из 3-х аппаратных потоков, и в реальности будет пофиг. Конкурирующий поток, разумеется, будет присутствовать в правильно написанном параллелном приложении — в большинстве случаев он будет. А если мы знаем, что его в большинстве случаев не будет, то и fine-grain синхронизацию на объекте типа строка делать — это идиотизм, нашпигованные мьютексами строки это просто плохой дизайн.
C>Ты еще учти, что скорее всего не удастся сохранить производительность текущих процессоров при записи в память при увеличении количества ядер. На Sparc'е с его 32 (AFAIR) регистрами это еще не так плохо, а вот на x86 — будет очень даже заметно.
Удастся. Я с дизайном процов несколько так знаком — и как раз с этим я вообще никаких проблем не вижу. Я вообще не понимаю твоих абстрактных теоретических рассуждений, когда у тебя есть под рукой UltraSPARC T1, и доступны тесты SPEC и TPC к нему. Сосут текущие процы, сосут.
C>>>Чем они другие? G>>Тем, что в ниагаре потоки переключаются каждый такт, их много на одно ядро, и основная их задача — борьба с задержками при обращении в память. И они с этой задачей великолепно справляются, так как вокруг этой идеи спроектирована вся Ниагара. C>Переключение каждый такт — это непринципиально.
Это принципиально, что совершенно очевидно. Один поток не сможет отработать достаточно долго, чтобы вытеснить из кэша данные второго потока, если они переключаются на каждый такт. Опять же, странно слышать такие умозрительные рассуждения при доступности бенчмарков и спецификаций доказывающих обратное.
16 KB primary instruction cache per core
— Parity protected and single-bit error recoverable
— 4-way set-associative
8 KB primary data cache per core
— Parity protected and single-bit error recoverable
— 4-way set-associative
3 MB unifed level 2 cache
— 12-way set associative, 4 banks
— ECC
Вопросы есть по размерам общих кэшей L1на одно ядро? Думаешь идиоты в сане сидят, и они перформанс не моделировали, когда общие кэша ставили на ядра небольшого размера, да? И тестам тоже не веришь, да, весь мир тебя обманывает?
G>>У пня — длинный конвейр и суперскалярное выполнение. Его несчастных два аппаратных потока переключаются не каждый такт (иначе суперскаляр не будет работать), переключение их дороже чем в ниагаре, и это, с одной стороны, никак не помогает в борьбе с задержками при обращении к памяти, более того — усугубляет проблему вытеснением данных из кэшей — два аппаратных суперскалярных потока работая подолгу конкурируют за один разделяемый кэш мешая друг другу, а кэш в силу их суперскалярности для них как воздух — их производительность очень критична к хитам в кэш. C>В P4 оно тоже используется для борьбы с задержками при промахе по кэшу (и срывами pipeline'а) — у каждого логического ядра свой L1-кэш.
Не сильно это поможет суперскалярному процу. Что и видно по тестам. Херовый там гипертрединг. А в ниагаре L1 кэш общий, он маленький, и работает при этом она быстрее. Смотри бенчмарки.
G>>В результате, суперскалярному пню этот гипертрединг — как собаке пятая нога, толку от него практически ноль. А в дизайне Ниагары наоборот — никакого суперскаляра, очень простые ядра, и все построено вокруг аппаратных потоков — поэтому в Ниагаре этих ядер 8 штук, а аппаратных потоков 32. А в пне — одно ядро, и два потока. Разницу в цифрах чувствуешь? Глядя на одни цифры уже можно понять, насколько это разные технологии. C>Ты на цену посмотри еще Понятно, что T1 — это процессор для больших серверов, а P4 — десктопный. Поэтому и такая разница в количестве ядер.
Слушай, ну хватит, смешно уже. Такая разница в количестве ядер не потому, что ниагара серверная, а пень — десктопный, а потому, что одно ядро Ниагары вместе с кэшом L1 занимает 12 мм2 на техпроцессе 0.90. На, полюбуйся на floorplan ниагары.
Сравни с ядром четвертого пня, которое без кэшей занимает более 135 мм2. Обрати внимание — ядро prescott занимает примерно 80 мм2 на том же техпроцессе.
Сравнивать, конечно, с несчастным p4 неспортивно. Надо с серверными процами от интела — которые имеют жирные кэша и сравнимую площадь кристалла. Ниагара у нас
performed similarly to a four socket, eight-core, sixteen-thread 3.0 GHz Intel Xeon "Paxville MP" server.
exceeded the performance of a four socket, four-core, four-thead 1.6 GHz Intel Itanium server.
Ай-ай-ай. Что-то не помогает "серверность" ни итаниумам, ни ксеонам. Сосут, пнимаешь. И посмотри, конечно же, на цену .
C>>>Длинный пайплайн, в данном случае, это просто причина подобного эффекта. В 80-процессорной машине у нас будут задержки из-за необходимости обеспечения когерентности, а в P4 были задержки из-за срывов pipeline'а. G>>Когерентность обойдется гораздо дешевле при дизайне а-ля Ниагара, и Ниагара устроена так, чтобы задержки были пофигу. Ты вообще читал мои объяснения про аппаратную многопоточность? Для кого пишу, блин? C>Читаю. Кстати, ты еще учти, что во время выполнения Interlocked — у тебя ВСЕ ядра будут курить бамбук при попытках обращения к памяти (шина-то блокирована, однако).
Блин, нифига ты не втыкаешь. Что надо сделать, чтобы объяснить еще понятнее? Откуда ты вообще это дикое, не побоюсь этого слова, предположение взял?
1) Какая нахрен шина. НЕТ у ниагары никакой шины памяти — процы зацеплены между собой и кэшем через коммутатор типа "кроссбар", который обеспечивает неблокирующий обмен данными во все направлениях, плюс возможность broadcast рассылки за то же время, что и передача point-to-point. В центре кристалла такой прямоугольничек — посмотри. Тэги кэша L2 (посмотри на картинку еще раз) хранятся рядом с каждым ядром, данные о блокировках будут лежать в них.
2) Блокировка является асинхронной операцией, которая временно приостановит поток, который ждет блокировки, и все. Все остальные потоки того же ядра продолжат работу. Все потоки всех остальных ядер этого вообще не заметят.
G>Сравни с ядром четвертого пня, которое без кэшей занимает более 135 мм2. Обрати внимание — ядро prescott занимает примерно 80 мм2 на том же техпроцессе.
Разумеется, с кэшами занимает ровно 135 мм2. Очепятка. Без L2 кэша — 80 мм2. G>
Здравствуйте, Gaperton, Вы писали:
C>>Я имею в виду целочисленные задачи. Как результат — не рвет на всех задачах. Сказывается примитивность отдельно взятого ядра — достаточно чтобы в вычислении были непараллелизуемые участки, и производительность уходит в пол. G>Ну, батенька, параллелить же надо. Понятно что отдельное ядро там тупое до безобразия — в этом вся и штука.
Ну так, батенька, не все же можно распараллелить.
C>>Перекомпиляция ядра — параллельный процесс (make -jN, где N — количество параллельных задач, встроено в сам make). На моем Core 2 Duo максимум производительности у меня при N=3, на T1 — при N=6. Тем не менее, все равно Core 2 Duo работает быстрее. G>На шести параллельных задачах t1 никак не сможет обогнать core 2 duo — это технически невозможно. Почему он медленнее на 32-х, или хотя бы восьми? Задачи то совершенно независимы.
А х.з., не может оно нагрузить больше 6-8 процессоров.
Вот, кстати, тоже не очень лестный benchmark: http://tweakers.net/reviews/649/10/database-test-sun-ultrasparc-t1-vs-amd-opteron-pagina-10.html
C>>Кстати, ты про суперкомпьютерные кластеры очень хорошо напомнил — это как раз nccNUMA, точнее NORMA (No Remote Memory Access). Там обращение к памяти соседнего узла стоит очень дорого — поэтому даже и не пытаются заниматься фигней вроде автоматической когенрентности памяти, а сразу используют явную передачу сообщений. G>Ну если ты считаешь передачу сообщений nccNUMA, то тогда я с тобой соглашусь. Асинхронные сообщения — это хорошо и удобно, ничего против не имею. Только необходимости применять это внутри кристалла пока вроде как нет — и так пока справляются.
Message passing — это вырожденная nccNUMA, мы просто вообще убираем общую память. Обычная nccNUMA — это промежуточный вариант, у нас все еще есть общая память, но доступ к ней уже требует определенных дополнительных действий (барьеры и т.п.). Кстати, транзакционная память вообще идеально к nccNUMA подходит.
G>Ты в кристалл все равно слишком много ядер не засунешь — коммерческая площадь кристалла не зависит от применяемого техпроцесса, и составляет около 200 мм2 плюс-минус 50 — если экстремальные случаи не рассматривать.
Ты закон Мура помнишь? По прогнозам, он будет работать до 2015 года минимум. Если взять сегодняшний Core Quatro, то к 2015 он как раз станет где-то Core 64 просто благодаря увеличению плотности. Ну а дальше возможно будут многослойные ядра и прочая магия.
У меня вообще очень простая логика — ни одна Ниагара не сможет поднять однопоточную производительность без введения out-of-order исполнения, предикторов и больших кэшей. Однако, эти фичи сделают TSO и глобальную когерентность кэшей непомерно дорогими. Значит придется как-то с этим бороться — ну а тут ничего лучше nccNUMA пока не придумали.
Здравствуйте, Cyberax, Вы писали:
C>>>Я имею в виду целочисленные задачи. Как результат — не рвет на всех задачах. Сказывается примитивность отдельно взятого ядра — достаточно чтобы в вычислении были непараллелизуемые участки, и производительность уходит в пол. G>>Ну, батенька, параллелить же надо. Понятно что отдельное ядро там тупое до безобразия — в этом вся и штука. C>Ну так, батенька, не все же можно распараллелить.
Пример пожалуйста. Ща будем параллелить.
C>>>Перекомпиляция ядра — параллельный процесс (make -jN, где N — количество параллельных задач, встроено в сам make). На моем Core 2 Duo максимум производительности у меня при N=3, на T1 — при N=6. Тем не менее, все равно Core 2 Duo работает быстрее. G>>На шести параллельных задачах t1 никак не сможет обогнать core 2 duo — это технически невозможно. Почему он медленнее на 32-х, или хотя бы восьми? Задачи то совершенно независимы. C>А х.з., не может оно нагрузить больше 6-8 процессоров.
C>Вот, кстати, тоже не очень лестный benchmark: http://tweakers.net/reviews/649/10/database-test-sun-ultrasparc-t1-vs-amd-opteron-pagina-10.html
Ну не знаю. Вот бенчмарки SPEC. http://www.anandtech.com/cpuchipsets/showdoc.aspx?i=2657&p=4
C>>>Кстати, ты про суперкомпьютерные кластеры очень хорошо напомнил — это как раз nccNUMA, точнее NORMA (No Remote Memory Access). Там обращение к памяти соседнего узла стоит очень дорого — поэтому даже и не пытаются заниматься фигней вроде автоматической когенрентности памяти, а сразу используют явную передачу сообщений. G>>Ну если ты считаешь передачу сообщений nccNUMA, то тогда я с тобой соглашусь. Асинхронные сообщения — это хорошо и удобно, ничего против не имею. Только необходимости применять это внутри кристалла пока вроде как нет — и так пока справляются. C>Message passing — это вырожденная nccNUMA, мы просто вообще убираем общую память. Обычная nccNUMA — это промежуточный вариант, у нас все еще есть общая память, но доступ к ней уже требует определенных дополнительных действий (барьеры и т.п.). Кстати, транзакционная память вообще идеально к nccNUMA подходит.
Что-то я не понимаю, а чем то отличается от обычной памяти в любом современно многоядерном проце? У тебя и в ниагаре есть общая память, но доступ к ней тоже тебует дополнительных действий. Тот же самый MEMBAR надо выставить. Можешь и не высталвять пожалуйста. Когерентность кэшей L1 практически нигде автоматом не поддерживается, знаешь ли, это технически сложно, и дает большую просадку даже для двух ядер. Везде надо специальные инструкции выдавать.
G>>Ты в кристалл все равно слишком много ядер не засунешь — коммерческая площадь кристалла не зависит от применяемого техпроцесса, и составляет около 200 мм2 плюс-минус 50 — если экстремальные случаи не рассматривать. C>Ты закон Мура помнишь? По прогнозам, он будет работать до 2015 года минимум. Если взять сегодняшний Core Quatro, то к 2015 он как раз станет где-то Core 64 просто благодаря увеличению плотности. Ну а дальше возможно будут многослойные ядра и прочая магия.
Закон мура перестал работать примерно в 2003 году. Я еще полтора года назад в свои презентации графики вставлял, которые это показывают. Посмотри на графики роста тактовой частоты и как они кореллируют с техпроцессом — не растет уже тактовая частота, проблемы с этим. Не заметил, что частоты у процов понизились?
Core 64 ты утончением техпроцесса не получишь. Можешь просто посчитать, насколькр больше таких ядер влезет на техпроцесс 20нм, если сейчас core 2 duo делается на 65 нм. Мало запихать в один кристалл много ядер. Надо решать проблемы общего доступа к памяти (количество ног у микросхем не подчиняется закону мура, извини), суметь накормить данными эти ядра, и решить вопросы синхронизации. Суперскалярные процы типа Core Duo будут иметь большие проблемы при увеличении количества ядер.
C>У меня вообще очень простая логика — ни одна Ниагара не сможет поднять однопоточную производительность без введения out-of-order исполнения, предикторов и больших кэшей. Однако, эти фичи сделают TSO и глобальную когерентность кэшей непомерно дорогими. Значит придется как-то с этим бороться — ну а тут ничего лучше nccNUMA пока не придумали.
Во первых, ты не прав. out-of-order совершенно не нужен при многопоточном дизайне проца — они будут только мешать друг другу и не будет никакой пользы. Это взаимоисключающие вещи, поэтому собственно гипертрединг и сосет. Суперскаларное выполнение при этом вводить вполне можно (выполнять подряд идущие инструкции впараллель) — но инструкции переупорядочивать глупость. К сожалению, для того, чтобы это объяснить, мне придется целую статью здесь написать, начав издалека, с устройства типового суперскалярного проца и типичных проблем, которые там возникают. А на это у меня нет ни времени ни сил. Могу порекомендовать книгу Танненбаума по архитектуре ЭВМ — лучшее введение в вопрос для программистов.
Во-вторых, считать можно все, что угодно, однако твоя логика расходится с логикой разработчиков аппаратуры. Видишь ли, лучший способ поднять производительность однопоточной программы — это современные навороченные суперскалярные процы. И это тупиковый путь, разработчики процессоров от него отказываются. Их, строго говоря, сейчас не особо волнует однопоточная производительность, их больше волнует удельная производительность на миллиметр кристалла. Логику аппаратчиков я достаточно подробно описал здесь
. in-order выполнение и отказ от предсказания переходов сделан специально — все это компенсируется аппаратной многопоточностью. Таким образом у тебя удельная производительность кристалла будет выше.
Обрати внимание, как устроен проц XBox 360 — предназначенный для наиболее требовательных "настольных" приложений — компьютерных игр. in-order execution + 3 ядра + аппаратная многопоточность (по 2 потока на ядро), общий кэш L2. Итого — 6 аппаратных потоков. Потому что делать так — дешевле, чем суперскаляр. Производительность одного потока там примерно 20% от скорости core duo. И ничего — в майкрософт выбрали такой дизайн, хотя вполне могли опять заказать проц интелу, как для первого XBox.
Здравствуйте, Gaperton, Вы писали:
G>... out-of-order совершенно не нужен при многопоточном дизайне проца — они будут только мешать друг другу и не будет никакой пользы. Это взаимоисключающие вещи, поэтому собственно гипертрединг и сосет. Суперскаларное выполнение при этом вводить вполне можно (выполнять подряд идущие инструкции впараллель) — но инструкции переупорядочивать глупость. К сожалению, для того, чтобы это объяснить, мне придется целую статью здесь написать, начав издалека, с устройства типового суперскалярного проца и типичных проблем, которые там возникают. А на это у меня нет ни времени ни сил. Могу порекомендовать книгу Танненбаума по архитектуре ЭВМ — лучшее введение в вопрос для программистов.
Здравствуйте, Gaperton, Вы писали:
C>>Ну так, батенька, не все же можно распараллелить. G>Пример пожалуйста. Ща будем параллелить.
Вот недавно занимался фиксами непараллельных методов в JBoss Cache Попробую набросать пример завтра (сейчас спать хочется).
C>>А х.з., не может оно нагрузить больше 6-8 процессоров. C>>Вот, кстати, тоже не очень лестный benchmark: http://tweakers.net/reviews/649/10/database-test-sun-ultrasparc-t1-vs-amd-opteron-pagina-10.html G>Ну не знаю. Вот бенчмарки SPEC. G>http://www.anandtech.com/cpuchipsets/showdoc.aspx?i=2657&p=4
Бенчмарки и реальная ситуация — не всегда друг другу соответствуют. Особенно в многоядерных системах, где bottleneck'и могут оказаться в самых интересных местах.
G>Что-то я не понимаю, а чем то отличается от обычной памяти в любом современно многоядерном проце? У тебя и в ниагаре есть общая память, но доступ к ней тоже тебует дополнительных действий. Тот же самый MEMBAR надо выставить. Можешь и не высталвять пожалуйста. Когерентность кэшей L1 практически нигде автоматом не поддерживается, знаешь ли, это технически сложно, и дает большую просадку даже для двух ядер. Везде надо специальные инструкции выдавать.
nccNUMA отличается тем, что у нас явно выделена локальная память. Причем есть возможности ее явно синхронизировать с "общей" памятью. Точнее, "общая" память формируется из локальной памяти каждого ядра.
Соответственно, работа по поддержанию когерентности уже ложится на программиста.
C>>Ты закон Мура помнишь? По прогнозам, он будет работать до 2015 года минимум. Если взять сегодняшний Core Quatro, то к 2015 он как раз станет где-то Core 64 просто благодаря увеличению плотности. Ну а дальше возможно будут многослойные ядра и прочая магия. G>Закон мура перестал работать примерно в 2003 году. Я еще полтора года назад в свои презентации графики вставлял, которые это показывают. Посмотри на графики роста тактовой частоты и как они кореллируют с техпроцессом — не растет уже тактовая частота, проблемы с этим. Не заметил, что частоты у процов понизились?
Ай-ай-ай. В законе Мура нет ничего про тактовую частоту, а есть про плотность транзисторов. В первом приближении можно считать, что можно наращивать количество ядер пропорционально количеству транзисторов.
G>Core 64 ты утончением техпроцесса не получишь. Можешь просто посчитать, насколькр больше таких ядер влезет на техпроцесс 20нм, если сейчас core 2 duo делается на 65 нм. Мало запихать в один кристалл много ядер. Надо решать проблемы общего доступа к памяти (количество ног у микросхем не подчиняется закону мура, извини), суметь накормить данными эти ядра, и решить вопросы синхронизации. Суперскалярные процы типа Core Duo будут иметь большие проблемы при увеличении количества ядер.
Почему-то мне кажется, что инженеры в Intel'е найдут решения этих проблем. Есть у меня вот такая железная уверенность, ну может будет не 64-ядерный, а 32-ядерный Core 32.
Собственно, четырехсокетный сервер с Core 2 Quadro уже дает нам 16 ядер.
G>Во первых, ты не прав. out-of-order совершенно не нужен при многопоточном дизайне проца — они будут только мешать друг другу и не будет никакой пользы. Это взаимоисключающие вещи, поэтому собственно гипертрединг и сосет. Суперскаларное выполнение при этом вводить вполне можно (выполнять подряд идущие инструкции впараллель) — но инструкции переупорядочивать глупость.
КАК еще ты добьешся увеличения однопоточной производительности?
G>К сожалению, для того, чтобы это объяснить, мне придется целую статью здесь написать, начав издалека, с устройства типового суперскалярного проца и типичных проблем, которые там возникают. А на это у меня нет ни времени ни сил. Могу порекомендовать книгу Танненбаума по архитектуре ЭВМ — лучшее введение в вопрос для программистов.
Я примерно представляю как работают предикторы, спекулятивное исполнение и т.п.
G>Обрати внимание, как устроен проц XBox 360 — предназначенный для наиболее требовательных "настольных" приложений — компьютерных игр. in-order execution + 3 ядра + аппаратная многопоточность (по 2 потока на ядро), общий кэш L2. Итого — 6 аппаратных потоков. Потому что делать так — дешевле, чем суперскаляр. Производительность одного потока там примерно 20% от скорости core duo. И ничего — в майкрософт выбрали такой дизайн, хотя вполне могли опять заказать проц интелу, как для первого XBox.
Ну так я не спорю, что оно им так дешевле получилось — разработчикам-то особого выбора нет. А если бы у покупателей был выбор что взять: крутой параллельный процессор или крутой однопоточный — это был бы другой вопрос.
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, Курилка, Вы писали:
К>>Здравствуйте, Gaperton, Вы писали:
[cut] К>>Ты вот эту книжку имеешь в виду?
G>Ну то прям жостко как-то. Не. Ничего из того, что трудно купить, достать, прочитать и понять.
G>Вот это — просто и попсово, но основы суперскаляра разобраны на примерах. Танненбаум. G>http://www.ozon.ru/context/detail/id/2967330/
Смотрим здесь и видим, что это одно и то же
G>Вот это — не танненбаум, существенно менее попсово — эту книгу писали аппаратчики. Вот это, пожалуй, по детальности изложения — оптимум для программиста, который хочет глубоко понять принципы аппаратного дизайна, но при этом не собирается переквалифицироваться в RTL-инженера. G>http://www.ozon.ru/context/detail/id/1374858/
Если вдруг появится время (хоть сие и маловероятно) — почитаем, спасибо.
Re[14]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>http://threadingbuildingblocks.org/ G>Вот это видал? Интеловская библиотека для С++, где аккуратно реализованы параллельные контейнеры (хэш-таблица, вектор, очередь), примитивы распараллеливания, и, главное, масштабируемый аллокатор. Работает быстрее, программится проще. Вот пример — они параллелят DES. Имеют почти линейную масштабируемость. G>http://www.devx.com/go-parallel/Article/34951
ты её читал? всё, что там используется — это параллельный for, который запускает оптимальное число тредов для выполнения миллионов независимых вычислений. реальной пользы от этого никакой, поскольку шифрование в ECB mode — профанация, а в других режимах используется информация из предыдущих блокоа, что делает их надёжными, но нераспарралеливаемыми
Здравствуйте, Gaperton, Вы писали:
G>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
там простые ядра, на уровне dsp-шек. в GPU их ещё больше
Люди, я люблю вас! Будьте бдительны!!!
Re[17]: Immutable data structures are the way of the future
Здравствуйте, BulatZiganshin, Вы писали:
G>>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
BZ>там простые ядра, на уровне dsp-шек. в GPU их ещё больше
Не совсем простые, они сложнее ниагарских. Там стоят довольно навороченные для sinle-issue (одна инстркция за такт) ядра PowerPC, у которых есть предсказалка переходов, неупорядоченная записть в память, и все-все навороты, которые single-issue проц может иметь.
На DSP они похожи только одним — туда добавили инструкцию MAC (умножение с накоплением), выполняющуюся за один такт. Это очень характерно для DSP-процов. Также, в этих ядрах по-моему есть защищенный режим (он точно есть в Cell, а там такое же ядро, только одно и без MAC) — чего нет в DSP.
В GPU — ядра совсем дебильные, похожие на самые простые DSP-шки. У них векторная арифметика, простейший конвейр и очень ограниченные возможности. Однако, там с приходом DX10 уже не все так просто стало. Раньше-то (DX8) было вобще тупо все. Ядер, типа, много, но. Они все разделяют один-единственный конвейр по выборке и декодированию инструкций, и, таким образом, всегда выполняют одну и ту же инструкцию, которая в декодированном виде (настройки коммутаторов внутри ядер фактически, что на что замыкать и откуда куда подавать) выставляется на общую для всех ядер шину. Все ядро — регистры да арифметика (вот почему ядер много и высокая удельная произвоительность). Именно поэтому в Dx8 не было условных переходов — все ядра выполняют один шейдер, но над разными данными. Также, там любят мутить аппаратный мультитрединг — выполняя переключение нескольких шейдеров для нагрузки конвейеризованной арифметики.
А вот DX10 уже имеет честные условные переходы, мать их. Так по-простому уже не сделаешь. Там, блин, уже хитрить надо — хз как у них сделано.
Re[18]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>А вот DX10 уже имеет честные условные переходы, мать их.
DX9 если быть более точным. А еще точнее: начиная с Shader Model 3.0
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
http://www.ibm.com/developerworks/power/library/pa-fpfxbox/
G>Не совсем простые, они сложнее ниагарских. Там стоят довольно навороченные для sinle-issue (одна инстркция за такт) ядра PowerPC, у которых есть предсказалка переходов, неупорядоченная записть в память, и все-все навороты, которые single-issue проц может иметь.
Плюс еще больше наворотов, чем я думал. У этих друзей multithread работает совсем не так, как в Ниагаре. Каждое ядро Xenon выдает на выполнение двеинструкции за такт по одной из каждого потока. О возможности чего я недавно тут писал в соседних ветках. У них два независимых конвейра выполнения в каждом ядре (а не один общий, как в ядрах Ниагары), который с некоторого момента разделяется на пять конвейров (работающих на общем кластере арифметики). Итого, каждое ядро умеет выдавать на исполнение 2 инструкции за такт, и выполнять впараллель 5 разных типов инструкций.
Дизайн сильно отличается от Ниагарского — в ниагаре борются с латентностью памяти, и многопоточность нужна чтобы заполнить один конвейр, а здесь — многопоточность заменяет суперскаляр — они гонятся за перформансом на разогретом конвейре.
В остальном — похоже, также общий кэш L2, и все компоненты зацеплены коммутатором типа кроссбар в центре кристалла.
Re[18]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>На DSP они похожи только одним — туда добавили инструкцию MAC (умножение с накоплением), выполняющуюся за один такт.
эта инструкция была в самом первом Power, хотя я не в курсе — может в powerpc или ещё где по дороге её и выкинули
ну в общем ядра тут попроще, чем современные x86, поэтому их больше влезает
G>В GPU — ядра совсем дебильные, похожие на самые простые DSP-шки.
скажем, порядка 8 или 16 независимых ядер, каждое из которых обрабатывает по нескольку десятков чисел одновременно (SIMD). насколько я понял, эту обработку можно маскировать, так что в худщем случае получаем 8-ядерный процессор. но на скромной частоте, с достаточно медленным одиночным образением в память. в общем, имеет смысл только для алгоритмов, унифицированно обрабатывающих большие наборы данных
Люди, я люблю вас! Будьте бдительны!!!
Re[19]: Immutable data structures are the way of the future
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, Gaperton, Вы писали:
G>>На DSP они похожи только одним — туда добавили инструкцию MAC (умножение с накоплением), выполняющуюся за один такт.
BZ>эта инструкция была в самом первом Power, хотя я не в курсе — может в powerpc или ещё где по дороге её и выкинули
BZ>ну в общем ядра тут попроще, чем современные x86, поэтому их больше влезает
Ну да, а именно — в них нет суперскалярного выполнения, оно заменено многопоточностью. Это им дало экономию примерно втрое по площади по сравнению с ядром пентиум-4, при том, что они в отличии от пня гораздо чаще выполняют две инструкции за такт на реальных программах. А вообще — это не самые простые ядра, они сложнее ниагарских. Там даже микрокод есть.
Re[18]: Immutable data structures are the way of the future
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, BulatZiganshin, Вы писали:
G>>>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
BZ>>там простые ядра, на уровне dsp-шек. в GPU их ещё больше
G>Не совсем простые, они сложнее ниагарских. Там стоят довольно навороченные для sinle-issue (одна инстркция за такт) ядра PowerPC, у которых есть предсказалка переходов, неупорядоченная записть в память, и все-все навороты, которые single-issue проц может иметь.
я-то говорил про 80-ядерник, а ты похоже — про xbox в gpu, если считать кол-во одновременно обрабатываемых чисел, доходит до 320, если не больше, хотя конечно ядрами я это зря назвал
Люди, я люблю вас! Будьте бдительны!!!
Re[19]: Immutable data structures are the way of the future
Здравствуйте, BulatZiganshin, Вы писали:
G>>>>Возьми XBox 360 — да, у него большая задержка на атомарный инкремент, однако он имеет возможность трижды переключится на другой аппаратный поток во время этой задержки — ядро продолжит работу. А у ниагары таких потоков 4 на ядро. У ниагары 2 — восемь. Обрати внимание — когда речь идет о "восьмидесяти ядрах" — не говорят ли на самом деле о количестве аппаратных потоков. Ставлю пирожок — об этом и идет речь.
BZ>>>там простые ядра, на уровне dsp-шек. в GPU их ещё больше
G>>Не совсем простые, они сложнее ниагарских. Там стоят довольно навороченные для sinle-issue (одна инстркция за такт) ядра PowerPC, у которых есть предсказалка переходов, неупорядоченная записть в память, и все-все навороты, которые single-issue проц может иметь.
BZ>я-то говорил про 80-ядерник, а ты похоже — про xbox в gpu, если считать кол-во одновременно обрабатываемых чисел, доходит до 320, если не больше, хотя конечно ядрами я это зря назвал
Ну, если говорить о 80-ядрнике — то там одно из двух. Либо я прав, и речь идет о количестве аппаратных потоков, либо ты прав, и там стоят простейшие DSP-шники, которые затрахаешься программить. Третьего не дано, реально.
Re[2]: Immutable data structures are the way of the future i
Здравствуйте, minorlogic, Вы писали:
M>Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?
А программочитатели? Им разве информация о неизменяемости совсем не нужна?
пожалуйста. Когерентность кэшей L1 практически нигде автоматом не поддерживается, знаешь ли, это технически сложно, и дает большую просадку даже для двух ядер. Везде надо специальные инструкции выдавать.
Это типа как "пчелы против меда" штоли?
Попробую набросать пример завтра (сейчас спать хочется).
