Talk: What every programmer should know about merging branches in Mercurial

Using named branches in Mercurial can be rather difficult especially when it gets to merging these branches. There are several useful techniques and process improvements that simplify the development/release loop. You can find some of them in the talk slides I did on Oct 11, 2012 here at Quickoffice(aka DoctorMobile). It doesn't restrain any development flow and can be useful for any Mercurial (or even non-Mercurial) user. For those who are not familiar with Mercurial at all I recommend to read some guides before looking at the slides. What every programmer should know about merging branches in Mercurial Sources for the slides can be found here

Counting bits

How would you count the number of bits set in a 32-bit integer? This question is amongst the favorite interviewing questions. The naïve approach is to loop through the bits aggregating the sum in a variable. It's already fast enough but you can make the interviewer happy with a much better "lookup table" solution: just use a static 256-entry table that contains pre-evaluated bits count for any 8-bit integer. With such table you need only 4 lookups and 4 summations to get the answer. "Lookup table" algorithm is even implemented as a GCC builtin function. Take a look at the code:

#include <stdint.h>

const uint32_t tbl[] = {
4181239173/*,lots of random data, I used 16384 integers for tests*/,2866015773 } ;

#define TEST_COUNT 100000
static const uint32_t ARRAY_SIZE = sizeof(tbl)/sizeof(tbl[0]);

int main()
{
 uint32_t i = 0;
 volatile register uint32_t c;

 for (; i< TEST_COUNT; ++i)
 {
  uint32_t j = 0;
  for (; j < ARRAY_SIZE; ++j)
  {
   c = __builtin_popcount(tbl[j]);
  }
 }
}

Here __builtin_popcount is a function that calculates the population count. If compiled with

gcc -O3 t.c -o bitcount

one can get such results:

$ time ./bitcount 
real 0m17.465s
user 0m17.425s
sys 0m0.000s

Not too fast, huh? Some of the time is wasted calling the function and inlining it can speed up things. But! There is even a better way. Compiling it with

gcc -O3 -mpopcnt t.c -o bitcount

results in:

$ time ./bitcount 
real 0m1.738s
user 0m1.728s
sys 0m0.004s

That's simply because modern processors have POPCNT instruction that can be used to count the number of bits and GCC is nice enough to support it. As you can see, in this case hardware optimization beats smart algorithm design with ease.

Resume

Algorithms are designed on paper but executed on a real hardware. Knowing what your hardware is capable of is a must for a software engineer. And please don't tell me about all these patterns and object-oriented stuff: unless you invent a machine that can run concepts instead of machine instructions, you must be aware of all the low-level stuff because it will save lives because I don't want to buy a new laptop capable of running new version of nano/Notepad.

I also highly recommend an awesome article "Benchmarking CRC32 and PopCnt instructions" for further reading.

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.

Kharkov DOU Hackathon - отчёт об участии

A hackathon, a hacker neologism, is an event when programmers meet to do collaborative computer programming(c) wiki

Вышеобозначеный хакатон проходил в Харькове 30-31 августа в соревновательном виде. За сутки нужно было написать что-нибудь интересное и команда Von Neumann Architecture в составе двух человек приняла вызов. В качестве задачи мы выбрали портирование Pascal игрушки 1994-го года на HTML5/JS посредством написания Haskell транслятора. Исходники здесь. Полноценный отчёт можно почитать здесь. Также можно посмотреть онлайн демку, демка доделывалась уже после Хакатона. Цитата:

Повторяю, вы видите как работает интерпретатор многопоточного (yield) Javascript, сконвертированного (via Haskell) из Turbo Pascal, сам интерпретатор Javascript-а "Rhino" написан на Java, портирован (via gwt + ножницы) в Javascript.
Внизу работающая программа, проверено под Chrome, Mozilla. Если в опере загрузить ее отладчик DragonFly, то там отчего-то тоже начинает работать.

ICFPC 2011

