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 супер.

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

 
0

dynаrray c++11

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

Попадна ми едно предложение за новия стандарт (С++14), масив чиито размер не може да се променя след като бъде създаден, но пък размера се определя runtime – dynarray.
С две думи – идеята е да ползва stack memory (когато поисканата памет не е твърде много), а в другите случаи да се ползва heap memory. Целта е и всякакви други контейнери го ползват, а резултата ще е повишена ефективност.
Разбира се, всичко това да се случва само в рамките на scope на функция (защото това е lifetime-a на stack memory).

Възможно приложение на тази структура : да речем имате multithreaded scanline render engine и всяка нишка има нужа от pixel buffer. Ако картинката е малка и се rend-ва бързо можем да ползваме stack mem, ако е голяма и се ренди бавно – heap (overhead-а от new[] ще е пренебрежим). (а можем да алокираме pixel buffer преди rend-a и да ползваме него, но да речем че не ни се занимава с това).

Сега, възниква въпроса, можем ли да имплементираме dynarray в С++11.
Ето oпитите, които направих и заключенията до които стигнах.


Единственото, което не е много ясно е как да алокираме динамично памет на стека.

Опция 1.
Заделяме костантно памет в обекта, ползваме нея ако стига, в противен случай – heap-a.

template<typename T, size_t maxBytesOnStack>
struct dyn_array {
    dyn_array(int elementsCount) {
        if (elementsCount*sizeof(T) > maxBytesOnStack) 
            //use heap mem
        else
            //use stack mem 
    }
    uint8 stackMemory[maxBytesOnStack];
    T* heapMemory;
};

Това работи. Проблема е, че дори и да ползваме heap memory, пак имаме overhead-a от maxBytesOnStack на стека. А това не е приемливо, защото се борехме за performance и memory.

Опция 2.
Заделяме споделене памет за всички dyn_array обекти, когато ползваме stack memory търсим в нея с custom allocator. Ако няма място – ползваме heap.

static const char sharedMemory[1024*1024*1024];
template<typename T, size_t maxBytesOnStack>
struct dyn_array {
    dyn_array(int elementsCount):ptr(nullptr) {
        if (elementsCount*sizeof(T) <= maxBytesOntStack)
            ptr = customAllocatorGetMemory(elementsCount)
        if (!ptr) 
            //use heap memory
    }
    T* ptr;
};

Проблема тук е, че трябва да подържаме допълнителна структура от данни, за да може customAllocator-a да работи, имаме overhead от търсенето в него. От време на време трябва да извършваме “поддръжката” му и да сливаме парчетата които са едно до друго, може да получим фрагментация, имплементацията е сложна. Та трябва да има и по-добър начин.

Oпция 3.
Можем да ползваме функцията alloca(size_t bytesCount), която прави точно това – алокира памет на стека. Тази памет още повече не се освобождава при излизане от scope, а чак при излизане от функцията, която е направила извикването. Тоест, този код crash-ва със stackoverflow :

for (size_t i = 1; i < (1 << 31); ++i) alloca(i << 1);

Ето и какво бихме написали с alloca

template <typename T, size_t maxBytesOnStack>
struct dyn_array {
    dyn_array(int elementsCount) {
        if (elementsCount*sizeof(T) > maxBytesOnStack>
            ptr = (T*)malloc(elementsCount*sizeof(T));
        else
            ptr = (T*)alloca(elementsCount*sizeof(T));
    }//(1)
    T* ptr;
}

Това компилирано с clang3.1 и с прости тестове работи. Но работи заради чист късмет – dyn_array() освен конструктор е и функция, и в (1) заделената памет с alloca() спира да я има.

Опция 4.
Да се опитаме да ползваме С++11 за да излъжем компилатора :)
Ще оставим една член-данна на класа от тип функция, а нея ще инициализираме с ламбда, която заделя статична памет и връща указател към нея (tnx to Komitov за идеята).

template<typename T, size_t maxBytesOnStack>
struct dyn_array {
    dyn_array(int elementsCount) {
        if (elementsCount * sizeof(T) <= maxBytesOnStack) {
            f = [](){
                T data[maxBytesOnStack];//(2)
                return (T*)data;
            };
            ptr = f();
        } else ptr = (T*)malloc(elementsCount * sizeof(T));
    }
    T* ptr;
    std::function<T*()> f;
};

