Rationale for intrusive_ptr

Manual memory management in C++ can easily become a nightmare. To alleviate this problem, someone invented smart pointers. Today we’ll focus on reference-counted ones, or, more precisely, why non-intrusive boost::shared_ptr (also called std::tr1::shared_ptr, since it became a part of TR1) is often a worse idea than, as the name suggests, intrusive, intrusive_ptr (of course, using a garbage collected language is almost always better).

The first thing is the performance (you care about performance, don’t you? If you weren’t, you wouldn’t be using such an unsafe language, would you?). There are actually several performance-related problems. The first one is thread-safety. It’s not necessarily bad, if your code is actually multi-threaded. But even then, you’re paying the price for that everywhere, even in the places where you’re absolutely sure you don’t share objects across threads. And you can’t turn off thread-safety in such places – you can do that either for whole project, or not at all. Pick your poison.

The second performance-related problem is that shared_ptr has to allocate memory for the reference counter on the heap. Yes, it’s possible to avoid this by using make_shared or allocate_shared, but it’s actually an ugly hack. The memory footprint of this smart pointer is no picnic, either – shared_ptr itself has a size of two pointers, and the size of reference counter is, at least on my machine, the same as the size of two longs and two pointers.

And there’s the deleter thing. Yeah, no doubt it’s useful. Sometimes. But, again, you have to pay the price for having one even if you don’t really use it (wasn’t „don’t pay for what you don’t use” one of C++ design principles?). And this time, it’s impossible to turn it off.

One could claim that these all things certainly won’t be bottlenecks. I thought so, too. But I saw applications where shared_ptr logic took much time (up to 50% in one, somewhat extreme, case). So how can substituting intrusive_ptr for shared_ptr improve performance? intrusive_ptr can be thread-safe only where we want it to be (ranging from nowhere to whole project), because we’re obliged to provide addRef and release methods (actually their names are slightly different, and they’re free functions). Also, it doesn’t have to allocate anything on heap, because reference counter is a part of the object. And intrusive_ptr is as big as a raw pointer (because behind the scenes it is a raw pointer). Unfortunately, there’s no deleter, yet I bet it’s possible to implement it somehow if one really needs it.

Next issue with shared_ptr is that it’s amazingly easy to cause double deletion. Consider this:

Foo* rp = new Foo;
 
shared_ptr<Foo> sp1(rp);
shared_ptr<Foo> sp2(rp);

Both sp1 and sp2 will create a reference counter with count 1, and at the destruction both will try to delete the pointer. Oops, rp got deleted twice.

Surely, it is programmer’s fault. Too bad it’s easy to make the same (or similar) mistake in more complicated code. There is enable_shared_from_this, which allows to get a working shared_ptr from this. Alas, there’s no enable_shared_from_any or something. intrusive_ptr doesn’t suffer from this problem, because reference counter is embedded in the object itself. The object will know it’s referenced by two intrusive_ptrs so it’ll get deleted only once.

Yup, shared_ptr can point to any type, not necessarily a user-defined type, whereas intrusive_ptr can point only to types for which appropriate functions are defined. So shared_ptr can point to built-in types (I don’t think anyone uses heap-allocated built-ins unless it’s an array) and the types from third-party libraries. intrusive_ptr can point to the third-party types if they already have some way of reference counting, or if we wrap them. It’s not always feasible, of course. But it’s also possible to not use smart pointers for them at all – that can work pretty well.

Of course I know that sometimes shared_ptr is really the right way to go. But more often than not it’s not the best idea, because of the problems outlined above. If you’re considering reference counting, think about intrusive reference counting first, and only if it doesn’t suit your needs, go non-intrusively.

Making PE multiboot-compliant

My old poor boot loader broke once again. Or should I say it was inherently broken and simply yet another bug manifested its existence? Anyway, I won’t fix anything in that boot loader anymore. It’s simply not worth any effort. So, farewell, my old boot loader! Let’s use GRUB, at least it won’t crash randomly, it has many useful features, and in general it’s better.

But wait! If I want GRUB to load my kernel, the kernel image must be multiboot-compliant. Almost every „roll your own operating system” talks about how you can make your kernel bootable by GRUB (aka multiboot-compliant). But they assume that the format of the kernel image is ELF. And mine kernel is not ELF, it’s PE. This makes things more complicated.

Of course, a solution exists. Sadly, this one, which is unfortunately pretty bad (look at these hardcoded values and think a while about problems they’ll cause), is, barring using GNU linker with a contrived script defining exact order of sections and what not, actually the only one I’ve heard of. Clearly, we need something better.