(((S (K (S ((S (K S)) ((S (K (S I))) K))))) ((S (K K)) K)) awesome! was ICFPC)

ICFP Contest 2011 точно войдет в список лучших ICFP контестов всех времен. Причина тому - интересное непутанное задание, которое при этом довольно сложное и хорошо продуманное. Я, как и в прошлом году, принимал участие в составе команды THIRTEEN. Отчёты от команды можно найти на сайте http://thirteen.kharkov.ru(сейчас там только один отчёт). Здесь постараюсь дать описание контеста со своей точки зрения.
Для меня контест начинался вдали от команды(я находился в командировке в Лондоне). Прочтение задания вызвало бурную радость(я как раз готовился к контесту написанием парсера и эвалуатора для лямбда-калькулюса). Из-за удаленности от команды я решил код не писать, а сосредоточиться на изучении того, что мы можем сделать с помощью карт. Это оказалось правильным решением - мои коллеги написали всё намного быстрее и лучше, чем с моим участием :) Первая ночь прошла в попытках использовать Y комбинатор для создания рекурсивных функций. К сожалению, strict evaluation не давал этого сделать. И даже Y комбинаторы для applicative order не работали. Также не получалось и организовать рекурсию через SII. Утром пятницы я отправился на работу, но потратил большую часть рабочего времени на исследование системы. Результатом этого стала "недорекурсия" через get ячейки. А по окончанию рабочего дня пришло лучшее понимание того, как работает вычисление в предложенной системе, и это дало возможность вывести настоящую рекурсию по аналогии с выводом Y комбинатора. Это позволило писать рекурсивные функции, пробегающие по всем ячейкам. К счастью, организаторы ограничили количество аппликаций одной тысячей(к счастью - потому что увеличение количества аппликаций до 3839 позволило бы уничтожать противника где-то на 85 ходу). И из-за этого ограничения рекурсивные функции пробегались только по нескольким ячейкам и самоуничтожались после применения.
К этому моменту в Харькове был написан конвертер из лямбда выражений в SKI выражения и конвертер из SKI выражений в программы. В ночь с пятницы на субботу я пытался оптимизировать конвертер и генерировать с его помощью выражения, вызывающие рекурсивный обход ячеек. Результат: больше 89 ячеек за один запуск для односложных команд при помощи настоящей рекурсии не обойти. Ночью же вылетел в Харьков(и наконец выспался в самолете). По прилету обнаружил, что коллеги вовсю думают над однотактными и двухтактными пушками. Идея была в том, чтобы создать пушку, которая будет уничтожать вражескую ячейку и восстанавливать после этого vitality. Двухтактная пушка перенаправлялась на следующую ячейку двумя тактами, однотактная(гениальное изобретение Sas/Rst) - одним. К вечеру пришло осознание того, что нам нужно писать хитрого стратега, который будет решать, какие выражения применять. San создал инфраструктуру для написания ботов-стратегов, и к этому моменту был написан язык для описания действий(by San/Dzhulgakov). Я продолжал в душе лелеять надежду на использование рекурсивных выражений и начал создавать ботов и стравливать их в турнире. Конечным результатом этого процесса к 10 утра воскресенья стал SuicideBot(убийца-камикадзе) и, главное, ZombaBot - бот, который за ~150 ходов уничтожал ~40 ячеек противника, а еще за ~90 ходов стирал всю информацию из них. Начальная стратегия использовала настоящую рекурсию(синтаксис языка не приводится):

power@0 = 8192;
@1 = (S (attack 0 0) (attack 1 0) (get 0));
pois@2 = ^x. (help x x @power);
part@3 = ^n.^f. (f (S @pois succ n) f);
part_func@4 = ^y. (@part (y 0) ) @part;
@5 = (dec 0) (zombie 0 @part_func);
newpois@6 = ^xx. (zombie xx I);
newpart@7 = ^nn.^ff. (ff (S @newpois succ nn) ff);
newpart_func@8 = (@newpart 219) @newpart;

