Беззамочные алгоритмы: ненастойчивый кэш

Original author: Raymond Chen
  • Translation
(Тот факт, что русского перевода понятию «lock-free» в литературе ещё не устоялось, — нисколько меня не убеждает, что такого перевода не должно быть.)

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

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;

 // если значение параметра не изменилось с прошлого раза,
 // воспользуемся готовым результатом
 if (n == nLast) return fLastIsPrime;

 // вычислим и запомним новый результат
 nLast = n;
 fLastIsPrime = slow_IsPrime(n);
 return fLastIsPrime;
}

Само собой, этот код потоконебезопасен: если один поток находится внутри вызова slow_IsPrime(), то другой поток, вызвавший IsPrime(), застанет значения переменных nLast и fLastIsPrime несоответствующими одно другому.

Простое решение — заключить код в критическую секцию; но простота идёт в ущерб производительности: если, скажем, nLast = 5, fLastIsPrime = TRUE, и два потока одновременно вызывают IsPrime(5), то совершенно ни к чему им выстраиваться в очередь: ничего не мешает им одновременно воспользоваться кэшированным значением.

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

#define IsLocked(l) ((l) & 1)

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;
 static LONG lCounter = 0;

 // попытаемся взять значение из кэша
 LONG lCounterStart = InterlockedReadAcquire(&lCounter, -1);
 if (!IsLocked(lCounterStart) && n == nLast) {
  BOOL fResult = fLastIsPrime;
  // никто не трогал кэш за нашей спиной?
  if (InterlockedReadRelease(&lCounter, -1) == lCounterStart)
   return fResult;
 }

 // либо чтение из кэша не удалось, либо значение не подошло:
 // вычисляем обычным способом
 BOOL fIsPrime = slow_IsPrime(n);

 // попытаемся сохранить значение в кэше
 lCounterStart = lCounter;
 if (!IsLocked(lCounterStart) &&
     InterlockedCompareExchangeAcquire(&lCounter,
              lCounterStart+1, lCounterStart) == lCounterStart) {
  nLast = n;
  fLastIsPrime = fIsPrime;
  InterlockedCompareExchangeRelease(&lCounter,
              lCounterStart+2, lCounterStart+1);
 }
 return fIsPrime;
}

Младший бит в lCounter означает, что кэш «заблокирован» на время записи; остальные биты хранят номер версии. Такая организация позволяет объединить снятие блокировки и обновление номера версии в одну простую операцию.

Функция состоит из двух частей: чтение из кэша и запись в кэш. При чтении из кэша сначала мы читаем lCounter операцией Acquire, чтобы убедиться, что прочитанные значения nLast и fLastIsPrime были записаны прежде, чем номер версии. Если, судя по прочитанному номеру, кэш не заблокирован, то мы читаем из него последние значения параметра и результата. Если результат подходит, мы берём его; но прежде нужно убедиться, что номер версии не изменился за то время, пока мы читали из кэша. Если он изменился, то, возможно, прочитанные нами значения не соответствуют друг другу, так что «подходящий» результат на самом деле недостоверен.

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

При записи в кэш мы не только проверяем, что кэш не заблокирован, но одновременно с этим ещё и блокируем его сами, устанавливая младший бит. (Если окажется, что кэш был заблокирован, — тоже не страшно: никто не будет в обиде, если не станем записывать в него вычисленный результат. Цель ведь сэкономить время, а не любой ценой избежать повторного вычисления.) Заблокировав кэш, мы обновляем в нём данные, и затем одной операцией InterlockedCompareExchangeRelease снимаем блокировку и увеличиваем номер версии. Операция должна быть Release, чтобы изменения данных записались в память раньше снятия блокировки.

