Здравствуйте, WolfHound, Вы писали:

WH>>>1)100К RPS Ты где железо такое видел?

R>>Не так фантастично, как кажется на первый взгляд.

WH>Так просто считать нельзя.
WH>Там еще ОСь под ногами путается...


Давай считать не просто. Единственное, где ОС под ногами обязательно — это IO. Приём/отправку делаем пакетами по, допустим, 1000 сообщений. Т.е. получается 200 системных вызовов в сек. Опять вполне реалистично.

Здравствуйте, remark, Вы писали:

R>Давай считать не просто. Единственное, где ОС под ногами обязательно — это IO.
Не единственное.
У нее еще шедуллер есть.
Менеджер виртуальной памяти.
...

R>Приём/отправку делаем пакетами по, допустим, 1000 сообщений. Т.е. получается 200 системных вызовов в сек. Опять вполне реалистично.
Ага. 1000 сообщений в пакете. Каждое сообщение 1 байт. Обработка сообщения увеличение значения каждого байта на 1...
Так может быть и больше...

Только это подтасовки.

А вот в 100К реальных (даже очень легких) запросов на обычном железе и обычных ОС я что-то не верю.

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, remark, Вы писали:

R>>Давай считать не просто. Единственное, где ОС под ногами обязательно — это IO.
WH>Не единственное.
WH>У нее еще шедуллер есть.
WH>Менеджер виртуальной памяти.
WH>...

Делаем по потоку на процессор. Шедулер отпадает.
Память кэшируем. Менеджер виртуальной памяти отпадает.
Что скрывается за "..."?


R>>Приём/отправку делаем пакетами по, допустим, 1000 сообщений. Т.е. получается 200 системных вызовов в сек. Опять вполне реалистично.
WH>Ага. 1000 сообщений в пакете. Каждое сообщение 1 байт. Обработка сообщения увеличение значения каждого байта на 1...
WH>Так может быть и больше...
WH>Только это подтасовки.

А что плохого в 1000 сообщений в пакете? Если у нас 100'000 в сек, то надо надо всего лишь собирать запросы за 10 мсек, и тогда отправлять.
Пакетная обработка — это паттерн производительности. Он неё никуда не уйти в высокопроизводительном приложении. Естественно ничего хорошего не получится, если каждое сообщение отправлять блокирующим send'ом.

Каждое сообщение не 1 байт, а я считал 64 байта. Если взять гипотетические запросы "получить баланс л/с", "изменить баланс л/с", то они вполне укладываются в 64 байта (если мы берём внутренний интерфейс между серверами одной компании).
Обработка запроса — 240'000 тактов, можно сделать и побольше сложения 2 чисел.

Здравствуйте, WolfHound, Вы писали:


V>>Схема весьма эффективна для типовых серваков приложений, обрабатывающих "много" запросов в единицу времени.
WH>Эта схема формализуется pure типами.

Мне не формализация нужна, а сериализация доступа. Даже в терминах pure-типа, при пересоздании коллекции объектов необходимо заблокировать другие потоки от подобного пересоздания.


V>>Затем, что этот массив является кешем данных некоего апп-сервака, обслуживающего по 100тыс запросов в секунду.
WH>1)100К RPS Ты где железо такое видел?

Ну, несколько тысяч простых запросов (не к БД, разумеется) поддерживает обычное современное железо, если вместо remoting и пр. использовать напрямую UDP (отдельная тема, как-то уже поднималась в рамках обсуждения стека IP, в котором отсутствует тип обслуживания "гарантированная доставка одного пакета"), этот тип обслуживания некоторые системы (IAX/IAX2) делают через UDP, и получают приличную скорость при малых затратах железа.

WH>2)Кешей в вакууме не бывает. Бывают кеши для конкретной задачи.

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


V>>Лочить линейку кеша надо для защиты от доступа другого ядра/проца.
WH>Ага. Для двух и более ядер надо лочить.

