I accidentally created an infinite loop

I needed to iterate through all values of 32-bit unsigned integer, so I wrote:

#include <stdint.h>
for (uint32_t i=0; i <= UINT32_MAX; i++) {
   // whatever
}

Is it ok? No, because value of uint32_t will never exceed UINT32_MAX = 0xffffffff. Of course we can use larger types, like uint64_t, but on 32-bit machines this requires some additional instructions. For example gcc 4.7 compiled following code:

void loop1(void (*fun)()) {
 for (uint64_t i=0; i <= UINT32_MAX; i++) {
  fun();
 }
}

to:

00000000 :
   0:   57                      push   %edi
   1:   bf 01 00 00 00          mov    $0x1,%edi
   6:   56                      push   %esi
   7:   31 f6                   xor    %esi,%esi
   9:   53                      push   %ebx
   a:   8b 5c 24 10             mov    0x10(%esp),%ebx
   e:   66 90                   xchg   %ax,%ax
  10:   ff d3                   call   *%ebx
  12:   83 c6 ff                add    $0xffffffff,%esi
  15:   83 d7 ff                adc    $0xffffffff,%edi
  18:   89 f8                   mov    %edi,%eax
  1a:   09 f0                   or     %esi,%eax
  1c:   75 f2                   jne    10 
  1e:   5b                      pop    %ebx
  1f:   5e                      pop    %esi
  20:   5f                      pop    %edi
  21:   c3                      ret    

TBH, I have no idea, why such weird sequence has been generated (add, adc, or, jnz). The simplest and portable solution is to detect wrap-around 32-bit value after increment:

uint32_t i=0;
while (1) {
 // loop body

 i += 1;
 if (i == 0) // wrap-around
  break;
}

In assembly code it's even simpler, because CPU sets the carry flag:

     xor %eax, %eax
loop:
     ; loop body

     add $1, %eax
     jnc loop

Calculate floor value without FPU/SSE instruction

Presented algorithm works properly for any normalized floating point value, examples are given for double precision numbers (64-bit). Read more ...

Convert float to int without FPU/SSE

This short note shows how normalized floating point value could be safely converted to integer value without assistance of FPU/SSE. Only basic bit and arithmetic operations are used. Read more ...

fopen a directory

It's not clear how function fopen applied to a directory should behave, manual pages don't say anything about this. So, our common sense fail --- at least when use standard library shipped with GCC, beacuse fopen returns a valid handle.

Discussion on stackoverflow pointed that fseek or ftell would fail. But on my system it's not true, ftell(f, 0, SEEK_END) returns size of opened directory.

Only when we trying to read data using fread or fgetc the errno variable is set to EISDIR error code.

Here is output from simple test program:

$ ./a.out ~
testing '/home/wojtek'...
fopen: Success [errno=0]
fseek: Success [errno=0]
fseek result: 0
ftell: Success [errno=0]
ftell result: 24576
feof: Success [errno=0]
feof result: 0 (EOF=no)
fgetc: Is a directory [errno=21]
fgetc result: -1 (EOF=yes)
fread: Is a directory [errno=21]
fread result: 0

Extensions to x86 ISA are useless

Intel announced new extension to SSE: instructions accelerating calculating hashes SHA-1 and SHA256. As everything else added recently to x86 ISA, these new instructions address special cases of "something". Number of instructions, encoding modes, etc. is increasing, but do not help in general.

Let see what sha1msg1 xmm1, xmm2 does (type of arguments is packed dword):

 result[0] := xmm1[0] xor xmm1[2]
 result[1] := xmm1[1] xor xmm1[3]
 result[2] := xmm1[2] xor xmm2[0]
 result[3] := xmm1[3] xor xmm2[1]