Let’s think a while about the structure of a PE file. What’s the first structure in the file? It’s the MZ header, which doesn’t contain anything important – only the first word and the last doubleword matters – as long as we don’t mind that DOS won’t run our executable. So, what we have there is basically 58 bytes of free space. Multiboot header is 48 bytes long in worst case. So, we can stash the multiboot header into the MZ header and everybody will be happy. The important thing is that we have to leave e_cblp field intact – not because it contains anything relevant, but simply for multiboot header has to be doubleword aligned.

This time I won’t provide a code which does the thing, but rather a general hints how the code should look like (what should be overwritten by what and the like). It should be easy to write a program which processes the image in the given way (yeah, this is the drawback of the idea – it requires separate program to process the executable. Fortunately, it’s possible to make it a post-build step in most IDEs) in your language of choice. Oh, I forgot one important thing: file alignment and section alignment have to be equal or else the kernel won’t run or will behave abnormally! Check your linker’s documentation for details about changing file or section alignment (by default they’re 512 and 4096 respectively).

So we’re starting overwriting from the fifth byte, as previous shouldn’t be modified (the first two are magic number, if they’re changed, our file won’t be a valid PE anymore). Magic number, flags (sixteenth bit must be set, or else GRUB will complain about the format) and checksum aren’t causing much trouble – they don’t depend on the image (i.e. they won’t change as the image grows larger or something), so it’s as simple as just writing 12 bytes (because it’s actually writing 12 bytes, heh).

Now, the funny part begins – physical multiboot header address. We can either hardcode it (not recommended), or read the image base from the PE optional header and add four to it (because multiboot header begins at fifth byte, and fifth byte is the one with address 4). Next thing is the start of things to be loaded, which must be less than or equal to the previous value. Putting image base here will do the trick. Next thing is more interesting – we have to find the physical address of the end of (initialized) data! Again, fields inside optional header come to the rescue – image base + base of data + size of initialized data (I’m unsure here, but so far it works for me just fine; perhaps the better way is to read all section headers and calculate this according to the values found there). Next thing is the physical address of the end of uninitialized data section. I’ve put image base + size of image (yes, it’s from optional header, too) here, but again I’m not sure whether it’s the best thing to do. And, finally, the last thing – address of entry point. Yeah, image base + address of entry point from optional header.

So we made our image multiboot-compliant, utilizing some unused space and without hardcoding anything. Surely it won’t work with some files, but as long as the kernel is just a simple PE (i.e. built without linker-switch-or-script-magic, just with default or almost default – remember, the file and section alignment! – settings), it’ll work. If you know how the idea can be improved, you have some valuable infos, or anything else, then don’t hesitate and write a comment – they’re appreciated, as always.

Saturated arithmetic

Unsigned types in C and C++ have pretty straightforward and predictable behavior upon an overflow or underflow – namely, they’re wrapping around (whereas signed types don’t like {over,under}flows – the behavior is undefined). However, sometimes wraparound doesn’t fit our needs, because we want the value to be set to the maximum in case of overflow and to the minimum in case of underflow. That’s exactly what saturated arithmetic is.

Of course, it’s very easy to implement it using a lot of if statements and other things involving branches – however, as you may already noticed, I don’t like branches ;> So, we’re going to use branchless equivalents.

We’ll be interested in keeping our values in range [0..255], i.e. the range of unsigned char on x86 and ARM (these are the only architectures of my interest ;>). Also, we’ll assume that values are already clamped to that range. It should also be simple to make the code work on unsigned shorts and the range [0..65535], by replacing every 8 for 16 and 16 for 32 (including these in type names) ;>

Okay, so let’s start by doing something simple, like incrementation. There’s a nice piece of code for doing that in a comment by Michael. I improved that code a bit, getting:

inline uint8 IncSaturated8(uint8 x)
{
  uint32 carry = ((uint32(x) + 1) >> 8);
  uint32 temp = uint32(x) + (carry ^ 1);
  return uint8(temp);
}

carry is equal to 1 if and only if x is equal to 255, because then x + 1 is equal to 256, and 256 >> 8 is of course 1. We XOR carry with 1, to get 1 IFF there was no carry and 0 otherwise. Finally, 255 + 0 = 255 and any other value + 1 = any other value + 1, giving us nice, branchless saturated increment.

Decrementation is similar:

inline uint8 DecSaturated8(uint8 x)
{
  uint32 carry = ((uint32(x) - 1) >> 31);
  uint32 temp = uint32(x) - (carry ^ 1);
  return uint8(temp);
}

Here, carry equals to 1 only when x equals to 0, because x - 1 underflows and gives us nice, large result with highest bit set. The rest is the same as in incrementation.

Next operation is addition:

inline uint8 AddSaturated8(uint8 x, uint8 y)
{
  uint32 sum = uint32(x) + uint32(y);
  uint32 carry = sum >> 8;
  return (-carry | sum);
}