Ес-но.

V>>Для потоков одного ядра достаточно переупорядочивания инструкций, чтобы избежать конфликтов,
WH>Ну вот локи и переупорядочат.
WH>Тем более что нафига двум потоком писать в одну линейку памяти если они не занимаются пересылкой данных друг другу не ясно.

Не в одну, а в соседние (я же упомянул обсчёт матриц).

V>>Почему один? Сколько потоков на других ядрах будут работать с этой линейкой, столько и тормознётся. Может и не одного.
WH>Стоять! Выше ты сказал что для двух ядер нужно лочить!
WH>Те потоки на других ядрах тормознутся по любому.

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

V>>Не представляю как ею заниматься, если размер поля объекта на порядок будет меньше размера линейки кеша, а сам объект — больше нескольких этих линеек. Ничего размещение не даст для целей независимого неблокирующего доступа к различным полям объекта.
WH>Я так и не понял откуда у тебя такие объекты.

Обычный массив ссылок, являющийся основой любого быстрого кеша.

Здравствуйте, remark, Вы писали:

V>>А теперь смотри еще весьма популярный сценарий для многопоточности в бизнес-логике:

R>А можно узнать, где это популярный сценарий? Я думал, что такие приложения я могу пересчитать по пальцам одной руки...

Да вот сервак аудио-видео конференций, например. Избавившись от лишних локов, увеличили максимальный предел одновременно обслуживаемых юзверей на порядок примерно.

R>В Java/CLI для обеспечения многопоточного доступа скорее всего придётся использовать volatile переменные (если не использовать TLS, который ты говоришь плох), следовательно доступ на чтение без барьеров памяти не реализуется.

А зачем volatile? Другим потокам не критично, когда они увидят изменения — прямо сейчас, или в следующий запрос. Главное — это целостность, поэтому контейнеры не изменяются, а пересоздаются заново при каждом изменении и просто обновляется ссылка так, чтобы указывать на новый контейнер. Юзвери входят/выходят из конференций (или меняют состояние) на много порядков реже, чем идёт обращение к микшируемым данным (50 раз в сек для каждого юзверя).

Серваков конференций — много, их ферма, зато management сервак — один, хранит всё в БД, но его дёргают множества серваков коференций (на одном серваке конференций множество одновременно обслуживаемых конференций, сколько железо позволяет), поэтому в нём кеши организованны аналогично, т.к. в свою очередь данные о конференциях меняются на порядки реже, чем юзвери заходят и выходят из них.

R>В С/С++ реализуется, но это огромный pain-in-the-ass, который может взять на себя не каждый...
R>Где можно посмотреть примеры таких приложений? Если closed-source, то хотя бы названия.

Пример таких приложений — Centra, WebEx и т.д., мы делаем аналог, который на одном железе позволит хостить больше всей этой ерунды.


R>С транзакциями тут большие проблемы. Транзакций в общем понимании (ACID) тут не получится.
R>Например если взять транзакцию на чтение. Допустим поток читает 2 списка. Другой поток (который выполняет транзакцию на запись) одновременно хочет "транзакционно" переместить элемент из одного списка во второй. При такой схеме может получится, что первый поток либо не увидит элемент ни в одном списке, либо увидит сразу в двух. Что, безусловно, противоречит определению ACID транзакции.

Могу повторить, как делаются транзакции программно у нас. Есть список сущностей, над которыми надо провести транзакцию. Этот список предварительно сортируется по неизменяемому ключу, затем последовательно сущности блокируются, после этого производится изменение или чтение, и сущности разблокируются в обратном порядке. Таким образом удаётся избежать дедлоков при намерениях разных транзакций захватить произвольное кол-во сущностей.


R>Тут можно говорить только о транзакционности на уровне отдельных объектов, которая с т.з. бизнес-логики имеет мало смысла.

Нет, транзакции как раз нужны для атомарного выполнения множества операций.

Здравствуйте, vdimas, Вы писали:

