Содержание


Методы оптимизации библиотечных функций для процессоров IBM PowerPC

Comments

Упреждающая выборка для предотвращения неудачных обращений к кэш-памяти

Упреждающая выборка – это метод повышения производительности приложений. Идея заключается в предварительном размещении блоков данных в кэш-памяти – как правило, за несколько циклов до фактического обращения к ним. Этот подход устраняет издержки ожидания данных, считываемых из основной памяти. Эффект упреждающей выборки зависит от того, насколько часто используются кэшированные данные. Для упреждающей выборки данных часто используются инструкции dcbt и dcbtst.Эти инструкции можно вызывать напрямую из ассемблер-кода или обращаться к ним через встроенные функции и директивы компилятора. Упреждающая выборка реализована и автоматически используется на физических процессорах IBM POWER8®™. Данный метод широко используется для повышения производительности приложений в однопоточных и одноядерных средах, а также в системах с низким коэффициентом использования.

Выравнивание данных в оперативной памяти

Центральный процессор обращается к блокам данных по их естественным выровненным границам. При обращении к невыровненным данным ему может потребоваться дополнительное время, которое будет зависеть от конкретных инструкций load и store. Для таких инструкций могут потребоваться перехват и эмуляция, выполняемые гипервизором физического хоста.

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

Листинг 1. Пример выравнивания данных в памяти
        dcbt	0, r3
	clrrdi	r8, r3, 3	  /* Выравнивание адреса по границам двойного слова.   */
	ld	r12, 0(r8)        /* Загрузка двойного слова из памяти.  */

	rlwinm	r6,r3,3,26,28     /* Вычисление размера заполнения.   */

	/* Сдвиг двойного слова влево и вправо для сброса битов, 
 не являющихся частью строки, и заполнение их нулями.   */
           
#ifdef __LITTLE_ENDIAN__
	srd     r12, r12, r6
	sld     r12, r12, r6
#else
 	sld	r12, r12, r6
	srd	r12, r12, r6
#endif

Отказ от побайтовых инструкций load/store (загрузка данных блоками по 8 байтов)

Работая с длинными строками, лучше загружать или записывать данные блоками по 8 байтов, а не загружать или записывать каждый байт последовательно. Так вы получите лучшие результаты при сравнении или копировании двух строк. Даже если длина строки заранее не известна, входящие данные можно загружать в виде 8-байтовых блоков, проверяя их на наличие завершающего null-символа.

Использование инструкции cmpb

Инструкция cmpb полезна при сравнении содержимого двух регистров. Поскольку большинство строковых функций так или иначе сравнивают входные данные, использование инструкции cmpb может положительно повлиять на производительность, поскольку она позволяет сравнивать 8 байтов за раз. Инструкция cmpb доступна начиная со спецификации ISA 2.06.

Сравнение байтов в X-форме

cmpb RA,RS,RB

Каждый байт содержимого регистра RS сравнивается с каждым соответствующим байтом содержимого регистра RB. Если они равны, то соответствующий байт в регистре RA устанавливается в 0xFF. В противном случае соответствующий байт в регистре RA устанавливается в 0x00.

Листинг 2. Пример проверки на null-значение
li	r5, 0		/* загружаем 0 в регистр r5  */
cmpb	r7, r5, r6      /* /* сравниваем регистры r6 и r5, сохраняя результат в r7  */
cmpdi	cr7, r7, 0	/* проверяем, не является ли регистр r7 нулевым */
beq	cr7, L(no_null)
cntlzd	r8, r7		/* подсчитываем ведущие нули  */

Если регистр r6 содержит значение 0x3100333435363700, то регистр r7 должен содержать значение 0x00ff0000000000ff. Таким образом, если регистр r7 не нулевой, значит, регистр r6 содержит нулевые значения. Их позицию можно определить при помощи инструкции cntlzd.

Развертывание циклов

Развертывание цикла – это реализуемый в компиляторах метод оптимизации, уменьшающий число итераций путем многократного дублирования тела цикла. Этот подход позволяет увеличить скорость выполнения программы за счет уменьшения количества инструкций управления циклом (вплоть до полного их отсутствия), а также вычислительных затрат на ветвления. Любой цикл можно переписать в виде повторяющейся последовательности одинаковых независимых выражений.