In this one, carry is 1 IFF the sum didn’t fit in 8 bytes (as in incrementation). We’re then OR’ing the sum with negated carry (i.e. 0 if no carry and -1 if carry), receiving 0xFF..FF | x, which resolves to 0xFF..FF, in case of overflow and 0 | x, which is the same as x, when no overflow occurs. After getting truncated to 8 bits the result is either 255 or x + y, exactly what we wanted it to be.

Subtraction is similar to addition:

inline uint8 SubSaturated8(uint8 x, uint8 y)
{
  uint32 difference = uint32(x) - uint32(y);
  uint32 carry = (difference >> 31) ^ 1;
  return (-carry & difference);
}

This time, carry is actually !carry, since it’s 0 when underflow occurred and 1 otherwise. After negation, it’s 0 or -1, respectively. So we have two cases – 0xFF..FF & difference (which equals to difference) when there was no underflow and 0 & difference (which is 0) when operation underflowed.

Only two operations are left – multiplication and division. We’ll cope with the latter first, because it’s simplier:

inline uint8 DivSaturated8(uint8 x, uint8 y)
{
  return x / y;
}
 

Yes, that’s right – it’s just plain old division. Unsigned division can overflow only if y is 0, which is undefined behavior anyway.

And, finally, the multiplication:

inline uint8 MulSaturated8(uint8 x, uint8 y)
{
  uint16 product = uint16(x) * uint16(y);
  uint8 hi = product >> 8;
  uint8 lo = product & 0xFF;
 
  return sex(hi | -hi) | lo;
}

We’re calculating the product of the operands, getting 16 bit result. If it’s higher part is not 0, that means operation overflowed. We’re checking for this 0 using our old & trustworthy sex function, taking advantage of the fact that x | -x is always a negative number, unless x = 0. So we end up with 0 | lo or 0xFF..FF | lo. They’re the same as lo and 255, respectively, after being simplified and truncated.

Maybe there exists even better way to implement saturated arithmetic while retaining branchlessness (does this word exist, actually? :>). I don’t know; if you know, please tell me.

Is an array a pointer?

„Array is a pointer” (also „an array’s name is a pointer to the array’s first element”) – I think most of us have heard that nonsense. So many people believe it’s true. And some of them think that they’re absolutely right, don’t even taking into account they may be wrong. I’m getting tired of this, so… I think it’s great time to write a post about this ;>

Let’s see what the standard says (4.2.1): „An lvalue or rvalue of type ‘array of N T’ or ‘array of unknown bound of T’ can be converted to an value of type ‘pointer to T.’ The result is a pointer to the first element of the array”. It’s pretty clear it means that these types are convertible (and, since they’re convertible, they can’t be the same type). Someone who doesn’t know that may think they’re in fact the same, since it’s perfectly fine to do something like:

int foo[11];
int* bar = foo;
*(foo + 8) = 42;
void sth(int*);
sth(foo);

Sure, it compiles and runs just fine. But this doesn’t mean that arrays are pointers. Consider this:

void function(float num);
int x = /* ... */;
function(x);

It compiles and runs fine, too. But it’s because of implicit conversion, not because the types are the same (I hope nobody thinks int and float are the same ;>).

If arrays and pointer actually were the same, then the following code wouldn’t compile:

template <typename T> struct sth;
 
template <> struct sth<int []> {};
 
// okay, int [] and int [6] are distinct types
template <> struct sth<int [6]> {};
 
// okay, int*, int [] and int [6] are distinct types
template <> struct sth<int*> {};
 
// sizeof(pointer to int) is not equal to sizeof(array of six ints)
// (in fact it could be true for a very obscure machine, though)
typedef char x[sizeof(int*) != sizeof(int[6]) ? 1 : -1];

But what about „arrays” in function arguments list? Let’s suppose we have something like

void f(int arr[])
{
 
}

In this function, arr is a pointer. sizeof(arr) will yield size of a pointer to int. It’s legal to do ++arr. It’s because an array passed to function by value decays to a pointer (this doesn’t mean that arrays are pointers!), arrays simply can’t be passed by value. Even if we’ll tell the compiler the size of the array:

void f(int arr[123])
{
 
}

it’s still a pointer. And because it’s a pointer, it’s not possible to overload a function based on the size of the „array” passed „by value”. „Arrays” in argument lists are pointers. So overloading for int [123] and int [456] is ill-formed – they’re both int*.

If we really want to pass an array and not a pointer to the function, then we can pass a reference to an array (possibly making the hard-coded 123 a template parameter, so that the function can take arrays with different sizes):

// void f(const int (&arr)[123]) if array of consts
void f(int (&arr)[123])
{
 
}

It’s impossible to pass a pointer to this function, the code won’t compile. This function takes a reference to an array, so pointers won’t do:

