No country for old men

Още един “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 & iPhone 6 – Raytrace 13s, Sort 11s, Rand mem access 9.5s, FPU 1.92s.

VTable по поръчка

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

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

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

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

Raytrace Interop

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.

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

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

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

Singleton & C++11

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

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

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

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

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

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

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

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

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

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

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

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

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

template template

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

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

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

aligned hack++

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

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

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

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

Ето пример :

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

Причината е проста.
Още по-точно, можем да изкажем твърдението, че първите 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 винаги. И като лоши хакери, ние трябва да се възползваме от това :).

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

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

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

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

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

dynаrray c++11

Попадна ми едно предложение за новия стандарт (С++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.

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

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

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

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

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

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

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

Сега, ясно е че имаме 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., с тази разлика че статичната памет се заделя където трябва (в извикващата функция). Освен това кода е по обширен

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

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

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

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