Сега, ясно е че имаме overhead oт това че заделяме maxBytesOnStack всеки път, вместо elementsCount*sizeof(T). А и не можем да зачистим статичната памет (2).
Опитите да го излъжа с връщане на const&, ползването на extension-a на gcc (int i = 42; int arr[i]) и др. не завършиха успешно.
Но пък написах този ред код докато пробвах всякаквите там неща :)
std::function < const T(&())[maxBytesOnStack] > (lambda която връща ref към С масив).
Все още обаче имам някакви надежди, че е възможно да се напише hack с такава ламбда.

Опция 5.
Опция 5. е Опция 3., с тази разлика че статичната памет се заделя където трябва (в извикващата функция). Освен това кода е по обширен

namespace codebg {
 
//kbytes to bytes
constexpr size_t operator"" _kb(unsigned long long b) noexcept {
    return 1024*b;
}
 
//mbytes to bytes
constexpr size_t operator"" _mb(unsigned long long b) noexcept {
    return 1024_kb*b;
}
 
//if more than this amount of mem is requested, heap will be used
static const auto DYN_ARRAY_MAX_BYTES_ON_STACK = 1024_kb;
 
//trying to mimic operator new() when using dyn_array
struct dyn_array_throw_policy {
    static void check_bad_alloc(void* ptr) {
        if (!ptr) throw std::bad_alloc();
    }
};
 
//noexcept version
struct dyn_array_no_throw_policy {
    static void check_bad_alloc(void* ptr) noexcept { }
};
 
//simple array struct, that can use stack or heap memory. 
//Use as if it uses stack mem aways.
//do *not* return this as a result (or out param) of a function or method.
template<typename T, size_t maxBytesOnStack=DYN_ARRAY_MAX_BYTES_ON_STACK, 
typename exception_policy=dyn_array_no_throw_policy>
struct dyn_array {
  //if memory is nullptr, heap mem will be used;
//else, memory will be used - it should be stack allocated;
//consider initalizer_list version and one without 3rd param.
   explicit dyn_array(T* memory, size_t elementsCount=1, const T& value=T())
   noexcept(
       noexcept(exception_policy::check_bad_alloc(nullptr)) &&
       noexcept(T()) && noexcept(T(T()))
    ) : ptr(memory), count(elementsCount)
    {
        allocMem();
        for (auto i = 0; i < size(); ++i)
            new (ptr+i) T(value);
    }
 
    //move ctor so we can fast move the constructed object
    dyn_array(dyn_array&& rhs) noexcept {
        ptr = rhs.ptr;
        count = rhs.count;
        useHeap = rhs.useHeap;
        rhs.ptr = nullptr;
        rhs.count = size_t(0);
        rhs.useHeap = size_t(0);
    }
 
    //asure we call dtors
    ~dyn_array() {
        freeMem();
    }
 
    size_t size() const noexcept {
        return count;
    }
 
    bool using_heap() const noexcept {
        return useHeap == 1;
    }
 
    T& operator[](size_t i) noexcept {
        return ptr[i];
    }
 
    const T& operator[](size_t i) const noexcept {
        return ptr[i];
    }
 
    dyn_array(const dyn_array& rhs)=delete;
    dyn_array& operator=(const dyn_array& rhs)=delete;
    dyn_array& operator=(const dyn_array&&)=delete;
private:
    //calls d'tors and clears mem if heap is used
    void freeMem() noexcept {
        if (ptr) {
            for (auto i = 0; i < size(); ++i)
                (ptr+i)->~T();
            if (using_heap())
                free(ptr);
        }
    }
 
    //if heap is used, allocs memory
    void allocMem() 
    noexcept(noexcept(exception_policy::check_bad_alloc(nullptr))) {
        if (ptr == nullptr) {
            size_t bytesNeeded = sizeof(T)*size();
            ptr = (T*) malloc(bytesNeeded);
 
            exception_policy::check_bad_alloc(ptr);
 
            markUseHeap();
        }
    }
 
    //raise the useHeap flag
    void markUseHeap() noexcept {
        useHeap = 1;
    }
 
