11

no except

Posted by savage309 on Sep 22, 2014 in Професионални

Ето една интересна лекция на Meyers, в която той обяснява много добре какво е std::move, std::forward и noexcept :)

Към средата има една част, в която е показано колко по-бърз може да е кода, когато е с noexcept там, където е възможно. Освен това имаше показани примери, как чрез проста смяна на компилатора със C++11/14 enabled такъв, кода става по-бърз. Във връзка с noexcept се появи в един момент и тази графика.

Колко хубаво, помислих си .. Ще направим сега едно NOEXCEPT макро (което ще е #define NOEXCEPT noexcept когато компилираме със С++11/14 компилатор), ще прекомпилираме всичко което имаме (и вкъщи и в офиса) с него и ще получим ей така едни проценти забързване от нищото ..

Та изрових една моя стара (С++98) микро библиотека за математика (вектор, точка, матрица, quaternion, в общи линии това) и реших да завъртя един цикъл с тях (тя всъщност е толкова проста, че не очаквах каквито и да е разлики в резултатите).
Ползвам clang-600.0.51(llvm 3.5svn), компилирам с -Os (което е по дефаулт) (с -O3 резултатите са почти същите) и C++14 enabled.

Кода от теста се намира тук.

Интересно, че противно на приказките на Meyers, Chandler (from LLVM) и не знам си кой друг, на моята машина (I7-3615QM) кода върви по-бавно с между 2 и 5 процента, когато функциите имат noexcept.
Или аз го ползвам много не както трябва, или някой някъде малко послъгва …

 
0

No country for old men

Posted by savage309 on Aug 24, 2014 in Професионални

Още един “benchmark” между ARM и Intel CPUs (идеята за него дойде след като разни JS benchmark-ове на iPad Mini Retina минаваха само 2-3-4 пъти по-бавно от колкото на i7 2600 … Логичният въпрос, който някой (Тео) зададе беше дали наистина е толкова по-бавен, на приложение като raytracer).

Тестваме smallpt (не че това е представителен raytracer, но е raytracer), naive quick sort, random mem access & floating point operations. Кода на тестовете е тук.

Тестваме I7-3720QM (2.6GHZ) (Macbook Pro Retina 2012) vs 64-bit A7 (1.3GHZ) (iPad Mini Retina).

Тестваме еднонишково.

Тестваме с clang-503.0.40 (based on LLVM 3.4svn) (с опции -O3, relaxed IEEE & strict aliasing).

Основният тест е smallpt, покрай него има и няколко проби с по-прости сметки.
Тестовете са правени по 5 пъти (да, само 5), максималната разликата в резултатите на Intel-a е в рамките на 8% (което е бая), а на iPad-a e в рамките на 2%.

По време на тестовете не е имало други пуснати приложения (а лаптопа не е бил в power-save mode, etc). Сиреч, почти може и да си помисли човек да им вярва.

Показани са усреднените стойности на времето, което е отнел всеки тест в секунди (тоест, по-ниските правоъгълничета означават по-добри резултати).

Ако някой има С/С++/Objective-C/Swift код който иска да бъде тестван, PM me :).

Като цяло, резултатите са такива, каквито се предполагаше че ще бъдат.

There is no country for old men.

p.s. през *почти* същите тестове мина и един iPhone 4, с ~ резултати Raytrace:240s, Sort:72s, Mem:56s, FPU 21s.

 
2

VTable по поръчка

Posted by savage309 on May 14, 2014 in Професионални

Ето в това видео от Going Native 2013 A. Alexandrescu разказва за някои от проблемите, които виртуалните функции в С++ създават. А именно : всеки обект държи по един (или повече) 64 битов (най-често) указател към виртуалната таблица, това измества разни неща от cache-а; винаги този указател седи в началото на обекта (а в началото е добре, да има неща които се ползват по-често. Това може да е указателят към виртуалната таблица, но може да е друго :)). Рядко в живота може човек да се докара до там, че да иска и това да забързв. Но се случва.

Идеята е да си напишем наша имплементация на виртуални функции, която да ползва не 64 битово число, ами 8 (така ще се ограничим по максимален брой виртуални функции в интерфейс или по максимален брой класове в йерархия, но 256 (2^8) често е повече от достатъчно).