Мы пользуемся тем, что успех операций над кэшем необязателен: и при чтении, и при записи, если кэш окажется заблокирован, то, по идее, лучше отказаться от преимуществ кэширования — «К чёрту всё! Сделаю всё сам!» — чем выстраиваться в очередь за право доступа к кэшу. Ценой избыточных вычислений мы избегаем проблем навроде инверсии приоритетов (когда высокоприоритетный поток ожидает освобождения замка, занятого низкоприоритетным потоком).

Важно обратить внимание, что получившаяся система не вполне беззамочна: используя беззамочные алгоритмы, мы фактически реализовали эффективный замок. Если «застрянет» поток, заблокировавший кэш для записи, — все прочие потоки, хотя и продолжат выполняться, кэшем пользоваться уже не смогут.

Аналогичную систему можно реализовать и при помощи TryEnterCriticalSection:

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;
 BOOL fHaveAnswer = FALSE;
 BOOL fIsPrime;

 // попытаемся взять значение из кэша
 if (TryEnterCriticalSection(&g_cs)) {
  if (n == nLast) {
   fHaveAnswer = TRUE;
   fIsPrime = fLastIsPrime;
  }
  LeaveCriticalSection(&g_cs);
 }
 if (fHaveAnswer) return fIsPrime;

 // либо критическая секция занята, либо значение не подошло:
 // вычисляем обычным способом
 fIsPrime = slow_IsPrime(n);

 // попытаемся сохранить значение в кэше
 if (TryEnterCriticalSection(&g_cs)) {
  nLast = n;
  fLastIsPrime = fIsPrime;
  LeaveCriticalSection(&g_cs);
 }
 return fIsPrime;
}

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

Начиная с Windows 7, мы можем также задействовать slim reader-writer locks:

BOOL IsPrime(int n)
{
 static int nLast = 1;
 static BOOL fLastIsPrime = FALSE;
 BOOL fHaveAnswer = FALSE;
 BOOL fIsPrime;

 // попытаемся взять значение из кэша
 if (TryAcquireSRWLockShared(&g_lock)) {
  if (n == nLast) {
   fHaveAnswer = TRUE;
   fIsPrime = fLastIsPrime;
  }
  ReleaseSRWLockShared(&g_lock);
 }
 if (fHaveAnswer) return fIsPrime;

 // либо кэш заблокирован для записи, либо значение не подошло:
 // вычисляем обычным способом
 fIsPrime = slow_IsPrime(n);

 // попытаемся сохранить значение в кэше
 if (TryAcquireSRWLockExclusive(&g_lock)) {
  nLast = n;
  fLastIsPrime = fIsPrime;
  LeaveSRWLockExclusive(&g_lock);
 }
 return fIsPrime;
}

