Как определить, выровнена ли память?

Я новичок в оптимизации кода с помощью инструкций SSE / SSE2, и до сих пор я не очень далеко продвинулся. Насколько мне известно, обычная функция, оптимизированная для SSE, будет выглядеть так:

void sse_func(const float* const ptr, int len){
    if( ptr is aligned )
    {
        for( ... ){
            // unroll loop by 4 or 2 elements
        }
        for( ....){
            // handle the rest
            // (non-optimized code)
        }
    } else {
        for( ....){
            // regular C code to handle non-aligned memory
        }
    }
}

Однако как мне правильно определить, выровнена ли память, на которую указывает ptr, например, 16 байт? Я думаю, что мне нужно включить обычный путь кода C для невыровненной памяти, поскольку я не могу гарантировать, что каждая память, переданная этой функции, будет выровнена. И использование встроенных функций для загрузки данных из невыровненной памяти в регистры SSE кажется ужасно медленным (даже медленнее, чем обычный код C).

Заранее спасибо...


person user229898    schedule 13.12.2009    source источник
comment
random-name, не уверен, но я думаю, что было бы более эффективно просто обрабатывать первые несколько «невыровненных» элементов отдельно, как вы делаете с несколькими последними. Тогда вы все еще можете использовать SSE для «средних» ...   -  person Rehno Lindeque    schedule 21.12.2009
comment
Хм, это хороший момент. Я попытаюсь. Спасибо!   -  person user229898    schedule 22.12.2009
comment
Лучше: используйте скалярный пролог для обработки смещенных элементов до первой границы выравнивания. (gcc делает это при автоматической векторизации указателем с неизвестным выравниванием.) Или, если ваш алгоритм идемпотентный (например, a[i] = foo(b[i])), выполните потенциально невыровненный первый вектор, а затем основной цикл, начиная с первой границы выравнивания после первого вектора, затем последний вектор, который заканчивается последним элементом. Если массив на самом деле был смещен и / или счетчик не был кратен ширине вектора, тогда некоторые из этих векторов будут перекрываться, но это все равно лучше скалярного.   -  person Peter Cordes    schedule 23.08.2017
comment
Лучшее: предоставить распределитель, который обеспечивает память с выравниванием по 16 байт. Затем работайте с 16-байтовым выровненным буфером без необходимости исправлять ведущие или хвостовые элементы. Это то, что библиотеки, такие как Botan и Crypto ++, делают для алгоритмов, использующих SSE, Altivec и другие.   -  person jww    schedule 24.08.2018


Ответы (8)


РЕДАКТИРОВАТЬ: приведение к long - дешевый способ защитить себя от наиболее вероятной возможности того, что int и указатели в настоящее время имеют разные размеры.

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

Указатель p выравнивается по 16-байтовой границе, если ((unsigned long)p & 15) == 0.

