Издательский дом ООО "Гейм Лэнд"ЖУРНАЛ ХАКЕР 124, АПРЕЛЬ 2009 г.

Питон для матерых хардкорщиков. Куем ассемблерные вставки в Python с помощью кошерного CorePy

Алексей Черкес (aleksey.cherkes@gmail.com)




Я постоянно использую в работе open source программы и не перестаю удивляться, какие необычные проекты порой зарождаются в этой свободной среде. На мой взгляд, коммерческие приложения никогда не будут отличаться таким полетом мысли, как в среде открытого ПО.

Осваивая подобные продукты, глубже понимаешь сложные концепции программирования, детальнее изучаешь интересные технологии. В этот раз речь пойдет о вещах немного непривычных. Я расскажу о скрещивании двух языков программирования: ассемблера и Python’a.

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

На первый взгляд, смесь двух подходов выглядит едва ли возможной. В Python даже нет понятия указателя, – тут вообще не идет речи о прямой работе с памятью, ведь всю грязную работу выполняет трудолюбивый garbage collector! А такие вещи, как динамическая типизация и функции, являющиеся объектами первого класса и делающие интеграцию с ассемблером, казалось бы, неразрешимой на практике задачей? Однако в этой статье я рассмотрю технологию CorePy, которая делает подобную интеграцию возможной.

Общий обзор

CorePy - это модуль расширения для Python, частично написанный на С. Он позволяет программисту писать и исполнять ассемблерные программы, работая исключительно с интерпретатором Python. Это дает возможность проводить машинно-зависимую оптимизацию Python-программ, которая обычно невозможна даже в случае использования таких языков, как C. К примеру, ты можешь напрямую использовать технологии наподобие MMX и SSE.

CorePy поддерживает процессоры x86, x86_64 (с поддержкой SSE), PowerPC (PPC32 и PPC64), VMX/AltiVec и Cell SPU. Он может работать в операционных системах linux и OS X. Microsoft Windows в спискепочему-то не значится ;).

Весь CorePy можно разбить на три основных слоя:

  1. Instruction Set Architectures (ISAs). Это библиотеки объектов, которые представляют собой инструкции из разных наборов команд. Один физический процессор может поддерживать несколько наборов команд (например, x86 и SSE).
  2. InstructionStreams или потоки команд. Это контейнеры для объектов из пункта 1. Отвечают за хранение последовательности инструкций и за взаимодействие с операционной системой для их исполнения.
  3. Processors. Выполняют потоки команд и отвечают за передачу и возврат аргументов. Возможно синхронное и асинхронное выполнение потоков.

В начале работы программисту необходимо создать один из объектов InstructionSream. Затем пустой поток команд наполняется другими объектами, каждый из которых однозначно идентифицирует машинную инструкцию и ее параметры. На данном этапе никакого кода реально не создается! Мы просто описываем нужную нам программу, наполняя коллекцию InstructionSream. Полученная последовательность передается на исполнение классу, представляющему абстракцию процессора. Внутренние механизмы CorePy парсят переданный нами InstructionStream и генерируют на его основе реальный машинный код. Теперь его можно вызывать почти как обычную функцию, обращаясь к нему через специальный интерфейс класса Processor.

Руки чешутся работать

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

  • Тупая, наивная сортировка, реализованная на чистом Python без всяких примочек;
  • То же самое, только с оптимизацией средствами PsyCo;
  • Собственная реализация на ассемблере;
  • Стандартная функция sort, предоставляемая интерпретатором.