1. Logical operation "xor" is hardcoded. Why we can't use "or", "and", "not and"? These operations are already present in ISA.
2. Indices to xmm1 and xmm2 are hardcoded too. Instruction pshufd accepts immediate argument (1 byte) to select permutation, why sha1msg1 couldn't be feed with 2 bytes allowing programmer to select any permutations of arguments?
3. Sources of operators are also hardcoded. Why not use another immediate (1 byte) to select sources, for example 00b = xmm1/xmm1, 01b = xmm1/xmm2, 10b = xmm2/xmm1, 11b = xmm2/xmm2.

Such generic instruction would be saved as generic_op xmm1, xmm2, imm_1, imm_2, imm_3 and execute following algorithm:

 for i := 0 to 3 do
  arg1_indice := imm_1[2*i:2*i + 1]
  arg2_indice := imm_2[2*i:2*i + 1]

  if imm_3[2*i] = 1 then
   arg1 := xmm1
  else
   arg1 := xmm2
  end if

  if imm_3[2*i + 1] = 1 then
   arg2 := xmm2
  else
   arg2 := xmm1
  end if

  result[i] := arg1[arg1_indice] op arg2[arg2_indice]
 end for

Then sha1msg1 is just a special case:

 generic_xor xmm1, xmm2, 0b11100100, 0b01001110, 0b01010000

Maybe this example is "too generic", too complex, and would be hard to express in hardware. I just wanted to show that we will get shine new instructions useful in few cases. Compilers can vectorize loops and make use of SSE, but SHA is used in drivers, OS and is encapsulated in libraries --- sha1msg1 and friends will never appear in ordinary programs.

The most complex instruction in x86 ISA

This instruction is... FBSTP. The instruction is advanced converter from integer part of floating point number to BCD format. Sounds weird? Read more.

Problems with PDO for PostgreSQL on 32-bit machine

Size of integer in PHP depends on machine, it has 32 bits on 32-bit architectures, and 64 on 64-bit architectures.

On 32-bit machines PDO for PostgreSQL always convert bigint numbers returned by server to string. Never cast to integer even if value of bigint would fit in 32-bit signed integer.

Type bigint is returned for example by COUNT and SUM functions.

On 64-bit machines there is no such problem because PHP integer is the same as bigint.

Procedury składowane w PostgreSQL

Książka na wikibooks - opisuje zarządzanie procedurami z punktu widzenia bazy danych, oraz szczegółowo wbudowany język PL/pgSQL.

Dopisek z 2013-12-09: udostępniłem skrypty SQL, które powstały na potrzeby tego podręcznika.

Hardware blog

Very interesting blog, posts about CPU/hardware design are worth to read - http://danluu.com/

Short story about PostgreSQL SUM function

Here is a simple PostgreSQL type:

CREATE TYPE foo_t AS (
 id    integer,
 total bigint
);

and a simple query wrapped in stored procedure:

CREATE FUNCTION group_foo()
 RETURNS SETOF foo_t
 LANGUAGE "SQL"
AS $$
 SELECT id, SUM(some_column) FROM some_table GROUP BY id;
$$;

Now, we want to sum everything:

CREATE FUNCTION total_foo()
 RETURNS bigint -- same as foo_t.total
 LANGUAGE "SQL"
AS $$
 SELECT SUM(total) FROM group_foo();
$$;

And we have an error about type inconsistency!

This is caused by SUM function -- in PostgreSQL there are many variants of this function, as the db engine supports function name overriding (sounds familiar for C++ guys). There are following variants in PostgreSQL 9.1:

$ \df sum
                         List of functions
   Schema   | Name | Result data type | Argument data types | Type 
------------+------+------------------+---------------------+------
 pg_catalog | sum  | numeric          | bigint              | agg
 pg_catalog | sum  | double precision | double precision    | agg
 pg_catalog | sum  | bigint           | integer             | agg
 pg_catalog | sum  | interval         | interval            | agg
 pg_catalog | sum  | money            | money               | agg
 pg_catalog | sum  | numeric          | numeric             | agg
 pg_catalog | sum  | real             | real                | agg
 pg_catalog | sum  | bigint           | smallint            | agg

Smaller types are promoted: from integer we get bigint, from bigint we get numeric, and so on.

