Вопрос по синхронизации доступа к переменным
От: sidorov18 США  
Дата: 25.12.09 10:03
Оценка:
    LONG CreateUniqueID()
    {
        static LONG id = 0;

        return id++;
    }

Обеспечит ли такой метод уникальность id в многопоточном приложении?
т.е. может ли при двух вызовах CreateUniqueID вернуться одинаковый id

или нужно делать нечто подобное:
    LONG CreateUniqueID()
    {
        static volatile LONG id = 0;

        return InterlockedIncrement( &id );
    }
Re: Вопрос по синхронизации доступа к переменным
От: jazzer Россия Skype: enerjazzer
Дата: 25.12.09 10:06
Оценка: 2 (1) +1
Здравствуйте, sidorov18, Вы писали:


S>
S>    LONG CreateUniqueID()
S>    {
S>        static LONG id = 0;

S>        return id++;
S>    }
S>

S>Обеспечит ли такой метод уникальность id в многопоточном приложении?

нет

S>т.е. может ли при двух вызовах CreateUniqueID вернуться одинаковый id


S>или нужно делать нечто подобное:

S>
S>    LONG CreateUniqueID()
S>    {
S>        static volatile LONG id = 0;

S>        return InterlockedIncrement( &id );
S>    }
S>


нужно. И заодно нужно убедиться, что инициализация id нулем происходит "до всего", чтоб не было никаких обнуляющих действий в рантайме (по идее, она должна лежать в памяти, которая забита нулями сразу при старте приложения).
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re: Вопрос по синхронизации доступа к переменным
От: remark Россия http://www.1024cores.net/
Дата: 25.12.09 10:44
Оценка: 4 (2)
Здравствуйте, sidorov18, Вы писали:

S>или нужно делать нечто подобное:

S>
S>    LONG CreateUniqueID()
S>    {
S>        static volatile LONG id = 0;
S>        return InterlockedIncrement( &id );
S>    }
S>


Как уже сказал jazzer, делать надо так.
Добавлю, что если используется студия, то лучше использовать функцию _InterlockedIncrement(), которая определена в <intrin.h>. InterlockedIncrement() — это функция Win API, которая имеет С интерфейс и предназначена для использования всякими паскалями и др языками, которые могут использовать С библиотеки.
_InterlockedIncrement() же является интринсиком компилятора, соотв. при его использовании нет накладных расходов на вызов функции и манипуляции со стеком.

Если идентификаторы выделяются часто и не требуется "плотных" идентификаторов, то целесообразно рассмотреть вариант с локальными кэшами идентификаторов (то, что делают базы данных для сиквенсов), он существенно снизит конкуренцию на разделяемом счётчике:
long id = 0;

struct cache_t
{
  long id;
  long end;

  static long const bucket = 128;
};
__declspec(thread) cache_t cache;

long CreateUniqueID()
{
  cache_t* c = cache;
  if (c->id != c->end)
  {
    // local fast-path
    return c->id++;
  }
  return CreateUniqueIDSlow();
}

// slow-path
__noinline
long CreateUniqueIDSlow()
{
  cache_t* c = cache;
  c->id = InterlockedExchangeAdd(&id, cache::bucket);
  c->end = c->id + cache::bucket;
  return c->id++;
}




1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Вопрос по синхронизации доступа к переменным
От: Николай Ивченков  
Дата: 25.12.09 11:07
Оценка: 2 (1) +1
sidorov18:

S>или нужно делать нечто подобное:


volatile и инициализатор "= 0" можно убрать.
Re[2]: Вопрос по синхронизации доступа к переменным
От: Николай Ивченков  
Дата: 25.12.09 11:07
Оценка:
remark:

R>лучше использовать функцию _InterlockedIncrement(),


Экономия на спичках. Сколько раз будет вызвана эта функция-счётчик?
Re[2]: Вопрос по синхронизации доступа к переменным
От: Кодт Россия  
Дата: 25.12.09 11:09
Оценка: +1
Здравствуйте, jazzer, Вы писали:

J>нужно. И заодно нужно убедиться, что инициализация id нулем происходит "до всего", чтоб не было никаких обнуляющих действий в рантайме (по идее, она должна лежать в памяти, которая забита нулями сразу при старте приложения).


Имя этой идее — стандарт С++

6.7 Declaration statement

4.
The zero-initialization (8.5) of all local objects with static storage duration (3.7.1) is performed before any other initialization takes place.

