Монитор от Герба Саттера

В недавно вышедшем выступлении Герба Саттера посвященном многопоточности он привел интересный пример примитива для синхронного выполнения последовательностей операций. Сам Майерс окрестил детище “монитором”, по аналогии с мониторами из мира Java и C#, хотя на мой взгляд, сходства между ними не так уж и много. Суть задумки в том, что бы синхронизировать работу с каким-либо объектом, который изначально не поддерживает синхронизации. При этом, обеспечив синхронность не только на уровне одной операции, но и на уровне “трансзакции”.

string s = "Start\n";
vector<future <void>> v;

for(int i=0; i&lt;5; ++i)
{
    v.push_back(async([&,i]{
        {
            // необходимо сделать атомарно.
            s += to_string(i) + " " + to_string(i);
            s += "\n";
        }
        {
            // так же необходимо сделать атомарно.
            cout < < s;
        }
    }));
}

В принципе, в приведенном выше примере вполне можно воспользоваться комбинацией mutex + lock_guard, но так не интересно, не красиво, да и о чем было бы рассказывать в течении полутора часов?
Решение предложенно действительно элегантное: Continue reading

RB-tree в sglib

Наткнулся на довольно мерзкий баг, в когда-то уважаемой мной библиотеке sglib. Дело в том, что на определенных наборах данных у rb-tree из этой библиотеки сносит башню! В результате добавленные ранее элементы перестают находиться, хотя, количество элементов не изменяется и при обходе дерева все элементы в нем присутствуют.

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>
#include "sglib.h"

struct rb_tree
{
    int64_t data;
    char color_field;
    struct rb_tree *left;
    struct rb_tree *right;
};
typedef struct rb_tree rb_tree;

#define CMPARATOR(x,y) ((x->data)-(y->data))

SGLIB_DEFINE_RBTREE_PROTOTYPES(rb_tree, left, right, color_field, CMPARATOR);
SGLIB_DEFINE_RBTREE_FUNCTIONS(rb_tree, left, right, color_field, CMPARATOR);

rb_tree *the_tree = 0;

int main(int argc, char *argv[])
{
    if( argc < 2 )
        return -1;

    const char *data_file_path = argv[1];
    FILE *data_file;
    data_file = fopen( data_file_path, "r" );
    if( 0 == data_file )
        return -1;

    uint64_t value;
    rb_tree *node, e;
    e.data = 6610223104;
    int added = 0;
    while( EOF != fscanf( data_file, "%llun", &value ) )
    {
        if( value == e.data )
            added = 1;
        node = malloc( sizeof(rb_tree) );
        node->data = value;
        sglib_rb_tree_add( &the_tree, node );
        if( 0 != added )
        {
            node = sglib_rb_tree_find_member( the_tree, &e );
            if( 0 == node )
                printf("ERRORn");
        }
    }

    return 0;
}

Файл с тестовыми данными.

Ускорение ветвления в C++

Немного поигрался с довольно редко испольуземой при разработке приложений дерективой компилятора __builtin_expect. Эта директива поддерживатеся как Clang, так и в GCC, а в случае с MSVC есть довольно похожая директива __assume, работающая только для switch, и которую, если верить MSDN, использовать не рекомендутся, так как она ведет к потенциальным проблемам. Сказать насколько может быть полезна директива __builtin_expect сложно, но мало ли, к примеру товарищу на моем любимом форуме это зачем-то понадобилось.
Немного о самой __builtin_expect. При генерировании ассемблерных инструкций, компилятор самостоятельно решает о том, какая из ветвей условия должна быть размещена в начале, а к какой необходимо перейти посредством условного перехода. Данное поведение никак не регламентируется стандартом и полностью зависит не только от компилятора, но и от выбранного уровня оптимизации, в чем можно легко убедится получив несколько ассемблерных листингов одного и того же кода. При помощи же __builtin_expect можно указать компилятору какую из ветвей в условии if-else или switch-case разместить первой, а на какую организовать условный переход. Continue reading

Тестовые задания в Яндексе. Часть 2.

Как и планировал, опробовал второй способ сортировки, а именно сортировку подсчетом. Кода в разы меньше, сам код куда проще, но… Крайне плохо масштабируемое решение с сильной зависимостью от количества доступной памяти. Так при использовании максимального количества доступной памяти в 256 Мб, приходится делать 64 прохода по файлу. Если же попытаться разнести чтение и запись (как я писал раньше, асинхронная запись дает ускорение приблизительно в 10-15%) то количество проходов вырастает до 128 и итоговая скорость оказывается даже меньше чем при последовательной обработке. Так же, мое решение не будет корректно работать в том случае, если количество одинаковых элементов превысит максимальное значение помещающееся в size_t.
Тем не менее, сортирует довольно быстро: 1 Гб, в среднем, обрабатывается за 108 секунд.

P.S. а вообще, я выдохся с данной задачкой (как делать ясно, побочные эффекты алгоритмов тоже очевидны), так что вернусь ней… через еще пару лет?