R>>С транзакциями тут большие проблемы. Транзакций в общем понимании (ACID) тут не получится.
R>>Например если взять транзакцию на чтение. Допустим поток читает 2 списка. Другой поток (который выполняет транзакцию на запись) одновременно хочет "транзакционно" переместить элемент из одного списка во второй. При такой схеме может получится, что первый поток либо не увидит элемент ни в одном списке, либо увидит сразу в двух. Что, безусловно, противоречит определению ACID транзакции.

V>Могу повторить, как делаются транзакции программно у нас. Есть список сущностей, над которыми надо провести транзакцию. Этот список предварительно сортируется по неизменяемому ключу, затем последовательно сущности блокируются, после этого производится изменение или чтение, и сущности разблокируются в обратном порядке. Таким образом удаётся избежать дедлоков при намерениях разных транзакций захватить произвольное кол-во сущностей.

Это плохо сочетается с тезисом о том, доступ на чтение — бесплатный, без атомарных операций и барьеров памяти. Заблокировать ряд мьютексов объектов — это атнюдь не без барьеров памяти.

Здравствуйте, remark, Вы писали:
R>С HTM (Hardware Transactional Memory) ситуация получше. Проездов по памяти нет, грязных чтений нет. Производительность вроде лучше, чем у мьютексов... по крайней мере на *некоторых* тестах.
Performance pathologies in hardware transactional memory:

None of the systems performs best on all of our benchmarks. We identify seven performance pathologies-interactions between workload and system that degrade performance-as the root cause of many performance differences: FriendlyFire, StarvingWriter, SerializedCommit, FutileStall, StarvingElder, RestartConvoy, and DuelingUpgrades.

Доступа у меня к статье нет, но, похоже, не всё так очевидно.

Здравствуйте, Andrei N.Sobchuck, Вы писали:

ANS>Здравствуйте, remark, Вы писали:
R>>С HTM (Hardware Transactional Memory) ситуация получше. Проездов по памяти нет, грязных чтений нет. Производительность вроде лучше, чем у мьютексов... по крайней мере на *некоторых* тестах.
ANS>Performance pathologies in hardware transactional memory:

ANS>

None of the systems performs best on all of our benchmarks. We identify seven performance pathologies-interactions between workload and system that degrade performance-as the root cause of many performance differences: FriendlyFire, StarvingWriter, SerializedCommit, FutileStall, StarvingElder, RestartConvoy, and DuelingUpgrades.

ANS>Доступа у меня к статье нет, но, похоже, не всё так очевидно.


Да вот же она:
http://www.cs.wisc.edu/multifacet/papers/isca07_pathologies.pdf

Ситуация получше, чем с STM.
А с концепцией TM, с как таковой, связан ряд врожденных проблем.
Т.е. вот этот их вывод видится достаточно симнительным:

The insight provided
by these pathologies motivated four enhanced systems that often significantly reduce transactional memory overhead. Importantly,
by avoiding transaction pathologies, each enhanced system performs well across our suite of benchmarks.

Надо будет прочитать.

Здравствуйте, vdimas, Вы писали:

V>>>Лочить линейку кеша надо для защиты от доступа другого ядра/проца.
WH>>Ага. Для двух и более ядер надо лочить.
V>Ес-но.
И чем тогда нам поможет HTM?

WH>>Ну вот локи и переупорядочат.
WH>>Тем более что нафига двум потоком писать в одну линейку памяти если они не занимаются пересылкой данных друг другу не ясно.
V>Не в одну, а в соседние
Тогда вобще проблем нет.
Линейки кеша лочатся независимо.

V>(я же упомянул обсчёт матриц).
Никто так мелко его распаралеливать не будет.
Это просто не имеет смысла.

