Здравствуйте, vdimas, Вы писали:
V>>>Кеш — это память, она не умеет делать простейших операций, типа декремента или проверки значения на 0, например. Поэтому дёргается АЛУ
R>>Не очень понятно, а в чём проблема дергать АЛУ? АЛУ — это ж самая быстродействующая и, зачастую, недозагруженная часть системы. Если считать, что АЛУ может выдавать 3 команды за такт,
V>3 команды сложения за такт означают наличие 3-х сумматоров, например.
Да, пожалуйста. Если у меня CPI 2 вместо 0.3, то мне вообще пофигу.
Разговор об АЛУ — это разговор о единицах тактов, разговор о синхронизации — это разговор о сотнях тактов.
R>>а на перемещение кэш-линии тратится 200 тактов, то доля АЛУ тут получается менее 1%.
V>В том-то и дело, что сейчас счётчики примитивов надо еще в кеш предварительно загружать.
В любом случае надо делать какую-то "удаленную" работу. "Удаленная" работа — это в любом случае дорого. Вопрос — насколько? Мне кажется, что меньше 50 тактов это сделать не получится.
На последних AMD latency инструкции RDTSC(P) — 57 тактов, именно из-за того, что она обращается к NorthBridge.
R>> Плюс к этому, примерно в 50% случаев обращение к примитиву синхронизации связано с проверкой, т.е. это ветвление,
V>Для встроенного примитива не должно быть ветвления, кроме случаев таймаута (т.е. постпроверки — по таймауту прошли примитив или нет). Для семафора/мьютекса/события должна быть просто некая команда wait #sync безо-всяких ветвлений. "Ветвление" должен делать шедуллер, путём распределения загрузок внутренних блоков. С предпросмотром тоже всё нормально — ведь шедуллер может посмотреть — будет в ближайшие несколько тактов изменяться данный примитив в других потоках, или нет (напомню, я считаю всю эту схему эффективной только при возможности хранить состояния приличного кол-ва потоков в процессоре). Если примитив в сигнальном состоянии, и шедуллер в видимой последовательности команд в других потоках не обнаруживает операций с этим примитивом, то на выполнение команды wait должно тратиться ровно 0 тактов.
Допустим поток 1 захватил аппаратный мьютекс 1, потом ОС отключила поток 1 от процессора, и поставила выполняться 100 других потоков на всё имеющиеся 100 аппаратных потоков. Все эти 100 потоков заблокировались на захвате аппаратного мьютекса 1. Система теряет 100 квантов времени на тупое ожидание мьютекса.
Я не вижу как это хорошо сделать без ветвления и ОС.
R>Допустим поток 1 захватил аппаратный мьютекс 1, потом ОС отключила поток 1 от процессора, и поставила выполняться 100 других потоков на всё имеющиеся 100 аппаратных потоков. Все эти 100 потоков заблокировались на захвате аппаратного мьютекса 1. Система теряет 100 квантов времени на тупое ожидание мьютекса. R>Я не вижу как это хорошо сделать без ветвления и ОС.
Да пускай себе теряет на здоровье. Ожидающие потоки не нагружают исполнительные блоки. Вся суть предложения этой схемы в том, что аппаратных потоков должно быть гораздо больше, чем исполнительных блоков (желательно на порядки, я же писал, что первая кеш-память и файл регистров должны слиться в одно целое). В случае, если шедуллер ОС захотел загрузить в проц очередной поток из памяти, а у того нет слотов под потоки, тогда надо вытеснять ступорные потоки, согласно приоритетам и времени ожидания. Логику вытеснения тоже можно поддержать аппаратно, если добавить аппаратное поле приоритета для потока и счётчик тактов ожидания потока. (Поле приоритета в любом случае должно быть у такой схемы, где в проце хранится множество аппаратных потоков)
Здравствуйте, vdimas, Вы писали:
R>>Допустим поток 1 захватил аппаратный мьютекс 1, потом ОС отключила поток 1 от процессора, и поставила выполняться 100 других потоков на всё имеющиеся 100 аппаратных потоков. Все эти 100 потоков заблокировались на захвате аппаратного мьютекса 1. Система теряет 100 квантов времени на тупое ожидание мьютекса. R>>Я не вижу как это хорошо сделать без ветвления и ОС.
V>Да пускай себе теряет на здоровье.
Если эта схема не о производительности, тогда о чём?
V>Ожидающие потоки не нагружают исполнительные блоки. Вся суть предложения этой схемы в том, что аппаратных потоков должно быть гораздо больше, чем исполнительных блоков (желательно на порядки, я же писал, что первая кеш-память и файл регистров должны слиться в одно целое). В случае, если шедуллер ОС захотел загрузить в проц очередной поток из памяти, а у того нет слотов под потоки, тогда надо вытеснять ступорные потоки, согласно приоритетам и времени ожидания. Логику вытеснения тоже можно поддержать аппаратно, если добавить аппаратное поле приоритета для потока и счётчик тактов ожидания потока. (Поле приоритета в любом случае должно быть у такой схемы, где в проце хранится множество аппаратных потоков)
Я не думаю, что целесообразно делать аппаратных потоков значительно больше, чем это было бы необходимо иначе, только для маскирования отсутствия хорошего высокоуровневого шедулинга.
Процессор может делать только микро-шедулинг, например, если поток вызвал промах кэша или некорректно предсказан переход. Макро-шедулинг же должен оставаться за ОС. Блокировка на мьютексе относится к макро-шедулингу, потому что время ожидания заранее не известно и может быть сколь угодно большим.
Добавлю так же, что кеш первого уровня, впервые появившийся в 386-м нужен был, в первую очередь, для эффективной реализации страничной памяти, доступ к кешу первого уровня равен по скорости доступу к файлу регистров, преобразователь адресов непосредственно оперирует данными таблиц распределения страниц из этого кеша без задержек. Т.е. фактически уже на процах имеется достаточное кол-во памяти, адресуемой со скоростью регистров.
Здравствуйте, vdimas, Вы писали:
V>Добавлю так же, что кеш первого уровня, впервые появившийся в 386-м нужен был, в первую очередь, для эффективной реализации страничной памяти, доступ к кешу первого уровня равен по скорости доступу к файлу регистров, преобразователь адресов непосредственно оперирует данными таблиц распределения страниц из этого кеша без задержек. Т.е. фактически уже на процах имеется достаточное кол-во памяти, адресуемой со скоростью регистров.
Я бы не сказал, что для всех программ достаточно 64K памяти
Тем более, что кэши обычно разделяются между аппаратными потоками. Т.е. если у нас 2 аппаратных потока (HT), то на поток фактически 32К. Это, кстати, проблема если делать *много* аппаратных потоков, т.к. L1$ много на кристалл не запихаешь.
Здравствуйте, remark, Вы писали:
V>>Да пускай себе теряет на здоровье.
R>Если эта схема не о производительности, тогда о чём?
Похоже, ты не понял суть схемы. Задача этой схемы — загрузить по-максимуму исполнительные устройства, простой блокированных потоков не означает простой вычислительных ресурсов — они свободны для других потоков. Задача большого кол-ва аппаратных потоков — минимизировать загрузки-выгрузки состояний регистров процессора для данного потока и избавиться от такой весьма нехорошей вещи как спин (пожирающий выч. ресурсы).
R>Я не думаю, что целесообразно делать аппаратных потоков значительно больше, чем это было бы необходимо иначе, только для маскирования отсутствия хорошего высокоуровневого шедулинга.
Да какой, блин, шедуллинг для потока в режиме ожидания?
И откуда ты вообще взял потерянные кванты (в пред. сообщении)? ОС, в отличие от прикладных программ, прекрасно знает, из-за какого конкретно хендлера (или списка хендлеров) поток находится в режиме ожидания.
R>Процессор может делать только микро-шедулинг, например, если поток вызвал промах кэша или некорректно предсказан переход. Макро-шедулинг же должен оставаться за ОС.
Чем макро отличается от микро? Системой приоритетов и очередей, не правда ли? Ну дык, а для ввода-вывода тем не менее уже имеется система приоритетов, которая разруливает "одновременно" пришедшие прерывания. Вот тебе зачатки макро-шедуллинга.
Опять же, никто не говорит, что весь шедуллинг может быть произведён аппаратно. Код по обслуживанию примитива скрыт в вызове ф-ий АПИ, после освобождения примитива (например мютекса) ОС может получить оповещение о том, что мютекс освободился, скорректировать очередь потоков, и привести множество загруженных аппаратных потоков в соответствии с головой очереди. Автоматически кванты будут выделяться лишь той части головы очереди, которая поместилась в проц (если вся очередь не влезла), т.е. задача макрошедуллера будет состоять в назначении приоритетов и поддержке общей очереди, сами же переключения пусть происходят в автоматическом режиме. Доп. можно зарезервировать несколько потоков для неспешного ручного выделения квантов членам остатка хвоста очереди, чтобы они периодически крутились в своих спинах (для ожидающих и неприоритетных потоков не критично, что эти спины будут не часто).
R>Блокировка на мьютексе относится к макро-шедулингу, потому что время ожидания заранее не известно и может быть сколь угодно большим.
И что? Ожидающие потоки постепенно будут "сползать" к концу очереди шедуллера, и в конце концов будут выгруженны из проца в память, коль места в проце не хватит под другие потоки.
------------
Кстати, бенефиты обсуждаемой схемы в первую очередь скажутся на вводе-выводе. Драйверы могут просто представлять из себя потоки, ожидающие некие хендлы. Высокоприоритетный поток ввода-вывода может постоянно находится в ядре, и автоматически получать выч. ресурсы (с помощью аппаратного шедуллера) по приходу данных без дорогостоящих прерываний. А то наблюдал я картину, когда росла наша местная городская сеть, и в одной маске IP крутилось пара тысяч домашних компьютеров, и все качают видео, либо рубятся в игры, в общем свист по витой паре в 100МГб стоял — закачаешься. Воткнешь сетевой кабель, и комп сразу заметно притормаживать начинает. Пока более мелко не порубили, да маршрутизаторов дополнительных не понаставили, ситуация с каждым месяцом ухудшалась. Привел как пример того, что задержки ввода-вывода вполне заметны даже субъективно.
WH>Ну не вижу я смысла защищать код. WH>Ибо защищать нужно только изменяемые данные.
Вообще-то, защищать надо логические сущности. А что это — код, или данные — дело десятое, и больше зависит от гранулярности блокировок. Если защищать только данные, то гранулярность может получиться неприлично малой, в итоге из дедлоков не будем вылезать.
WH>Я вроде гдето по твоим ссылкам читал что все выкрутасы на эту тему приводили к проездам по памяти.
С какой стати?
WH>Да и вобще куча мутной семантики типа грязного чтения итп мягко говоря настораживает.
Нормальное чтение. Просто атомарным может быть не только ячейка, размером со слово, но и целая область. Особенно удобно будет для сценариев, завязанных не на ожидание данных, а на периодический их мониторинг. Безлоковые структуры данных работают из-за предположения об атомарности операции изменения указателя, им даже барьер не нужен для работы, достаточно атомарности. Теперь, однако, передавать данные из потока в поток можно будет по-значению в некоем кольцевом буфере, без выделения динамической памяти под каждую ячейку безлокового списка.
WH>С деревянными локами куда как понятнее и спокойней.
Если локи нужны для логики ожидания (воода/вывода, или конца вычислений), то это понятно, ну а если локи используются для сериализации доступа — то это действительно деревянно, и транзакционная память поможет избежать лишних дорогостоящих искуственных ожиданий.
Здравствуйте, vdimas, Вы писали:
V>Вообще-то, защищать надо логические сущности.
А кто спорит?
V>А что это — код, или данные — дело десятое,
Код защищать не надо.
Никогда.
Он не меняется.
Следовательно защищать нечего.
V>и больше зависит от гранулярности блокировок. Если защищать только данные, то гранулярность может получиться неприлично малой, в итоге из дедлоков не будем вылезать.
Ты точно прочитал то что я написал про систему типов?
WH>>Да и вобще куча мутной семантики типа грязного чтения итп мягко говоря настораживает. V>Нормальное чтение.
Что значит нормальное?
Нам нужны гарантии того что мы никогда и ни при каких условиях не увидим то что делает паралельная не закомиченная транзакция.
Иначе мы вобще ни на что пологаться не можем.
А обеспечение данной гарантии для TM задачка мягко говоря не тривиальная. Там же код что попало делать может.
V>Просто атомарным может быть не только ячейка, размером со слово, но и целая область.
Ага. Размером с линейку кеша.
Меньше не залочить. Больше не эффективно.
Разве что если совсем приперло.
V>Особенно удобно будет для сценариев, завязанных не на ожидание данных, а на периодический их мониторинг.
Если к тому локу что я описал добавить ридонли версию то этот сценарий становится вполне себе работающим.
А если нам нужно одно слово мониторить то вобще локи не нужны.
V>Безлоковые структуры данных работают из-за предположения об атомарности операции изменения указателя, им даже барьер не нужен для работы, достаточно атомарности. Теперь, однако, передавать данные из потока в поток можно будет по-значению в некоем кольцевом буфере,
А что делать если место в буфере закончится?
V>без выделения динамической памяти под каждую ячейку безлокового списка.
Ой беда то какая.
Особенно при наличии мусорщика.
V>Если локи нужны для логики ожидания (воода/вывода, или конца вычислений), то это понятно,
Эти локи нужно реализовывать на уровне шедуллера ОС.
V>ну а если локи используются для сериализации доступа — то это действительно деревянно, и транзакционная память поможет избежать лишних дорогостоящих искуственных ожиданий.
Ты точно понял что будет делать этот лок
? (кстати он тоже ориентирован на синхронизацию по памяти)
Сделать операцию дешевле чем описанный примитив просто не реально.
Ибо у тебя в этой твоей транзакционной памяти при коммите будет тоже самое...
Так нафига козе баян?
Нафига мутные примитивы с мутной семантикой?
Если есть простой и понятный примитив?
Который просто лочит на несколько тактов кусочек памяти.
При том что сам по себе лок кусочка памяти куда дороже и он всеравно будет происходить при коммите HTM...
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
R>Я бы не сказал, что для всех программ достаточно 64K памяти R>Тем более, что кэши обычно разделяются между аппаратными потоками. Т.е. если у нас 2 аппаратных потока (HT), то на поток фактически 32К. Это, кстати, проблема если делать *много* аппаратных потоков, т.к. L1$ много на кристалл не запихаешь.
— потоки одного процесса могут работать с одними и теми же данными (числодробилки или просто какая-нить т.н. "бизнес-логика"), в любом случае, обычные потоки тоже делят эту память, и так же используют её под файлы регистров неявно при загрузке/выгрузке оных при смене текущего потока в проце.
— таблицы распределения виртуальной памяти общие для всех потоков одного процесса
— файл регистров на поток — от силы 2-3 десятка ячеек (их не нужно больше, чем может выполняться одновременно команд одного потока, помноженное на кол-во логических регистров общего назначения, а спец-регистры — это не ячейки памяти, а часть исполнительного механизма)
В общем, учитывая, что закон Мура относительно транзисторов на кристалле пока что соблюдается, не в размере L1 кеша загвоздка. Самая загвоздка будет в планировщиках, кои сейчас составляют приличную долю от сложности кристалла. Однако, при современной численности транзисторов, уже через пару лет прирост их общего кол-ва (по Муру) покроет с лихвой требуемый.
V>>Вообще-то, защищать надо логические сущности. WH>А кто спорит?
Ты споришь, приравнивая логическую сущность к данным. Логической сущностью может быть некое устройство, например pipe, который может иметь разные хендлы в разных процессах. Как записать туда транзакционно единый блок данных с помощью твоей модели мне понятно — это делать сериализацию на уровне OC (драйвера и т.д., который имеет однозначную ссылку на ассоциированную с устройством структуру). Но как транзакционно записать туда несколько данных, или тем паче — обменяться транзакционно — это с т.з. твоей модели полное хз. Ты же предлагаешь такую фундаментальную вещь, как грануляцию блокировок, прибить нафик, и подменить системой типов. Понимаешь... на современном уровне абстракции ПО система типов не отображается однозначно на систему логических понятий, до такого мы пока не доросли и вряд ли дорастём в ближайшие несколько десятилетий. По крайней мере, C#/Java/Nemerle и пр. — вовсе не из этой фантастической области, хоть пересыпь ты их любым сахаром и макросами. Потому как логическое понятие — это не статическая структура, это может быть и операция, и данные.
Даже такая простая вещь, как транзакционное изменение нескольких сущностей, каждая из которых предполагает и отдельный сериализованный доступ, не пройдёт в твоей системе типов, когда защищается каждая сущность отдельно, ибо запросто возможен дедлок, когда много потоков выполняют несколько подобных несвязанных транзакционных изменений. Подобный сценарий имеет хорошо известное решение: необходимые сущности сортируются по какому-нить признаку, предполагающему однозначную сортировку (по ключу обычно), а затем блокируются согласно сортированному списку, тогда мы не нарвёмся на дедлок.
В твоей системе потребуется хранить доп. immutable структуру на каждую сущность, котрая хранит immutable ключ и uniqueness ссылку на данные (которые тоже хранят свой ключ), в итоге мы еще больше будем усложнять систему типов, вместо упрощения.
Еще больше непонятно, что будет происходить с большинством современных паттернов проектирования, которые в большинстве своём представляют комбинации типов. Где-то эти типы будут работать самостоятельно и требовать самостоятельной блокировки, а где-то будут входить в состав структур более высокого уровня, и совершенно не требовать отдельного последовательного доступа и т.д. Даже просто после создания, когда поток знает, что эту сущность никто больше не видит, ну нахрена её защищать?
V>>А что это — код, или данные — дело десятое, WH> WH>Код защищать не надо. WH>Никогда. WH>Он не меняется. WH>Следовательно защищать нечего.
Да никто и не защищает код. С чего ты решил, что термин "защита" тут уместен? Речь идёт о сериализации доступа, и больше ни о чём. И как раз сериализировать исполнение определённых участков кода — вполне нормально. Тут Андрей высказывался, что это не всегда удобно, ибо зачастую раскидано по логике, ну дык это дело десятое пока что...
V>>и больше зависит от гранулярности блокировок. Если защищать только данные, то гранулярность может получиться неприлично малой, в итоге из дедлоков не будем вылезать. WH>Ты точно прочитал то что я написал про систему типов?
Прочитал всё, не волнуйся. Сама идея блочить линейки кеша представляется не очень. Там не так много линеек кеша в проце, буквально еще несколько лет и 4/8/16-ядерные процы станут нормой, и каждое ядро будет исполнять по 4 потока минимум, а доступ к ОП будет идти по тысячеразрядной шине данных, твоя система прибъёт эффективность L1 на корню. L1 никогда не будет очень большим, ибо статический триггер требует в общей сложности 6 транзисторов на исполнение. Транзакционная память, о которой тебе говорят — это практически одно и то же, но они не претендуют на логическую защиту данных, как претендуешь ты (ибо опять же — термин защита тут неуместен, более того — вреден, ибо речь всё время идёт только об атомарности последовательностей операций, боле не о чём). Сама транзакционность предполагает, что в транзакции может участвовать произвольный набор логических сущностей, согласись, это гораздо более гибкое и широкое решение.
WH>>>Да и вобще куча мутной семантики типа грязного чтения итп мягко говоря настораживает. V>>Нормальное чтение. WH>Что значит нормальное? WH>Нам нужны гарантии того что мы никогда и ни при каких условиях не увидим то что делает паралельная не закомиченная транзакция. WH>Иначе мы вобще ни на что пологаться не можем.
Правильно рассуждаешь, только выводы не правильные делаешь. Зачем сразу предлагаешь техническое решение, какие-то мифические блокировки линеек? Надо просто формулировать задачу, а не бросаться в технические подробности.
Если в твоём решении расширить от линейки до произвольного набора данных, и отказаться от т.н. "передачи владения" то твоё решение превратиться в то, что предлагает Sun. Они ведь тоже начали пока с очень малого в этой области (понятное дело, выпуск серийного проца новой архитектуры — это целая эпоха в жизни каждой фирмы, они пока просто осторожничают).
WH>А обеспечение данной гарантии для TM задачка мягко говоря не тривиальная. Там же код что попало делать может.
Да, параллельно и что попало. Но если проц увидит, что в результате менялись и читались разные участки данных даже у одной и той же сущности (разные поля твоего типа, например, а тип целиком лежит в линейке кеша, понятное дело), то одновременные транзакции разрешаются, иначе — сериализуются. Прочувствуй разницу, как говорится. Серваки БД работают именно так на определённых уровнях транзакции, зачем что-то изобретать, всё давно изобретено. Речь идёт лишь о том, чтобы частично (пока) поддержать часть этой логики в железе.
V>>Просто атомарным может быть не только ячейка, размером со слово, но и целая область. WH>Ага. Размером с линейку кеша. WH>Меньше не залочить. Больше не эффективно.
С чего бы это меньше не залочить? Да хоть целый список областей произвольной длины, даже если все эти области не помещаются целиком в целый кеш. Сейчас под этот список в новом сановском проце, насколько я понял, отведено 4 ячейки на поток, значит всего 32*4=128, их в перспективе может быть произвольное кол-во.
WH>Разве что если совсем приперло.
Припрёт уже прямо сейчас на современных задачах. Пусть они поиграют с тем, насколько такая система эффективна для целей сериализации доступа, если окажется эффективной (в чём я не сомневаюсь), то оно будет расти вширь (ибо по частоте практически упёрлись, теоретический предел современного тех-процесса в районе 10МГц, даже при произвольной дальнейшей миниатюризации, так что расти можно будет только вширь одновременно с дальнейшей миниатюризацией... возможно придумают что-то вместо транзисторов когда-нить, но пока не придумали, и используют их, родимых, и дырочную проводимость, которая имеет геометрический минимальный предел, чтобы диод оставался диодом, и порог около 0.5-0.6В для кремния, так что пока упёрлись вплотную, и 1-1.2В — это примерно минимум для напряжения питания).
V>>Особенно удобно будет для сценариев, завязанных не на ожидание данных, а на периодический их мониторинг. WH>Если к тому локу что я описал добавить ридонли версию то этот сценарий становится вполне себе работающим. WH>А если нам нужно одно слово мониторить то вобще локи не нужны.
V>>Безлоковые структуры данных работают из-за предположения об атомарности операции изменения указателя, им даже барьер не нужен для работы, достаточно атомарности. Теперь, однако, передавать данные из потока в поток можно будет по-значению в некоем кольцевом буфере, WH>А что делать если место в буфере закончится?
Выделить новый, после этого обновить ссылку на буфер, делов то. В следующий раз читатель полезет уже в новый буфер.
V>>без выделения динамической памяти под каждую ячейку безлокового списка. WH>Ой беда то какая. WH>Особенно при наличии мусорщика.
Как показала практика — всё-таки беда. Даже для моей задачи микширования звука. Сервак загибается, если всего-лишь 50 раз в сек выделять динамически под каждый буфер данных 320 байт, и кол-во пользователей всего-лишь 4096, а на каждого — 4 таких буфера. Пока что рулят статические буфера. Так же сильно помогло использование, где можно, безлоковых алгоритмов. Мало того, что Monitor.Enter/Exit работает гораздо тормознее чем родные CriticalSection, так даже последние прилично тормозят процесс.
V>>Если локи нужны для логики ожидания (воода/вывода, или конца вычислений), то это понятно, WH>Эти локи нужно реализовывать на уровне шедуллера ОС.
V>>ну а если локи используются для сериализации доступа — то это действительно деревянно, и транзакционная память поможет избежать лишних дорогостоящих искуственных ожиданий. WH> WH>Ты точно понял что будет делать этот лок
? (кстати он тоже ориентирован на синхронизацию по памяти) WH>Сделать операцию дешевле чем описанный примитив просто не реально.
Транзакционная память дешевле, чем блокировка целой линейки кеша из-за одного int.
WH>Ибо у тебя в этой твоей транзакционной памяти при коммите будет тоже самое...
Ты наверно недопонял. Еще до коммита понятны намерения участников, кто что будет читать/писать. В случае отсутствия кофликтов вообще ничего не происходит, иначе — сериализация на уровне планировщика потоков в проце.
WH>Так нафига козе баян? WH>Нафига мутные примитивы с мутной семантикой?
Согласен, мютекс — это искуственный примитив, отсутствующий в теории о синхронизации. Так и есть, этот семафор с N=1, имеющий собственное имя, нужен исключительно для сериализации последовательности операций.
WH>Если есть простой и понятный примитив?
Простой и понятный примитив только один — это атомарно изменяемый счётчик. "Транзакция" — это не примитив, а логическое понятие. Сейчас транзакции делаются на мютексах и обслуживающей логике.
WH>Который просто лочит на несколько тактов кусочек памяти.
Его не надо лочить
Надо проследить за атомарностью изменений в нём.
WH>При том что сам по себе лок кусочка памяти куда дороже и он всеравно будет происходить при коммите HTM...
Нет, не будет, ты недопонял. Коммит — это вообще абстракция, реально никакого коммита нет, есть атомарные изменения 2-х ячеек (пока 2-х).
Тот примитив процессора что я описал не имеет никакого отношения к системе типов.
Это совершенно не зависящие друг от друга сущьности.
Которые могут использоваться отдельно или вместе.
V>Ты споришь, приравнивая логическую сущность к данным.
Так они всегда данными и выражаются.
V>Логической сущностью может быть некое устройство, например pipe, который может иметь разные хендлы в разных процессах.
pipe устройство? Интересная точка зрения.
А я то думал что это FIFO комуникационный канал.
В любом случае мимо ибо на мою систему типов ложаться гораздо более кучерявые примитивы.
Например каналы из сингулярити.
V>Как записать туда транзакционно единый блок данных с помощью твоей модели мне понятно — это делать сериализацию на уровне OC (драйвера и т.д., который имеет однозначную ссылку на ассоциированную с устройством структуру). Но как транзакционно записать туда несколько данных, или тем паче — обменяться транзакционно — это с т.з. твоей модели полное хз.
Ты совсем ничего не понял.
Все это делается очень легко.
Легче чем на всяких там мъютексах.
V>Ты же предлагаешь такую фундаментальную вещь, как грануляцию блокировок, прибить нафик, и подменить системой типов.
Да не нужны нам блокировки.
Нам нужна синхронизация. А она может быть достигнута различными способами.
V>Понимаешь... на современном уровне абстракции ПО система типов не отображается однозначно на систему логических понятий, до такого мы пока не доросли и вряд ли дорастём в ближайшие несколько десятилетий. По крайней мере, C#/Java/Nemerle и пр. — вовсе не из этой фантастической области, хоть пересыпь ты их любым сахаром и макросами.
А кто их предлагает?
Я давно говорю что модель CLR и тем более жабы унылое говно которое ни для чего использовать нельзя.
V>Потому как логическое понятие — это не статическая структура, это может быть и операция, и данные.
Операция всегда производится над некими данными.
И сериализовать выполнение некой последовательности комманд при условии что работа происходит с независимыми данными смысла нет вобще.
V>Даже такая простая вещь, как транзакционное изменение нескольких сущностей, каждая из которых предполагает и отдельный сериализованный доступ, не пройдёт в твоей системе типов, когда защищается каждая сущность отдельно, ибо запросто возможен дедлок, когда много потоков выполняют несколько подобных несвязанных транзакционных изменений.
Конечно пройдет.
V> Подобный сценарий имеет хорошо известное решение: необходимые сущности сортируются по какому-нить признаку, предполагающему однозначную сортировку (по ключу обычно), а затем блокируются согласно сортированному списку, тогда мы не нарвёмся на дедлок.
И?
V>В твоей системе потребуется хранить доп. immutable структуру на каждую сущность, котрая хранит immutable ключ и uniqueness ссылку на данные (которые тоже хранят свой ключ), в итоге мы еще больше будем усложнять систему типов, вместо упрощения.
Чё?
Вобще говоря immutable данные могут ссылаться только на immutable данные.
V>Еще больше непонятно, что будет происходить с большинством современных паттернов проектирования, которые в большинстве своём представляют комбинации типов.
Еще один проектирующий паттернами...
Другая система типов — другие решения.
Все просто.
Даже С++ные решения при переходе на жабу приходится выкидывать. Факт медицинский.
А тут совсем другая система типов.
V>Где-то эти типы будут работать самостоятельно и требовать самостоятельной блокировки, а где-то будут входить в состав структур более высокого уровня, и совершенно не требовать отдельного последовательного доступа и т.д. Даже просто после создания, когда поток знает, что эту сущность никто больше не видит, ну нахрена её защищать?
Моя система типов справляется с этим иделально.
Читай ветку до просветления.
V>Да никто и не защищает код. С чего ты решил, что термин "защита" тут уместен? Речь идёт о сериализации доступа, и больше ни о чём. И как раз сериализировать исполнение определённых участков кода — вполне нормально. Тут Андрей высказывался, что это не всегда удобно, ибо зачастую раскидано по логике, ну дык это дело десятое пока что...
И зачем сериализовать доступ к коду?
Сериализовать доступ к не изменяемым сущьностям бред полный и без просветный.
А код сущьность таки не изменяемая.
Его один раз скомпилировали и все.
Или ты пишешь полиморфные вирусы? Как по мне чем у вирусописателей больше проблем тем лучше.
V>>>и больше зависит от гранулярности блокировок. Если защищать только данные, то гранулярность может получиться неприлично малой, в итоге из дедлоков не будем вылезать. WH>>Ты точно прочитал то что я написал про систему типов? V>Прочитал всё, не волнуйся. Сама идея блочить линейки кеша представляется не очень.
Какие к черту линейки кеша?
Я про систему типов высокоуровневой ВМ говорю.
Именно она гарантирует синхронизацию.
А линейки кеша это деталь реализации на конкретной жележзке.
V>Там не так много линеек кеша в проце, буквально еще несколько лет и 4/8/16-ядерные процы станут нормой, и каждое ядро будет исполнять по 4 потока минимум, а доступ к ОП будет идти по тысячеразрядной шине данных, твоя система прибъёт эффективность L1 на корню.
Чё? Ты все это к чему?
V>L1 никогда не будет очень большим,
А ему и не надо.
V>ибо статический триггер требует в общей сложности 6 транзисторов на исполнение.
И чё?
V>Транзакционная память, о которой тебе говорят — это практически одно и то же, но они не претендуют на логическую защиту данных, как претендуешь ты (ибо опять же — термин защита тут неуместен, более того — вреден, ибо речь всё время идёт только об атомарности последовательностей операций, боле не о чём).
Ты не переводи разговор на спор о терминах.
V>Сама транзакционность предполагает, что в транзакции может участвовать произвольный набор логических сущностей, согласись, это гораздо более гибкое и широкое решение.
Ага. Только эффективно не реализуемое.
V>Правильно рассуждаешь, только выводы не правильные делаешь.
Это какие же?
V>Зачем сразу предлагаешь техническое решение, какие-то мифические блокировки линеек?
Мифические? Интересно. А что префикс lock на современных x86'х процессорах делает?
Ни когда не задумывался?
V>Надо просто формулировать задачу, а не бросаться в технические подробности.
Задача простая: Обеспечить правильную синхронизация в многопоточной среде.
V>Если в твоём решении расширить от линейки до произвольного набора данных,
Каком именно?
Ты постоянно путаешься.
Система типов не накладывает подобных ограничений.
А в железе один хрен меньше чем с линейкой кеша работать не получится.
V>и отказаться от т.н. "передачи владения"
Не выдет.
Ни там ни там.
Ты знаешь что делают процессоры при записи в память?
Вот поинтересуйся...
V>то твоё решение превратиться в то, что предлагает Sun.
Нет.
Оно никогда не будет таким мутным и страшным.
V>Они ведь тоже начали пока с очень малого в этой области (понятное дело, выпуск серийного проца новой архитектуры — это целая эпоха в жизни каждой фирмы, они пока просто осторожничают).
Я думаю это будет последний процессор с этой архитектурой.
V>Да, параллельно и что попало. Но если проц увидит, что в результате менялись и читались разные участки данных даже у одной и той же сущности (разные поля твоего типа, например, а тип целиком лежит в линейке кеша, понятное дело), то одновременные транзакции разрешаются, иначе — сериализуются. Прочувствуй разницу, как говорится.
Теперь осталась маленькая проблема. Реализовать это технически.
И что-то мне подсказывает что оверхед бедт такой что
V>Серваки БД работают именно так на определённых уровнях транзакции, зачем что-то изобретать, всё давно изобретено. Речь идёт лишь о том, чтобы частично (пока) поддержать часть этой логики в железе.
Оракл в железе. Круто.
V>С чего бы это меньше не залочить?
С такой.
Память в железке ходит нашенкованная на линейки кеша.
V>Да хоть целый список областей произвольной длины, даже если все эти области не помещаются целиком в целый кеш.
Чё? Ты хочень сказать что можно делать в железе эффективные транзакции на нескольких кусках памяти каждый из которых не влезает в L1 кешь?
Ты серьезно?
V>Сейчас под этот список в новом сановском проце, насколько я понял, отведено 4 ячейки на поток, значит всего 32*4=128, их в перспективе может быть произвольное кол-во.
4 слова на поток в одной тразакции? Гы! Даже не смешно.
V>Припрёт уже прямо сейчас на современных задачах. Пусть они поиграют с тем, насколько такая система эффективна для целей сериализации доступа, если окажется эффективной (в чём я не сомневаюсь),
А я сомневаюсь что оно вобще будет работать.
V>то оно будет расти вширь (ибо по частоте практически упёрлись, теоретический предел современного тех-процесса в районе 10МГц,
Ты точно несколько ноликов не потерял?
V>даже при произвольной дальнейшей миниатюризации, так что расти можно будет только вширь одновременно с дальнейшей миниатюризацией... возможно придумают что-то вместо транзисторов когда-нить, но пока не придумали, и используют их, родимых, и дырочную проводимость, которая имеет геометрический минимальный предел, чтобы диод оставался диодом, и порог около 0.5-0.6В для кремния, так что пока упёрлись вплотную, и 1-1.2В — это примерно минимум для напряжения питания).
А это тут вобще причем?
V>Как показала практика — всё-таки беда. Даже для моей задачи микширования звука. Сервак загибается, если всего-лишь 50 раз в сек выделять динамически под каждый буфер данных 320 байт, и кол-во пользователей всего-лишь 4096, а на каждого — 4 таких буфера. Пока что рулят статические буфера.
Не занимайся поддтасовками.
Ты взял тупой мусорщик из .NET. И обобщаешь на все...
Я так тоже могу взять сортировку из этой темы
и обобщить на все сортировки.
V>Так же сильно помогло использование, где можно, безлоковых алгоритмов. Мало того, что Monitor.Enter/Exit работает гораздо тормознее чем родные CriticalSection, так даже последние прилично тормозят процесс.
Так я и предлагаю на корню убить все эти локи просто перейдя в другой базис.
V>Транзакционная память дешевле, чем блокировка целой линейки кеша из-за одного int. А ты в курсе что для записи одного int'а линейка кеша всегда захватывается для монопольного доступа.
В данном случае ее захватывают на один такт.
Если ее захватить на 3-10 тактов то на фоне 100 тактов которые требуются для того чтобы ее доставить в L1...
V>Ты наверно недопонял. Еще до коммита понятны намерения участников, кто что будет читать/писать. В случае отсутствия кофликтов вообще ничего не происходит, иначе — сериализация на уровне планировщика потоков в проце.
V>Согласен, мютекс — это искуственный примитив, отсутствующий в теории о синхронизации. Так и есть, этот семафор с N=1, имеющий собственное имя, нужен исключительно для сериализации последовательности операций.
В какой именно? Даже wikipedia http://en.wikipedia.org/wiki/Category:Process_calculi знает несколько теорий.
Еще раз: Есть разные базисы на которых можно строить синхронизацию.
WH>>Который просто лочит на несколько тактов кусочек памяти. V>Его не надо лочить V>Надо проследить за атомарностью изменений в нём.
Так на данном уровне эффективнее лока ничего не сделать.
V>Нет, не будет, ты недопонял. Коммит — это вообще абстракция, реально никакого коммита нет, есть атомарные изменения 2-х ячеек (пока 2-х).
А у меня что?
У меня атомарное изменение одной или 2х линеек кеша.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
V>>Зачем сразу предлагаешь техническое решение, какие-то мифические блокировки линеек? WH>Мифические? Интересно. А что префикс lock на современных x86'х процессорах делает? WH>Ни когда не задумывался?
Дык, он по другому пока не умеет. А задумывался лет 10 или больше назад, если тебя дата интересует.
V>>Надо просто формулировать задачу, а не бросаться в технические подробности. WH>Задача простая: Обеспечить правильную синхронизация в многопоточной среде.
Атомарность, скорее. Синхронизация — это ближе к событиям, а если речь о данных — то атомарность.
V>>Если в твоём решении расширить от линейки до произвольного набора данных, WH>Каком именно? WH>Ты постоянно путаешься. WH>Система типов не накладывает подобных ограничений.
Накладывает, ведь мы можем в экземпляре типа менять и читать независимые одиночные поля, нафига нам тут блокировки? А можем захотеть транзакционно прочитать/изменить сразу несколько полей. Твоя система типов с этим не справляется.
WH>А в железе один хрен меньше чем с линейкой кеша работать не получится.
Получилось же у Sun.
WH>Ты знаешь что делают процессоры при записи в память? WH>Вот поинтересуйся...
Началась старая песня... А ты знаешь как работают многоканальные контроллеры памяти? Поинтересуйся
V>>то твоё решение превратиться в то, что предлагает Sun. WH>Нет. WH>Оно никогда не будет таким мутным и страшным.
Это тебе оно кажется страшным, а мне кажется логичным.
V>>Они ведь тоже начали пока с очень малого в этой области (понятное дело, выпуск серийного проца новой архитектуры — это целая эпоха в жизни каждой фирмы, они пока просто осторожничают). WH>Я думаю это будет последний процессор с этой архитектурой.
С этой, не этой... Кол-во потоков на ядро будет только расти, транзакционность всё-равно нужна и её будут делать.
V>>Да, параллельно и что попало. Но если проц увидит, что в результате менялись и читались разные участки данных даже у одной и той же сущности (разные поля твоего типа, например, а тип целиком лежит в линейке кеша, понятное дело), то одновременные транзакции разрешаются, иначе — сериализуются. Прочувствуй разницу, как говорится. WH>Теперь осталась маленькая проблема. Реализовать это технически. WH>И что-то мне подсказывает что оверхед бедт такой что
Хочешь об этом поговорить?
Я вот не вижу никакого оверхеда в аппаратном исполнении, могу даже схему принципиальную накидать, которая сравнивает транзакционные области и сигнализирует о конфликтах. А шедуллер потоков (там несколько потоков на ядро), может просто так раскидать потоки, чтобы обеспечить сериализацию доступа в случае конфликтов. Пока что доступна операция атомарного изменения 2-х ячеек, но их может быть и больше. Понятно, что аппаратно всегда будет некий предел на такую аппаратную транзакцию. Дык, если проц не позволяет аппаратно включить достаточное кол-во сущностей в транзакцию, всегда можно по-старинке.
V>>Серваки БД работают именно так на определённых уровнях транзакции, зачем что-то изобретать, всё давно изобретено. Речь идёт лишь о том, чтобы частично (пока) поддержать часть этой логики в железе. WH>Оракл в железе. Круто.
Частоизменяемых данных в реальных приложениях не много. В большинстве своём данные накапливаются и опрашиваются. Индекс идёт отдельно от данных. Сами данные идут мимо проца и его кешей напрямую через DMA, что с диска, что в сетку.
V>>С чего бы это меньше не залочить? WH>С такой. WH>Память в железке ходит нашенкованная на линейки кеша.
Пусть себе ходит, зачём всю линейку лочить? В линейке могут лежать логические несвязанные данные.
V>>Да хоть целый список областей произвольной длины, даже если все эти области не помещаются целиком в целый кеш. WH>Чё? Ты хочень сказать что можно делать в железе эффективные транзакции на нескольких кусках памяти каждый из которых не влезает в L1 кешь? WH>Ты серьезно?
Я о том, что хранить список диапазонов участвующих в транзакциях данных — это весьма экономно в общем случае. А сами данные могут занимать произвольный объём. Да, почему бы планировщику не спланировать задачи даже в тех случаях, когда все данные за один раз не лезут в L1? Ведь есть еще L2, разрядность обмена с ним растёт не по дням, а по часам, т.е. скорость обмена L1 и L2 тоже растёт. Есть еще и другие потоки, которым нужен L1, так что интеерсующие данные можно "прокачать" через выделенный участок L1 (примерно 50 тактов на обмен сегодня). Сейчас речь идёт о 32-х потоках, когда зайдет о 256-ти, то это будет вполне нормальный сценарий.
V>>Сейчас под этот список в новом сановском проце, насколько я понял, отведено 4 ячейки на поток, значит всего 32*4=128, их в перспективе может быть произвольное кол-во. WH>4 слова на поток в одной тразакции? Гы! Даже не смешно.
Да понятно, что это эксперимент.
V>>Припрёт уже прямо сейчас на современных задачах. Пусть они поиграют с тем, насколько такая система эффективна для целей сериализации доступа, если окажется эффективной (в чём я не сомневаюсь), WH>А я сомневаюсь что оно вобще будет работать.
Работает на отладчике, при том что отладчик — это не как они хотят чтобы работало, а тупой эмулятор вентилей железки.
V>>то оно будет расти вширь (ибо по частоте практически упёрлись, теоретический предел современного тех-процесса в районе 10МГц, WH>Ты точно несколько ноликов не потерял?
3 потерял.
V>>даже при произвольной дальнейшей миниатюризации, так что расти можно будет только вширь одновременно с дальнейшей миниатюризацией... возможно придумают что-то вместо транзисторов когда-нить, но пока не придумали, и используют их, родимых, и дырочную проводимость, которая имеет геометрический минимальный предел, чтобы диод оставался диодом, и порог около 0.5-0.6В для кремния, так что пока упёрлись вплотную, и 1-1.2В — это примерно минимум для напряжения питания). WH>А это тут вобще причем?
При том, что дальнейшее развитие будет идти только вширь на текущих технологиях. Т.е. линейки кеша будут всё шире и шире, аппаратных потоков будет всё больше, и тем менее эффективно будет лочить всю линейку ради одного int.
V>>Как показала практика — всё-таки беда. Даже для моей задачи микширования звука. Сервак загибается, если всего-лишь 50 раз в сек выделять динамически под каждый буфер данных 320 байт, и кол-во пользователей всего-лишь 4096, а на каждого — 4 таких буфера. Пока что рулят статические буфера. WH>Не занимайся поддтасовками. WH>Ты взял тупой мусорщик из .NET. И обобщаешь на все...
Я ответил насчёт эффективности передачи без локов данных на кольцевых буферах взамен lock-free списка из динамических узлов. Какие нафик обощения? что имеем, то имеем.
V>>Транзакционная память дешевле, чем блокировка целой линейки кеша из-за одного int. WH> А ты в курсе что для записи одного int'а линейка кеша всегда захватывается для монопольного доступа. WH>В данном случае ее захватывают на один такт.
Ты не знаешь, как это реально происходит в многопоточных ядрах. Я вот не уверен, что на каждый поток там свой контроллер доступа к памяти. Sun предложила именно это, но пока контроллирует только 2 значения на поток.
Здравствуйте, vdimas, Вы писали:
V>>>Надо просто формулировать задачу, а не бросаться в технические подробности. WH>>Задача простая: Обеспечить правильную синхронизация в многопоточной среде. V>Атомарность, скорее. Синхронизация — это ближе к событиям, а если речь о данных — то атомарность.
Ага. Событие чтения. Событие записи...
Короче хватит заниматься разведением спора то терминах.
V>Накладывает, ведь мы можем в экземпляре типа менять и читать независимые одиночные поля, нафига нам тут блокировки? А можем захотеть транзакционно прочитать/изменить сразу несколько полей. Твоя система типов с этим не справляется.
Справится.
Читай еще раз ибо ты вобще ничего не понял.
WH>>А в железе один хрен меньше чем с линейкой кеша работать не получится. V>Получилось же у Sun.
И с какой эффективностью?
V>С этой, не этой... Кол-во потоков на ядро будет только расти, транзакционность всё-равно нужна и её будут делать.
Потоки да.
Транзакционная память нет.
V>Я вот не вижу никакого оверхеда в аппаратном исполнении, могу даже схему принципиальную накидать, которая сравнивает транзакционные области и сигнализирует о конфликтах. А шедуллер потоков (там несколько потоков на ядро), может просто так раскидать потоки, чтобы обеспечить сериализацию доступа в случае конфликтов.
Точно оракл в железе.
V>Пока что доступна операция атомарного изменения 2-х ячеек, но их может быть и больше. Понятно, что аппаратно всегда будет некий предел на такую аппаратную транзакцию. Дык, если проц не позволяет аппаратно включить достаточное кол-во сущностей в транзакцию, всегда можно по-старинке.
По какой из: http://en.wikipedia.org/wiki/Category:Process_calculi
И колличество "старинок" этим списком не ограничивается.
V>Частоизменяемых данных в реальных приложениях не много. В большинстве своём данные накапливаются и опрашиваются. Индекс идёт отдельно от данных. Сами данные идут мимо проца и его кешей напрямую через DMA, что с диска, что в сетку.
И?
V>Пусть себе ходит, зачём всю линейку лочить?
За тем что для того чтобы в линейку что-то записить нужно по любому получить эксклюзивный доступ.
А если у нас есть эксклюзивный доступ то продержим мы эту линейку один или 10 тактов разници нет.
AtomicIncrement — 3 такта
AtomicCompareExchange — 3-4 такта
V>В линейке могут лежать логические несвязанные данные.
Откуда они там возьмутся?
Ты что предлагаешь эффективной раскладкой данных на низком уровне вобще не заниматься?
Может еще и на аллигмент забить?
V>Я о том, что хранить список диапазонов участвующих в транзакциях данных — это весьма экономно в общем случае.
В общем!?
V>А сами данные могут занимать произвольный объём. Да, почему бы планировщику не спланировать задачи даже в тех случаях, когда все данные за один раз не лезут в L1? Ведь есть еще L2, разрядность обмена с ним растёт не по дням, а по часам, т.е. скорость обмена L1 и L2 тоже растёт. Есть еще и другие потоки, которым нужен L1, так что интеерсующие данные можно "прокачать" через выделенный участок L1 (примерно 50 тактов на обмен сегодня). Сейчас речь идёт о 32-х потоках, когда зайдет о 256-ти, то это будет вполне нормальный сценарий.
Не оракл отдыхает.
WH>>4 слова на поток в одной тразакции? Гы! Даже не смешно. V>Да понятно, что это эксперимент.
А сильно больше и не будет.
Можешь не надеяться.
V>Работает на отладчике, при том что отладчик — это не как они хотят чтобы работало, а тупой эмулятор вентилей железки.
ню-ню.
V>При том, что дальнейшее развитие будет идти только вширь на текущих технологиях. Т.е. линейки кеша будут всё шире и шире, аппаратных потоков будет всё больше, и тем менее эффективно будет лочить всю линейку ради одного int.
А куда ты от этого денешься?
V>Я ответил насчёт эффективности передачи без локов данных на кольцевых буферах взамен lock-free списка из динамических узлов. V>Какие нафик обощения?
Такие.
V>что имеем, то имеем.
В частном случае.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
V>>Накладывает, ведь мы можем в экземпляре типа менять и читать независимые одиночные поля, нафига нам тут блокировки? А можем захотеть транзакционно прочитать/изменить сразу несколько полей. Твоя система типов с этим не справляется. WH>Справится. WH>Читай еще раз ибо ты вобще ничего не понял.
Еще раз, как в твоей системе типов разные потоки могут одновременно атомарно менять непересекающиеся множества полей типа int твоего uniqueness типа? А что будет, если множества полей пересекаются? И ты не отсылай, ты разъясни что будет в этом случае, я в предыдущем сообщении привёл этот сценарий, ты не отреагировал. Как мне, например, транзакционно менять некоторые элементы массива, не блокируя весь массив?
WH>>>А в железе один хрен меньше чем с линейкой кеша работать не получится. V>>Получилось же у Sun. WH>И с какой эффективностью?
Наверно, с эффективностью обычного исполнения кода.
V>>Пока что доступна операция атомарного изменения 2-х ячеек, но их может быть и больше. Понятно, что аппаратно всегда будет некий предел на такую аппаратную транзакцию. Дык, если проц не позволяет аппаратно включить достаточное кол-во сущностей в транзакцию, всегда можно по-старинке. WH>По какой из: http://en.wikipedia.org/wiki/Category:Process_calculi WH>И колличество "старинок" этим списком не ограничивается.
Имел ввиду — через примитивы синхронизации.
V>>Частоизменяемых данных в реальных приложениях не много. В большинстве своём данные накапливаются и опрашиваются. Индекс идёт отдельно от данных. Сами данные идут мимо проца и его кешей напрямую через DMA, что с диска, что в сетку. WH>И?
Что и? Если кеша хватает размещать индексы, то оракл в железе получается.
V>>Пусть себе ходит, зачём всю линейку лочить? WH>За тем что для того чтобы в линейку что-то записить нужно по любому получить эксклюзивный доступ.
Еще раз, ты не знаешь, как это реально происходит в многопоточных ядрах.
V>>В линейке могут лежать логические несвязанные данные. WH>Откуда они там возьмутся? WH>Ты что предлагаешь эффективной раскладкой данных на низком уровне вобще не заниматься? WH>Может еще и на аллигмент забить?
Какое еще выравнивание на два рядомстоящих int в массиве или в полях одного типа?
V>>Я о том, что хранить список диапазонов участвующих в транзакциях данных — это весьма экономно в общем случае. WH>В общем!?
Ес-сно, кроме случаев, когда запись о диапазоне (адрес+длина) больше чем содержимое.
V>>Работает на отладчике, при том что отладчик — это не как они хотят чтобы работало, а тупой эмулятор вентилей железки. WH>ню-ню.
Интелы так же отлаживали при разработке, да и вообще любую сложную технику таким образом эмулируют. Нет ничего проще, чем эмуляция вентиля.
V>>Я ответил насчёт эффективности передачи без локов данных на кольцевых буферах взамен lock-free списка из динамических узлов. V>>Какие нафик обощения? WH>Такие.
Ну так я тебе показал сценарий, где подобная транзакционность даст приличный выигрыш при передаче данных м/у потоками, ввиду пользования статическими буферами. Ты сам напомнил про ГЦ, а потом заявляешь о каких-то обобщениях, когда по факту 16к выделений в секунду — это для GC оказалось плохо. А для передачи такого кол-ва данных через статические буфера — загрузка проца близка к нулевой, если примитивами синхронизации не пользоваться.
Здравствуйте, vdimas, Вы писали:
V>Еще раз, как в твоей системе типов разные потоки могут одновременно атомарно менять непересекающиеся множества полей типа int твоего uniqueness типа?
Говорю же ничего не понял.
2 потока не могут не только писать но и читать разные поля одного объекта uniqueness типа. Ибо ссылку может держать только один поток.
V>А что будет, если множества полей пересекаются? И ты не отсылай, ты разъясни что будет в этом случае, я в предыдущем сообщении привёл этот сценарий, ты не отреагировал. Как мне, например, транзакционно менять некоторые элементы массива, не блокируя весь массив?
ЗАЧЕМ?
Только смотри чтобы не получилось как тут
.
WH>>>>А в железе один хрен меньше чем с линейкой кеша работать не получится. V>>>Получилось же у Sun. WH>>И с какой эффективностью? V>Наверно, с эффективностью обычного исполнения кода.
Чудес не бывает.
WH>>По какой из: http://en.wikipedia.org/wiki/Category:Process_calculi WH>>И колличество "старинок" этим списком не ограничивается. V>Имел ввиду — через примитивы синхронизации.
Они разные бывают.
V>Что и? Если кеша хватает размещать индексы, то оракл в железе получается.
А он в железе нужен?
V>>>Пусть себе ходит, зачём всю линейку лочить? WH>>За тем что для того чтобы в линейку что-то записить нужно по любому получить эксклюзивный доступ. V>Еще раз, ты не знаешь, как это реально происходит в многопоточных ядрах.
Ну просвети.
Только не забудь про то что у нас несколько ядер на кристале.
А на серваках несколько процессоров.
И так 2 потока работающих на разных процессорах хотят сделать на одной ячейке памяти AtomicCompareExchange.
Расказывай как ты это сделаешь без локов линейки кеша.
Ворос по проще: Тоже самое но только потоки живут на двух ядрах одного кристала.
А на одном ядре тормознуть один из 32х потоков на 3-4 такта не проблема.
V>>>В линейке могут лежать логические несвязанные данные. WH>>Откуда они там возьмутся? WH>>Ты что предлагаешь эффективной раскладкой данных на низком уровне вобще не заниматься?
На вопрос ответь.
WH>>Может еще и на аллигмент забить? V>Какое еще выравнивание на два рядомстоящих int в массиве или в полях одного типа?
Такое. Можно же эти инты по адресу 1111111111 разместить.
V>Ну так я тебе показал сценарий, где подобная транзакционность даст приличный выигрыш при передаче данных м/у потоками, ввиду пользования статическими буферами. Ты сам напомнил про ГЦ, а потом заявляешь о каких-то обобщениях, когда по факту 16к выделений в секунду — это для GC оказалось плохо.
ДЛЯ КОНКРЕТНОГО ГЦ!
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
V>>Еще раз, как в твоей системе типов разные потоки могут одновременно атомарно менять непересекающиеся множества полей типа int твоего uniqueness типа? WH>Говорю же ничего не понял. WH>2 потока не могут не только писать но и читать разные поля одного объекта uniqueness типа. Ибо ссылку может держать только один поток.
Тогда твоя схема идёт в сад.
Uniqueness type был разработан для совсем других вещей, а именно — для оптимизаций выделения памяти в функциональных языках. Это техника позволяет придавать ссылочным типам семантику value-типов, и не перевыделять память, например, под операнд в рекурсии. Когда существует конфликт, то создаётся просто копия
А теперь смотри еще весьма популярный сценарий для многопоточности в бизнес-логике:
— мы имеем некий граф объектов, чей корень хранится в статической памяти или в некоем передаваемом по стеку контексте (больше способов не знаю для многопоточности, кроме тормозного TLS).
— этот корень — суть некий домен различных сущностей, домен содержит основную хеш-таблицу, в которой содержатся объекты-менеджеры сущностей.
— менеджеры обычно тоже содержат хеш-таблицу, в которой хранятся сами сущности.
— в доменах отсутствует синхронизация для читателей (даже барьер памяти отсутствует), синхронизация есть только в случае добавления или удаления класса сущностей (менеджеров), в этом случае содаётся новая хеш-таблица и просто подменяется ссылка на новую хеш-таблицу.
— сами менеджеры тоже зачастую работают по такой же схеме (без синхронизации читателей), если подавляющая часть реальных сценариев — это чтение ссылок на сами хранимые сущности (а не добавление или удаление оных).
— транзакции осуществляются более чем просто: блокируется список участвующих менеджеров (как не допускаются дедлоки уже приводил), создаются копии объектов для изменения, по коммиту новые объекты распихиваются обратно в хранилища менеджеров.
— транзакции на чтение аналогично блокируют список интересующих менеджеров, но без копирования экземпляров интересующих целевых объектов.
Схема весьма эффективна для типовых серваков приложений, обрабатывающих "много" запросов в единицу времени.
Так вот, где тут должен начинаться uniqueness тип, чтобы твоя схема нам помогла оптимизировать блокировки? И как не допустить конфликтов? В каком месте конкретно в этом графе компилятор заранее выдаст ошибку о нарушении совместного владения? (Ведь мы идём к конкретному объекту через цепочку ссылок).
V>>А что будет, если множества полей пересекаются? И ты не отсылай, ты разъясни что будет в этом случае, я в предыдущем сообщении привёл этот сценарий, ты не отреагировал. Как мне, например, транзакционно менять некоторые элементы массива, не блокируя весь массив? WH>ЗАЧЕМ?
Затем, что этот массив является кешем данных некоего апп-сервака, обслуживающего по 100тыс запросов в секунду.
WH>>>И с какой эффективностью? V>>Наверно, с эффективностью обычного исполнения кода. WH>Чудес не бывает.
Да нет никаких чудес, включи воображение и прикинь, как это реализовано в ядре того проца.
V>>Что и? Если кеша хватает размещать индексы, то оракл в железе получается. WH>А он в железе нужен?
Хоть в железе, хоть в бумаге, львиная доля задержек сейчас происходит от дёрганья множества примитивов синхронизации, от неподходящей конкретному сценарию гранулярности блокировок, при том что гранулярность задаётся на момент написания программы, а доля различных сценариев может меняться многократно в течении рабочего дня разработанного продукта.
V>>>>Пусть себе ходит, зачём всю линейку лочить? WH>>>За тем что для того чтобы в линейку что-то записить нужно по любому получить эксклюзивный доступ. V>>Еще раз, ты не знаешь, как это реально происходит в многопоточных ядрах. WH>Ну просвети.
Лочить линейку кеша надо для защиты от доступа другого ядра/проца. Для потоков одного ядра достаточно переупорядочивания инструкций, чтобы избежать конфликтов, не зачем каждому потоку "перелочивать" на себя всю линейку, если ядро уже владеет линейкой кеша. Актуально, кстати, при обсчёте тех же матриц. Но вот атомарное изменение или чтение нескольких ячеек — по прежнему проблема, для которой предлагается экспериментальное решение.
Учитывая, что вместо многоядерности расширение идёт в сторону многопоточности, то наши представления должны будут малость поменяться.
WH>А на одном ядре тормознуть один из 32х потоков на 3-4 такта не проблема.
Почему один? Сколько потоков на других ядрах будут работать с этой линейкой, столько и тормознётся. Может и не одного.
V>>>>В линейке могут лежать логические несвязанные данные. WH>>>Откуда они там возьмутся? WH>>>Ты что предлагаешь эффективной раскладкой данных на низком уровне вобще не заниматься? WH>На вопрос ответь.
Не представляю как ею заниматься, если размер поля объекта на порядок будет меньше размера линейки кеша, а сам объект — больше нескольких этих линеек. Ничего размещение не даст для целей независимого неблокирующего доступа к различным полям объекта.
WH>>>Может еще и на аллигмент забить? V>>Какое еще выравнивание на два рядомстоящих int в массиве или в полях одного типа? WH>Такое. Можно же эти инты по адресу 1111111111 разместить.
Это ничего не даст при независимом доступе к соседним ячейкам.
V>>Ну так я тебе показал сценарий, где подобная транзакционность даст приличный выигрыш при передаче данных м/у потоками, ввиду пользования статическими буферами. Ты сам напомнил про ГЦ, а потом заявляешь о каких-то обобщениях, когда по факту 16к выделений в секунду — это для GC оказалось плохо. WH>ДЛЯ КОНКРЕТНОГО ГЦ!
Здравствуйте, vdimas, Вы писали:
V>Тогда твоя схема идёт в сад.
Ни куда она не идет.
V>Uniqueness type был разработан для совсем других вещей,
Да мне плевать для чего их разработали.
Вобще говоря я их придумал сам задолго до того как узнал слова uniqueness type.
V>А теперь смотри еще весьма популярный сценарий для многопоточности в бизнес-логике:
Популярные сценарии идет в сад.
Другая система.
Другие сценарии.
V>Схема весьма эффективна для типовых серваков приложений, обрабатывающих "много" запросов в единицу времени.
Эта схема формализуется pure типами.
V>Затем, что этот массив является кешем данных некоего апп-сервака, обслуживающего по 100тыс запросов в секунду.
1)100К RPS Ты где железо такое видел?
2)Кешей в вакууме не бывает. Бывают кеши для конкретной задачи.
V>Лочить линейку кеша надо для защиты от доступа другого ядра/проца.
Ага. Для двух и более ядер надо лочить.
Запомним.
V>Для потоков одного ядра достаточно переупорядочивания инструкций, чтобы избежать конфликтов,
Ну вот локи и переупорядочат.
Тем более что нафига двум потоком писать в одну линейку памяти если они не занимаются пересылкой данных друг другу не ясно.
V>не зачем каждому потоку "перелочивать" на себя всю линейку, если ядро уже владеет линейкой кеша.
А в чем проблема?
Если ядро владеет линейкой то это один такт.
V>Почему один? Сколько потоков на других ядрах будут работать с этой линейкой, столько и тормознётся. Может и не одного.
Стоять! Выше ты сказал что для двух ядер нужно лочить!
Те потоки на других ядрах тормознутся по любому.
V>Не представляю как ею заниматься, если размер поля объекта на порядок будет меньше размера линейки кеша, а сам объект — больше нескольких этих линеек. Ничего размещение не даст для целей независимого неблокирующего доступа к различным полям объекта.
Я так и не понял откуда у тебя такие объекты.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, vdimas, Вы писали:
V>А теперь смотри еще весьма популярный сценарий для многопоточности в бизнес-логике:
А можно узнать, где это популярный сценарий? Я думал, что такие приложения я могу пересчитать по пальцам одной руки...
В Java/CLI для обеспечения многопоточного доступа скорее всего придётся использовать volatile переменные (если не использовать TLS, который ты говоришь плох), следовательно доступ на чтение без барьеров памяти не реализуется. В С/С++ реализуется, но это огромный pain-in-the-ass, который может взять на себя не каждый...
Где можно посмотреть примеры таких приложений? Если closed-source, то хотя бы названия.
V>- мы имеем некий граф объектов, чей корень хранится в статической памяти или в некоем передаваемом по стеку контексте (больше способов не знаю для
многопоточности, кроме тормозного TLS). V>- этот корень — суть некий домен различных сущностей, домен содержит основную хеш-таблицу, в которой содержатся объекты-менеджеры сущностей. V>- менеджеры обычно тоже содержат хеш-таблицу, в которой хранятся сами сущности. V>- в доменах отсутствует синхронизация для читателей (даже барьер памяти отсутствует), синхронизация есть только в случае добавления или удаления класса сущностей (менеджеров), в этом случае содаётся новая хеш-таблица и просто подменяется ссылка на новую хеш-таблицу. V>- сами менеджеры тоже зачастую работают по такой же схеме (без синхронизации читателей), если подавляющая часть реальных сценариев — это чтение ссылок на сами хранимые сущности (а не добавление или удаление оных). V>- транзакции осуществляются более чем просто: блокируется список участвующих менеджеров (как не допускаются дедлоки уже приводил), создаются копии объектов для изменения, по коммиту новые объекты распихиваются обратно в хранилища менеджеров. V>- транзакции на чтение аналогично блокируют список интересующих менеджеров, но без копирования экземпляров интересующих целевых объектов.
С транзакциями тут большие проблемы. Транзакций в общем понимании (ACID) тут не получится.
Например если взять транзакцию на чтение. Допустим поток читает 2 списка. Другой поток (который выполняет транзакцию на запись) одновременно хочет "транзакционно" переместить элемент из одного списка во второй. При такой схеме может получится, что первый поток либо не увидит элемент ни в одном списке, либо увидит сразу в двух. Что, безусловно, противоречит определению ACID транзакции.
Теперь возьмём транзакцию на запись. Допустим потоку надо выполнить следующую операцию. Добавить элемент в список 1, только если в списке 2 нет некого элемента. Он проверяет, что в списке 2 нет некого элемента, и планирует операцию добавления элемента в список 1. При коммите добавление элемента в список 1 производится, хотя в этот момент некий элемент в списке 2 уже может присутствовать. Опять же не ACID семантика.
Тут можно говорить только о транзакционности на уровне отдельных объектов, которая с т.з. бизнес-логики имеет мало смысла.
Здравствуйте, WolfHound, Вы писали:
V>>Затем, что этот массив является кешем данных некоего апп-сервака, обслуживающего по 100тыс запросов в секунду.
WH>1)100К RPS Ты где железо такое видел?
Не так фантастично, как кажется на первый взгляд.
Допустим у нас 8-ми ядерная система, каждое ядро 3 GHz — типовой сервер на основе "бытового" (х86) железа. Получается по 240'000 тактов на запрос. Не так уж и мало.
Ввод-вывод. Допустим сервер общается с другими серверами, т.е. есть мало сокетов с большим потоком. Допустим 64 байта на запрос/ответ. Получается поток 100Mbps. Тоже вполне реалистично.
Конечно, для сервера, обрабатывающего web приложение, это не реалистично. Но в то же время для некоторых типов серверов это видится более-менее реалистичным. Ну и очевидно, так такая производительность не получилась "сама собой".
Здравствуйте, remark, Вы писали:
WH>>1)100К RPS Ты где железо такое видел? R>Не так фантастично, как кажется на первый взгляд.
Так просто считать нельзя.
Там еще ОСь под ногами путается...
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Так и есть, этот семафор с N=1, имеющий собственное имя, нужен исключительно для сериализации последовательности операций.