Листинг 3. Пример развертывания цикла при сравнении строк
L(process_unaligned_bytes):
        lbz r9, 0(r3)           /* загружаем байт из регистра s1  */
        lbz r10, 0(r4)          /*загружаем байт из регистра s2  */
        cmpdi cr7, r9, 0        /* сравниваем *s1 с NULL   */
        beq cr7, L(diffOfNULL)  /* если *s1 равен NULL, возвращаем *s1 - *s2   */
        cmplw cr7, r9, r10      /* сравниваем *s1 и *s2   */
        bne cr7, L(ComputeDiff) /* ветвь для вычисления разницы и возврата   */

        lbz r9, 1(r3)           /* загружаем следующий байт из регистра s1   */
        lbz r10, 1(r4)          /* загружаем следующий байт из регистра s2  */
        cmpdi cr7, r9, 0        /* сравниваем *s1 с NULL   */
        beq cr7, L(diffOfNULL)  /* если *s1 равен NULL, возвращаем *s1 - *s2   */
        cmplw cr7, r9, r10      /* сравниваем *s1 и *s2   */
        bne cr7, L(ComputeDiff) /* ветвь для вычисления разницы и возврата   */

        lbz r9, 2(r3)           /* развертывание 3-го байта   */
        lbz r10, 2(r4)
        cmpdi cr7, r9, 0
        beq cr7, L(diffOfNULL)
        cmplw cr7, r9, r10
        bne 7, L(ComputeDiff)

        lbz r9, 3(r3)           /* развертывание 4-го байта   */
        lbz r10, 3(r4)
        addi r3, r3, 4          /* увеличиваем значение s1 на коэффициент развертывания   */
        cmpdi cr7, r9, 0
        cmplw cr6, 9, r10
        beq cr7, L(diffOfNULL)

        addi r4, r4, 4          /* увеличиваем значение s2 на коэффициент развертывания   */
        beq cr6, L(process_unaligned_bytes)     /* выполнение развертывания байта  */

Использование хеш-таблиц

При работе со строковыми функциями, выполняющими поиск символов (например, strchr, strspn, strtok и т. д.), можно использовать метод хеширования, который позволяет избежать сканирования повторяющихся записей в строке поиска. В следующем примере показано, как создать хеш-таблицу и обновить ее на основе входной строки.

Листинг 4. Листинг 4. Пример создания хеш-таблицы
/* Инициализация хэш-таблицы нулями  */
            li      r6, 0
            li      r8, 4
            mtctr   r8
            mr      r10, r9
            .align  4
L(zerohash):
            std     r6, 0(r10)
            std     r6, 8(r10)
            std     r6, 16(r10)
            std     r6, 24(r10)
            std     r6, 32(r10)
            std     r6, 40(r10)
            std     r6, 48(r10)
            std     r6, 56(r10)
            addi    r10, r10, 64
            bdnz    L(zerohash)
            
            
            lbz     r10, 0(r4)      /* загружаем в регистр r10 "иголку" (r4)  */
            li      r8, 1           /* r8=1, метка в хеше, если найдено в "иголке"   */
            
            cmpdi   cr7, r10, 0     /* предполагаем, что "иголка" равна NULL  */
            beq     cr7, L(skipHashing)     /* если "иголка" равна NULL, пропускаем хеширование  */
            
            .align 4                /* выравниваем раздел по 16-байтовой границе  */
L(hashing):
            stbx    r8, r9, r10     /* обновляем хеш маркером для элемента сравнения "иголки"  */
            lbzu    r10, 1(r4)      /* загружаем "иголку" в регистр r10 и переходим к следующему   */
            cmpdi   cr7, r10, 0     /*если достигли NULL в "иголке", продолжаем   */
            bne     cr7, L(hashing) /* цикл для хеширования "иголки"   */
            
L(skipHashing):
            b       L(beginScan)

Заключение

Рассмотренные в этой статье методы можно комбинировать в зависимости от входных наборов данных. Например, эти методы можно использовать при работе со следующими строковыми функциями библиотеки Linux glibc for POWER: strchr, strstr, strspn, strlen, strcmp, strcpy, strtok. Применение рассмотренных методов при работе со строковыми функциями увеличивает производительность приложений в среднем на 40%.

Ссылки


Ресурсы для скачивания


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=1023240
ArticleTitle=Методы оптимизации библиотечных функций для процессоров IBM PowerPC
publish-date=07092015