A local object of POD type (3.9) with static storage duration initialized with constant-expressions is initialized before its block is first entered.
An implementation is permitted to perform early initialization of other local objects with static storage duration under the same conditions that an implementation is permitted to statically initialize an object with static storage duration in namespace scope (3.6.2).

Otherwise such an object is initialized the first time control passes through its declaration; such an object is considered initialized upon the completion of its initialization.

То есть, с нулём — однозначно будет от начала времён; с ненулевой константой — заведомо, не позднее, чем инициализуруются внешние статики (от начала времён до входа в main() — в любом случае, однопоточный рантайм); с неконстантой — тут уже как повезёт.

Чисто теоретически, можно поймать гонку и в однопоточном рантайме: если некий обработчик асинхронного события (прерывания, сигнала) будет зарегистрирован на этапе статической инициализации и выполнится прямо в момент инициализации статиков этого модуля. Или, опять же, стартовать поток ОС в обход сишного рантайма до входа в main().
Но это уже совсем сумрачный тевтонский гений.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[3]: Вопрос по синхронизации доступа к переменным
От: remark Россия http://www.1024cores.net/
Дата: 25.12.09 11:20
Оценка:
Здравствуйте, Николай Ивченков, Вы писали:

НИ>remark:


R>>лучше использовать функцию _InterlockedIncrement(),


НИ>Экономия на спичках. Сколько раз будет вызвана эта функция-счётчик?


Экономия на спичках — это если принять за точку отсчёта InterlockedIncrement(), на что никаких оснований нет. А если принять за точку отсчёта _InterlockedIncrement(), то попробуй обосновать зачем использовать более медленную InterlockedIncrement().
_InterlockedIncrement() — это просто правильный способ делать вещи. Так же как и предача контейнеров по ссылке; не смотря на то, что передача по значению не внесёт никакой видимой разницы во многих случаях. И что же теперь взять за правило передавать контейнеры по значению, и на все замечания бросать "экономия на спичках" и "преждевременная оптимизация"? Каждый, конечно, сам выбирает стиль программирования, но это не для меня.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: Вопрос по синхронизации доступа к переменным
От: jazzer Россия Skype: enerjazzer
Дата: 25.12.09 11:23
Оценка:
Здравствуйте, Кодт, Вы писали:

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


J>>нужно. И заодно нужно убедиться, что инициализация id нулем происходит "до всего", чтоб не было никаких обнуляющих действий в рантайме (по идее, она должна лежать в памяти, которая забита нулями сразу при старте приложения).


К>Имя этой идее — стандарт С++


Ну, надо начать с того, что существующий стандарт однопоточный, и в нем сосуществование потоков вообще никак не прописано
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[3]: Вопрос по синхронизации доступа к переменным
От: remark Россия http://www.1024cores.net/
Дата: 25.12.09 11:27
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Чисто теоретически, можно поймать гонку и в однопоточном рантайме: если некий обработчик асинхронного события (прерывания, сигнала) будет зарегистрирован на этапе статической инициализации и выполнится прямо в момент инициализации статиков этого модуля. Или, опять же, стартовать поток ОС в обход сишного рантайма до входа в main().

К>Но это уже совсем сумрачный тевтонский гений.

Если речь идёт о коде для конкретного приложения, про которое известно, что оно не запускает потоки до main(), то полностью согласен.
Если же речь идёт о коде из библиотеки, то я бы предпочёл корректно обрабатывать случай старта потоков до main(). Кто знает, что взбредёт в голову какому-то программисту. Плюс библиотеки типа логирования, пулов потоков, работа с БД и т.д., любят создавать рабочие потоки в DllMain() или в конструкторах глобальных объектов. В любом случае приятно вместо того, что бы добавлять дополнительное предупреждение в документацию (которое всё равно никто не будет читать, пока не налетит на проблему), просто не давать повода для проблем.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[4]: Вопрос по синхронизации доступа к переменным
От: Кодт Россия  
Дата: 25.12.09 11:45
Оценка:
Здравствуйте, remark, Вы писали:

R>Если речь идёт о коде для конкретного приложения, про которое известно, что оно не запускает потоки до main(), то полностью согласен.

R>Если же речь идёт о коде из библиотеки, то я бы предпочёл корректно обрабатывать случай старта потоков до main(). Кто знает, что взбредёт в голову какому-то программисту. Плюс библиотеки типа логирования, пулов потоков, работа с БД и т.д., любят создавать рабочие потоки в DllMain() или в конструкторах глобальных объектов. В любом случае приятно вместо того, что бы добавлять дополнительное предупреждение в документацию (которое всё равно никто не будет читать, пока не налетит на проблему), просто не давать повода для проблем.

