C ++ улучшает алгоритм индексации палитры

Question

У меня есть игровой движок, который индексирует цвета некоторых растровых изображений, что позволяет использовать некоторые безумные эффекты olde (color strobing et c.). К сожалению, алгоритм индексации не является ни медленным, ни быстрым, но поскольку спрайт-листы в наши дни гигантские c, он действительно складывается. В настоящее время загрузка одной большой таблицы спрайтов может занимать 150+ миллисекунд, что является вечностью, условно говоря.

Это алгоритм:

auto& palette = p->pal;     // vector
auto& lookup  = p->lookup;  // vector_map

palette.reserve(200); // There are on average ~100 unique colors
palette.push_back(0); // Index zero is the blank color

uint32_t lastColor = 0;
uint32_t lastPalette = 0;

for (size_t i = 0; i < pixels; i++)
{
    const auto color = data[i];
    if (color == lastColor)
    {
        data[i] = lastPalette;
        continue;
    }
    else if (color == 0)
    {
        continue;
    }
    uint32_t j = 0;
    const auto& it = lookup.find(color);
    if (it != lookup.end()) {
        j = it->second;
    }
    else
    {
        j = palette.size();
        palette.push_back(color);
        lookup.emplace(color, j);
    }

    lastColor = color;
    // Write the index back to the bitmap:
    // (this is just a GPU texture encoding, don't mind it)
    data[i] = (j & 255) | ((j >> 8) << (8 + 6));
    lastPalette = data[i];
}

Базовый алгоритм довольно прост: Go через каждый пиксель, найдите или создайте для него запись (цвет), запишите индекс обратно к изображению.

Теперь вы можете распараллелить это? Возможно нет. Я пробовал с OMP и обычные темы. Это просто не будет быстрым, потому что независимо от того, сколько времени вы экономите, просматривая каждую часть изображения отдельно, в конце у вас должен быть общий набор индексов, которые применяются ко всему изображению, и эти индексы должны быть записано обратно на изображение. К сожалению, поиск уникальных цветов сначала, а затем обратная запись с использованием распараллеливания также выполняется медленнее, чем один раз, последовательно. Имеет смысл, не так ли?

Использование набора битов здесь не имеет никакой функции. Знание того, существует ли цвет, полезно, но цвета 32-битные, что составляет 2 ^ 32 бита (или 530 МБ). В отличие от 24-битных это всего ~ 2 МБ, что может быть микрооптимизацией. Во всяком случае, я этого не ищу. Мне нужно сократить время в 10 раз.

Итак, есть идеи? Можно ли обрабатывать 4 или 8 цветов одновременно, используя SSE / AVX?