Использовать массив указателей на структуры или просто массив структур?

Question

Я работаю над алгоритмом FFT в C для микроконтроллера , Я сталкиваюсь с противоречивыми требованиями, что код должен выполняться в небольшом объеме памяти, и при этом быть максимально быстрым. Я полагаю, что массив указателей на структуры будет иметь несколько больший объем памяти, но в моем коде есть строка, похожая на следующую:

for (uint8_t i = 0; i < RECORD_SIZE; i++)
{
    uint8_t decimateValue = fft_decimate(i);
    fftData[i]->realPart = fftTempData[decimateValue]->realPart;
    fftData[i]->imPart = fftTempData[decimateValue]->imPart;
}

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

Answer 1

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

Тогда вы должны учитывать размер данных. Насколько большой указатель? 2 байта? 4 байта? Насколько велики структуры? 4 байта? 8 байт?

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

Answer 2

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

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

Answer 3

Первый : зависит.Профиль.

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

Затем можно распределить нагрузку между ядрами процессора.

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

Answer 4

Ты прав.Массив указателей будет работать быстрее, но это приведет к дополнительным расходам памяти.Если у вас есть память, чтобы использовать указатели, используйте их.