Ето и примерна имплементация (с малко macro-та и нагласявки :)). На места е малко redundant; мисля че може да се постигне и по-приятен синтаксис.

 
//custom vtable that uses 8 bits for vtable ptr, in stead of 64 bits
//the vtable ptr is first in the mem layout, aways there and aways giving us that +1 cache miss
//this vtable implementation is slimmer in terms of memory and as fast as c++ vtable (this two facts = (probably) faster code)
//it is ugly, but that should not scares you
//there may be some (macro) redudancy, but this is just a PoC
//credits : a.alexandrescu, going native 2013.
 
#include <iostream>
 
//add some dummy defines for having semantic in some places
#define CLASS(X) X
#define INTERFACE(X) X
#define NAME(X) X
#define RETURN(X) X
#define PARAM0(X) X
#define PARAM1(X) X
 
//our virtual functions will be static functions with "this" as 1st argument
#define VIRTUAL static
 
//declare (virtual) interface method; syntax:
//VTABLE_METHODN_DEFINE(0, InterfaceName, MethodName, MethodReturnType, Param0Type, ..., ParamN-1Type)
//first int goes from 0 to n (every next method has idx the idx of the previous+1)
//*this should be used to declare the interface methods in the interface class*
#define VTABLE_METHOD0_DEFINE(IDX, CLASS, NAME, RETURNTYPE) \
                    RETURNTYPE NAME() {  typedef RETURNTYPE (*name_t)(CLASS&); return ((name_t)(vtbl[this->tag*CLASS_LAST + IDX]))(*this); }
 
 
#define VTABLE_METHOD1_DEFINE(IDX, CLASS, NAME, RETURNTYPE, PARAM0) \
                    RETURNTYPE NAME(PARAM0 p0) { typedef RETURNTYPE (*name_t)(CLASS&, PARAM0); return ((name_t)(vtbl[this->tag*CLASS_LAST + IDX]))(*this, p0); }
 
//fills in vtable; syntax:
///REGISTER_METHODN(TheMethodIdx, Interface, ClassThatImplementsTheInterface, MethodReturnType, Param0Type, ..., ParamN-1Type)
///*to be used in the "init" proc*
#define REGISTER_METHOD0(METHOD, BASE, DERIVE, RETURNTYPE, NAME) { RETURNTYPE (*ptr)(BASE&); ptr = DERIVE::NAME; BASE::vtbl[DERIVE::ID*CLASS_LAST + METHOD] = (BASE::FP)ptr; }
#define REGISTER_METHOD1(METHOD, BASE, DERIVE, RETURNTYPE, NAME, PARAM0) { RETURNTYPE (*ptr)(BASE&, PARAM0); ptr = DERIVE::NAME; BASE::vtbl[DERIVE::ID*CLASS_LAST + METHOD] = (BASE::FP)ptr; }
 
#define TAG(X) tag = X;
 
//every class hierarchy with all of its classes has separate enum
//we use this and the next enum to calculate the method position in the vtable
enum {
    CLASS_BASE = 0,
    CLASS_DERIVED,
    CLASS_DERIVED_2,
    CLASS_LAST=CLASS_DERIVED_2,//because of some funny ptr arithmetic
};
//lets give names to the method indexes
enum {
    METHOD_GET=0,
    METHOD_SET=1,
    METHOD_LAST,
};
 
//every base class has :
//1. tag - every hierarchy class writes its id there
//2. static vtable
 
//every hierarchy class has :
//1. static ID
 
//example of base class and 2 derived classes
class Base {
protected:
    //specifies the object type
    uint8_t tag;
public:
    //specifies the class type
    static const int ID = CLASS_BASE;
    //**
    //vtable
    typedef void (*FP)();
    static FP vtbl[(CLASS_LAST+1) * METHOD_LAST];
    //**
    Base() {
        //set the obj type
        TAG(ID);
    }
 
    //define the interface methods
    VTABLE_METHOD0_DEFINE( METHOD_GET,
                           INTERFACE(Base),
                           NAME(get),
                           RETURN(int)
                          );
 
    VTABLE_METHOD1_DEFINE( METHOD_SET,
                           INTERFACE(Base),
                           NAME(set),
                           RETURN(void),
                           PARAM0(int)
                          );
 
    //implement the interface methods
    VIRTUAL int get(Base& self) {
        throw std::bad_function_call();
    }
 
    VIRTUAL void set(Base& self, int) {
        throw std::bad_function_call();
    }
};
 
//
 
class Derived : public Base {
    int i;
public:
    static const int ID = CLASS_DERIVED;
 
    Derived() {
        TAG(ID);
    }
 