Время работы замеряется с помощью модуля timeit. Собранная статистика отражена на графиках. Они сгенерированы с помощью библиотеки PyLab - опенсорсовом убийце MatLab. Самый главный листинг, содержащий CorePy-код, помещен на врезке. Кроме основных компонент, в поставку CorePy входит модуль printer для отображения созданных инструкций в привычном формате. Я не стал упускать хорошей возможности воспользоваться им – на соседней врезке помещен ассемблерный листинг в формате NASM. Наверное, его можно даже скомпилировать :). Глядя на обе врезки, ты без труда поймешь, как работает CorePy. Про модуль PsyCo и более высокоуровневую оптимизацию Python-программ ты можешь прочитать в предыдущем номере ][.

Как уже было сказано, CorePy поддерживает несколько процессорных архитектур. Все примеры я привожу для x86 как для самой распространенной и единственной мне знакомой :). Программные модели отличаются друг от друга в основном наборами команд. Для работы с тем или иным набором необходимо импортировать corepy.arch.*.isa (вместо * подставь имя архитектуры).

В этих модулях находятся объекты, из которых потом компонуются программы. Для начала работы создай экземпляр InstructionStream (в примере это code). Затем с помощью метода add в него заносятся конкретные команды, например:

code.add(x86.mov(eax, 0)).

Мы добавили к командам из code операцию обнуления eax. Примерно так и составляется вся программа. x86 - это псевдоним для соответствующей ISA. Для того чтобы все время не писать code.add(команда), можно просто вызвать функцию x86.set_active_code(code) для экземпляра твоей ISA. После этого все создаваемые инструкции будут автоматически добавляться к code. Названия и структура параметров команд полностью совпадают с ассемблерными аналогами, поэтому запомнить их не составляет труда.

Для работы с регистрами импортируй все имена из corepy.arch.x86.types.registers. Далее в параметрах команд просто пиши, что нужно: eax, bp и т.д.
Здесь есть одна хитрость: регистры - это обычные объекты. Поэтому для них можно вводить псевдонимы. В примере я ввел альтернативное имя is_finish для esi. Такой подход облегчает восприятие, как правило, сильно запутанных ассемблерных программ.

Механизмы адресации традиционно считаются сложным аспектом в программировании на ассемблере. Действительно, x86 поддерживает несколько ее типов: прямая, косвенная, базовая, индексная, со смещением и т.д. В этих разновидностях немудрено заблудиться.Для формирования указателей на ячейки памяти CorePy предоставляет удобный класс MemRef (передается как параметр соответствующим конструкторам команд), который может заметно облегчить работу и повысить визуальную наглядность кода. Например: MemRef(0xABCD) - указатель на абсолютный адрес, MemRef(rip, -1024) - указатель на ячейку памяти, смещенную относительно IP, MemRef(rsi, disp = 0, index = rcx, scale = 4) - эффективный адрес = base + (index * scale) + disp (индексная базовая адресация со смещением). Последний случай используется в примере.

Редкая программа выполняется линейно и может обойтись без меток для переходов. Объекты меток в CorePy создаются классами InstructionStream – выглядит приблизительно так: lbl_loop = code.get_label("LOOP"). Здесь lbl_loop - это новая метка, а code - поток команд. Если у code запросить еще одну метку с именем «LOOP», вернется тот же экземпляр. Для использования созданной метки ее нужно поместить в код. Это очень просто: code.add(lbl_loop) добавляет метку на текущую позицию в коде. Концепция раздельного создания и использования меток может показаться странной, но она необходима для организации прыжков на метки, которые идут впереди по коду.

Если ты изучил ассемблерный листинг нашей программы, то наверняка обратил внимание, что CorePy разделяет каждую функцию на три части и вводит предопределенные метки: PROLOGUE, BODY, и EPILOGUE. Все, что мы пишем, попадает в главную часть - BODY. Код эпилога и пролога генерируется автоматически. Он нужен для обеспечения бинарного интерфейса между функцией и внешним миром. Наличие такой автоматизации - еще одно преимущество CorePy: теперь программист тратит меньше сил на реализацию рутинных вещей, таких как инициализация регистра bp указателем на вершину стека и т.п.