PHPCon 2013

PHPCon 2013 był moją pierwszą konferencją, więc miałem pewne wyidealizowane wyobrażenia co do przebiegu całej przygody. W skrócie: chciałem dowiedzieć się czegoś nowego, zostać zmiażdżonym wiedzą prelegentów.

Do Szczyrku pojechałem z czwórką kolegów z pracy. I to był naprawdę dobry wybór, choćby dlatego, że się znamy. Aha, te oszołomy, jak jeden mąż, napisali że są z Wrocławia, chociaż żaden z nich się tam nie urodził, a mieszkają w tym mieście od ledwie paru lat. Jako jedyny nie wstydziłem się, że pochodzę z głębokiej prowincji i miałem na plakietce napisane "Łańcut". Na szczęście nikt tego nie zauważył. Chyba.

Organizacyjnie było całkiem nieźle, chociaż irytowało nieterminowe rozpoczynanie wykładów. Szczytem był wykład w soboty, gdzie czekaliśmy dobry kwadrans, przy ogólnym chaosie i hałasie. Jedzenie było dobre, łóżka wygodne, a woda w łazience mokra. Mieliśmy karty magnetyczne do pokojów, co kojarzyło mi się z Jamesem Bondem. Być może dlatego, że w tym filmie -- oglądanym w telewizorze marki Rubin, czy innym sowieckim barachle -- po raz pierwszy zobaczyłem takie cudo.

Poniżej opinie o wykładach, nie siliłem się na obiektywność. A że lubię narzekać, to narzekałem. Posłuchajcie.

 

Praktyczne Code Reviews - Sebastian Marek

Niestety, był to pierwszy wykład na którym byliśmy, ominął nas -- zdaje się legendarny -- wykład o Drupalu.

Temat był niezwykle ciekawy, Sebastian mówił jasno i klarownie (miałem nadzieję, że pozostałe wykłady będą prowadzone jeśli nie lepiej, to co najmniej tak dobrze). Całość była dość ogólnikowa, naprawdę brakowało konkretnych przykładów code review, może nawet jakiegoś rzeczywistego CR. Sebastian nie powiedział na co zwracać uwagę, a co można olać. Odwołanie się do zdrowego rozsądku jest w sumie oczywiste, ale to trochę mało. Czułem niedosyt.

Jednak myślę, że dla osób, które dopiero wprowadzają proces code review lub chcą wprowadzić, ten wykład dał dużo.

W przypadku tego wystąpienia zabrakło czasu na pytania z sali. A mogło być ciekawie, szkoda.

Dependency Injection w PHP - Kacper Gunia

Wykład był skierowany do osób, które nie zetknęły się z DI. Przyzwoite teoretyczne wprowadzenie z punktu widzenia wzorców projektowych dało dobry grunt dla dalszej części. Następne pokazanie tych idei na dość prostym przykładzie (ale błędy w kodzie... eee) też było porządne. Niestety końcówka wykładu była omówieniem realizacji DI w Symfony. Dla osób, które z niego nie korzystają, to na pewno było raczej ciężkie, dla osób używających Symfony -- banały.

Szkoda, że ta ostatnia część nie poruszyła tematu compiler passów, w ogóle tematu budowania kontenera, który jest mocnym atutem symfonowego rozwiązania. Albo zamiast wchodzenia w szczegóły tej jednej implementacji można było pokazać praktyczną realizację także w innych bibliotekach do DI.

 

Komunikacja czasu rzeczywistego w PHP - czyli co z tymi WebSocketami - Przemysław Pawliczuk

Temat naprawdę gorący w świecie webowy (chociaż biorąc pod uwagę, że idea socketu ma 40 lat, to sprawa ma temperaturę górskiego kamienia). Niestety wykład był słaby i chaotyczny. Przemek próbował uzyskać kontakt z publicznością, ale wg mnie raz, że było za duże audytorium, dwa że mało osób się zetknęło z websocketami, mocno te próby utrudniło.

