На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишите свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: shadeofgray, JoeUser
  
> Атомарная операция с большими числами
    Если A > разрядности системы, то чтобы атомарно добавить к A значение B, вернув в качестве результата новое значение, обычно делается так (для 32 битов):
    ExpandedWrap disabled
      ADD(A, B) {
        DO {
          OLD = A
        } WHILE(InterlockedCompareExchange64(A, OLD+B, OLD) != OLD)
        RETURN OLD+B
      }
    Здесь InterlockedCompareExchange64 - функция, работающая с повышенной разрядностью (т.е. с 64 битами - сравнение A и OLD и запись в A значения OLD+B в случае совпадения, возвращает старое значение - инструкция cmpxchg8b).
    Вопрос: есть ли алгоритм, позволяющий реализовать всё это БЕЗ InterlockedCompareExchange64? Т.е. работая с числами только той же разрядности? :)
    Tell me would you kill to save a life?
    Tell me would you kill to prove you're right?
    Crash, crash, burn, let it all burn
    This hurricane's chasing us all underground...
      Ээ... InterlockedAdd нужно?
        А если нужно 64 разряда, может уже использовать имеющиеся библиотечные типы std::atomic_uint_fast64_t ну или вроде того.

        А если больше можно и синхронизацию добавить. Вроде где-то по скорости ты выиграешь с атомарными типами, а где-то нет.
          Цитата MBo @
          Ээ... InterlockedAdd нужно?
          InterlockedAdd64, которая не вызывает внутри себя InterlockedCompareExchange64 :)

          ter_nk_, можешь название функции скинуть, которая делает что-то вроде InterlockedAdd64 ?
          Мне надо исходник увидеть, что-то не нахожу...
          Tell me would you kill to save a life?
          Tell me would you kill to prove you're right?
          Crash, crash, burn, let it all burn
          This hurricane's chasing us all underground...
            http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gc...c-Builtins.html
            https://github.com/scalien/scaliendb/blob/m...eading/Atomic.h

            Такого алгоритма нет. Для интаниум такое возможно потому что они 64 битные. Для обычных Intel'ов только при использование 64 битных регистров - и то скорее всего компилятор их обернёт через префикс lock. А для старых систем только InterlockedCompareExchange64.
            Правильный обед должен состоять из 5 блюд приготовленных из 33 ингредиентов.
              Pavia, в этих исходниках только Interlocked-функции и использование __sync_fetch_and_add, исходников которой (я про последнюю) так и нет в итоге...
              Для 64 бит проблем нет, а вот для 32 что-нибудь бы найти. Наверняка что-то можно продумать такое... :)

              Добавлено
              Цитата ter_nk_ @
              А если больше можно и синхронизацию добавить. Вроде где-то по скорости ты выиграешь с атомарными типами, а где-то нет.
              Если ты про критические секции/спин-локи, то они неуниверсальны. В том плане, что другие потоки должны их тоже использовать. А хочется безусловные атомарные операции произвести.
              Tell me would you kill to save a life?
              Tell me would you kill to prove you're right?
              Crash, crash, burn, let it all burn
              This hurricane's chasing us all underground...
                Цитата Jin X @
                ter_nk_, можешь название функции скинуть, которая делает что-то вроде InterlockedAdd64 ?


                Функций?

                InterLocled не знаю, а атомарные типы, в одном месте объявил инициализировал переменную, а дальше библиотека тебе обеспечивает, что например ты в любом потоке делашь добавление, если тебе нужно my_var.fetch_add(value)

                и типа библиотека гарантирует что она делает эту операцию потокобезопасной.

                А второе что-то вроде того
                if(пришло время инкремента)
                {
                std::lock_guard<std::mutex> lock(my_mutex);
                my_var++
                }

                // здесь my_var освобождена

                Добавлено
                Цитата Jin X @
                Если ты про критические секции/спин-локи, то они неуниверсальны. В том плане, что другие потоки должны их тоже использовать. А хочется безусловные атомарные операции произвести.


                А что значит не универсальны. Тебе нужно быстродействие прямо чтоб ничего не потерять, так все равно на атомарных операциях потеряешь, как бы проблемы не вижу с "неуниверсальностью".
                  Критические секции (если брать именно виндовые) довольно "тяжёлые", а если не устанавливать SpinLockCount, то начинаются заморочки с Event'ом. Плюс нужно использовать переменную. Я не хочу сказать, что это прям проблема большая, но если можно сделать проще, почему бы не сделать? Скажем, InterlockedIncrement64 работает же через cmpxchg8b, а не через критические секции. Я не против cmpxchg8b, в принципе, просто мне интересен алгоритм работы без него. По идее, можно и с его помощью работать с более сложными данными (128 битами), если найти алгоритм...

                  А my_var.fetch_add(value) скорее всего через InterlockedCompareExchange64 (cmpxchg8b, короче) и работает...
                  Tell me would you kill to save a life?
                  Tell me would you kill to prove you're right?
                  Crash, crash, burn, let it all burn
                  This hurricane's chasing us all underground...
                  1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                  0 пользователей:


                  Рейтинг@Mail.ru
                  [ Script Execution time: 0,0889 ]   [ 14 queries used ]   [ Generated: 22.11.17, 22:13 GMT ]