    VIRTUAL void set(Base& self, int j) {
        Derived& myself = static_cast<Derived&>(self);
        myself.i = j;
        std::cout << "set" << std::endl;
    }
 
    VIRTUAL int get(Base& self) {
        Derived& myself = static_cast<Derived&>(self);
 
        int res = myself.i;
        std::cout << "get " << res << std::endl;
        return res;
    }
};
 
//
 
class Derived2 : public Derived {
    float f;
public:
    static const int ID = CLASS_DERIVED_2;
 
    Derived2() {
        TAG(ID);
    }
 
    VIRTUAL void set(Base& self, int j) {
        Derived2& myself = static_cast<Derived2&>(self);
 
        myself.f = j * .42f;
        std::cout << "set" << std::endl;
    }
 
    VIRTUAL int get(Base& self) {
        Derived2& myself = static_cast<Derived2&>(self);
        float res = myself.f;
        std::cout << "get " << res << std::endl;
        return res;
    }
};
 
 
void init/*vtable*/() {
    //init the vtable for "Base" class
    REGISTER_METHOD1(METHOD_SET,
                     INTERFACE(Base),
                     CLASS(Base),
                     RETURN(void),
                     NAME(set),
                     PARAM0(int)
                     );
    REGISTER_METHOD0(METHOD_GET,
                     INTERFACE(Base),
                     CLASS(Base),
                     RETURN(int),
                     NAME(get)
                     );
    // ***
    //init the vtable for "Derived" class
    REGISTER_METHOD0(METHOD_GET,
                     INTERFACE(Base),
                     CLASS(Derived),
                     RETURN(int),
                     NAME(get)
                     );
    REGISTER_METHOD1(METHOD_SET,
                     INTERFACE(Base),
                     CLASS(Derived),
                     RETURN(void),
                     NAME(set),
                     PARAM0(int)
                     );
    // ***
    //init the vtable for "Derived2" class
    REGISTER_METHOD0(METHOD_GET,
                     INTERFACE(Base),
                     CLASS(Derived2),
                     RETURN(int),
                     NAME(get)
                     );
    REGISTER_METHOD1(METHOD_SET,
                     INTERFACE(Base),
                     CLASS(Derived2),
                     RETURN(void),
                     NAME(set),
                     PARAM0(int));
}
 
Base::FP Base::vtbl[(CLASS_LAST+1) * METHOD_LAST];
 
int main(int argc, const char* argv[]) {
    init();
 
    Base* der = new Derived2();
 
    der->set(196);
    der->get();
 
    return 0;
}

Не успях да събера мотивация да направя тестове за да видя има ли забързване, в кои случаи има и колко е то. Според Alexanderscu Facebook работи 4% по-бързо заради тази магия :).
Предимство е, че така можем и да изберем къде да поместим този “char”, който ползваме като указател към виртуална таблица -> ако не се очаква виртуални методи да се викат често, навярно е по-добре да не е в началото на обекта.

 
0

Raytrace Interop

Posted by savage309 on Dec 26, 2013 in Професионални

Oпитвам се напоследък да правя разни бързи неща с CUDA.
Често има проблем с вземането на резултата от GPUs app (то не става особено бързо, да започне да се случва асинхронно е голяма болка, а пък понякога трябва да става особено често), та един начин това да се случва е с CUDA/OpenGL interop.

Идеята (поне моята) е с някой CUDA kernel да рисувам нещо в някоя текстура, а с OpenGL само да си я рисувам на екрана. И така, понеже всичко си е на едно място (ze gpu), да спестя всякакво четене/писане от видео паметта.

В резултат на ровене из форуми, stackoverflow, tutorials && references, ето какво се получи :

1. YouTube (beware of the video compression)(out-of-core version).
2. GitHub.

Имам около 40fps, интериорна сцена с голяма лампа (cornell box), Macbook Pro, i7 2.6GHZ, nVidia 650M, 512×512 resolution, ray depth 8, rays per pixel 1.

Това, което се случва е : CPU-то инициализира CUDA & OpenGL, стартира CUDA kernel които трасира няколко лъча, резултата се записва в текстура, и накрая се рисува с OpenGL.

Целта на кода по-горе е да се ползва като бърз startup за някои CUDA driven apps (като raytracers :)).

Pros на моят вариант : почти всичко се смята на GPU-то (генериране на семпли, random числа, трасиране, събиране на резултата), ползва Halton редици (beware, nVidia държат патент над тях), ползва CUDA/OpenGL interop (сиреч, ъпдейта на картинката се случва максимално бързо).