V>Не уверен, что внутри одного многоядерного проца другие потоки задерживаются при блокировке линейки кеша в случае отсутствия кофликтов доступа к одной линейке. Всё-таки менеджер памяти — это железка, и задерживать доступ она вполне может позволить себе только при наличии конфликтов.
Ага. Если нет конфликтов то у локов не будет никаких проблем.
А если есть то никакой HTM нам не поможет ибо он всеравно все лочить будет.

Короче как не крути, а HTM просто физически не может быть лучше локов.
Ибо HTM всеравно превращается в локи в случае конфликтов.

Здравствуйте, WolfHound, Вы писали:


V>>>>Лочить линейку кеша надо для защиты от доступа другого ядра/проца.
WH>>>Ага. Для двух и более ядер надо лочить.
V>>Ес-но.
WH>И чем тогда нам поможет HTM?

Тем, что данные лочатся лишь однократно, что шедуллер учитывает "транзакции" при составлении очереди команд на обработку. Ведь interlocked exchange — это не достаточно для блокировки, потом надо делать ветвление, и смотреть, заблокированны мы или нет, потом опять interlocked exchange для освобождения. А тут — одной командой.

WH>Короче как не крути, а HTM просто физически не может быть лучше локов.
WH>Ибо HTM всеравно превращается в локи в случае конфликтов.

Лучше по кол-ву операций блокирования, + переупорядочивание для предварительного избежания локов.

Здравствуйте, remark, Вы писали:


R>Это плохо сочетается с тезисом о том, доступ на чтение — бесплатный, без атомарных операций и барьеров памяти. Заблокировать ряд мьютексов объектов — это атнюдь не без барьеров памяти.

Блокируются обычно не экземпляры, а их контейнеры. Опять же, транзакционные потребности на чтение сразу большого кол-ва сущностей обычно редки, а получение доступа к одному экземпляру получается бесплатным. Для редактирования одного экземпляра создаётся копия, которая помещается на место старого, контейнер просто блокируется. При добавлении-удалении контейнер не только блокируется, но и пересоздаётся. Читатели одиночных экземпляров по прежнему читают всё бесплатно.

Здравствуйте, vdimas, Вы писали:

R>>Это плохо сочетается с тезисом о том, доступ на чтение — бесплатный, без атомарных операций и барьеров памяти. Заблокировать ряд мьютексов объектов — это атнюдь не без барьеров памяти.

V>Блокируются обычно не экземпляры, а их контейнеры. Опять же, транзакционные потребности на чтение сразу большого кол-ва сущностей обычно редки, а получение доступа к одному экземпляру получается бесплатным. Для редактирования одного экземпляра создаётся копия, которая помещается на место старого, контейнер просто блокируется. При добавлении-удалении контейнер не только блокируется, но и пересоздаётся. Читатели одиночных экземпляров по прежнему читают всё бесплатно.


А, ясно, значит я изначально не так понял. Я думал и транзакционность и бесплатный доступ на чтение.

з.ы. а если не секрет, на каком языке разрабатывается именно эта часть приложения? И под какие платформы работает? Только x86 или более портируемое?

Здравствуйте, WolfHound, Вы писали:

V>>Не уверен, что внутри одного многоядерного проца другие потоки задерживаются при блокировке линейки кеша в случае отсутствия кофликтов доступа к одной линейке. Всё-таки менеджер памяти — это железка, и задерживать доступ она вполне может позволить себе только при наличии конфликтов.

WH>Ага. Если нет конфликтов то у локов не будет никаких проблем.
WH>А если есть то никакой HTM нам не поможет ибо он всеравно все лочить будет.

WH>Короче как не крути, а HTM просто физически не может быть лучше локов.
WH>Ибо HTM всеравно превращается в локи в случае конфликтов.


Ну нет, не скажи. При использовании мьютексов, из-за очень жесткого API, реализация максимально прямолинейная, при использовании TM, из-за "гибкого" API, получается громадное множество (порядка сотни) вариантов реализации, и некоторые аспекты реализации, которые можно варьировать, коренным образом влияют на производительность и масштабируемость.