CorePy использует стек для передачи параметров в функции. На стороне Python-кода для этого нужно использовать специальный класс ExecParams. У него есть восемь полей: p1, p2, ... , p8 – каждое соответствует одному из восьми параметров, которые можно передать в функцию. Такой объект передается экземпляру класса Processor во время запуска процедуры. Из ассемблера доступ к параметрам осуществляется по старинке: через смещение относительно указателя начала стека. Чтобы, например, скопировать первый параметр в eax, напиши следующее: x86.mov(eax, MemRef(ebp, 16)). Для возврата значений из функций используется регистр с предопределенным именем. Обычно это gp_return.

Разумеется, ассемблер имеет смысл применять для обработки больших массивов данных - только в этом случае можно увидеть повышение быстродействия. Но много информации через регистры и стек в функцию не передашь, и эта проблема имеет отдельное решение. Например, можно пользоваться классом array из стандартной библиотеки. Это обычный динамический гомогенный массив для Python. Среди встроенных типов есть только гетерогенные списки, но они неэффективны при работе с большими блоками однотипных элементов. К тому же, они не предоставляют прямого доступа к памяти, а это нужно для работы ассемблерного кода. Поэтому и появился класс array – у него есть метод buffer_info(), возвращающий адрес начала массива и количество элементов в нем. Этот адрес можно использовать напрямую из ассемблера, в своем примере я так и сделал.

CorePy предоставляет похожий класс с почти идентичным интерфейсом - extarray. В отличие от стандартного array, он всегда выделяет память, выровненную по границам страниц. За счет такой оптимизации твои программы будут работать максимально эффективно. Плюс, на Linux поддерживается технология huge pages, и ее использование абсолютно прозрачно для программиста.

Иногда очень удобно использовать средства Python для автоматизации создания потоков команд. Ты можешь написать программы, которые будут автоматически генерировать последовательности ассемблерных инструкций. В примерах, которые идут с CorePy, можно встретить такие участки кода:

for i in xrange(0, 65):
code.add(x86_isa.pop(edi))

Здесь вместо того, чтобы заниматься copy and paste, разработчики написали цикл, который создает 65 pop-инструкций, идущих друг за другом. Я думаю, развив эту идею, можно сделать библиотеку удобных макросов – и использование старого доброго asm’а станет еще комфортнее.

Анализируем результаты

Выходит, ассемблерная версия рвет обычную на несколько порядков! Мы получили выигрыш от тысячи до десяти тысяч раз по скорости при использовании одинакового алгоритма, и с ростом количества элементов в массиве этот отрыв становится все заметнее. На графиках с четырьмя кривыми я вывел зависимость логарифма времени выполнения от количества элементов. Я провел два эксперимента с малым и большим N (до тысячи и до семи тысяч) – на графиках с двумя линиями выводятся абсолютные величины и сравниваются методы с приблизительно одинаковым порядком производительности. На одном показано время выполнения Python-реализации с PsyCo-оптимизацией и без.

Видно, что PsyCo работает, но в этом тесте эффект, все же, не слишком убедителен - кривые идут почти одна под другой. На другом графике мы наблюдаем стандартную функцию sort против нашей ассемблерной реализации – sort работает приблизительно на один порядок быстрее с нашим количеством элементов, но заметна тенденция к увеличению этого разрыва. Связано это с тем, что встроенные функции пишут на C, и они обычно очень хорошо оптимизированы. И конечно, там используется алгоритм с меньшей сложностью, чем n**2, как у нашей bubble sort :). Это очень хорошо прослеживается на графиках.

Подведем итоги

Позволяя писать низкоуровневые процедуры прямо в Python-коде с использованием его синтаксиса, CorePy снижает порог вхождения в машинное программирование до минимума. На официальном сайте приведена цитата одного из пользователей. Он говорит, что CorePy опять сделал программирование на ассемблере увлекательным и веселым занятием. Я полностью разделяю это мнение: библиотека логична и последовательна, ее освоение не займет много времени, а от комфортного программирования получаешь почти феерическое удовольствие :). Важно, что количество программ, используемых в рабочем процессе, при этом не увеличивается. Ты по-прежнему работаешь с одним Python-интерпретатором, а значит, не нужно читать документацию к незнакомым компиляторам и другим утилитам, которыми ты никогда не пользовался (или пользовался, но давно). Это может служить хорошим стимулом для использования CorePy в промышленном программировании. Библиотека найдет применение в самых разных областях: встраиваемые приложения, научные расчеты, производство игр – и так далее. Отличная технология!