person Pascal Cuoq    schedule 13.12.2009
comment
Я считаю, что приведение указателя на int - плохая идея? Мой код будет скомпилирован как на x86, так и на x64 системах. Я надеялся, что там будет какой-нибудь секретный системный макрос is_aligned_mem() или около того. - person user229898; 14.12.2009
comment
Вместо этого вы можете использовать uintptr_t - это гарантирует правильный размер для хранения указателя. Конечно, при условии, что это определяет ваш компилятор. - person Anon.; 14.12.2009
comment
Нет, указатель является числом типа int. Просто оно обычно не используется как числовое. - person Paul Nathan; 14.12.2009
comment
На самом деле не имеет значения, совпадают ли указатель и целочисленный размер. Вы заботитесь только о нескольких нижних битах. - person Richard Pennington; 14.12.2009
comment
Что ж, если был секретный системный макрос, вы можете быть уверены, что он будет работать, указав указатель на int. В этом приведении нет ничего волшебного, вы просто просите компилятор позволить вам посмотреть, как указатель представлен в битах. Если вы этого не сделаете, как вы узнаете, выровнено ли оно? - person Bill Forster; 14.12.2009
comment
Я обычно использую p % 16 == 0, поскольку компиляторы обычно знают степень двойки так же хорошо, как и я, и я считаю это более читаемым - person Hasturkun; 14.12.2009
comment
int традиционно был размером системного слова, или указателя. Это изменится при переходе с 32-битной на 64-битную? (любопытный) - person Paul Nathan; 14.12.2009
comment
@Hasturkun Деление / по модулю целых чисел со знаком не скомпилировано в побитовых трюках в C99 (какой-то тупой ход с округлением до нуля), и это действительно умный компилятор, который распознает, что результат по модулю сравнивается с нулем (в котором случае побитовый материал снова работает). Не невозможно, но и нетривиально. Вообще говоря, лучше привести к беззнаковому целому числу, если вы хотите использовать% и позволить компилятору скомпилировать &. - person Pascal Cuoq; 14.12.2009
comment
Спасибо за ответы на все вопросы. @ Ричард Пеннингтон: Это хороший момент. @Bill Forster: Я знаю, что кому-то в конце концов придется сравнивать фактические биты, но мне нужен был безопасный и кроссплатформенный (x86, x64) способ. Немного пугает то, что существует столько самодельных решений. И я не нашел рекомендованного ни на MSDN, ни на сайте Intel. - person user229898; 14.12.2009
comment
@ Паус Натан: Это зависит от того, какая у вас система - ILP64 или LP64 x64. E. g. Windows на архитектуре x64 - это LP64, это означает, что int по-прежнему 32-битный, но длинный имеет 64-битный формат. Однако я не уверен насчет Linux на x64. - person user229898; 14.12.2009
comment
@Pascal Cuoq, gcc замечает это и выдает точно такой же код для (p & 15) == 0 и (p % 16) == 0 с установленным флагом -O. Я видел ряд других компиляторов, которые распознают целочисленное деление / модуль / умножение на степень двойки и делают с этим умные вещи. (Я согласен с приведением к неподписанному) - person Hasturkun; 14.12.2009
comment
конечно, компилятор может распознать их только при работе с постоянной времени компиляции. если вы обнаружите, что используете несколько возможных значений, вернитесь к использованию & - person Hasturkun; 14.12.2009
comment
@Hasturkun Я только что скомпилировал int d(int x) { return x / 8; } с gcc -S. Это и красиво, и грустно ... В основном грустно ... - person Pascal Cuoq; 14.12.2009
comment
@Pascal Cuoq: Я согласен с этим, но он по-прежнему обрабатывает модуль и правильно сравнивает с 0 (пока используется оптимизатор, в противном случае он может испускать модуль (чего нет в моем случае, но делает это далеко) менее эффективно). - person Hasturkun; 14.12.2009
comment
Но мы не можем вывести исходное выравнивание указателя, только максимальное выравнивание. то есть ((unsigned long)p & 15) == 0 может выполняться для указателей, которые изначально запрашивались с выравниванием по 4 или 8 байтов. - person Jarrod Smith; 09.08.2017
comment
@Anon .: Вам все равно нужно проверять только младшие биты указателя, так что можно потерять старшие биты при приведении к узкому беззнаковому типу. Однако важно использовать uintptr_t, если вы хотите вернуться к указателю после округления вниз или вверх до следующей границы выравнивания. - person Peter Cordes; 23.08.2017

#define is_aligned(POINTER, BYTE_COUNT) \
    (((uintptr_t)(const void *)(POINTER)) % (BYTE_COUNT) == 0)

Преобразование в void * (или, эквивалентно, char *) необходимо, потому что стандарт гарантирует только обратимое преобразование в uintptr_t для void *.

Если вам нужна безопасность типов, подумайте об использовании встроенной функции:

static inline _Bool is_aligned(const void *restrict pointer, size_t byte_count)
{ return (uintptr_t)pointer % byte_count == 0; }

и надейтесь на оптимизацию компилятора, если byte_count - константа времени компиляции.

Почему нам нужно преобразовывать в void * ?

Язык C допускает различные представления для разных типов указателей, например, у вас может быть 64-битный тип void * (все адресное пространство) и 32-битный тип foo * (сегмент).

Преобразование foo * -> void * может включать фактическое вычисление, например добавление смещения. Стандарт также оставляет на усмотрение реализацию того, что происходит при преобразовании (произвольных) указателей в целые числа, но я подозреваю, что это часто реализуется как noop.

