Статья для Хабра №6 ‘Транспайлер-цепь Python → 11l → C++ [для ускорения Python-кода и не только]’

.gitignore

/perf_tests

6.pq.txt

[[[
[[[Хабы: C++, Python, Ненормальное программирование]]]
[[[Заголовок: Транспайлер-цепь Python → 11l → C++ [для ускорения Python-кода и не только][[[‘не только’ — имеется в виду использование 11l в качестве более изящной [и кроссплатформенной] альтернативы Bash и Windows Cmd {то есть, когда требуются достаточно несложные действия}, а также для проверки ошибок {как транспайлером Python → 11l → C++, так и компилятором C++} в исходном Python-коде (например: `def minimum(a : int, b : int)...minimum(input(), input())`)]]]]]]
[[[Метки: Python, C++, 11l]]]
]]]
Р‘https://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Python_logo_and_wordmark.svg/250px-Python_logo_and_wordmark.svg.png’Р‘https://upload.wikimedia.org/wikipedia/commons/thumb/8/8d/U%2B2192.svg/100px-U%2B2192.svg.png’Р‘https://avatars1.githubusercontent.com/u/22068453?s=150’Р‘https://upload.wikimedia.org/wikipedia/commons/thumb/8/8d/U%2B2192.svg/100px-U%2B2192.svg.png’Р‘https://upload.wikimedia.org/wikipedia/commons/thumb/1/18/ISO_C%2B%2B_Logo.svg/125px-ISO_C%2B%2B_Logo.svg.png’

