Ruby-like blocks and yield "keyword" in C

Today I want to show you some of the plain old C black magic. This is the magic of direct user context manipulating. You can use this low-level feature to implement some high-level language abstractions such as generators and ruby-like blocks. Let's start with an example(test1.c):

#include <stdio.h>
#include <string.h>
#include "gens.h"
#include "cblocks.h"


int main(int argc, char** argv)
{
    EXECUTE_BLOCK(enumerate, (1, 10), int, x)
        printf("Got %d\n", *x);
    END_BLOCK
    char* buf = "Hello, world!";
    EXECUTE_BLOCK(enumerate, (1, 4), int, z)
        printf("Saying it %d time\n", *z);
        EXECUTE_BLOCK(for_each, (buf, buf + strlen(buf)), char, c)
            printf("%c.", *c);
        END_BLOCK
        printf("\n");
    END_BLOCK

    return 0;
}

The code above is a valid C code. It produces such output:

Yielding 1
Got 1
Yielding 2
Got 2
Yielding 3
Got 3
Yielding 4
Got 4
Yielding 5
Got 5
Yielding 6
Got 6
Yielding 7
Got 7
Yielding 8
Got 8
Yielding 9
Got 9
Yielding 1
Saying it 1 time
H.H.e.e.l.l.l.l.o.o.,.,. . .w.w.o.o.r.r.l.l.d.d.!.!.
Yielding 2
Saying it 2 time
H.H.e.e.l.l.l.l.o.o.,.,. . .w.w.o.o.r.r.l.l.d.d.!.!.
Yielding 3
Saying it 3 time
H.H.e.e.l.l.l.l.o.o.,.,. . .w.w.o.o.r.r.l.l.d.d.!.!.

Let's take a look on the implementation of used generators (enumerate, for_each in gens.c):

#include "gens.h"
#include <stdio.h>

START_GENERATOR(int, enumerate, (int start, int end))
    int i = start;
    for(; i<end; ++i)
    {
        printf("Yielding %d\n", i);
        YIELD(i);
    }
END_GENERATOR

START_GENERATOR(char, for_each, (char* start, char* end))
    while (start != end)
    {
        YIELD(*start);
        YIELD(*start); // intentionally
        ++start;
    }
END_GENERATOR

As you can see, the implementation of generators is pretty straightforward. All the magic is done in cblocks.h:

#include <stdlib.h>
#include <ucontext.h>

#define DECLARE_GENERATOR(type, name, params) extern ucontext_t name ## _context__; \
extern ucontext_t name ## _out_context__; \
extern int name ## _finished__; \
extern type name ## _out_var__; \
extern void name ## _fun__ params

#define START_GENERATOR(type, name, params) ucontext_t name ## _context__; \
ucontext_t name ## _out_context__; \
int name ## _finished__ = 0; \
type name ## _out_var__; \
void name ## _fun__ params \
{ \
name ## _finished__ = 0; \
int* current_finished = & name ## _finished__; \
ucontext_t* current_context = & name ## _context__; \
ucontext_t* current_out_context = & name ## _out_context__; \
type* current_var = & name ## _out_var__;

#define END_GENERATOR *current_finished = 1; \
}