Cons : това не е production, aми по-скоро naive имплементация на ray trace, може да се стане няколко пъти по-бързо и noise-free (няма shadow rays, complex sampling), GPU-тата се feed-ват от 1 CPU thread, etc.

 
1

Every now and then

Posted by savage309 on Nov 12, 2013 in Професионални

over confident bug fixer

 
0

Халтон и патентите

Posted by savage309 on Nov 9, 2013 in Професионални

Днес си поиграх нагледно да изпробвам това и да го сравня с псевдо-рандом генератор на ActionScript 3 :) (full link here)

п.с. ползването на подобни редици в CG е патентовано, така че моля разпространявайте тази страница само апокрифно …

 
0

Keep Calm And Keep CUDA

Posted by savage309 on Oct 3, 2013 in Uncategorized

След всеки Blue Screen of Death / 999 driver api error / неработещ SDK feature …

Keep calm. Have to be calm …

 
1

Singleton & C++11

Posted by savage309 on Aug 17, 2013 in Професионални

От време на време всеки ползва Singleton като (анти) шаблон за дизайн.
От време на време пишем и многонишкови програми.
От време на време ползваме тези двете в една програма.

Сложното тогава е, как да сме сигурни че ще имаме точно една инстанция на обекта, който желаем.
Нишките трябва да се разберат една да създаде инстанцията, а другите да не и се пречкат.

Наивният начин за имплементиране на това е с обикновен lock :

Singleton& get() {
    GuardedLock guardedLock(lock);//(1)
    if (!instance)
        instance = new Singleton; //(2)
    return *instance;
}

Така нещата ще потръгнат. Проблема е, че в (1) ще имаме lock-ване всеки път, когато викаме get(). Това може да е много често. А всъщност имаме нужда от 1 локване – само при създаването на обекта (тоест в (2)).

От тази книга навремето научих за double-checking метода. В общи линии, идеята е проста.

Singleton& get() {
    if (!instance) {//(1)
        GuardedLock guardedLock(lock);//(2)
        if (!instance)
            instance = new Singleton;
    }
    return *instance;
}

Вместо да локваме всеки път, локваме само ако няма instance (1). След това локваме и проверяваме пак (2) – така хем имаме синхронизация, хем почти няма локване.
Като начин това работи *почти* винаги, и заради това е известен anti-pattern.

Без да е volatile указателя, компилатора(или интерпретатора) могат да спретнат кофти номер. Въпреки че логически изглежда абсолютно коректен, тов не е съвсем така. Както в С++98, така и в Java, така и навярно в други езици. Заради разни полу-странни оптимизации описани тук.

Ако указателя е volatile, тогава всичко се случва както се очаква.
Той обаче може да се ползва и на други места из кода – това че е volatile може да причини overhead именно там – онези полу-странни оптимизации ще бъдат блокирани и на места, на които не е нужно.

А и нещата с тази проста идея почнаха да загрубяват.
Lock, volatile, double-checking, overheads.

Сега, по темата. Със С++11 освен unique_ptr и move constructors получаваме още няколко неща. Ето една извадка от стандарта.

If control enters the declaration concurrently while the variable is being 
initialized, the concurrent execution shall wait for completion of the 
initialization.—§6.7 [stmt.dcl] p4

Shall wait for completion of the initialization.
Така, с новият стандарт, всичко казано дотук може да бъде заменено със следното.

static Singleton& get(){
     static Singleton instance;
     return instance;
}

Програмата самичка ще се грижи нишките да се изчакат правилно.
А с решаването на всички възможни проблеми се заемат хората, пишещи компилатори :).

п.с.
В новият стандарт се намира и това, което също може да реши проблема сравнително елегантно, с неизвестено какъв overhead.
Anyway, pretty cool stuff.

 
2

template template

Posted by savage309 on Jul 27, 2013 in Професионални

Още едно интересно парче код, което мернах из хаоса :)
То е за template<> template<>, ама не много в контекста на Alexandrescu.

Ето как изглежда синтаксиса, когато искаме да специализираме темплейтен метод на темплейтен клас (тествано, че се компилира в gcc и msvc).

template <typename T>
struct TemplateClass {
    template<typename U>
    void templateMethod(T foo, U bar) {
	std::cout << "TemplateClass<T>::templateMethod<U>\n";
    }
};
 
//some awesome syntax here
template<> 
template<>
void TemplateClass<int>::templateMethod<int>(int foo, int bar) {
    std::cout << "TemplateClass<int>::templateMethod<int>\n";
}