Trudno było złapać myśl przewodnią. Bardzo szkoda, bo wiele wskazywało na to, że miał praktyczną wiedzę -- jakoś nie potrafił tego przekazać. Wydaje się, że w jednej prezentacji prelegent upchnął za dużo materiału, pojawił się jakiś prosty przykład [kod], ale zupełnie bez kontekstu i dalszego rozwinięcia.

Aha, web działa głównie na TCP, który to protokół nie jest czasu rzeczywistego. Więc cokolwiek z niego korzysta, też nie będzie czasu rzeczywistego. Rozumiem jednak, że tutaj "czas rzeczywisty" był synonimem dla "całkiem szybko".

 

Moving Away from Legacy code with BDD - Konstantin Kudryashov

Bardzo przystępnie przedstawione pewne pomysły, jak sobie poradzić z kodem "po prostu działającym", szczególnie fajnie przedstawiona, dla mnie nowa, idea impact mappingu. Jednak to temat raczej dla managerów, zarządu, a więc tych którzy decydują na co wydawać pieniądze firmy.

Jeden minus tej prezentacji: Konstantin na 3 slajdzie pt. "O czym nie będzie" wymienił Behata i PHPSpec, po czym jednak trochę o nich powiedział. Ponieważ jest ich twórcą można ten psikus zrozumieć.

Aplikacje internetowe w chmurze obliczeniowej - Piotr Bubacz

Wykład był prowadzony bardzo wesoło, ale jednocześnie dość konkretnie, prowadzący miał dobry kontakt z publicznością. Była to interaktywna reklama chmury obliczeniowej Microsoftu, Azure cośtam. Uczciwie trzeba przyznać, że wygląda to całkiem ciekawie, ale podejrzewam, że firmy potrzebujące tego rodzaju rozwiązań już słyszały o Azure. Dla mnie takie sobie.

Najciekawsze: okazało się przy okazji, że Microsoft już nie produkuje programów. Pewnie wynika to z tego, że inżynierów podkupuje im Google, AFAIR trafiło nawet architekta kernela Windowsa. A trochę szkoda, bo Microsoft ma naprawdę porządny dział badawczy, gdzie np. opracowują narzędzia do weryfikacji formalnej kodu (oczywiście nie PHP).

 

Problemy wielozadaniowości w PHP i próby ich rozwiązania - Marek Wałach, Marcin Ceran

Rozumiem to tak: wykład był ogólnie o tym, jak kilku inżynierów zrównolegliło pewne procesy obliczeniowe, polegające na skomplikowanej, konfigurowalnej analizie dużej ilości danych. Użyli do tego demonów pisanych w PHP, co samo w sobie było dość zaskakujące.

Niestety, wykład niespecjalnie odkrywał szczegóły techniczne, prelegenci nie zawsze potrafili wyrazić się jasno i precyzyjnie. Osoby pytające chciały się tego dowiedzieć, jednak tutaj też były problemy, tak że na część pytań odpowiedział współpracownik Marka i Marcina, który lepiej znał technikalia.

Wykład wypadł słabo, a temat był naprawdę, naprawdę ciekawy. Wydaje mi się, że spora część aplikacji wymaga systemów raportowania, więc byłoby fajnie uzyskać przynajmniej jakąś podpowiedź w jakich warunkach to zrównoleglenie się "urodziło"? Jakie były inne próby przyspieszenia i dlaczego zawiodły? Jakie były problemy z PHP-em? Byłem rozczarowany, myślałem, że to samograj -- tylko opowiedzieć o swoich doświadczeniach.

Z ciekawostek: ktoś zapytał o procent pokrycia kodu testami. Padła odpowiedź 5-10%. Kolega Krzyś podsumował to krótko: czyli nie ma testów.

 

Dane przestrzenne, czyli jak nauczyć PHP geografii - Michał Mackiewicz