#define YIELD(x) *current_var = x; swapcontext(current_context, current_out_context);
#define EXECUTE_BLOCK(gen, params, type, varname) do{ type* varname = & gen ## _out_var__; \
ucontext_t* current_context = & gen ## _context__; \
ucontext_t* current_out_context = & gen ## _out_context__; \
volatile int gen ## _temp_var__ = 0; \
getcontext(& gen ## _out_context__); \
if (gen ## _temp_var__ == 0) \
{ \
    gen ## _temp_var__ = 1; \
    gen ## _fun__ params; \
}\
else \
{ \
    while (! gen ## _finished__) { 
         
#define END_BLOCK swapcontext(current_out_context, current_context); } \
} \
} while(0);

Manual pages for swapcontext and getcontext can help in understanding what's going on here.

Resume

• It's possible to implement nifty language features in C using its low-level features. The generators described above can be even used to build cooperative multitasking systems.
• It doesn't mean that you should do it just because you can ;). Beware that context manipulating doesn't work on all platforms.
• You can find the source code on github. The code should be considered just a playground so please forgive me its untidiness. If you want something mature(e.g., you're seeking for coroutines support in C), check out the libtask, libtorque or libcoro

As always I will be happy to accept any criticism on the code above. Feel free to contact me in any way you can imagine.

Сказ о том, как Python С++ обогнал

Я всегда защищаю С++, когда приверженцы других языков ругают его за невыразительный синтаксис, чрезмерную сложность или раздутость, потому что, по-моему мнению, на С++ можно писать красиво, и особенно в этом помогают различные высокоуровневые конструкции из стандартной библиотеки.
В одном из споров в c_plus_plus@c.j.r речь зашла о том, какой же из языков лучше - простой С или всё же С++? В качестве одного из аргументов я предложил провести эксперимент - сколько времени понадобится для решения простой задачи: из stdin считываются строки текста, и после этого в обратном порядке записываются в stdout, т.е., первая строка в stdin становится последней в stdout. Длина строк не ограничена, поэтому для решения ее на С понадобится выделять и перевыделять память, от этого код на С разбухнет, что станет наглядной демонстрацией превосходства высокоуровневых конструкций С++. Более того, я предположил, что код на С++ может быть даже производительней кода на С, написанного без дополнительного профилирования - ведь контейнеры С++ выделяют память так, чтобы reallocate происходил реже. Пример кода на С++, написан за пару минут для демонстрации:

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> v;
    while(std::cin)
    {
        std::string s;
        std::getline(std::cin,s);
        v.push_back(s);
    }
    for (std::vector<std::string>::reverse_iterator it = v.rbegin();it!=v.rend();++it)
    {
        std::cout<<*it<<"\n";
    }
}

Как видите, код далеко не оптимален, однако мне хотелось показать, что даже такое решение лучше, чем код на С.
Тут же захотелось проверить, а как другие языки справятся с этой задачей. Например,однострочник на Ruby:

$stdin.readlines.reverse.join.display

Когда я протестировал его на небольших файлах, С++ решение оказалось быстрее решения на Ruby в десятки раз, что меня нисколько не удивило. Однако для чистоты эксперимента я решил увеличить размер файла. Я сгенерировал файл в 100 строк общим размером ~600mb(исходник на Python):

open("/tmp/z.txt",'w').write((''.join(map(str,xrange(1000000)))+'\n')*100

Результаты тестирования на нём были просто поразительны:

ruby 1.8.6 (2009-06-08 patchlevel 369) [i686-linux]:
real 0m9.841s
user 0m0.849s
sys 0m7.206s

gcc (GCC) 4.1.2 (Gentoo 4.1.2 p1.3):
real 0m51.902s
user 0m48.682s
sys 0m1.429s

Я тут же решил проверить решение на Python:

import sys
sys.stdout.write('\n'.join(reversed(sys.stdin.readlines())))

Результаты:

Python 2.6.2
real 0m4.855s
user 0m0.913s
sys 0m1.233s

Т.е., еще быстрее, чем ruby (что уже не удивительно ;) ). Просмотрев код на С++, я добавил простейшую оптимизацию, которую изначально добавлять не хотел, чтобы код совсем не был похож на С. Я добавил хранение в векторе указателей, а не строк, что должно было убрать ненужное копирование:

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string*> v;
    while(std::cin)
    {
        std::string * s = new std::string();
        std::getline(std::cin,*s);
        v.push_back(s);
    }
    for (std::vector<std::string*>::reverse_iterator it = v.rbegin();it!=v.rend();++it)
    {
        std::cout<<*(*it)<<"\n";
        delete *it;
    }
}

Но результат всё так же не вдохновляет:

real 0m46.444s
user 0m43.462s
sys 0m1.379s

Назначив ответственным за тормоза std::string, я попытался переписать всё на QString из Qt, которые, по слухам, умеют copy-on-write и вообще быстрые. Наивный код:

#include <iostream>
#include <QtCore/qstring.h>
#include <QtCore/qlist.h>
#include <QtCore/qtextstream.h>
#include <vector>

int main() {
    QList<QString> v;
    QTextStream st (stdin);
    QTextStream sto (stdout);
    while(!st.atEnd())
    {
        v.push_back(st.readLine());
    }
    QListIterator<QString> it(v);
    it.toBack ();
    while (it.hasPrevious ())
        sto<<it.previous()<<"\n";
}

Однако это решение пожрало все 2 гигабайта моей оперативной памяти и я его остановил, попросив Qt-шников с c_plus_plus@c.j.r помочь с оптимизацией. После нескольких минут получился вот такой код, который использовал уже 1.4 гигабайта оперативки:

#include <iostream>
#include <QtCore/qstring.h>
#include <QtCore/qlist.h>
#include <QtCore/qtextstream.h>

int main ()
{
    QList<QByteArray> v;
    QTextStream st (stdin);
    QTextStream sto (stdout);
    int line = 0;
    while (!st.atEnd ())
    {  
        std::cerr << "Reading line... " << line++ << std::endl;
        v.push_back (qCompress (st.readLine ().toUtf8 (), 9));
    }
    QListIterator<QByteArray> it (v);
    it.toBack ();
    while (it.hasPrevious ())
    {  
        std::cerr << "Writing line... " << std::endl;
        sto << qUncompress (it.previous ()) << "\n";
        sto.flush ();
    }
}

Однако он работал еще медленнее, чем на стандартных строках - более двух минут. Для чистоты эксперимента я также написал вариант на Python, который не использовал стандартные join и reversed, а был более похож на код на С++:

import sys
s = sys.stdin.readlines()
for x in xrange(len(s)-1,-1,-1):
    sys.stdout.write(s[x]+'\n')

Его результаты:

real 0m2.198s
user 0m0.884s
sys 0m1.190s

Выводы

Если не учитывать опыты с Qt(всё равно ведь хороших результатов добиться не удалось), ни в одном из языков не было использовано каких-либо особых оптимизаций, напротив, были использованы те конструкции высокого уровня, которые предлагает сам язык. И удивительно, что программы на Python и Ruby смогли с большим отрывом обогнать аналогичную программу на С++. Я сам еще не знаю причину этого, и я был бы очень рад, если бы кто-то смог прогнать аналогичные тесты у себя на машине. Однако вне зависимости от причины, такой результат явственно говорит одно - нельзя безоговорочно верить в то, что С++ быстрее интерпретируемых языков, особенно если простейшие высокоуровневые конструкции в них, такие как строки, работают лучше.

P.S.

Я не старался создать идеальные условия для тестирования и не прогонял тесты сотни раз, чтобы получить идеальный результат. Достаточно всего-лишь заметить, что в этом синтетическом тесте Python был в 2-5 раз быстрее Ruby, а Ruby была в 4-5 раз быстрее С++. Спасибо за внимание!

Частичная реабилитация(update)

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

int main() {
    std::ifstream fin("/dev/stdin");
    std::vector<std::string*> v;
    while(fin)
    {
        std::string * s = new std::string();
        std::getline(fin,*s);
        v.push_back(s);
    }
    for (std::vector<std::string*>::reverse_iterator it = v.rbegin();it!=v.rend();++it)
    {
        std::cout<<*(*it)<<"\n";
        delete *it;
    }
}

real 0m1.783s
user 0m0.656s
sys 0m1.070s

Т.е., тормозил std::cin. Естественно, это не оправдание, поэтому реабилитация только частичная. Вывод: tools don't kill software. people kill software.

Reia - скриптовый язык для виртуальной машины Erlang`а

Лично я считаю Erlang одним из самых простых яызков программирования, а среди знакомых мне функциональных языков - самым простым. К тому же на Erlang благодаря его направленности на создание конкурентных приложений написано уже множество проектов, таких как Yaws, CouchDB, ejabberd, которые являются для него наилучшей рекламой.
Таким образом, Erlang - функциональный язык с простым и понятным синтаксисом, который нашёл свою нишу, и если вы интересуетесь созданием масштабируемых конкурентных систем - вам стоит выучить его. Однако из-за того, что Erlang - функциональный, его синтаксис и стиль понятен не всем - он слишком отличается от императивных языков(таких как С и подобные) и даже от Ruby/Python, которые включают в себя частицы функционального подхода.
Если Вы столкнулись с такой проблемой - обратите внимание на Reia - скриптовый Ruby/Python like язык для виртуальной машины BEAM(эта виртуальная машина используется также и в Erlang). Язык Reia совместим с Erlang и может использоваться для создания конкурентых приложений, однако используя при этом скриптовый синтаксис. Вот простейший пример:

module Foo
    def bar
        receive
        when msg
            ["Received ",msg].join().puts()
            bar()
pid = Process.spawn(fun {Foo.bar()})
pid ! "Hello"
pid ! "World"

Результат:

Received Hello
Received World

В язык заложено очень много возможностей(как по мне - слишком много :) ): отсылка сообщений процессам и объектам, встроенные регулярные выражения, pattern matching, асинхронные вызовы функции, лямбда функции, а также многое-многое другое. Многое из этого не реализовано(например, циклы), но часть функциональности уже существует и работает, как можно увидеть из примера.

Выводы

1. Reia - многообещающий ЯП, которому, однако, не хватает разработчиков. Возможно, если реализации будет уделяться больше времени, то этот ЯП станет мостиком, по которому толпы приверженцев императивного подхода ринутся в страну Erlang
2. Как по мне, синтаксис Reia перегружен. Этот вывод только подкрепляет моё убеждение, что Erlang - отлично спроектирован и очень элегантен