Из этих 3 методов чтения связанных списков из разделяемой памяти, почему 3-й самый быстрый?

Question

У меня есть «серверная» программа, которая обновляет многие связанные списки в общей памяти в ответ на внешние события. Я хочу, чтобы клиентские программы как можно быстрее заметили обновление в любом из списков (самая низкая задержка). Сервер помечает узел связанного списка state_ как FILLED, как только его данные будут заполнены, а его следующий указатель будет установлен в допустимое местоположение. До этого момента его state_ составляет NOT_FILLED_YET. Я использую барьеры памяти, чтобы убедиться, что клиенты не видят state_ как FILLED до того, как данные внутри действительно готовы (и, похоже, они работают, я никогда не вижу поврежденных данных). Кроме того, state_ является volatile, чтобы убедиться, что компилятор не поднимает проверку клиента из циклов.

Сохраняя код сервера точно так же, я придумал 3 разных метода для проверки клиентом связанных списков для изменений. Вопрос в следующем: почему 3-й метод наиболее быстрый?

Метод 1: Круговой над всеми связанными списками (так называемые «каналы») непрерывно, глядя, чтобы увидеть, если какие-либо узлы заменить на «FILLED»:

void method_one() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    while(true) 
    { 
     for(std::size_t i = 0; i < channel_list.size(); ++i) 
     { 
      Data* current_item = channel_cursors[i]; 

      ACQUIRE_MEMORY_BARRIER; 
      if(current_item->state_ == NOT_FILLED_YET) { 
       continue; 
      } 

      log_latency(current_item->tv_sec_, current_item->tv_usec_); 

      channel_cursors[i] = static_cast<Data*>(current_item->next_.get(segment)); 
     } 
    } 
} 

Метод 1 дал очень низкую латентность, когда то количество каналов было небольшим. Но когда число каналов выросло (250K +), оно стало очень медленным из-за циклизации по всем каналам. Поэтому я пробовал ...

Способ 2. Дайте каждому связанному списку ID. Сохраните отдельный «список обновлений» сбоку. Каждый раз, когда обновляется один из связанных списков, введите его идентификатор в список обновлений. Теперь нам просто нужно следить за единственным списком обновлений и проверять идентификаторы, которые мы получаем от него.

void method_two() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment)); 

    while(true) 
    { 
      ACQUIRE_MEMORY_BARRIER; 
     if(update_cursor->state_ == NOT_FILLED_YET) { 
      continue; 
     } 

     ::uint32_t update_id = update_cursor->list_id_; 

     Data* current_item = channel_cursors[update_id]; 

     if(current_item->state_ == NOT_FILLED_YET) { 
      std::cerr << "This should never print." << std::endl; // it doesn't 
      continue; 
     } 

     log_latency(current_item->tv_sec_, current_item->tv_usec_); 

     channel_cursors[update_id] = static_cast<Data*>(current_item->next_.get(segment)); 
     update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment)); 
    } 
} 

Метод 2 дал TERRIBLE латентность. Принимая во внимание, что метод 1 может давать задержка 10us, метод 2 необъяснимо часто дает 8 мс латентности! Используя gettimeofday, кажется, что изменение в update_cursor-> state_ было очень медленным, чтобы протаиваться с представления сервера на клиентский (я нахожусь в многоядерном поле, поэтому я предполагаю, что задержка связана с кешем). Поэтому я попробовал гибридный подход ...

Способ 3: Сохраните список обновлений. Но циклически переходите по всем каналам непрерывно, и в каждой итерации проверьте, обновлен ли список обновлений. Если это так, пойдите с номером, нажатым на него. Если это не так, проверьте канал, в который мы сейчас итерализовались.

void method_three() 
{ 
    std::vector<Data*> channel_cursors; 
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i) 
    { 
     Data* current_item = static_cast<Data*>(i->get(segment)->tail_.get(segment)); 
     channel_cursors.push_back(current_item); 
    } 

    UpdateID* update_cursor = static_cast<UpdateID*>(update_channel.tail_.get(segment)); 

    while(true) 
    { 
     for(std::size_t i = 0; i < channel_list.size(); ++i) 
     { 
      std::size_t idx = i; 

      ACQUIRE_MEMORY_BARRIER; 
      if(update_cursor->state_ != NOT_FILLED_YET) { 
       //std::cerr << "Found via update" << std::endl; 
       i--; 
       idx = update_cursor->list_id_; 
       update_cursor = static_cast<UpdateID*>(update_cursor->next_.get(segment)); 
      } 

      Data* current_item = channel_cursors[idx]; 

      ACQUIRE_MEMORY_BARRIER; 
      if(current_item->state_ == NOT_FILLED_YET) { 
       continue; 
      } 

      found_an_update = true; 

      log_latency(current_item->tv_sec_, current_item->tv_usec_); 
      channel_cursors[idx] = static_cast<Data*>(current_item->next_.get(segment)); 
     } 
    } 
} 