Для такой реализации foo * -> uintptr_t -> foo * будет работать, но foo * -> uintptr_t -> void * и void * -> uintptr_t -> foo * - нет. Вычисление выравнивания также не будет работать надежно, потому что вы проверяете выравнивание только относительно смещения сегмента, которое может быть, а может и не быть тем, что вы хотите.

В заключение: всегда используйте void *, чтобы добиться независимого от реализации поведения.

person Christoph    schedule 14.12.2009
comment
Этот макрос сразу выглядит действительно противно и изощренно. Обязательно протестирую. - person user229898; 14.12.2009
comment
Приведите известные вам примеры платформ, на которых non-void * не выдает целочисленное значение в диапазоне uintptr_t. И / или знаете ли вы, в чем причина такой формулировки стандарта? - person Craig McQueen; 26.11.2010
comment
Зачем ограничивать ?, похоже, он ничего не делает, когда есть только один указатель? - person Mikhail; 23.09.2015
comment
@Mikhail: комбинация const * с restrict является более сильной гарантией, чем простой const *: без restrict законно отбросить const и изменить память; при наличии restrict это не так; к сожалению, я узнал, что это бесполезно на практике, поскольку оно вступает в силу только в том случае, если указатель действительно используется, что вызывающий не может предположить в целом (т.е. полезность лежит исключительно на стороне вызываемого); в этом конкретном случае это в любом случае излишне, поскольку мы имеем дело со встроенной функцией, поэтому компилятор может видеть ее тело и самостоятельно делать вывод о том, что память не изменяется - person Christoph; 23.09.2015
comment
Если float * может (теоретически) иметь представление, отличное от void *, означает ли это, что проверка выравнивания может происходить на другом значении, отличном от предполагаемого? - person mwfearnley; 14.03.2019

В других ответах предлагается операция И с установленными младшими битами и сравнение с нулем.

Но более простой тест - выполнить MOD с желаемым значением выравнивания и сравнить его с нулем.

#define ALIGNMENT_VALUE     16u

if (((uintptr_t)ptr % ALIGNMENT_VALUE) == 0)
{
    // ptr is aligned
}
person Craig McQueen    schedule 13.12.2009
comment
Я поддержал вас, но только потому, что вы используете беззнаковые целые числа :) - person Pascal Cuoq; 14.12.2009
comment
Я считаю, что это не работает с uint8_t типами, которые иногда требуют выравнивания 1. - person jww; 24.08.2018
comment
@jww Я не уверен, что понимаю, что вы имеете в виду. Требование выравнивания 1 означало бы, по существу, отсутствие требования выравнивания. Не нужно беспокоиться о выравнивании uint8_t. Но, пожалуйста, поясните, если я неправильно понимаю. - person Craig McQueen; 29.08.2018
comment
Предоставляет ли 16u преимущество портативности, которого нет у 16? - person Todd Lehman; 08.08.2019
comment
Суффикс u целого числа делает его беззнаковым. Рекомендуется избегать смешивания знаковых и беззнаковых выражений в выражениях, чтобы избежать некоторых возможных ошибок, которые могут произойти с арифметикой со смешанными знаками. См. Сравнение предупреждений GCC между знаковыми и беззнаковыми целочисленными выражениями. В данном случае это, наверное, не имеет значения, но полезно иметь хорошие привычки. (Полагаю, 0 тоже должно быть 0u) - person Craig McQueen; 08.08.2019

С шаблоном функции, например

#include <type_traits>

template< typename T >
bool is_aligned(T* p){
    return !(reinterpret_cast<uintptr_t>(p) % std::alignment_of<T>::value);
}

вы можете проверить выравнивание во время выполнения, вызвав что-то вроде

struct foo_type{ int bar; }foo;
assert(is_aligned(&foo)); // passes

Чтобы проверить, что неправильное выравнивание не удается, вы можете сделать

