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

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

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

Метод 1: Циклический алгоритм по всем связанным спискам (названный 'каналами') непрерывно, надеясь видеть, изменились ли какие-либо узлы на 'ЗАПОЛНЕННЫЙ':

void method_one()
{
    std::vector channel_cursors;
    for(ChannelList::iterator i = channel_list.begin(); i != channel_list.end(); ++i)
    {
        Data* current_item = static_cast(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(current_item->next_.get(segment));
        }
    }
}

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

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

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

    UpdateID* update_cursor = static_cast(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(current_item->next_.get(segment));
        update_cursor = static_cast(update_cursor->next_.get(segment));
    }   
}

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

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

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

    UpdateID* update_cursor = static_cast(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(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(current_item->next_.get(segment));
        }
    }
}

Задержка этого метода была так же хороша как Метод 1, но масштабировалась к большим количествам каналов. Проблема, у меня нет подсказки почему. Только бросить ключ в вещи: если я некомментирую 'найденный через обновление' часть, оно печатает между КАЖДЫМ СООБЩЕНИЕМ ЖУРНАЛА ЗАДЕРЖКИ. Что означает, что вещи только когда-либо находятся в списке обновления! Таким образом, я не понимаю, как этот метод может быть быстрее, чем метод 2.

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

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

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