В данной статье [[[рассмотрены/]]]рассматриваются наиболее интересные преобразования, которые выполняет цепочка из двух транспайлер[https://ru.wikipedia.org/wiki/Транспайлер]ов (первый переводит код на языке Python в код на ‘новом языке программирования 11l’[http://11l-lang.org/ru/], а второй — код на 11l в C++), а также производится[[[/приводится]]] сравнение производительности с другими средствами ускорения/исполнения кода на Python (PyPy, Cython, Nuitka).
'‘<cut />’'
Н‘Замена "слайсов"\slices на диапазоны\ranges’
Т‘
‘‘Python’ ‘11l’’
‘‘#(Python)‘
s[-1]
s[-2]
s[:-1]
s[1:]
s[:2]
s[1:2]
s[::2]
s[1::2]
s[3:10:2]
’’
‘[[[#(Python) but not #(11l) because with #(11l) ‘s[(len)-2]’ looks as ‘s~‘[(len)-2]’’]]]#(Python)‘
s.last
s[(len)-2]
s[0..<(len)-1]
s[1..]
s[0..<2]
s[1..<2]
s[(0..).step(2)]
s[(1..).step(2)]
s[(3..<10).step(2)]
’
’’’
Явное указание для индексирования от конца массива `s[(len)-2]` вместо просто `s[-2]` нужно для исключения следующих ошибок:
1. Когда требуется к примеру получить предыдущий символ по `s[i-1]`, но при i = 0 такая/данная запись вместо ошибки молча вернёт последний символ строки [и я на практике сталкивался с такой ошибкой — коммит[https://sourceforge.net/p/pqmarkup/code/ci/aad8d2a0d7bf8851371ee28b9d711c4cd476f382/ <- https://bitbucket.org/pqmarkup/pqmarkup/commits/aad8d2a0d7bf8851371ee28b9d711c4cd476f382]].
2. Выражение `s[i:]` после `i = s.find(":")` будет работать неверно когда символ не найден в строке [вместо ‘‘часть строки начиная с первого символа `:` и далее’’ будет взят последний символ строки] (и вообще, возвращать `-1` функцией `find()` в Python-е я считаю также неправильно [следует возвращать null/None (а если требуется -1, то следует писать явно: `i = s.find(":") ?? -1`)]).
3. Запись `s[-n:]` для получения `n` последних символов строки будет некорректно работать при `n = 0`.

Также отказ от поддержки отрицательного `index` в `s[index]` целесообразен с точки зрения производительности — не нужно делать лишнюю проверку на `index < 0`.

Н‘Цепочки операторов сравнения’

На первый взгляд выдающаяся черта языка Python, но на практике от неё легко можно отказаться/обойтись посредством оператора `in` и диапазонов:
Т‘
‘‘`a < b < c`’   ‘`b in a<..<c`’’
‘‘`a <= b < c`’  ‘`b in a..<c`’’
‘‘`a < b <= c`’  ‘`b in a<..c`’’
‘‘`0 <= b <= 9`’ ‘`b in 0..9`’’
’
Н‘Списковое включение (list comprehension)’

Аналогично, как оказалось, можно отказаться и от другой интересной фичи Python — list comprehensions.
В то время как одни ‘прославляют list comprehension и даже предлагают отказаться от filter() и map()’[https://stackoverflow.com/a/3013722/2692494 ‘[[[<- google:‘python filter list’]]]Guido considered removing map, filter and reduce from Python 3’], я обнаружил, что:
1. ‘Во всех местах, где [[[я использую]]]мне встречалось Python's list comprehension, можно легко обойтись функциями `filter()` и `map()`.’{
#(Python)‘
dirs[:] = [d for d in dirs if d[0] != '.' and d != exclude_dir]
dirs[:] = filter(lambda d: d[0] != '.' and d != exclude_dir, dirs)

'[' + ', '.join(python_types_to_11l[ty] for ty in self.type_args) + ']'
'[' + ', '.join(map(lambda ty: python_types_to_11l[ty], self.type_args)) + ']'

# Nested list comprehension:
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
]
[[row[i] for row in matrix] for i in range(4)]
list(map(lambda i: list(map(lambda row: row[i], matrix)), range(4)))
’
}
2. ‘`filter()` и `map()` в 11l выглядят красивее, чем в Python’{
#‘
dirs[:] = filter(lambda d: d[0] != '.' and d != exclude_dir, dirs)
dirs = dirs.filter(d -> d[0] != ‘.’ & d != @exclude_dir)

'[' + ', '.join(map(lambda ty: python_types_to_11l[ty], self.type_args)) + ']'
‘[’(.type_args.map(ty -> :python_types_to_11l[ty]).join(‘, ’))‘]’

outfile.write("\n".join(x[1] for x in fileslist if x[0]))
outfile.write("\n".join(map(lambda x: x[1], filter(lambda x: x[0], fileslist))))
outfile.write(fileslist.filter(x -> x[0]).map(x -> x[1]).join("\n"))
’
} и следовательно необходимость в list comprehensions в 11l фактически отпадает [замена list comprehension на `filter()` и/или `map()` выполняется в процессе преобразования Python-кода в 11l автоматически].

Н‘Преобразование цепочки if-elif-else в switch’

В то время как Python не содержит оператора switch, это одна из самых красивых конструкций в языке 11l, и поэтому я решил вставлять switch автоматически:
Т‘
‘‘Python’ ‘11l’’
‘‘#(Python)‘
ch = instr[i]
if ch == "[":
    nesting_level += 1
elif ch == "]":
    nesting_level -= 1
    if nesting_level == 0:
        break
elif ch == "‘":
    ending_tags.append('’') # ‘‘
elif ch == "’":
    assert(ending_tags.pop() == '’')
’’
‘#(11l)‘
switch instr[i]
    ‘[’
        nesting_level++
    ‘]’
        if --nesting_level == 0
            loop.break
    "‘"
        ending_tags.append("’") // ‘‘
    "’"
        assert(ending_tags.pop() == "’")

’
’’’
‘Для полноты картины вот сгенерированный код на C++’{
#(C++)‘
switch (instr[i])
{
case u'[':
    nesting_level++;
    break;
case u']':
    if (--nesting_level == 0)
        goto break_;
    break;
case u'‘':
    ending_tags.append(u"’"_S);
    break; // ‘‘
case u'’':
    assert(ending_tags.pop() == u'’');
    break;
}
’
}


Н‘Преобразование [[[коротких/]]]небольших словарей в нативный код’

Рассмотрим такую строчку кода на Python:
#(Python)‘
tag = {'*':'b', '_':'u', '-':'s', '~':'i'}[prev_char()]
’
Скорее всего, такая форма записи не очень эффективна [с точки зрения производительности], зато очень удобна.

В 11l же соответствующая данной строчке [и полученная транспайлером Python → 11l] запись не только удобная [впрочем, не настолько изящная как в Python], но и быстрая:
#(11l)‘
var tag = switch prev_char() {‘*’ {‘b’}; ‘_’ {‘u’}; ‘-’ {‘s’}; ‘~’ {‘i’}}
’

Приведённая строчка странслируется в:
#(C++)‘
auto tag = [&](const auto &a){return a == u'*' ? u'b'_C : a == u'_' ? u'u'_C : a == u'-' ? u's'_C : a == u'~' ? u'i'_C : throw KeyError(a);}(prev_char());
’
[Вызов лямбда-функции компилятор C++ встроит\inline в процессе оптимизации и останется только цепочка операторов `?/:`.]

В том случае, когда производится присваивание переменной, словарь оставляется как есть:
Т‘
‘‘Python’ ‘#(Python)‘rn = {'I': 1, 'V': 5, 'X': 10, 'L': 50, ...}’’’
‘‘11l’    ‘#(11l)‘var rn = [‘I’ = 1, ‘V’ = 5, ‘X’ = 10, ‘L’ = 50, ...]’’’
‘‘C++’    ‘#(C++)‘auto rn = create_dict(dict_of(u'I'_C, 1)(u'V'_C, 5)(u'X'_C, 10)(u'L'_C, 50)...);’’’
’

Н‘Захват\*‘Ca’pture[[[/@pture]]] внешних переменных’

В Python для указания того, что переменная не является локальной, а должна быть взята снаружи [от текущей функции], используется ключевое слово nonlocal [в противном случае к примеру `found = True` будет трактоваться как создание новой локальной переменной `found`, а не присваивание значения уже существующей внешней переменной].[[[
В C++ для этого используется список захвата (*‘ca’pture list).]]]
В 11l для этого используется префикс @ (так как он похож на английские буквы Ca):
Т‘><‘‘Python’ ‘11l’’
‘‘#(Python)‘
writepos = 0
def write_to_pos(pos, npos):
    nonlocal writepos
    outfile.write(...)
    writepos = npos
’’
‘#(11l)‘
var writepos = 0
fn write_to_pos(pos, npos)
    @outfile.write(...)
    @writepos = npos

’’
’’
C++:
#(C++)‘
auto writepos = 0;
auto write_to_pos = [..., &outfile, &writepos](const auto &pos, const auto &npos)
{
    outfile.write(...);
    writepos = npos;
};
’

Н‘Глобальные переменные’

Аналогично внешним переменным, если забыть объявить глобальную переменную в Python [посредством ключевого слова global], то получится [[[трудно уловимый/]]]незаметный баг:
Т‘‘
‘#(Python)‘
break_label_index = -1
...
def parse(tokens, source_):
    global source, tokeni, token, scope
    source = source_
    tokeni = -1
    token = None
    break_label_index = -1
    scope = Scope(None)
    ...
’’
‘#(11l)‘
var break_label_index = -1
...
fn parse(tokens, source_)
    :source = source_
    :tokeni = -1
    :token = null
    break_label_index = -1
    :scope = Scope(null)
    ...

’’’’
Код на 11l [справа] в отличие от Python [слева] выдаст на этапе компиляции ошибку ‘необъявленная переменная `break_label_index`’.

Н‘Индекс/номер текущего элемента контейнера’

Я всё время забываю порядок переменных, которые возвращает Python-функция `enumerate` {сначала идёт значение, а потом индекс или наоборот}. Поведение аналога в Ruby — `each.with_index` — гораздо легче запомнить: with index означает, что index идёт после value, а не перед. Но в 11l логика ещё проще для запоминания:
Т‘
‘‘Python’ ‘11l’’
‘‘#(Python)‘
items = ['A', 'B', 'C']
for index, item in enumerate(items):
    print(str(index) + ' = ' + item)
’’
‘#(11l)‘
var items = [‘A’, ‘B’, ‘C’]
loop(item) items
   print(loop.index‘ = ’item)
’
’’’

Н‘Список как значение по умолчанию аргумента функции’

Как известно, запись `def f(l = [])` в Python ‘приводит к нежелательному поведению на практике’[https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument <- google:‘Python list default argument’]. Ниже представлен корректный код на Python и соответствующий ему полученный код на 11l.
Т‘
‘‘Python’ ‘11l’’
‘‘#(Python)‘
def f(l : List[int] = None):
    if l is None:
        l = []
    l.append(1)
    print(l)
’’
‘#(11l)‘
fn f([Int] &l = [Int]())
   l.append(1)
   print(l)


’
’’’

Н‘Двумерные массивы’

В Python для создания двумерного массива размера `n` на `m` вместо `[[0] * m] * n` необходимо/приходится писать `[[0] * m for i in range(n)]`. Но так как в 11l запись `[[0] * m] * n` является [[[допустимой/]]]корректной, транспайлер заменяет списковое включение `[[0] * m for i in range(n)]` на `[[0] * m] * n` для лучшей читаемости [[[генерируемого/]]]сгенерированного кода на 11l и C++.

Н‘Производительность[[[ сгенерированного C++ кода]]]’

В качестве тестировочной используется ‘программа преобразования пк-разметки в HTML’[https://sourceforge.net/p/pqmarkup/code/ <- https://bitbucket.org/pqmarkup/pqmarkup], а в качестве исходных данных берётся исходник ‘статьи по пк-разметке’[https://habr.ru/post/348218/] [так как эта статья на данный момент — самая большая из написанных на пк-разметке], и повторяется 10 раз, то есть получается из 48.8 килобайтной статьи файл размером 488Кб[[[ (этот пример не синтетический, а вполне себе жизненный, так как пк-разметка подходит, также как и Markdown (‘Markdown started to be used beyond the web, to author books’[http://spec.commonmark.org/0.28/#what-is-markdown-]), для написания [электронных] книг)](статья по пк-разметке довольно своеобразная — много таблиц, много спойлеров, много закомментированного текста, поэтому пример скорее синтетический, чем [реальный/]"жизненный")]].

Вот диаграмма, показывающая во сколько раз соответствующий способ исполнения Python-кода быстрее оригинальной реализации [CPython]:
Р‘https://gist.githubusercontent.com/alextretyak/5524244126944a4c39f70341ef21b87a/raw/99affb505cb1563f34ff71034bc776d06cac37e0/chart1.png’
‘А теперь добавим на диаграмму реализацию, сгенерированную транспайлером Python → 11l → C++:’{
Р‘https://gist.githubusercontent.com/alextretyak/5524244126944a4c39f70341ef21b87a/raw/99affb505cb1563f34ff71034bc776d06cac37e0/chart2.png’
Время выполнения [время преобразования файла размером 488Кб] составило 868 мс[[[на Intel(R) Core(TM) i3 CPU M 350 @ 2.27GHz]]] для CPython и 38 мс для сгенерированного C++ кода [это время включает в себя полноценный [т.е. не просто работу ‘с данными в оперативной памяти’[‘в этом случае получается 710 мс для CPython и 19 мс для сгенерированного C++ кода’]] запуск программы операционной системой и весь ввод/вывод [чтение исходного файла [.pq] и сохранение нового файла [.html] на диск]].

Я хотел ещё попробовать ‘Shed Skin’[http://shedskin.github.io], но он не поддерживает локальные функции[[[ и даже не понимает ключевое слово nonlocal]nonlocal нужен как раз только для локальных функций]].
Numba использовать также не получилось (выдаёт ошибку ‘Use of unknown opcode LOAD_BUILD_CLASS’).
‘Вот архив’[https://gist.github.com/alextretyak/5524244126944a4c39f70341ef21b87a/raw/e6cb2f07446ef4a19a3d6cdc1f8c483287ef1308/perf_tests.7z] с использовавшейся программой для сравнения производительности [под Windows] (требуются установленный Python 3.6 или выше и следующие Python-пакеты: pywin32, cython).
}

Исходник на Python и вывод [[[тестировочной программы]]]транспайлеров Python → 11l и 11l → C++:
Т‘‘‘Python[https://sourceforge.net/p/pqmarkup/code/ci/055831213261078276a604c2e1d8e4491897934f/tree/pqmarkup.py <- https://bitbucket.org/pqmarkup/pqmarkup/src/055831213261078276a604c2e1d8e4491897934f/pqmarkup.py]’ ‘‘Сгенерированный 11l’[https://gist.github.com/alextretyak/5524244126944a4c39f70341ef21b87a/raw/c3217e8745443d2f977b4287f3dfd96a4a4e7e13/pqmarkup.11kw]
(с ключевыми словами вместо букв)’ ‘11l[https://gist.github.com/alextretyak/5524244126944a4c39f70341ef21b87a/raw/c3217e8745443d2f977b4287f3dfd96a4a4e7e13/pqmarkup.11l]
(с буквами)’ ‘‘Сгенерированный C++’[https://gist.github.com/alextretyak/5524244126944a4c39f70341ef21b87a/raw/c3217e8745443d2f977b4287f3dfd96a4a4e7e13/pqmarkup.cpp]’’’
[[[P.S. [[[Всем заинтересованным в ускорении имеющихся у вас Python-программ]]]Принимаются заявки на перевод ваших Python-программ в C++ посредством данной цепочки транспайлеров [с целью развития данного проекта].](чтобы не выглядело рекламой)]][[[
> Бесплатно?
< Поскольку я согласен/намерен[/собираюсь] делать только то, что мне интересно, то разумеется бесплатно :)(:!]]]

chart1.png

chart2.png

chart_prime.xls

charts.xls

perf_tests.7z

pqmarkup.11kw

pqmarkup.11l

pqmarkup.cpp