Согласен. Да, по большому счёту, можно и безо всяких потоков нахватать UB — достаточно вспомнить, что порядок инициализации модулей не специфицирован.
Так что, только нуль-инициализация нас спасёт. Либо здоровый пофигизм
Автор: Николай Ивченков
Дата: 25.12.09
.
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Перекуём баги на фичи!
Re[4]: Вопрос по синхронизации доступа к переменным
От: carpenter Россия  
Дата: 25.12.09 12:58
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, Николай Ивченков, Вы писали:


НИ>>remark:


R>>>лучше использовать функцию _InterlockedIncrement(),


НИ>>Экономия на спичках. Сколько раз будет вызвана эта функция-счётчик?


R>Экономия на спичках — это если принять за точку отсчёта InterlockedIncrement(), на что никаких оснований нет. А если принять за точку отсчёта _InterlockedIncrement(), то попробуй обосновать зачем использовать более медленную InterlockedIncrement().

R>_InterlockedIncrement() — это просто правильный способ делать вещи. Так же как и предача контейнеров по ссылке; не смотря на то, что передача по значению не внесёт никакой видимой разницы во многих случаях.

ну вы сравнили " этот самый " с пальцем
Весь мир — Кремль, а люди в нем — агенты
Re[2]: Вопрос по синхронизации доступа к переменным
От: sidorov18 США  
Дата: 25.12.09 13:23
Оценка:
Здравствуйте, jazzer, Вы писали:

J>нужно. И заодно нужно убедиться, что инициализация id нулем происходит "до всего", чтоб не было никаких обнуляющих действий в рантайме (по идее, она должна лежать в памяти, которая забита нулями сразу при старте приложения).


с 0-м вроде понятно — инициализировать 0-м статическую переменную нет смысла.
а если, например, это не 0, то следует убедиться, что на этапе инициализации статических переменных нет обращения к CreateUniqueId?
Re[2]: Вопрос по синхронизации доступа к переменным
От: sidorov18 США  
Дата: 25.12.09 13:42
Оценка:
Здравствуйте, Николай Ивченков, Вы писали:

НИ>volatile и инициализатор "= 0" можно убрать.


А если наоборот? volatile оставить, а InterlockedIncrement убрать(компилятор mcvs).
Re[2]: Вопрос по синхронизации доступа к переменным
От: sidorov18 США  
Дата: 25.12.09 14:40
Оценка:
Здравствуйте, remark, Вы писали:

R>Добавлю, что если используется студия, то лучше использовать функцию _InterlockedIncrement(), которая определена в <intrin.h>. InterlockedIncrement() — это функция Win API, которая имеет С интерфейс и предназначена для использования всякими паскалями и др языками, которые могут использовать С библиотеки.

R>_InterlockedIncrement() же является интринсиком компилятора, соотв. при его использовании нет накладных расходов на вызов функции и манипуляции со стеком.

Только если подключить этот хедер, компилятор выдает ошибку error C2733: second C linkage of overloaded function '_interlockedbittestandset' not allowed
По видимому это связано с тем, что такая ф-я(только с volatile в первом аргументе) уже объявлена в winnt.h
В интернете советуют отредактировать intrin.h, заменить

unsigned char _interlockedbittestandset(long *a, long b)


на
unsigned char _interlockedbittestandset(long volatile *a, long b)


так можно делать? т.е. эта ф-я потенциально будет вызываться?
или есть более красивое решение?
Re[3]: Вопрос по синхронизации доступа к переменным
От: remark Россия http://www.1024cores.net/
Дата: 25.12.09 14:48
Оценка: 2 (1)
Здравствуйте, sidorov18, Вы писали:

S>Только если подключить этот хедер, компилятор выдает ошибку error C2733: second C linkage of overloaded function '_interlockedbittestandset' not allowed

S>По видимому это связано с тем, что такая ф-я(только с volatile в первом аргументе) уже объявлена в winnt.h
S>В интернете советуют отредактировать intrin.h, заменить

S>
S>unsigned char _interlockedbittestandset(long *a, long b)
S>


S>на

S>
S>unsigned char _interlockedbittestandset(long volatile *a, long b)
S>


S>так можно делать? т.е. эта ф-я потенциально будет вызываться?

S>или есть более красивое решение?