Также в это время формируется SanBot(by San) - консервативный бот, который умеет защищаться, уничтожая "горячие" ячейки противника. В свободное время он собирает более быстрые атакующие программы и переключается на них. San постоянно развивал своего бота, тренируясь на кошках - на SuicideBot и ZombaBot. В схватках с ZombaBot он научился закрывать порталы для зомби, а по дороге научился воскрешаться, восстанавливать команды из кеша, красть константы. ZombaBot тоже не стоял на месте. Sas подхватил идею с использованием copy для организации рекурсии и придумал, как с ее помощью сделать обход ячеек. В конечном итоге, этот способ и оказался самым эффективным способом обхода. Он дал возможность ZombaBotу полностью уничтожать противника за 4 запуска рекурсивного зомби, за 198 тактов. К этому времени submissionы SanBotа показали, что он слишком консервативен, и поэтому не столь эффективен. Воспользовавшись наработками, я добавил еще и UndeadRiseBotа - бота, который пытался уничтожить противника за 198 ходов, а после этого переключался на SanBotа. Этот бот оказался весьма эффективным - он крошил противников на неофициальном сервере и даже побеждал самого SanBotа, потому что использовал его же механизмы лечения. Мы продолжали развивать эту идею и оптимизировать код. Результат(язык получился довольно мощный и выразительный, а к концу контеста Dzhulgakov добавил в него и средства для ручной оптимизации):

power@0 = 8192;
@24 = (attack 0 0) (get 0);
@24 = (attack 1 0) (get 0);
pois@1 = ^x. (help x x @power);
!clear @0;
part@0 = \x. ((@pois x) (copy (K 0 x)) (succ x));
!clear @1;
part_func@1 = ^z.^y. ((get 0) (y z));
@128 = (S zombie @part_func);
// optional dec 0; here is done by UndeadRiseBot 
@128 += @@ 0;
address@2 = 66;
@129 ~ zombie1 = (zombie 0 (@part_func @address));
// optional dec 0; here is done by UndeadRiseBot 
!continue zombie1;
@2 += dbl @@;
@130 ~ zombie2 = (zombie 0 (@part_func @address));
// optional dec 0; here is done by UndeadRiseBot 
!continue zombie2;
!clear @2;
@2 = 198;
@131 ~ zombie3 = (zombie 0 (@part_func @address));
// optional dec 0; here is done by UndeadRiseBot 
!continue zombie3;

Этот вариант уничтожал противника за 177 ходов. В копилке наших знаний есть еще парочка оптимизаций, которые должны уменьшить код до 171-172 ходов. Хочется верить, что это минимальная программа, которая уничтожает безвольного противника.
Всё это время Sas собирал своего бота - SasBot, который использовал супероружие - зомбопушку (убить+стереть). Он добился того, что своей пушкой уничтожал и SanBotа, и UndeadRiseBotа. Но, к сожалению, он был готов слишком поздно и не очень хорошо справлялся с реальными противниками на официальном сервере, поэтому в последний момент было решено сабмитить UndeadRiseBota, который в душе - SanBot.

Выводы по окончанию контеста: по результатам битв на неофициальном сервере видно, что наш бот неплох, но далеко не лучший. Что особенно интересно - есть сильные боты, которые используют сходную с нами тактику, но при этом побеждают нас. Это значит, что мы просто не отладили бота окончательно. Еще стоит пожалеть о судьбе SasBotа. Он был готов слишком поздно, чтобы его достижения использовать в SanBot/UndeadRiseBot, и не был готов к submission самостоятельно. Основной вывод - нужно было начинать создавать ботов и описывать стратегии раньше. Тогда к концу контеста у нас бы было лучшее понимание того, какая тактика оптимальна.

Как я уже говорил выше - один из лучших ICFP contests за всё время, что я о нём знаю. Спасибо организаторам - великолепное задание и отличная организация. Спасибо каждому из команды THIRTEEN. Мне кажется, мы отлично сыгрались и можем и будем таким составом выигрывать :)