int array[123];
int* pointer;
 
f(array); // okay
// f(pointer); // error

To sum up: pointers and arrays are two different things. They often behave similarly, they’re related, but they’re nonetheless different.

Zmienianie obiektów tymczasowych [pl]

Przeciętny program w C++ tworzy i niszczy w czasie swojego działania wiele obiektów tymczasowych. Czym jest obiekt tymczasowy, to chyba wyjaśniać nie trzeba (a jeśli trzeba, to sobie tego poszukaj, nie chce mi się powtarzać po kimś :>). Okazuje się, że w C++ możemy zmieniać takie obiekty, jeśli tylko nie są typu wbudowanego. Napiszmy więc sobie jakiś prosty przykład, aby sprawdzić, czy nie gadam głupot :>

struct foo
{
  int x;
 
  foo& mutate(int a)
  {
    x = a;
    return *this;
  }
 
foo wtf(int x)
{
  foo a;
  a.x = x;
  return a;
}

Teraz spróbujmy wywołać tę funkcję i zmienić obiekt tymczasowy:

wtf(8).x = 11;

Mamy błąd kompilacji (pod Comeau – kompilatorowi Microsoftu, g++ i pewnie wielu innym kompilatorom nie przeszkadza fakt, że próbujemy zmienić obiekt tymczasowy), mówiący, że wyrażenie musi być modifikowalną lwartością. U nas oczywiście nie jest – obiekt tymczasowy jest rwartością. Widzimy więc, że tak na chama zmienić pól obiektu tymczasowego się nie da – spróbujmy więc poprosić obiekt o to wywołując metodę mutate (zauważmy, że nie jest ona const):

wtf(8).mutate(11);

Tym razem się udało zmienić obiekt tymczasowy – możemy nawet to sprawdzić, wypisując wartość pola x (specjalnie dlatego metoda mutate zwraca foo&). To ma nawet zastosowania – przykładowo move constructor (nie będzie to konieczne w C++0x, z powodu referencji do rwartości).

Czy można to w jakiś sposób uniemożliwić? Standard mówi, że „Class rvalues can have cv-qualified types”, więc rwartość typu const foo to coś innego niż rwartość typu foo (w przeciwieństwie do typów wbudowanych, w przypadku których int i const int oznaczają to samo w przypadku rwartości). Spróbujmy więc:

const foo wtf(int x)
{
  // ciało funkcji bez zmian
}

Jeśli teraz spróbujemy wywołać niestałą metodę obiektu, to dostaniemy błąd kompilacji – właśnie to chcieliśmy osiągnąć. Niestety, zwracanie const T zamiast zwykłego T powoduje, że (odnosi się to do C++0x) powstałego obiektu tymczasowego nie będzie można przekazać jako T&&, a najwyżej const T& (const T&& oczywiście też), przez co tracimy kilka fajnych możliwości optymalizacji, na przykład wspomniany move constructor.

Co dalej z tymi maskami? (branchless code, część druga) [pl]

Widzę, że linki do mojego bloga pojawiają się w dosyć dziwnych miejscach ;P, więc kończę idlowanie i zabieram się za pisanie kolejnej, drugiej tym razem części minitutka o pisaniu branchless code. Jeśli ktoś nie czytał części pierwszej, to niech to lepiej zrobi, bo bez tego będzie dosyć ciężko – nie będę tu powtarzał, jak uzyskać maskę 0/-1… No dobra, będę, ale tym razem w trochę inny sposób.

W tej chwili jesteśmy na takim etapie, że mamy jakąś maskę i nie wiemy za bardzo, co z nią możemy dalej zrobić. Oczywiście sama maska się nam nie przyda, musimy wiedzieć, do czego możemy jej użyć i w jaki sposób.

Na początek powiem o dwóch prostych czynnościach – konwersji maski na 0/1 (czyli do czegoś przypominającego bool /w zasadzie to bool jest zwykle reprezentowany jako liczba całkowita o wartościach 0 dla false i 1 dla true/) oraz w drugą stronę.
Konwersja na 0/1 jest banalnie prosta, wystarczy zrobić bitowy AND maski z jedynką, gdyż 0 and 0 = 0 i 0xFF...FF and 1 = 1:

inline unsigned int bitmask_to_01(int mask)
{
  return mask & 1;
}

Jeśli chcemy zrobić konwersję zanegowanej maski na 0/1 (czyli dla 0xFF...FF dostajemy 0, a dla 0 otrzymujemy 1), to co prawda możemy użyć negacji bitowej na masce a następnie przedstawionej wyżej funkcji, ale jest lepszy sposób – dodanie 1 – 0 + 1 = 1 i -1 (czyli 0xFF...FF) + 1 = 0:

inline unsigned int bitmask_to_10(int mask)
{
  return mask + 1;
}

Konwersja w drugą stronę (0/1 => 0/-1) jest równie prosta – wystarczy odwrócić znak:

inline unsigned int bitmask_from_01(int value)
{
  return -value;
}

To jest bardzo przydatna funkcja – pozwala zrobić z warunku typu a > b (czymkolwiek by a i b nie były – mogą być stringami czy jakimiś fajniejszymi rzeczami, nie muszą to być liczby!) maskę. Zaletą jest to, że takie porównanie jest zwykle overflow-safe, (w przypadku porównywania liczb albo jeśli operator porównania sam jest branchless) również branchless (przynajmniej na niektórych architekturach, jeśli mają jakieś conditional set lub conditional move. Tak, x86 pod to podpada), a w dodatku potrafi być szybsze (vide równość – 6 instrukcje na „czystym” bit twiddlingu, 3 lub 4 w tym przypadku).
Konwersja 0/1 => -1/0 (czyli negacja tego, co wyżej), to miast kombinowcji z bitowym NOT, odejmowanie jedynki – 0 - 1 = -1 i 1 - 1 = 0:

inline unsigned int bitmask_from_10(int value)
{
  return value - 1;
}

Przejdźmy wreszcie do tego, jak teraz użyć tej maski do uniknięcia rozgałęzień. Jeśli czytałeś moją notkę o clapmingu, to prawdopodobnie wyobrażasz już sobie, jak to wygląda. Otóż maska, jak wiemy, ma w zależności od prawdziwości warunku dwie wartości – 0 w przypadku fałszu oraz 0xFF...FF (czyli wszystkie bity zapalone) w przypadku prawdy. Jeśli chcemy wyciągnąć z maski 0 gdy fałsz i x (czyli dowolną liczbę, może to być zmienna) gdy prawda, to musimy w jakiś sposób zgasić niepotrzebne nam jedynki. Robi się to przez AND – cokolwiek AND 1 = cokolwiek i cokolwiek AND 0 = 0. Po przelaniu na kod wygląda to tak:

inline unsigned int bitmask_to_x(int mask, int x)
{
  return mask & x;
  // return (mask == -1) ? (x) : (0);
}

Powiedzmy, że mamy prosty kod:

if(sth < 0)
  x += 10;

który chcemy przekształcić na wersję branchless. Możemy to sprowadzić do następującego wyrażenia:

x += (sth < 0) ? (10) : (0);

Wyrażenie w tej postaci łatwo już przekształcić na branchless (no dobra, w takiej postaci pod większością kompilatorów również jest branchless) code. Najbardziej odpowiadać nam będzie funkcja sex – ona w końcu zwraca -1 wtedy i tylko wtedy, gdy argument jest ujemny i 0 w przeciwnym wypadku. Ale przecież nie chcemy odjąć 1, tylko dodać 10. Musimy więc zrobić z maski 0/-1 coś (bo nie wiem jak to nazwać :>) 0/x, używająć bitmask_to_x (albo bezpośrednio AND):

x += bitmask_to_x(sex(sth), 10);

I tyle, oto cała sztuka transformowania prostych ifów do branchless code. Oczywiście działa to równie dobrze z innymi działaniami, nie tylko z dodawaniem.

Obiecałem, że napiszę tutaj także o bardziej skomplikowanych rzeczach, jak np. wybór jednej z dwóch zmiennych, ale okazało się, że wyszło niekrótko, więc będzie pewnie w trzeciej części ;)