В последних студиях она так и объявлена в intrin.h. Я думаю, что так пофиксить будет нормально.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: Вопрос по синхронизации доступа к переменным
От: Николай Ивченков  
Дата: 25.12.09 15:28
Оценка:
sidorov18:

S>А если наоборот? volatile оставить, а InterlockedIncrement убрать(компилятор mcvs).


volatile тут совершенно бесполезен.
Re[3]: Вопрос по синхронизации доступа к переменным
От: remark Россия http://www.1024cores.net/
Дата: 26.12.09 18:00
Оценка: 2 (1)
Здравствуйте, sidorov18, Вы писали:

S>с 0-м вроде понятно — инициализировать 0-м статическую переменную нет смысла.

S>а если, например, это не 0, то следует убедиться, что на этапе инициализации статических переменных нет обращения к CreateUniqueId?


Тут дело не в 0 или не 0, а статическая инициализация или динамическая.
Т.е. вот так это тоже будет статическая инициализация и проблем не будет:
int g = 37;

А вот так это будет уже динамическая инициализация:
int g = rand();

Тут есть 2 варианта — (1) убедиться, что на этапе инициализации статических переменных нет обращений к этой переменной, или (2) инициализировать статически допустим нулём, а при первом обрщении потоко-безопасно инициализировать нужным значением. Для потоко-безопасной инициализации можно использовать pthread_once() (POSIX), InitOnceExecuteOnce() (Windows), call_once() (boost) и т.д.

Кстати, С++0х существенно расширяет понятие статической инициализации, там можно будет делать например вот так:
class mutex
{
public:
  mutex() constexpr
    : state(0)
    , owner(-1)
    , do_debug_checks(true)
  {}

  //...

private:
  uintptr_t state;
  uintptr_t owner;
  bool do_debug_checks;  
};

mutex g_mutex; // <--- статическая инициализация





1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[5]: Вопрос по синхронизации доступа к переменным
От: remark Россия http://www.1024cores.net/
Дата: 26.12.09 18:03
Оценка: 1 (1) +1
Здравствуйте, carpenter, Вы писали:

R>>Экономия на спичках — это если принять за точку отсчёта InterlockedIncrement(), на что никаких оснований нет. А если принять за точку отсчёта _InterlockedIncrement(), то попробуй обосновать зачем использовать более медленную InterlockedIncrement().

R>>_InterlockedIncrement() — это просто правильный способ делать вещи. Так же как и предача контейнеров по ссылке; не смотря на то, что передача по значению не внесёт никакой видимой разницы во многих случаях.

C>ну вы сравнили " этот самый " с пальцем


Дело не в том, сколько там конкретно тактов теряется. А в том, что в обоих случаях разница на глаз будет не заметна, но это не повод делать хуже, а потом говорить "экономия на спичках".


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: Вопрос по синхронизации доступа к переменным
От: remark Россия http://www.1024cores.net/
Дата: 26.12.09 18:16
Оценка: 2 (1)
Здравствуйте, sidorov18, Вы писали:

S>
S>    LONG CreateUniqueID()
S>    {
S>        static LONG id = 0;

S>        return id++;
S>    }
S>

S>Обеспечит ли такой метод уникальность id в многопоточном приложении?

Строго говоря, дело не в многопоточности, а в том, на каких процессорах они выполняются.
Если на машине всего один процессор; или все потоки, работающие со счётчиком, привязаны к одному процессору; или к счётчику обращается поток и обработчик сигнала, работающий на этом же потоке, то "Interlocked" использовать нет необходимости, можно использовать вот такую функцию, она гарантирует, что чтение, инкремент и запись будут выполнены одной инструкцией:
uint32_t noninterruptable_fetch_and_add(uint32_t* p, uint32_t a)
{
    uint32_t val;
    __asm
    {
        mov     eax,        a;
        mov     edi,        p;
        xadd    [edi],      eax;
        mov     val,        eax;
    }
    return val;
}



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: Вопрос по синхронизации доступа к переменным
От: Николай Ивченков  
Дата: 27.12.09 12:14
Оценка:
remark:

R>А если принять за точку отсчёта _InterlockedIncrement(), то попробуй обосновать зачем использовать более медленную InterlockedIncrement().

R>_InterlockedIncrement() — это просто правильный способ делать вещи.

В данном случае я не вижу принципиального отличия. Для меня это разница примерно такого же масштаба, как между for (;;) и while (true), и я бы не стал сильно из-за этого заморачиваться. Но если для тебя подобные мелочи имеют столь большое значение, то я ничего против не имею. Каждый может придерживаться своих религиозных убеждений.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.