Тестовые задания в Яндексе

Когда-то, давным-давно, в разгар активного поиска работы я написал в Яндекс. Не то что бы я думал туда пройти, все же алгоритмы не моя сильная сторона, но мне подумалось “а почему бы не попробовать, особенно с учетом того, что на РСДНе ходят легенды о полнейшей невменяемости собеседующих там товарищей”. Вобщем решил сходить и чисто позырить. Позырить мне так и не удалось, т.к. яндексовцы дали тестовое задание на дом, а на такое я принципиально не соглашаюсь. Но, надо признать, задание было интересное, и я его прикопал с целью когда-нибудь, когда будет соответствующее настроение, решить. Соответствующего настроения не было у меня два года, и вдруг оно появилось! Continue reading

Поддержка C++11 в Clang

Зашел на страницу “C++11 implementation status” на сайте Clang и обрадовался. В Clang версии 3.1 появятся:

По большому счету, действительно не хватает TLS, которая появится не известно когда, да и все вобщем-то.

Сборка и тестирование проекта при помощи CMake и CTest.

Думаю что большинство C++ разработчиков так или иначе сталкивались с CMake, в то же время что такое CTest и как с его помощью можно автоматизировать модельное тестирование знают далеко не все.
Для того, что бы показать как можно использовать CMake и CTest вместе, я в качестве примера создал маленькую библиотечку, состоящую из пары строк кода, которое умеет складывать и делить Кроме приложений CMake и CTest, понадобится какая-либо UnitTest библиотека (в данном примере я взял Boost.Test, хотя, можно взять и GoogleTest). Тут стоит обратить внимание на то, что CTest не является фрэймворком для написания тестов. CTest – это приложение для запуска тестов и, если это необходимо, отправки результатов в какое-либо из поддерживаемых хранилищ. Continue reading

Классы в Rust

В Rust, зачем-то запихали классы. Видимо для того, что бы было “как у всех”. Ощущения от классов, мягко говоря, противоречивые. Хотя в рассылке и утверждают, что с тем, как классы будут выглядеть еще не определились, но ничто так не постоянно, как все временно. Итак, выглядит это дело следующим образом:

class test_class {
    priv {
        let mut val: int;
    }
    new(val: int) {
        self.val = val;
    }
    fn foo() {
        self.val += 1;
        io::println(#fmt("val+1 == %d", self.val));
    }
}

fn main() {
    let obj = test_class(10);
    obj.foo();
}

Любой класс должен иметь конструктор, в противном случае, компилятор скажет что-то типа следующего:

class.rs:14:0: 14:2 error: class with no ctor

В то же время, никаких подтверждений наличию деструкторов я не нашел. Полагаю, будут, но позже, а сейчас можно воспользоваться типом resource, пусть и будет выглядеть итоговое решение крайне криво.
Вторая не понравившаяся особенность классов, необходимость использовать self для доступа к членам из функций классов. Так же self используется для доступа к функциям класса, что выглядит как некий атавизм.
А в целом… Ну, классы, такие классы…

Перегрузка функций по параметрам. Часть 2.

В результате обсуждения в мэйл-листе Rust вопроса о перегрузке функций, родился еще один довольно занятный вариант:

enum input { int(int), str(str) }

iface to_input { fn to_input() -> input; }
impl of to_input for int { fn to_input() -> input { ret int(self); } }
impl of to_input for str { fn to_input() -> input { ret str(self); } }

fn to_input<T: to_input>(t: T) {
    alt t.to_input() {
        int(v) { io::println("int"); }
        str(v) { io::println("str"); }
    }
}

fn main() {
    to_input(5);
    to_input("hello")  
}

В принципе, выгляди это дело крайне громоздко, но, я думаю, что количество кода можно существенно подсократить засчет использования макросов.

Управление памятью в Rust. Часть 2.

К сожалению, а может и к счастью, Rust не предоставляет возможности создать не управляемый объект в хипе. Так или иначе, объект будет управляться при помощи либо разделяемых, либо уникальных указателей. И в первом и во втором случаях, по входу последнего из указателей за пределы области видимости объект в памяти будет уничтожен. В довольно редких случаях, такое поведение не подходит. В качестве примера можно взять данные, передаваемые в качестве параметра для асинхронной функции в неуправляемую библиотеку.
Для решения подобной задачи остается только одно, выделить память при помощи malloc и не забыть освободить ее при помощи free. Ну и небольшой примерчик того, как облегчить себе жизнь.

unsafe fn mk_mem_obj_copy<T>(src: T) -> *T {
    let size = sys::size_of::<T>();
    let dst = libc::malloc(size);
    libc::memcpy(dst, ptr::addr_of(src) as *libc::c_void, size);
    ret dst as *T;
}

unsafe fn mk_mem_obj<T>() -> *T {
    libc::malloc(sys::size_of::<T>()) as *T
}

unsafe fn mem_obj_free<T>(obj: *T) {
    libc::free( obj as *libc::c_void );
}