Lubię narzekać, więc ten wykład powinienem pominąć. Było jak trzeba, a żeby być fair, trzeba napisać, że było bardzo dobrze. Widać, że Michał zna sprawę z praktyki, wykład był rzeczowy, poprowadzony wartko, naprawdę miło się słuchało. Zostały pokazane chyba najważniejsze rozwiązania i problemy związane z GIS. Do tego jasne odpowiedzi na ciekawe pytania z sali.

Jedyne do czego muszę się przyczepić, to używanie słowa "poligon" jako tłumaczenia dla angielskiego "polygon". Na poligonach granaty urywają ręce młodym chłopcom płci obojga, a "polygon" to po prostu swojski "wielokąt".

 

Testy automatyczne - fakty i mity - Wojciech Sznapka

Merytorycznie było ok, chociaż szanowny imiennik nieco za szybko ten wykład prowadził. Zabrakło mi tam nieco szczegółów o testach funkcjonalnych i integracyjnych, tzn. jaką warstwę aplikacji testy funkcjonalne mają testować.

Szkoda trochę, że nie było dokładniejszej dyskusji mitów, czy nawet zabawy ze strony prelegenta w adwokata diabła. Sam uważam, że klient płaci za testy [to był pierwszy mit, o ile się nie mylę].

Ciekawa była dyskusja po wykładzie [dzięki błyskawicznemu tempu zostało sporo czasu], szczególnie o zapewnianiu świeżego środowiska do testów. Co jak się okazało dla wielu z nas jest bolączką i padło kilka pomysłów: przygotowanie "dumpów" przed testami, użycie bazy plikowej SQLlite, baza na RAM-dysku.

 

Allowed memory size of X bytes exhausted - Piotr Pasich

Z jednej strony było to ciekawe wystąpienie, rzeczowe, naprawdę porządne. Wydaje się, że jedno z najbardziej zaawansowanych na tej konferencji. Ciekawe było pokazanie bardzo niskiego poziomu -- jak zapamiętywane są wartości w interpreterze. Fajne było pokazanie, że Xdebug potrafi dużo więcej niż nam się wydaje (sam kiedyś z tego skorzystałem, co pozwoliło mi zwalić winę na innych -- to tak na zachętę).

Był tam jednak jeden fragment, który -- mówiąc eufemistycznie -- mocno mnie zdziwił. Zobaczyliśmy rysunek mapowania pamięci logicznej (virtual memory) na fizyczną (physical memory), z komentarzem, że sterta (heap) jest pofragmentowana. Ale to nie jest ze sobą w ŻADEN sposób powiązane. Aplikacja, nieważne w jakim języku napisana, nie ma pojęcia o pamięci fizycznej. Mapowanie na adresy fizyczne to problem na poziomie systemu operacyjnego, który tak naprawdę ostatecznie rozwiązuje mikroprocesor. Fragmentacja pamięci, a dokładniej "fragmentacja wewnętrzna" to problem o którym mówił Piotr.

Ten błąd rzeczowy trochę razi, ale summa sumarum nie rzutował na całość prezentacji. A może to był po prostu zły rysunek?

Poza tym, gdy była mowa o stosie -- tj. interakcji C z PHP -- też miałem wrażenie, że coś tam nie pasuje. Szczególnie, że trochę w C i asemblerze programowałem, wiem mniej-więcej jak działają interpretery, więc stwierdzenie, że zmienne PHP "żyją" na stosie C mocno mi nie pasowało. Ale nie znam implementacji PHP, więc może niepotrzebnie się tej kwestii czepiam.

Schibsted Tech Polska – Do IT in the Scandinavian Way - Aleksandra Guzik

"Przepraszam, czy ma ktoś laptopa z Windowsem? Serio pytam". Ktoś miał.

 

Sprytne środowiska developerskie - Wojciech Sznapka

W porównaniu do sobotniego wykładu Wojtek zwolnił -- tempo wykładu było w sam raz. Pokazał praktyki wypracowane w swojej firmie, zareklamował kilka narzędzi, które im ułatwiają życie. Okazało się, że w mojej firmie mamy całkiem podobny styl pracy, więc w sumie jedna najważniejsza myśl, która utkwiła mi z wykładu: narzędzia i techniki które pomagają zespołowi nie są za darmo, wymagają tak jak wszystko inne czasu, wysiłku i zasobów, ale bez tego będzie jeszcze gorzej.