Здравствуйте, remark, Вы писали:

R>Ну нет, не скажи. При использовании мьютексов, из-за очень жесткого API, реализация максимально прямолинейная, при использовании TM, из-за "гибкого" API, получается громадное множество (порядка сотни) вариантов реализации, и некоторые аспекты реализации, которые можно варьировать, коренным образом влияют на производительность и масштабируемость.
Мъютексы и мои локи

Автор: WolfHound
Дата: 16.04.08

несколько отличаются...
И я не вижу где HTM будет лучше моих локов.

Здравствуйте, WolfHound, Вы писали:

R>>Ну нет, не скажи. При использовании мьютексов, из-за очень жесткого API, реализация максимально прямолинейная, при использовании TM, из-за "гибкого" API, получается громадное множество (порядка сотни) вариантов реализации, и некоторые аспекты реализации, которые можно варьировать, коренным образом влияют на производительность и масштабируемость.

WH>Мъютексы и мои локи

Автор: WolfHound
Дата: 16.04.08

несколько отличаются...
WH>И я не вижу где HTM будет лучше моих локов.

Основное отличие в том, что с помощью мьютексов и TM можно предоставлять высокоуровневый API:

mutex.lock();
моя_произвольная_бизнес_логика();
mutex.unlock();

htm_trx_begin();
моя_почти_произвольная_бизнес_логика();
htm_trx_commit();

А с помощью твоих локов — нет. Они сродни InterlockedCompareExchange() — хороша, да только большинству разработчиков и в большинстве ситуаций — никакой пользы.

Этим я не говорю, что твои локи плохи, я говорю, что сравнивать их с TM бессмысленно. Учитывая, что они на более низком уровне, не удивительно, что они могут предоставлять большую производительность.

Здравствуйте, remark, Вы писали:

R>

R>htm_trx_begin();
R>моя_почти_произвольная_бизнес_логика();
R>htm_trx_commit();
R>

моя_почти_произвольная_бизнес_логика очень сильно сказано.
Транзакция ограничена 4мя машинными словами.
Сомневаюсь что это колличество когда либо будет заметно больше 10.
Иначе это уже будет оракл в железе.

R>А с помощью твоих локов — нет. Они сродни InterlockedCompareExchange() — хороша, да только большинству разработчиков и в большинстве ситуаций — никакой пользы.
Разработчики получат более высокоуровневые механизмы.

R>Этим я не говорю, что твои локи плохи, я говорю, что сравнивать их с TM бессмысленно. Учитывая, что они на более низком уровне, не удивительно, что они могут предоставлять большую производительность.
Фигня в том что по факту они на том же уровне. Только без всякого кучерявого булщита который не дает ничего кроме мутной семантики и не нужного усложнения.

Здравствуйте, WolfHound, Вы писали:

WH>Комманда lock N, Rx, Ry
WH>Лочит одну или 2 линейки кеша (в которые попадают адреса из регистров Rx и Ry) на время выполнения следующих N (скажем до 16 комманд).
WH>Под локом можно обращаться только к залоченным частям памяти и делать только переходы вперед (никаких циклов под локом) и ессно никаких локов под локом.
WH>Если в одной линейке кеша есть несколько ячеек памяти которые нас интересуют то достаточно указать адрес одной из них но обращаться можно ко всем ибо всеравно вся линейка кеша залочена.
WH>Захвативший лок поток на время выполнения лока получает высший приоритет (ибо лок нужно отпустить как можно быстрее).
WH>Одновременно может выполняться только один лок на одном ядре.


Я так понимаю, что ты хочешь запрещать прерывания на время удержания lock. Правильно?
Будет не очень приятно, если в это время будут происходить промахи в L1-I кэше... таким образом мы можем запретить прерывания на тысячи тактов... Да и дедлок можно словить. Причём такой дедлок будет означать, что N процессоров выводятся из работы системы до следующей перезагрузки. Ну если сами процессоры ещё можно будет как-то реанимировать, то процессы точно придётся мочить в сортире.