Задержка этого метода не хуже метода 1, но масштабируется до большого количества каналов. Проблема в том, что я не знаю, почему. Просто бросить гаечный ключ в вещах: если я раскомментирую часть «найденный через обновление», он печатает между КАЖДОЙ СООБЩЕНИЕМ LATENCY LOG. Это означает, что вещи всегда встречаются только в списке обновлений! Так что я не понимаю, как этот метод может быть быстрее, чем метод 2.

Полный, компилируемый код (требуется GCC и повышения-1,41), который генерирует случайные строки в качестве тестовых данных находится по адресу: http://pastebin.com/0kuzm3Uf

Update: Все 3 метода эффективно спин-блокировки до тех пор, пока не произойдет обновление. Разница заключается в том, сколько времени им требуется, чтобы заметить, что обновление произошло. Они все непрерывно уплачивают процессор, так что не объясняют разницу в скорости. Я тестирую на 4-ядерном компьютере, где ничего больше не работает, поэтому серверу и клиенту нечего конкурировать. Я даже сделал версию кода, в которой обновления сигнализируют о состоянии и ждут клиентов при условии - это не помогло латентности любого из методов.

Update2: Несмотря на то, что существует 3 метода, я пробовал только 1 за раз, поэтому только 1 сервер и 1 клиент конкурируют за элемент state_.

Answer 1

Ответ был сложным для выяснения, и быть справедливым было бы сложно с представленной мной информацией, хотя если бы кто-то собственно скомпилировал источник код, при условии, что у них будет шанс на бой;) Я сказал, что после каждого сообщения журнала латентности было напечатано «найденное через список обновлений», но это не было правдой - это было верно только в том случае, если бы я мог прокручивать мой терминал. В самом начале появилось множество обновлений без использования списка обновлений.

Проблема заключается в том, что между тем, когда я установил отправную точку в списке обновлений и отправную точку в каждом из списков данных, будет некоторое отставание, потому что эти операции требуют времени. Помните, что списки все это время растут. Рассмотрим простейший случай, когда у меня есть 2 списка данных: A и B. Когда я устанавливаю отправную точку в списке обновлений, в нем должно быть 60 элементов из-за 30 обновлений в списке A и 30 обновлений в списке B. Скажите, что они «ве чередовался:

A 
B 
A 
B 
A // and I start looking at the list here 
B 

Но после того, как я установил список обновлений, чтобы там, есть множество обновлений для B и без обновлений к A. Тогда я установил свои исходные места в каждом из списков данных. Мои начальные точки для списков данных будут после, что всплеск обновлений, но моя начальная точка в списке обновлений до этого всплеска, так что теперь я собираюсь проверить кучу обновлений, не найдя их. Смешанный подход выше работает лучше всего, потому что, повторяя все элементы, когда он не может найти обновление, он быстро закрывает временный разрыв между тем, где находится список обновлений и где находятся списки данных.

Answer 2

Я заметил как в методе 1, так и в методе 3 у вас есть строка ACQUIRE_MEMORY_BARRIER, которая, как я полагаю, имеет какое-то отношение к многопоточным/гоночным условиям?

В любом случае, метод 2 не имеет каких-либо спит, что означает следующий код ...

while(true) 
{ 
    if(update_cursor->state_ == NOT_FILLED_YET) { 
     continue; 
    } 

собирается забивать процессор. Типичным способом выполнения этой задачи производителя/потребителя является использование своего рода семафора, чтобы сообщить читателю, что список обновлений изменился. Поиск многопоточности для производителей/потребителей должен дать вам большое количество примеров. Основная идея здесь заключается в том, что это позволяет потоку спать, пока он ожидает изменения состояния update_cursor->. Это предотвращает этот поток от кражи всех циклов процессора.

Answer 3

Гипотеза: метод 2 каким-то образом блокирует обновление от получения письменной информации от сервера.

Одна из вещей, которые вы можете забить, помимо самих процессорных ядер, - это ваш когерентный кеш. Когда вы читаете значение на заданном ядре, кэш L1 на этом ядре должен получить доступ к чтению к этой строке кэша, что означает, что ему необходимо аннулировать доступ на запись к этой строке, который имеет любой другой кеш. И наоборот, чтобы написать значение. Таким образом, это означает, что вы постоянно просматриваете строку кэша между «состоянием записи» (в кеше серверного ядра) и «прочитанным» состоянием (в кэшах всех клиентских ядер).

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

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

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

Answer 4

Я не знаю, если вы когда-либо читали столбцы параллелизма из Herb Sutter. Они довольно интересны, особенно когда вы попадаете в проблемы с кешем.

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

Однако то, что на самом деле может случиться, что у вас есть такая строка кэша:

Line of cache = [ID1, ID2, ID3, ID4, ...] 
       ^  ^
      client   server 

Который затем создает раздор.

Настоящая статья Герба Саттера: Eliminate False Sharing. Основная идея - просто искусственно раздуть ваш идентификатор в списке, чтобы он полностью занимал одну строку кеша.

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