Но и в этой реализации потоки, читающие из кэша, могут помешать записи в кэш; тогда как в нашей первой «беззамочной по духу» реализации только одновременные попытки записи приводят к конфликту. Если IsPrime() вызывается несколько раз с одним значением (например, 13), и затем много раз подряд с другим значением (например, 17) — то напор потоков, проверяющих, не закэширован ли результат для 17, просто не пропустит ни один поток действительно закэшировать результат для 17! Получается, если нагрузка на кэш очень высокая (а собственно, именно поэтому мы его идобавили!) — тогда реализация на основе slim reader-writer locks превращает кэш в почти бесполезный.

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 40

  • UFO just landed and posted this here
      • UFO just landed and posted this here
          0
          Не всё дело в блокировке потоков: ближе к концу поста разбирается реализация на основе неблокирующей TryEnterCriticalSection, и сравнивается с беззамочной.
          • UFO just landed and posted this here
              +1
              Вот тоже глаз режет «беззамочный». Все таки английские слова так в лоб переводить не годится, можно дойти до весьма забавных неувязок.

              Как вариант, могу предложить «безмьютексовый». Сам термин «мьютекс» вполне себе устоявшийся, представляет из себя примитив для захвата ресурса.
                –1
                А я встречал «не реентерабельный»
          +4
          В данном случае подходит прилагательное «безблокировочный». Класс неблокирующих алгоритмов — гораздо шире, чем нужно, действительно. Но производное слова «замок» не подходит, т.к. исторически в соответствующем значении использовалось слово «блокировка» (в т.ч. на ЖД, до развития ВТ).
            0
            Есть два устоявшихся термина:
            lock-free — это алгоритм, который гарантированно не ведёт к deadlock.
            wait-free — это алгоритм, не требующий ни от одного потока простоя в ожидании ресурса.

            Изобретение своих словянофильских терминов ничего кроме бардака и проблем с поиском не приносит. В частности из вашего коментария (по сслыке) я понял, что ресь идёт о wait-free алгоритме. Разбираться в том где у вас косяк: в объяснении или в голове мне лень, думаю любому здравомыслящему человеку тоже.
              +1
              Разбираться в каком месте косяк у Вас мне тоже лень. Поэтому славянофильские определения с переводом:

              Без ожиданий (wait-free)
              Самая строгая гарантия прогресса. Алгоритм работает без ожиданий, если каждая операция выполняется за детерминированное количество шагов, независящее от других потоков.
              — Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom. An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.
              Без блокировок (lock-free)
              Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например поток, выполняющий операцию сравнение с обменом в цикле теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, т.е. система в целом совершает прогресс.
              — Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress (for some sensible definition of progress). All wait-free algorithms are lock-free.
              Без препятствий (obstruction-free)
              Самая слабая из гарантий. Поток совершает прогресс, если не встречает препятствий со стороны других потоков. Алгоритм работает без препятствий, если поток, запущенный в любой момент (при условии, что выполнение всех препятствующих потоков приостановлено) завершит свою работу за детерминированное количество шагов.
              — Obstruction-freedom is possibly the weakest natural non-blocking progress guarantee. An algorithm is obstruction-free if at any point, a single thread executed in isolation (i.e., with all obstructing threads suspended) for a bounded number of steps will complete its operation. All lock-free algorithms are obstruction-free.

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

                То есть «неблокирующие» и «без ожиданий» — это синонимы в великом и могучем?

                Мне кажется или «независящее от других потоков» не гарантируется для wait-free? (вот та-жа STM-транзакция не блокирует, но время на выполнение явно зависит от других потоков).
          –2
          мне чаще встречается термин «lockless»
          • UFO just landed and posted this here
              0
              Начиная с Windows 7, мы можем также задействовать slim reader-writer locks

              Вообще-то, начиная с Windows Vista: InitializeSRWLock
                +1
                В Vista они блокирующие; TryAcquireSRWLockXxx появились в Windows 7
                +1
                Важно обратить внимание, что получившаяся система не вполне беззамочна: используя беззамочные алгоритмы, мы фактически реализовали эффективный замок. Если «застрянет» поток, заблокировавший кэш для записи, — все прочие потоки, хотя и продолжат выполняться, кэшем пользоваться уже не смогут.

                Как раз именно потому, что другие потоки будут выполняться, данный алгоритм не только lock-free, но и wait-free. И не важно, что кэшем никто не может воспользоваться, это с характеристикой алгоритма никак не связано.
                  +1
                  Предположим, анализ производительности вашего приложения выявил, что существенная часть процессорного времени тратится в некой вычислительной функции, и более того, эта функция многократно вызывается с одними и теми же параметрами — выполняя одинаковые вычисления вновь и вновь. Напрашивается простая оптимизация — кэш из одной записи, в котором бы хранились исходные данные и результат последнего вычисления.


                  Как бы решить эту проблему в системном приложении, работающем на микроядре L4?

                  Можно вывести вычислительную функцию в отдельный поток:

                  void CalculatingThread(void)
                  {
                     L4_ThreadId_t  tid;
                     L4_Msg_t       msg;
                     L4_MsgTag_t    tag;
                     BOOL           result;
                     int            n;
                  
                     while( true )
                     {
                         tag = L4_Wait( &tid );         // ждём сообщение
                         L4_Store( tag, &msg );  
                         n = (int) L4_Get( &msg, 0 );   // берём первый аргумент сообщения
                  
                         result = IsPrime( n );         // вызываем потоко-небезопасную функцию
                  
                         L4_Clear(&msg);
                         L4_Append( &msg, (L4_Word_t) n );  // формируем ответ
                         L4_Load( &msg );
                         L4_Send( tid );                    // посылаем ответ
                     }
                  }
                  


                  Обращаемся к этому потоку через L4_Call — синхронный вызов IPC.

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

                  Кстати, мой код делает не совсем то, что Вы описали — он «замыкает» не только IsPrime, но и slow_IsPrime. С одной стороны это не оптимально, зато гарантирует потоко-безопасность slow_IsPrime. В случае же, если значение уже в кэше, два IPC в одном адресном пространстве будут ничуть не тяжелее, чем работа с критическими секциями. Хотя, конечно, сравнивать не совсем корректно — платформы разные.

                  Я ни чуть не преуменьшаю ценность Вашей статьи — она познавательна и имеет практическую ценность, но у меня есть своё представление о lock-free системах, которые построены на несколько других принципах — реализуют асинхронные сообщения на основе синхронных сообщений и конечного автомата.

                    0
                    OMG! У меня ошибка в коде, вот исправление:

                       L4_Append( &msg, (L4_Word_t) result );  // формируем ответ
                    

                    Простите.
                      +1
                      Разве ваш код не будет повторять вычисления при каждом сообщении, даже если параметр не менялся?
                        0
                        Не будет, потому что он вызывает Ваш первый пример BOOL IsPrime(int n) (который ещё без элементов синхронизации).
                    +2
                    Эх. Но у слова lock вполне есть официальный перевод — блокировка. В данном контексте замок — это не верная метафора. Никто же никого нигде не запирает. Происходит именно блокировка процессов при доступе в критические секции. И это устоявшийся перевод термина lock (как бы, Танненбаума можно почитать, да и любую книжку по ОС на русском языке).

                    Поэтому, у lock-free есть устоявшийся перевод: свободный от блокировок. Не, я понимаю, что изобретать велосипеды нужно, но не такие же корявые…
                      0
                      Моя единственная претензия к слову «блокировка» — что оно похоже на название действия, а не объекта. Тем не менее, в продолжении серии воспользуюсь именно вариантом «безблокировочный».

                      А так, для слова «thread» тоже есть устоявшийся перевод «поток», но это же вам не мешает сообщением ниже использовать «однонитевой подход» :)
                        +1
                        Ну… ООП вообще мало дружен с параллельным программированием, потому что там надо мыслить именно действиями, а не объектами с состояниями. Вот, кстати, преимущество русского языка, он больше на действия ориентирован, а не на объекты.

                        С потоками не всё так просто. У англичан есть три термина, которые используются для описания систем: flow, stream, thread. И всё можно перевести как поток, но смысловой оттенок у этих терминов разный… Поэтому постепенно переходят на терминологию поток данных и нить управления. Thread от stream тем и отличается, что это такой тоненький ручеёк, как в душе, как нить. И вполне есть устойчивые выражения: нить Ариадны — Ariadne's thread, нить рассуждений — thread of thoughts. То есть, первоначальный термин был неудачным.

                        Блокировки, кстати, это тоже не исходный перевод. Сначала в книгах это называлось захватами. И это даже близко к изначальному смыслу на английском, потому что раньше, когда поддержки в ядрах OS не было, процессы именно захватывали ресурсы, выставляя всякие флажки по специальным алгоритмам. Отсюда и термин race-condition, когда процессы соревнуются за то, кто первый захватит шину для записи.

                        Но сейчас OS занимается блокированием — снятием с исполнения — нитей при синхронизации, поэтому стали говорить о блокировках. Объектов же, при помощи которых достигается блокирование — уйма. Есть семафоры, мьютексы, очереди сообщений, события… Так что, тут главное — действие, а не объект.
                          0
                          «Захват» действительно интересный вариант…

                          Ну уж слишком неестественно звучит, «к видам блокировок относятся семафоры, мутексы, критические секции и т.п.»
                          Тем более, что не любой объект синхронизации — замок/захват, хотя все эти объекты способны блокировать нить.

                          Тенденцию перехода на «нить» для «thread», по правде говоря, совершенно не наблюдаю, хотя и сам душою за «нить». А то иначе как переводить «fiber» — «струйка»?
                            0
                            В быту:
                            Process — процесс.
                            Thread — нить.
                            Fiber — волокно (более мелкая нить, одиночная из которых сделана thread, кому любопытно: посмотрите катушку ниток: нити состоят из волокон).
                            Lock — 1) пучёк, 2) замок, запирать.
                            Picklock — взломщик (замков).
                            Default — неплатёж, неявка.

                            В программировании:
                            Process — процесс.
                            Thread — поток.
                            Fiber — нить.
                            Cracker — взломщик (програм)
                            Lock — блокировка, блокировать.
                            Default — значение по-умолчанию.

                            Вот может удивляет какое внимание уделяется слову, ну чего прикапываются? Но для меня ситуация ясна, это вовсе не случайно. Большинству не нравится слово „беззамочные“. И на то есть две причины:
                            1) слово неблагозвучное получилось, ладно бы, но
                            2) оно по смыслу неправильное, совсем из другой области, фактически неверный перевод

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

                            И вот переводить lock-free как беззамочный — это всё-равно что переводить default, как неплатёжный.

                            И потому большинству ну просто подсознательно бьёт слово „беззамочный“.

                            Ну, а чтобы совсем рассмешить: lock — это ещё и колдун.

                            И вдогонку: а не глагол ли там английский lock?
                      0
                      Вообще, странный подход пропагандирует товарищ Чен.

                      Во-первых, у него производительность умрёт от false-sharing линий кэша с данными (умрёт этак раз в 10). И вот предложенный однонитевой подход может быть даже эффективнее: нет накладных расходов на false-sharing и нити не тратят больше времени, чем на один вызов IsPrime.

                      Во-вторых, Interlocked — это функции с блокировками, они потому и называются Interlocked. То, что он описывает, называется wait-free синхронизация, а не lock-free. Потому что, на аппаратном уровне обеспечение lock'а, например, при выполнении cmpxchg требует много времени, при чём рост тут линейный, в зависимости от количества ядер.

                      В-третьих, функции семейства reader-writer lock тут были бы более предпочтительны, просто Чен использует их каким-то странным образом. Если бы обновляющий данные Exclusive-захват был бы без Try, то писатель бы не был бы вытолкнут потоком читателей. Ну. И тут хотя бы гарантировалось, что последнее значение будет закэшировано. А ещё при таком подходе можно было бы сделать нормальный B-tree кэш на несколько значений.

                      В его же решении, кэшироваться будет чёрт знает. Плюс будет куча накладных раскходов в случае не успехов, которые не будут редкими.
                        0
                        Эээ? Парсер — глюк? Предложения:

                        «кэшироваться будет, чёрт знает что» и «предложенный alman» были написаны верно… Хм…
                          0
                          > Во-вторых, Interlocked — это функции с блокировками, они потому и называются Interlocked
                          поток-то не блокируется, блокируется только доступ к переменной
                            0
                            А какая разница, по какой причине код потока перестаёт выполнятся? Либо его ядро скинуло в состояние BLOCKED, либо работа всего процессора приостановлена на десятки тысяч тактов, потому что оно ждёт своей очереди сделать CompareExchange? Да ещё при этом ограничивается работа с памятью тех процессоров, которые не выполняют нитей, связанных с этой самой Interlocked синхронизацией. А на некоторых моделях такие Interlocked операции вообще означают остановку работы с памятью всех ядер. В итоге, за такой псевдо lock-free приходится платить длительными простоями системы. SUN как-то считала, сколько это стоит, и оказалось, что 30% процессорного времени на 32-ядерной машине.

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

                            Я вот сомневаюсь вообще в основной мысли Чена: давайте избавимся от системных вызовов синхронизации с целью достижения производительности, но при этом заменим их на интенсивный поток Interlocked-операций. Это, как мне кажется, очень не правильный подход, потому что задержки из одного места (программного) переносятся на аппаратный уровень, где соревнования за ресурсы распространяются уже и на доступ к шинам данных, простаивать может начать и I/O, и другие процессоры. Правильнее в таких ситуациях пересматривать сам алгоритм, чтобы снизить необходимость в синхронизациях.

                            Вот в данном случае: а что мешает использовать Thread Local Storage для того, чтобы сделать по кэшу на каждую нить? Они же всё-равно в худшем случае в Ченовском алгоритме будут IsPrime считать каждая для себя. Ну и пусть посчитают по одному разу — не страшно. Зато потом конфликтов будет на порядки меньше, и блокировок в любом виде не понадобится.
                              0
                              Я не правильно сформулировал своё высказывание.
                              Имелось в виду то, что Interlocked-функции крайне быстры, в отличии от системных вызовов синхронизующих API, поэтому простой потока минимален.
                              Системные вызовы стоят десятки тысяч тактов, в большинстве случаев Interlocked-функции использовать эффективнее.
                              Вот вы приводите пример Sun, но Чен прежде всего ориентируется на Win-платформу с соответственно x86/x64 камушки.
                              А TLS да, рулит, тем более есть и на *nix, и на windows.
                                0
                                Так у x86/x64 камушков ядер становится всё больше и больше, соответственно Interlocked-функции всё дороже и дороже начинают стоить. Поэтому, imho, сомнительное решение.
                                  0
                                  не обязательно лочить шину, для реализации выбранного примера достаточно инструкций xchg и mov, которые по-дефолту являются атомарными (mov насколько я помню требует выравнивания, но это не проблема, конечно).
                                    0
                                    Не достаточно. Там важно, что cmpxchg используется (чтобы +1 менять на +2 корректно). А cmpxchg лочит шину, не полностью, там есть свои оптимизации в x86. Но всё же, это суровый lock.
                                0
                                Я вот сомневаюсь вообще в основной мысли Чена: давайте избавимся от системных вызовов синхронизации с целью достижения производительности, но при этом заменим их на интенсивный поток Interlocked-операций.
                                Вы неверно его поняли. Его основная мысль — «посмотрите, какая интересная штука, какие интересные у неё характеристики; может быть, вам однажды пригодится»

                                Вот в данном случае: а что мешает использовать Thread Local Storage для того, чтобы сделать по кэшу на каждую нить?
                                Чен на этот вопрос ответил сам: «Если вам достаточно одного кэша на поток, то TLS подходит отлично. А вдруг вам нужен отдельный кэш в каждом объекте? И это не высосанная из пальца ситуация. Например, „пусть у каждой транзакции будет свой собственный кэш SID, потому что её права скорее всего не изменяются; но у различных транзакций, скорее всего, будут различные SID-ы“.»
                                  0
                                  Ох… Вот этот рассказ про SID'ы и есть высосанная из пальца ситуация. Никогда не видел, чтобы так делали. Если предусматривать возможность обработки объекта разными нитями, то там на каждый чих придётся делать синхронизацию. Это всю производительность убьёт.

                                  Тут гораздо выгоднее обрабатывать определённые объёмы объектов одной нитью, и делить такую обработку через пул нитей и очереди задач.

                                  Конечно, про Interlocked нужно знать, и иногда приходится их использовать, особенно при создании-удалении объектов, когда надо ссылки считать, а критической секцией нельзя воспользоваться, потому что она внутри объекта, и её тоже надо удалить или создать при конструировании. Это, конечно, весьма актуально для Win, и COM-объектов, которые должны быть объектами в себе.

                                  Но лучше проектировать приложение так, чтобы синхронизации были достаточно редкими, чтобы не страшно было использовать «тяжёлые» примитивы.
                                    0
                                    Если предусматривать возможность обработки объекта разными нитями, то там на каждый чих придётся делать синхронизацию. Это всю производительность убьёт.
                                    Речь, собственно, об обратном: одна нить (например, STA-апартмент) обрабатывает несколько объектов, и у каждого объекта свой собственный кэш.
                                      0
                                      Тут гораздо выгоднее обрабатывать определённые объёмы объектов одной нитью, и делить такую обработку через пул нитей и очереди задач.


                                      Вот вот. Но это не даёт автоматической гарантии повышения производительности. Всё зависит от реализации обработчика.

                                      <основная функция> ---> <сложный обработчик> ---> <ещё один уровень обработчика>
                                      


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

                                                          +---<-----------<------------<-----------<---------<-----------+
                                                          |                                                              ^
                                      <основная функция> ---> <сложный обработчик> ---> <ещё один уровень обработчика> --+
                                      


                                      Таким образом мы имеем одну точку входа в «сложном обработчике», куда попадают как запросы от верхнего уровня, так и ответы от вложенных обработчиков. Введём понятие «контекст», который будет передаваться по цепочке и на основе которого <сложный обработчик> производит диспетчеризацию между вызовами и ответами.

                                      Что в результате? Пока <основная функция> вошла в <сложный обработчик> а тот, в свою очередь, обратился к нижележащему обработчику, следующий пользовательский поток может вызвать <сложный обработчик> и (о чудо!) взять данные из кэша (если они там оказались). Т.е. блокировки (в общепринятом смысле) как бы и не случилось вообще. Если же данных в кэше не оказалось, то пойдёт ещё одно сообщение во вложенный обработчик.

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

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

                                      Таким образом мы отказались от традиционных элементов блокировки и перенесли их на уровень синхронных IPC, что на самом деле не так и уж плохо, поскольку в данном случае количество блокировок определяется лишь точками входа в обработчики и никак не зависит от количества операций с данными, которые необходимо защищать от совместного доступа.
                              +1
                              Да, а ещё меня вот что забавляет. В прошлом посте описывалось долго и упорно, как нужно правильно static-переменные инициализировать, а тут они инициируются весьма… эмс… вольно. И если брать этот код дословно, то ошибки обеспечены: что если некая нить решила обновить кэш при первом запуске, а в этот момент работает другая нить, которая тоже думает, что запуск первый. nLast и fLastPrime запросто могут оказаться рассогласованными.

                              В общем, как бы, то ли Чена специально посадили мозги программистам пудрить, то ли в Microsoft действительно так пишут программы… Ну. И это ещё один повод задуматься о качестве их системного софта.
                                0
                                Вот из-за таких вот комментаторов Чен предварил код к своему следующему посту комментарием:
                                // WARNING! IF YOU USE THIS CODE YOU ARE AN IDIOT - READ THE TEXT ABOVE
                                А в тексте поста — подобное разъяснение, что его код — иллюстрация объясняемых принципов, а не пример для подражания. И что если бы он постил в блоге код «промышленного качества», то никто бы не продрался сквозь второстепенную шелуху к той сути, ради которой код постится.
                                  0
                                  Ну тык… Если ему не нужны были такие комментарии, сразу бы и сделал эту надпись :) Ибо, не все ж такие умные. Некоторые займутся копи-пастом, вообще не думая.

                              Only users with full accounts can post comments. Log in, please.