Мне кажется более реалистичной идея "fixed size" HTM:
trx_begin failure_address, read_write_set, read_write_mask
trx_commit

trx_begin — начинает транзакцию, failure_address — адрес куда перейти в случае ошибки при выполнении транзакции, read_write_set — указатель на область памяти, где лежит 8 указателей на память, которую надо добавить в read_set или write_set (не используемые указатели отмечаем нулями), read_write_mask — битовая маска, указывающая куда надо добавлять адрес — в read_set или write_set.
trx_commit — коммитит транзакцию

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

Здравствуйте, WolfHound, Вы писали:

R>>

R>>htm_trx_begin();
R>>моя_почти_произвольная_бизнес_логика();
R>>htm_trx_commit();
R>>

WH>моя_почти_произвольная_бизнес_логика очень сильно сказано.
WH>Транзакция ограничена 4мя машинными словами.
WH>Сомневаюсь что это колличество когда либо будет заметно больше 10.
WH>Иначе это уже будет оракл в железе.

4 слова на что? На код? На readset? На writeset? Или на сумму?

R>>А с помощью твоих локов — нет. Они сродни InterlockedCompareExchange() — хороша, да только большинству разработчиков и в большинстве ситуаций — никакой пользы.
WH>Разработчики получат более высокоуровневые механизмы.

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

R>>Этим я не говорю, что твои локи плохи, я говорю, что сравнивать их с TM бессмысленно. Учитывая, что они на более низком уровне, не удивительно, что они могут предоставлять большую производительность.
WH>Фигня в том что по факту они на том же уровне. Только без всякого кучерявого булщита который не дает ничего кроме мутной семантики и не нужного усложнения.

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

Здравствуйте, remark, Вы писали:

R>Я так понимаю, что ты хочешь запрещать прерывания на время удержания lock. Правильно?
В том потоке где лок да.
Но у нас много потоков на одном ядре...
Да и ядер несколько.

R>Будет не очень приятно, если в это время будут происходить промахи в L1-I кэше...
В том потоке где случился лок во время лока никаких промохов не может быть в принципе.
Ибо процессор подтянет в L1 и в L1-I все что нужно.
А промохи в других потоках нас не волнуют.

R>таким образом мы можем запретить прерывания на тысячи тактов... Да и дедлок можно словить. Причём такой дедлок будет означать, что N процессоров выводятся из работы системы до следующей перезагрузки. Ну если сами процессоры ещё можно будет как-то реанимировать, то процессы точно придётся мочить в сортире.
С чего бы?

Короче ИМХО проблем будет не больше чем с префиксом lock в x86'х процессорах.

Здравствуйте, WolfHound, Вы писали:

R>>Я так понимаю, что ты хочешь запрещать прерывания на время удержания lock. Правильно?
WH>В том потоке где лок да.
WH>Но у нас много потоков на одном ядре...
WH>Да и ядер несколько.

Это что-то меняет в данном контексте?


R>>Будет не очень приятно, если в это время будут происходить промахи в L1-I кэше...
WH>В том потоке где случился лок во время лока никаких промохов не может быть в принципе.
WH>Ибо процессор подтянет в L1 и в L1-I все что нужно.
WH>А промохи в других потоках нас не волнуют.

Как он подтянет инструкции, на которые мы хотим выполнить вычисляемый переход? За 16 инструкций можно успеть "поскакать" по 16-ти различным страницам с кодом. Да, кстати, если страничное прерывание, то предется держать лок 10 мс.


R>>таким образом мы можем запретить прерывания на тысячи тактов... Да и дедлок можно словить. Причём такой дедлок будет означать, что N процессоров выводятся из работы системы до следующей перезагрузки. Ну если сами процессоры ещё можно будет как-то реанимировать, то процессы точно придётся мочить в сортире.
WH>С чего бы?

Что именно?