// would almost certainly fail
assert(is_aligned((foo_type*)(1 + (uintptr_t)(&foo)));
person rubicks    schedule 23.02.2015
comment
Здесь было бы хорошо объяснить, как это работает, чтобы ОП понимал это. - person Danny Staple; 23.02.2015
comment
C ++ явно запрещает создание невыровненных указателей на данный тип T. Поскольку такой указатель не может существовать, компилятору разрешено оптимизировать is_aligned(p) до true для любого указателя p. - person Paweł Bylica; 31.08.2016
comment
@ paweł-bylica, вы, наверное, правы. Не могли бы вы дать ссылку (документ, главу, стих и т. Д.), Чтобы я мог исправить свой ответ? - person rubicks; 31.08.2016
comment
Кроме того, шаблонные функции всегда inline, поэтому ключевое слово inline является избыточным. - person gnzlbg; 08.08.2017
comment
@gnzlbg, я не думаю, что шаблоны функций всегда встроены; по крайней мере, не в соответствии с этим: stackoverflow.com/a/10536588/3798657. - person rubicks; 09.08.2017
comment
В этом ответе говорится, что inline имеет значение для явных специализаций, но явные специализации не являются шаблонами. Второй ответ на этой странице правильный: stackoverflow.com/a/10535711/1422197 В принципе, если бы вы явно специализировались этот шаблон в функцию, тогда, в зависимости от того, где вы решите его специализировать (например, файл заголовка), вам может потребоваться использовать ключевое слово inline в специализации, чтобы избежать проблем ODR, но это всегда так, независимо от того, используете ли вы inline по шаблону или нет. inline в шаблоне совершенно не имеет значения. - person gnzlbg; 09.08.2017
comment
@gnzlbg, признаю; ты прав. Я немедленно изменю свой ответ. - person rubicks; 09.08.2017

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

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

template <unsigned int alignment>
struct IsAligned
{
    static_assert((alignment & (alignment - 1)) == 0, "Alignment must be a power of 2");

    static inline bool Value(const void * ptr)
    {
        return (((uintptr_t)ptr) & (alignment - 1)) == 0;
    }
};

Чтобы узнать, что происходит, вы можете использовать это:

// 1 of them is aligned...
int* ptr = new int[8];
for (int i = 0; i < 8; ++i)
    std::cout << IsAligned<32>::Value(ptr + i) << std::endl;

// Should give '1'
int* ptr2 = (int*)_aligned_malloc(32, 32);
std::cout << IsAligned<32>::Value(ptr2) << std::endl;
person atlaste    schedule 27.02.2015

Оставьте это профессионалам,

https://www.boost.org/doc/libs/1_65_1/doc/html/align/reference.html#align.reference.functions.is_aligned.

bool is_aligned(const void* ptr, std::size_t alignment) noexcept; 

пример:

        char D[1];
        assert( boost::alignment::is_aligned(&D[0], alignof(double)) ); //  might fail, sometimes
person alfC    schedule 08.07.2019

Можете ли вы просто «и» ptr с 0x03 (выровнен по 4s), 0x07 (выровнен по 8s) или 0x0f (выровнен по 16s), чтобы увидеть, установлен ли какой-либо из младших битов?

person Paul Tomblin    schedule 13.12.2009
comment
Нет, не можешь. Указатель не является допустимым аргументом для оператора &. - person Steve Jessop; 14.12.2009
comment
@SteveJessop можно преобразовать в uintptr_t. - person ; 21.12.2016
comment
@MarkYisri: да, я ожидаю, что на практике каждая реализация, поддерживающая инструкции SSE2, дает гарантию, зависящую от реализации, которая будет работать :-) - person Steve Jessop; 10.01.2017

Как насчет:

void *mem = malloc(1024+15); 
void *ptr =( (*(char*)mem) - (*(char *)mem % 16) );
person Ramana    schedule 04.09.2012
comment
-1 Не отвечает на вопрос. (вопрос был в том, как определить, выровнена ли память? а не как выделить какую-то выровненную память?) - person milleniumbug; 01.08.2015
comment
@milleniumbug он выравнивает его во второй строке - person ; 20.12.2016
comment
@MarkYisri Тоже не как выровнять буфер? - person milleniumbug; 21.12.2016
comment
@milleniumbug не имеет значения, буфер это или нет. mem - указатель. - person ; 21.12.2016
comment
@MarkYisri Тоже не как выровнять указатель ?. Ответ на mem выровнен? не указатель. Да или нет. - person milleniumbug; 21.12.2016