Код нашей функции на CorePy

import corepy.arch.x86.isa as x86
import corepy.arch.x86.platform as env
from corepy.arch.x86.types.registers import *
from corepy.arch.x86.lib.memory import MemRef

code = env.InstructionStream()
lbl_begin = code.get_label('BEGIN_ALL')
lbl_loop = code.get_label('BEGIN_LOOP')
lbl_le = code.get_label('LE')
lbl_end = code.get_label('END_LOOP')
is_finish = esi # флаг завершения
x86.set_active_code(code)

# Непосредственно функционал
# Принимаем через стек два параметра:
# начальный адрес массива и максимальный
# допустимый индекс в нем.
code.add(lbl_begin)
x86.mov(is_finish, 0)
x86.mov(ecx, 0)

code.add(lbl_loop)
# Заносим в edi адрес начала массива
# Он всегда состоит из 4байтных целых чисел
x86.mov(edi, MemRef(ebp, 8))
x86.mov(eax, MemRef(edi, disp = 0, index = ecx, 4)
x86.mov(ebx, MemRef(edi, disp = 4, index = ecx, 4)

# Если порядок сортировки нарушен...
x86.cmp(eax, ebx)
x86.jle(lbl_le)

# меняем элементы местами
x86.mov(is_finish, 1)
x86.mov(MemRef(edi, disp = 0, index = ecx, 4), ebx)
x86.mov(MemRef(edi, disp = 4, index = ecx, 4), eax)

code.add(lbl_le)
x86.inc(ecx)
x86.cmp(ecx, MemRef(ebp, 12)) # уже конец?
x86.je(lbl_end)
x86.jmp(lbl_loop)
code.add(lbl_end)

# Если не было ни одной перестановки,
# то массив отсортирован.
x86.cmp(is_finish, 0)
x86.jne(lbl_begin)

Машинный код, созданный CorePy на основе нашего. Выведен в формате NASM

# Platform: linux.spre_linux_x86_32
BITS 32
SECTION .text
global bubble_sort
bubble_sort:

PROLOGUE:
push ebp
mov ebp, esp
push edi
push esi
push ebx

BODY:

BEGIN_ALL:
mov esi, 0
mov ecx, 0

BEGIN_LOOP:
mov edi, dword [ebp + 8]
mov eax, dword [edi + ecx * 4 + 0]
mov ebx, dword [edi + ecx * 4 + 4]
cmp eax, ebx
jle LE
mov esi, 1
mov dword [edi + ecx * 4 + 0], ebx
mov dword [edi + ecx * 4 + 4], eax

LE:
inc ecx
cmp ecx, dword [ebp + 12]
je END_LOOP
jmp BEGIN_LOOP

END_LOOP:
cmp esi, 0
jne BEGIN_ALL

EPILOGUE:
pop ebx
pop esi
pop edi
leave
ret

Запуск нашей сортировки

import corepy.arch.x86.platform as env

proc = env.Processor()
params = env.ExecParams()

def sort(array):
bi = array.buffer_info()
# Подготовка параметров
params.p1 = bi[0]# начало массива
params.p2 = bi[1] - 1# количество элементов
# Запуск asm - кода!
proc.execute(code, params = params)

DVD

На диске тебя ждут все сорцы к статье, архив CorePy из SVN с примерами и документацией, а также модули SciPy, NumPy и matplotlib, необходимые для построения графиков.

WWW

  • www.corepy.org – официальный сайт проекта. Единственный источник информации по теме!

WARNINIG

CorePy реализован только под Linux и OS X. Версии для Windows не существует в природе!

Содержание
загрузка...
Журнал Хакер #151Журнал Хакер #150Журнал Хакер #149Журнал Хакер #148Журнал Хакер #147Журнал Хакер #146Журнал Хакер #145Журнал Хакер #144Журнал Хакер #143Журнал Хакер #142Журнал Хакер #141Журнал Хакер #140Журнал Хакер #139Журнал Хакер #138Журнал Хакер #137Журнал Хакер #136Журнал Хакер #135Журнал Хакер #134Журнал Хакер #133Журнал Хакер #132Журнал Хакер #131Журнал Хакер #130Журнал Хакер #129Журнал Хакер #128Журнал Хакер #127Журнал Хакер #126Журнал Хакер #125Журнал Хакер #124Журнал Хакер #123Журнал Хакер #122Журнал Хакер #121Журнал Хакер #120Журнал Хакер #119Журнал Хакер #118Журнал Хакер #117Журнал Хакер #116Журнал Хакер #115Журнал Хакер #114Журнал Хакер #113Журнал Хакер #112Журнал Хакер #111Журнал Хакер #110Журнал Хакер #109Журнал Хакер #108Журнал Хакер #107Журнал Хакер #106Журнал Хакер #105Журнал Хакер #104Журнал Хакер #103Журнал Хакер #102Журнал Хакер #101Журнал Хакер #100Журнал Хакер #099Журнал Хакер #098Журнал Хакер #097Журнал Хакер #096Журнал Хакер #095Журнал Хакер #094Журнал Хакер #093Журнал Хакер #092Журнал Хакер #091Журнал Хакер #090Журнал Хакер #089Журнал Хакер #088Журнал Хакер #087Журнал Хакер #086Журнал Хакер #085Журнал Хакер #084Журнал Хакер #083Журнал Хакер #082Журнал Хакер #081Журнал Хакер #080Журнал Хакер #079Журнал Хакер #078Журнал Хакер #077Журнал Хакер #076Журнал Хакер #075Журнал Хакер #074Журнал Хакер #073Журнал Хакер #072Журнал Хакер #071Журнал Хакер #070Журнал Хакер #069Журнал Хакер #068Журнал Хакер #067Журнал Хакер #066Журнал Хакер #065Журнал Хакер #064Журнал Хакер #063Журнал Хакер #062Журнал Хакер #061Журнал Хакер #060Журнал Хакер #059Журнал Хакер #058Журнал Хакер #057Журнал Хакер #056Журнал Хакер #055Журнал Хакер #054Журнал Хакер #053Журнал Хакер #052Журнал Хакер #051Журнал Хакер #050Журнал Хакер #049Журнал Хакер #048Журнал Хакер #047Журнал Хакер #046Журнал Хакер #045Журнал Хакер #044Журнал Хакер #043Журнал Хакер #042Журнал Хакер #041Журнал Хакер #040Журнал Хакер #039Журнал Хакер #038Журнал Хакер #037Журнал Хакер #036Журнал Хакер #035Журнал Хакер #034Журнал Хакер #033Журнал Хакер #032Журнал Хакер #031Журнал Хакер #030Журнал Хакер #029Журнал Хакер #028Журнал Хакер #027Журнал Хакер #026Журнал Хакер #025Журнал Хакер #024Журнал Хакер #023Журнал Хакер #022Журнал Хакер #021Журнал Хакер #020Журнал Хакер #019Журнал Хакер #018Журнал Хакер #017Журнал Хакер #016Журнал Хакер #015Журнал Хакер #014Журнал Хакер #013Журнал Хакер #012Журнал Хакер #011Журнал Хакер #010Журнал Хакер #009Журнал Хакер #008Журнал Хакер #007Журнал Хакер #006Журнал Хакер #005Журнал Хакер #004Журнал Хакер #003Журнал Хакер #002Журнал Хакер #001