Branchless clamp to [0..255] [pl]

Parę dni temu na blogu Gynvaela Coldwinda pojawił się wpis o bardzo fajnej tematyce – zrobienia clampa dowolnej liczby całkowitej do zakresu [0..255] bez skoków. Postanowiłem się przyjrzeć temu z bliska, bo problem jest dość ciekawy i nie pozwolę, żeby mi ktoś chleb zabierał ;P.

Napisałem więc dwie funkcje, które także dają poprawny wynik i są branchless:

int my1(int x)
{
  x -= (x - 255) & -(x > 255);
  x += (-x) & -(x < 0);
  return x;
}

Pierwsza instrukcja spowoduje ustawienie x na 255 tylko wtedy, gdy x > 255. Jakim trafem to działa? x > 255 wynosi 1 (w rzeczywistości to wynosi true, ale bool ma niejawną konwersję do int), jeśli, jak łatwo się domyślić, x jest większe od 255 i 0 w przeciwnym wypadku. Jeśli zafundujemy temu negację arytmetyczną, to dostaniemy (x > 255) ? (-1) : (0). Ponieważ (prawie?) wszystkie architektury używają uzupełnienia do dwóch, -1 jest równe 0xFF...FF, czyli ma wszystkie bity równe 1. Pamiętając, że cokolwiek & 0xFF...FF = cokolwiek oraz cokolwiek & 0 = 0 uzyskujemy x -= (x > 255) ? (x - 255) : (0). Pozostaje nam to tajemnicze x - 255. Ile wynosi cokolwiek - (cokolwiek - 255)? Po opuszczeniu nawiasów otrzymujemy cokolwiek - cokolwiek + 255. cokolwiek - cokolwiek wynosi zawsze 0, więc zostaje 255. Ostatecznie daje nam to x = (x > 255) ? (255) : (x).