    //ptr to memory chunk - heap or stack
    T* ptr;
    //if 0 stack is used, else if 1 - heap
    size_t useHeap:1;
    //63 bits for elements count, that should be enough
    size_t count:(sizeof(size_t)*8-1);
};
 
//use this to create dyn_array. Example :
//auto pixelBuffer = make_dyn_array(float, 640, 0.f);
//std::cout << pixelBuffer[0];
#define make_dyn_array(TYPE, COUNT, VALUE) codebg::dyn_array<TYPE>(sizeof(TYPE)*(COUNT) > codebg::DYN_ARRAY_MAX_BYTES_ON_STACK ? nullptr : (TYPE*)(alloca(sizeof(TYPE)*(COUNT))), (COUNT), (VALUE))
}

Можем да го ползваме почти като нормална функция :

auto myDynArray = codebg::make_dyn_array(float, 640, 0.f);

Като заключение,
(1) std::dynarray ползвайки С++11 изглежда не може да се направи (имплементацията в clang e cheat&fake – ползва единствено malloc, това не нарушава стандарта, ама все пак ..), трябват промени в компилатора и/или да се пише на assembler.

(2) В С++11 един прост конструктор отнема над 200 символа – сигурен съм че с python с толкова мога да вдигна web server :). Изглежда пичовете от С++ комитета пружинките на клавиатурата за нищо ги нямат.

(3) Може би е добре да си отворя един github :)

 
0

Design Pattern

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

Както в повечето ИТ компании и в Chaos имаме собствена библиотечка.
Книжката по-долу обаче получи специално внимание, и бе покръстена така веднага щом я докараха :D.

Ако трябва да сме честни, това четивo може и да е полезно. Чувал съм да го ползват като не-толкова-добра ракета за тенис на маса, например.


п.с. every problem can be solved using one more abstraction layer, except too many abstraction layers … or javascript-like performance.

 
1

Lets talk C++

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

Има едно видео за скриптовите езици, което бая ме забавлява :).
Аз се порових, stackoverflow и из стар код. Та.


Lets talk C++.

auto str = "Let's talk C++";
auto strLength = strlen(str);
std::cout << strLength << " ... " << std::endl;
if (strLength < -1) 
    std::cout << "WAT." << std::endl;

Резултат: 14 … WAT.

strlen връща size_t, което бидейки unsigned по стандарт, каства -1 до unsigned, което е всъщност едно доста голямо число :).
if (strLength < -1.f) обаче работи както трябва (понеже по стандарт се каства до най-големия тип с плаваща запетая, ако има такъв).


Lets talk C++. 11.

auto  a = new int(42);
auto* b = new int(196);
bool starsAreImportant = strcmp(typeid(a).name(), typeid(b).name()) != 0;
if (starsAreImportant == false)
   std::cout << "WAT.";

аuto като feature ползва механизма на template-ите за определяне на типа. Звездичката, която седи там е безсмислена, но може да я има, за да е объркването пълно.


Lets talk C++.

int *ptr, value = NULL;
if (ptr) *ptr = 42; //crash here
value = ptr; //compilation error here
std::cout << (value + 42); //works fine ...
std::cout << "WAT";

На първият ред декларираме int* ptr, и int value = NULL – което е все едно:
int* ptr;int value = 0; … Неинициализиран ptr и int със стойност 0. Трябва да признаем, че поне nullptr решава част от недоразумението.


Lets talk C++.

int i = -1;
std::cout << (i >> 1) << " WAT.";

Недефиниран WAT. Cтандарта указва какво влияние имат битовите операции върху signed типове. В по-голямата си част са undefined, а в другата е достатъчно оплетено, за да не искате да ги ползвате никога.


Lets talk C++.

int main() {
    http://code-bg.com
    std::cout << "WAT.";
    return 0;
}

Това се компилира. То е етикет за goto с име http, а след него има коментар code-bg.com


Lets talk C++.

struct Storage {
    static int const value = 42;
};
 
template<typename T>
void bar(T const&){}
int main() {
    bar(Storage::value);//compile time error
    bar(+Storage::value);//fine
    std::cout << "WAT.";
}

Унарният оператор + създава копие :).


Останалите за друг път.
А за бонус, този ред:

typedef int (*(Foo::*bar())[196]);

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