Производительность pthread_mutex_lock / unlock

Question

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

Есть ли способ помочь в этом? Будет ли использование семафора более / менее эффективным?

Спасибо

typedef struct _treenode{
   struct _treenode *leftNode;
   struct _treenode *rightNode;
   int32_t data;
   pthread_mutex_t mutex;
}TreeNode;

pthread_mutex_t _initMutex = PTHREAD_MUTEX_INITIALIZER;

int32_t insertNode(TreeNode **_trunk, int32_t data){
   TreeNode **current;
   pthread_mutex_t *parentMutex = NULL, *currentMutex = &_initMutex;

   if(_trunk != NULL){
      current = _trunk;
      while(*current != NULL){
         pthread_mutex_lock(&(*current)->mutex);
         currentMutex = &(*current)->mutex;
         if((*current)->data < data){
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            pthreadMutex = currentMutex;
            current = &(*current)->rightNode;
         }else if((*current)->data > data){
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            parentMutex = currentMutex;
            current = &(*current)->leftNode;
         }else{
            pthread_mutex_unlock(currentMutex);
            if(parentMutex != NULL)
               pthread_mutex_unlock(parentMutex);
            return 0;
         }
      }
      *current = malloc(sizeof(TreeNode));
      pthread_mutex_init(&(*current)->mutex, NULL);
      pthread_mutex_lock(&(*current)->mutex);
      (*current)->leftNode = NULL;
      (*current)->rightNode = NULL;
      (*current)->data = data;
      pthread_mutex_unlock(&(*current)->mutex);
      pthread_mutex_unlock(currentMutex);
   }else{
      return 1;
   }
   return 0;
}

int main(){
   int i;
   TreeNode *trunk = NULL;
   for(i=0; i<1000000; i++){
      insertNode(&trunk, rand() % 50000);
   }
}

Answer 1

Вместо того, чтобы беспокоиться о травинках, отойдите назад и осмотрите весь лес.

Любой алгоритм, который зависит от двух потоков, потенциально тесно наступающих друг на друга, по своей сути неэффективен. Попробуйте найти способ радикально снизить потребность во взаимодействии.

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

Answer 2

pthread_mutex_lock и pthread_mutex_unlock различаются по стоимости в зависимости от конкуренции:

1. Использование одного потока - либо существует только один поток, либо только один поток использует мьютекс и защищаемый ресурс:блокировка практически свободна , возможно, максимум 80-100 циклов.
2. Несколько потоков используют ресурс, но блокировки удерживаются в течение очень коротких интервалов, и конфликты случаются редко: блокировка имеет определенную стоимость, иэто трудно измерить;стоимость состоит в основном из-за аннулирования строк кэша других ядер / процессоров.
3. Значительный конфликт блокировок: почти каждая операция блокировки и разблокировки потребует помощи от ядра, а стоимость легко составляет несколько тысяч (возможно, даже десятки).тысяч) циклов на блокировку / разблокировку.

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

Answer 3

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

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

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

Answer 4

Ваши замки, вероятно, слишком мелкозернистые.Конечно, оптимальная гранулярность может варьироваться в зависимости от рабочей нагрузки.

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

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

Answer 5

Блокировка и разблокировка являются очень дорогими операциями в случае pthread_mutex_lock / unlock.С более подробной информацией об алгоритме я мог бы сделать некоторые предложения, но, насколько я могу судить, я не могу вам ничего сказать наверняка.Семафоры являются альтернативой (опять же в зависимости от алгоритма), а также барьеры - еще один полезный метод для параллелизма.Чтобы снизить накладные расходы, вы можете сделать такие вещи, как сделать ваши замки меньшей зернистости или большей зернистости.блокировки внутри циклов, которые повторяются многократно, плохая идея, и вы можете переместить их за пределы цикла.Это только один пример, но, вероятно, я могу придумать еще кое-что.Речь идет о том, чтобы определить, больше ли стоимость блокировки, чем стоимость критической части вашего кода.Если вы предоставите свой алгоритм или некоторый пример кода, я буду рад взглянуть на него.