Druga linia jest podobna – jest to równoważne x += (x < 0) ? (-x) : (0). x + 0 to x, co jest oczywiste, więc pomyślmy nad tym -x. x + (-x) to x - x, czyli ładne 0. Całość sprowadza się więc do x = (x < 0) ? (0) : (x).

Druga funkcja natomiast jest nieco inna (wydaje się dłuższa, ale w rzeczywistości po skompilowaniu jest mniejsza):

int my2(int r)
{
  int min = r ^ ((255 ^ r) & -(r > 255));
  int max = min ^ ((0 ^ min) & -(min < 0));
  return max;
}

W tym przypadku całość jest chyba odrobinę (ale tylko odrobinę, bo ciągle jest mnóstwo operatorów bitowych, więc wskaźnik WTF/min jest wciąż wysoki ;>) czytelniejsza, ze względu na porządne nazwy zmiennych. Pierwsza instrukcja oblicza min(255, r). Druga natomiast max(0, min). Zwracany jest max, czyli efektywnie max(0, min(255, r)). Nie będę teraz tłumaczył czemu to tak wygląda, bo przypadkowo mam w planach pisanie o tym w części drugiej minitutka pisania branchless code /EDIT (16th November 2009): plany oczywiście się nie sprawdziły ;>. Teraz planuję o napisać o tym w trzeciej części, trudno, musisz zaczekać ;>/ ;).

Teraz słowo o wydajności. Przetestowałem cztery funkcje – te dwie pokazane wyżej, funkcję Gynvaela oraz pewną niespodziankę. Co się okazało? Wyniki były dla mnie niespodzianką, bo wyszło na to, że jestem lamką i nie potrafię napisać porządnego branchless code – moje funkcje uzyskiwały zwykle nieco gorsze czasy niż wynalazek Gyna. Najbardziej jednak zdziwiła mnie zwycięska funkcja, która w prawie wszystkich przypadkach była szybsza niż pozostałe… że co? Mam podać jej kod? Ok, proszę bardzo:

int clamp(int r)
{
  if(255 < r)
    return 255;
  else if(r < 0)
    return 0;
  else
    return r;
}

Tak, to jest ta funkcja. Najprostsza możliwa implementacja tego clampa okazała się najszybsza. Nawet już nie wspominam o czytelności. Ech, nie ma to jak niespodzianki sprawiane przez kompilator ;).

…co? Że niby to nie jest branchless? W takim razie sprawdźmy sobie jej kod wynikowy:

__Z5clampi:
; arg = esp + 4
mov eax, [esp + 4] ; eax = arg
xor edx, edx       ; edx = 0
test eax, eax      ;
cmovns edx, eax    ; if(eax >= 0) edx = eax
mov eax, 0FFh      ; eax = 0xFF
cmp edx, 0FFh      ;
cmovle eax, edx    ; if(edx <= 0xFF) eax = edx
ret                ; return eax

Nie ma skoków, mamy tylko conditional moves, więc jest branchless. Amen.

Niezgodności kompilatora Microsoftu [pl]

Co chwilę jakiś nawiedzony fanatyk zaczyna wrzeszczeć na cały świat (chwilowo ograniczmy świat do wątku rzeczonego fanatyka na dowolnym forum :>), że skoro jego (mocno niepoprawny, ew. używający rozszerzeń jakichś innych kompilatorów) über-kod się pod kompilatorem Microsoftu nie kompiluje, to ten kompilator musi być niesamowicie niezgodny ze standardem. Mam tego serdecznie dosyć, więc podsumuję krótko te olbrzymie niezgodności ze standardem.

Sprawdźmy więc w dokumentacji (nie, MS wcale nie kłamie), czego im się nie chciało zrobić w zgodzie z standardem, którego nikt nie jest w stanie pojąć.