Ocena: "celująco, siadaj trzy".

BigData w PHP - Mariusz Gil

Motyla noga, podobał mi się ten wykład! Naprawdę spełnił mój warunek wstępny -- dowiedziałem się czegoś nowego i trochę podjrałem tematem, nie ukrywam. Wykład był prowadzony porządnie, Mariusz miał wiedzę praktyczną, przeszedł bardzo płynnie od ogółu do szczegółu, a nawet do działającego kodu. Powiedział trochę o algorytmie MapReduce, trochę Hadoopie i popularnym MongoDB. Jedyny wykład do którego nie potrafię się przyczepić. Przepraszam.

 

Wprowadzenie do OAuth2 - Michał Pipa

Wykład pokazał wszystko, dużym plusem było to, że Michał w "opisach przyrody" jasno wyraził cele istnienia OAuth2 i jego ograniczenia. Trochę w didaskaliach przemycił informacje, że do tego całego OAuth2 są biblioteki dla PHP.

Jednak bezsensowne było pokazywanie treści konkretnych nagłówków POST i GET. Ja wiem, że to wszystko można ładnie nie tylko curlem, ale i emacsem przez sendmaila, ale mieliśmy przykład przerostu szczegółu nad treścią. W ogóle przykład użycia był mało czytelny.

Jednak ogólnie było w porządku, wiem już o co chodzi.

Inne

 

Zapamiętałem dwie rzeczy:

• Kilkanaście/-dziesiąt osób skandujących "mergujemy". Niestety nikt nie podchwycił okrzyków kolegi Pawełka "pusz z forsem do mastera".
• Anonimowego Tomka, którego przyjaciele próbowali wprowadzić po schodach. Tomek miał pewne problemy ze świadomością wywołane płynami pozaustrojowymi.

A właśnie -- nie pijcie na wykładach, bo to naprawdę wsiowe. Mówię ja, chłopak ze wsi.

SQL surprise

Secret Hackers Rule #11: Hackers read manuals.

Recently I've discovered that PostgreSQL supports setting NULL on column referenced to another table (i.e. foreign constraint) before deleting a row:

CREATE TABLE foo (
 id integer PRIMARY KEY
);

CREATE TABLE bar (
 id integer PRIMARY KEY,
 foo_id integer REFERENCES foo ON DELETE SET NULL
);

INSERT INTO foo (id) VALUES (1);
INSERT INTO bar (id, foo_id) VALUES (1, 1);
DELETE FROM foo;

Without ON DELETE SET NULL server reports error that key foo.id = 1 is still referenced in table bar.

Set of great articles

Lockless Inc publish a lot of interesting, advanced articles. There are some low-level things, algorithms, threading, and many more. Definitely worth to read!

PHP quirk

PHP is very funny language. Here we are simple class, without constructor:

class Foo
{
}

$foo = new Foo($random, $names, $are, $not, $detected);
echo "ok!\n";

One can assume, that interpreter will detect undeclared variables, but as their names state this doesn't happen (PHP versions 5.3..5.5):

$ php foo1.php 
ok!

When class Foo have constructor

class Foo
{
 public function __construct()
 {
 }
}

$foo = new Foo($random, $names, $are, $not, $detected);

everything works as expected:

$ php foo2.php 
PHP Notice:  Undefined variable: random in /home/wojtek/foo2.php on line 10
PHP Notice:  Undefined variable: names in /home/wojtek/foo2.php on line 10
PHP Notice:  Undefined variable: are in /home/wojtek/foo2.php on line 10
PHP Notice:  Undefined variable: not in /home/wojtek/foo2.php on line 10
PHP Notice:  Undefined variable: detected in /home/wojtek/foo2.php on line 10