Такива парчета код във ФМИ нямаше …

 
3

aligned hack++

Posted by savage309 on Jul 20, 2013 in Професионални

Вчера на работа се сблъсках с един интересен хак, който бях забравил напоследък …

В езиците от високо ниво не можем да менажираме ръчно памета. Всичко си става автоматично. А напоследък все повече мразя автоматичните неща, защото цената им понякога е твърде висока.

В С++ например, можем експлицитно да укажем как да бъде подравнена паметта, която заделяме (на 1, 2, 4 или друга степен на 2). Oт гледна точка на програмиста, ако паметта е подравнена на 4 байта например, това означава че pointer-ите винаги по модул 4 ще дават 0 (макар в стандарта да не е специфицирано точно така, поведението днес е такова).
Подравняването е важно.

В днешно време повечето компилатори подравняват паметта самички и без да им казваме на колко. Но имат и разни атрибути, с които можем да си изберем ние.

Ето пример :

//gcc 4.2
#define ALIGNED(X) __attribute__((aligned (X)))
struct
ALIGNED(4)
FooBar {
    size_t a;
};

Сега е време за един що-годе известен хак.
Лесно можем да проверим, че най-младшите няколко бита, от стойноста на поинтърите към памет винаги са 0.

for (int i = 0; i < 4096; ++i) {
    auto* ptr = new int;
    cout << ptr;
}

Причината е проста.
Още по-точно, можем да изкажем твърдението, че първите log2(n) – 1 брой бита, винаги са 0, когато ползваме подравнена памет (а тя е такава често дори без да сме указали експлицитно).

Мисля, че не е трудно да го докажем : поинтъра n се дели на число k без остатък, к е точна степен на 2 – да речем, i-та степен на 2. Тоест, n се дели на 2 i-пъти без остатък. Всяко делене можем да представим като right-shift на битове. Така, ако сме имали 1 на някое от местата 0…i-2, да речем на място p, след p шифтове ще получим нечетно число (p ще е стигнало позиция 0), а то при делене с 2 ще има остатък.

Сега, излиза така че няколко бита от стойноста на поинтъра са 0 ако ползваме подравнена памет. Всъщност, съвременните процесори обичат подравняване на около 128 бита. И двата компилатора, с които тествах автоматично правеха това (gcc & clang)
Излиза, че няколко бита във всеки поинтър са си 0 винаги. И като лоши хакери, ние трябва да се възползваме от това :).

Сега, да речем че ни трябва следната структура :

template <typename T>
struct Node {
    T* left;
    T* right;
    bool something;
    bool somethingElse;
};

На моят компилатор (clang3.1 x64) sizeof(Node) е 24 .. 2 ptrs x 8 = 16; Oстаналите 8 идват от автоматичното подравняване заради 2-та булеви флага. Сега, можем да напишем кода така, предполагайки че данните са подравнени :

template <typename T>
void setFlag(T*& ptr, size_t flagIndex, bool value) {
    size_t ptrAsSizeT = reinterpret_cast<size_t>(ptr);
    if (value) {
        ptr = reinterpret_cast<T*>( ptrAsSizeT | (1 << flagIndex) );
    } else {
        ptr = reinterpret_cast<T*>( ptrAsSizeT & (~ (1 << flagIndex)));
    }
}
 
template<typename T>
bool getFlag(const T* ptr, size_t flagIndex) {
    return ptr & (1 << flagIndex);
}
 
template<typename T>
struct Node {
private:
    T* left;
    T* right;
public:
    Т* getLeft() const { //make getRight() too
        T* tempPtr = left;
        setFlag(tempPtr, 0, 0);
        setFlag(tempPtr, 1, 0);
        return tempPtr;
    }
    bool getSomething() const { return getFlag(left, 0); }
    bool getSomethingElse() const { return getFlag(left, 1); }
    void setSomething(bool foo) { setFlag(left, 0, foo); }
    void setSomethingElse(bool foo) { setFlag(left, 1, foo); }
};

Вече sizeof(Node) е 16, което е 33% спестена памет. За няколко милярда такива node-a бая гигабайта ще се съберат :) А можем всъщност и доста повече информация да компресираме по този начин в указателите.

Вероятно няма да работи на всякакви архитектури, но за x86 e супер.

п.с. знам за не една и две програми, ползвали този хак; тоест, доказал се е в битка. Компресираите си здраво и наздраве :)

Copyright © 2014 blOgo All rights reserved. Theme by Laptop Geek.