• Oczywiście, na pierwszym miejscu tej listy musiało się znaleźć słowo kluczowe export. To słowo kluczowe określa bardzo trudną w implementacji właściwość (i nie tak wcale użyteczną, jak się niektórym wydaje), więc nic dziwnego, że jest zaimplementowane przez aż dwa kompilatory – Comeau i kompilator Intela.
• Specyfikacje wyjątków – kolejny ficzer o wątpliwej przydatności, rzadko używany, więc nikt za nim płakał nie będzie. W rzeczywistości jest zaimplementowany, tylko go ukrywają.
• Covariant return types nie działają, jeśli funkcja jest vararg.
• Problemy z dependent names (niezauważalne, dopóki ktoś nie ma zboczenia na punkcie wzorców):

  #include <cstdio>
  using std::puts;
  namespace N
  {
    void f(int) { puts("f(int)\n"); }
  }
  
  template <typename T>
  void g(T)
  {
    N::f('a'); // calls f(char) but should call f(int)
  }
  
  namespace N
  {
    void f(char) { puts("f(char)\n") ;}
  }
  
  int main()
  {
    g('c');
  }

• Stringizing operator nie radzi sobie, jeśli się mu poda string z sekwencjami ucieczki (\n itp.).
• std::char_traits<wchar_t>::eof jest poprawnym znakiem, a standard jasno mówi, że to musi być znak niepoprawny (chociaż to bardziej błąd biblioteki standardowej, nie kompilatora).
• Według standardu, każdy obiekt musi się znajdować w innym miejscu w pamięci. Kompilator czasami w celach optymalizacyjnych wypieprza obiekty, które nie mają pól, co powoduje niezgodność (która jest niezauważalna dla 99.9999% programistów).
• Pewne ograniczenia liczbowe, typu mniejsza niż zalecana przez standard maksymalna liczba parametrów makra, która i tak jest na tyle duża, że trzeba się mocno postarać, żeby ją przekroczyć.

I to by było wszystko. Ludzie, to nazywacie „olbrzymimi niezgodnościami”? No bez jaj… Niejeden kompilator ma więcej (i to w dodatku poważnych) niezgodności… Czyżby znowu chodziło o to, że skoro to jest produkt MS, to musi być be, kupa i w ogóle międzynarodowy skandal?!?

PS. Jakby ktoś chciał się czepić liczby rozszerzeń (że niby MS wymyśla jakieś własne standardy i podobne), to zauważę tylko, że np. taki GCC ma więcej rozszerzeń.

#include <windows.h> [pl]

Dzisiaj przy próbie kompilacji pewnego kodu zdarzyła mi się pewna ciekawa rzecz. Linker krzyczał, że pewna metoda pewnej klasy w pewnym pliku obiektowym (chyba nadużywam pewnego słowa :>) jest unresolved external symbolem. Błąd jak każdy inny, pewnie poradziłbym sobie z nim dosyć szybko, gdyby nie to, że kilka razy sprawdzałem, czy ta metoda faktycznie istnieje i wszystkie sprawdzenia dały wynik pozytywny (tj. istniała)… Winowajcą okazał się pewien nagłówek (popatrz na tytuł notki i zgadnij, o jaki header chodzi :>).

Najpierw zreprodukujmy sobie ten błąd, żeby lepiej widzieć, co się dzieje (kod został trochę pozmieniany /i mocno uproszczony/ dla niepoznaki; tradycyjnie najpierw kod, potem wyjaśnienia :>):
main.cpp:

#include <cstdio>
#include "foo.h"
 
int main()
{
  CFoo sth;
  sth.SendMessage("blahblah");
  std::printf("%d", sth.GetValue());
}
 

foo.h:

#pragma once
 
class CFoo
{
public:
  CFoo();
  void SendMessage(const char*);
  int GetValue() const;
private:
  int myValue;
};
 

foo.cpp:

#include <windows.h>
#include "foo.h"
 
CFoo::CFoo()
 : myValue(11)
{
}
 
void CFoo::SendMessage(const char* msg)
{
  // avoid warnings
  (void)msg;
  /* some work */
}
 
int CFoo::GetValue() const
{
  return myValue;
} 

Kompilacja (dowolny inny kompilator też będzie dobry):

 >> cl /O2b2ity /GL /W4 /nologo /c main.cpp
main.cpp
 >> cl /O2b2ity /GL /W4 /nologo /c foo.cpp
foo.cpp
 >> cl /nologo main.obj foo.obj /link /LTCG
main.obj : error LNK2001: unresolved external symbol "public: void __thiscall CFoo::SendMessage(char const *)" (?SendMessage@CFoo@@QAEXPBD@Z)
main.exe : fatal error LNK1120: 1 unresolved externals
 >>

Super, unresolved external, a metoda przecież istnieje…

…właśnie, że nie istnieje. Przyjrzyjmy się dokładnie plikowi winuser.h (jeden z pierdyliona dołączanych przez windows.h). Znajdziemy tam takie pięć linii:

#ifdef UNICODE
#define SendMessage  SendMessageW
#else
#define SendMessage  SendMessageA
#endif // !UNICODE

Aha. Czyli nasza cudowna metoda nazywa się w rzeczywistości SendMessageW (lub SendMessageW, w zależności od ustawień)… Zastanawiam się, czy ktokolwiek w Microsofcie pisał coś większego niż hello world. Jedna z pierwszych rzeczy, której można się nauczyć przy pisaniu większych rzeczy jest to, że kolizje nazw są złe. Z tego powodu ktoś prawie mądry (prawie, bo wolałbym porządny system modułów, jak w D) dodał do C++ przestrzenie nazw. W C tego nie ma, ale większość programistów wyrobiła sobie nawyk dodawania prefiksów przed nazwami zmiennych, funkcji i makr, przykładowo jeśli ktoś pisał bibliotekę foo, to zaczynał wszystkie nazwy od foo_, dzięki czemu kolizje nazw były rzadsze. W Microsofcie nikt o tym nie słyszał, dzięki czemu funkcje o nazwach SendMessage czy GetObject noszą w rzeczywistości nazwy SendMessageA i GetObjectA…

To nie wszystko! Jest kilka nawet ciekawszych rzeczy! Jeśli zaczniemy szperać w tej kupie bajzlu, znajdziemy coś takiego (rpcndr.h):

#define small char

Naprawdę fajnie. Nawet fajniej jest, gdy później w kodzie nazwiemy jakąś zmienną small. Dostaniemy uroczy komunikat błędu, który niewiele pomoże (chyba, że wiemy o tej definicji). Są też dwa, można rzec klasyczne już, wk***iacze:

#define far
#define near

Szkoda, że te nazwy są zapisane małymi literami – jeśli byłyby z dużej, to ktoś mógłby pomyśleć, że to naprawdę są makra, a tak ktoś zajmuje nam całkiem miłą nazwę. Nieładnie!

Na całe szczęście WinAPI jako takiego używa się stosunkowo rzadko – zwykle istnieją wygodniejsze sposoby na zrobienie czegoś. Ciekawi mnie, czy zostanie to kiedykolwiek poprawione. Ktoś chętny do przerobienia windows.h? ;P

Specyfikacje wyjątków a Visual [pl]

Specyfikacje wyjątków nie są często używane (z pewnych powodów), ale jak już ktoś chce tego użyć, to natrafia na pewien problem o nazwie „Microsoft C/C++ Optimizing Compiler”, który wsparcia dla nich nie ma… Ale czy tak jest na pewno?

Napiszmy sobie jakiś bardzo prosty kod, który ich używa (main.cpp):

#include <cstdio>
#include <cstdlib>
#include <exception>
using namespace std;
 
int foo() throw(int)
{
  throw 4.2;
}
 
void test()
{
  puts("ok");
  exit(1);
}
 
int main()
{
  set_unexpected(test);
  try
  {
    foo();
  }
  catch(double)
  {
    puts("wtf?");
  }
}

Spróbujmy to teraz skompilować:

>> cl /EHsc /W4 main.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.30729.01 for 80x86
Copyright (C) Microsoft Corporation.  All rights reserved.
main.cpp
main.cpp(6) : warning C4290: C++ exception specification ignored except to indicate a function is not __declspec(nothrow)
Microsoft (R) Incremental Linker Version 9.00.30729.01
Copyright (C) Microsoft Corporation.  All rights reserved.
/out:main.exe
main.obj
>> 

Jak widać, kompilujemy z włączonym wyjątkami (/EHsc) i ostrzeżeniami na prawie najwyższym poziomie (można jeszcze zrobić /Wall, ale kompilator wtedy przesadza, /W4 wystarcza), czyli tak, jak na codzień kompiluję większość kodów (nie do końca, bo na codzień jeszcze zwykle dorzucam optymalizacje :>). Widać też, że ta specyfikacja wyjątków się kompilatorowi nie podoba i twierdzi on, że ją zignoruje. Uruchommy więc program:

>> ./main
wtf?
>> 

Wynika więc z tego tyle, że kompilator ma specyfikacje wyjątków w głębokim poważaniu… A ściślej, ma je w głębokim poważaniu, jeśli nie podrzucimy mu pewnego nieudokumentowanego switcha – /d1ESrt. Skompilujmy więc ten kod jeszcze raz, ale teraz dla odmiany z tym hidden switchem (i /nologo, które powoduje, że kompilator nie wypluwa swojej nazwy i takich tam):

>> cl /EHsc /W4 /d1ESrt /nologo main.cpp
main.cpp
>> 

OK, siedzi cicho i nie wypluwa ostrzeżenia. Sprawdźmy teraz, czy kod działa:

>> ./main
ok
>> 

Pełen sukces. Udało nam się przekonać cl do respektowania czegoś, czego oficjalnie nie wspiera… MS is too lame :P.