My theory about the future of the web

The shape of today's network is rapidily changing. First there was dot-com bubble, now we have Web 2.0 and „user generated content" era. It's time to wonder what's going to be next.

I'm not the first one to mention that, but I think that in the nearest future we'd see User Generated Portal. I can imagine users that are programming features they need in portal, and share this code with others. Firefox plugins seem to be an example of such idea but on client's side. No one has yet created technical possibilities to dynamically create web portal and include custom applications in it.

Facebook API is the first sign of new era. But their implementation is very simple. Sorry, but including 3rd party content in an Iframe is just a raw hack, not a solution to the problem. They also don't provide any kind of hosting, to run application you have to run your own datacenter. If you could upload applications directly to portal it would result in a trivial deployment cycle (from the programmer's point of view).

Nowadays programmer work time is very expensive. Everything suggests that this price isn't going to fall, even with the crowd of cheap chineese/Indian developers. The demand for software is growing.

Try to imagine web portal with all possible features anyone could ever need. The only problem would be to learn how to use them. That is the job for the portal owner. He should carefully choose enabled applications by default for each target group.

Today building new features is limited primairly by developers, it can be changed.

Social networking: shortest path between users

Description of my algorithm for finding shortest paths in social network portal. It reduced search times to several milliseconds.

Introduction to Motoman industrial robots

At robotics in PJIIT we have two Motoman SK6 industrial robots. Here are movies with robots doing sample jobs.

Left robot with job called "bottle". The robot was intended to get bottle from table and shake it several times. It almost works...


The same job, but view is from camera on robot arm.


Right robot with my favorite fast-speed test

Motomany - podnoszenie kostki

Projekt ma już dwa lata, ale może czas go przypomnieć.

Robot miałby automatycznie znajdować Kostki w okolicy, podnosić je, i coś z nimi dalej robić. Na przykład układać w piramidkę :)

Największą częścią projektu jest rozróżnienie kostki od otoczenia. Aby to uprościć oznaczyłem kostki specjalnymi markerami. Oto wczesny etap prac nad markerami. W oknie po lewej części widać obraz z kamery wraz z nałożonymi czerwonymi liniami określającymi kontury markera. Po prawej stronie okno z widokiem rozpoznawanych krawędzi.



Oto film, na którym pokazane jest działanie algorytmu w czasie rzeczywistym. Czerwony kwadrat, numerki i kolorowe punkty zostały nałożone na obraz z kamery.


A tak wygląda robot automatycznie podnoszący kostkę. Na tym prace niestety stanęły. Pewnie dlatego, że temat przestaje być ciekawy gdy już wiadomo jak go rozwiązać...

Jak ustawić tablicę integerów na zadaną wartość?

Mam proste zadanie. Ustawić tablicę kilku milionów intów na podaną wartość. (kompilaor gcc, procek p4/xeon)

Brzmi banalnie. Pierwszy kod:

void fill_standard(int bit_field, int *buf, int nodes_length){
    int uid;
    for(uid=0; uid < nodes_length; uid++)
        *buf++ = bit_field;
}

Problem taki, że to strasznie długo trwa. W przypadku 16 milionów integerów zajmuje to 87ms.
No to może by to zaimplementować dla mmx?

void fill_mmx(int bit_field, int *buf, int nodes_length){
    __m64 m =  _mm_set1_pi32(bit_field); /*m = */
    __m64 *ptr = (__m64*) buf;
    int uid;
    for(uid=0; uid < nodes_length/2; uid++)
        *ptr++ = m;
}

Już lepiej. 47 milisekund. A może sse2?

void fill_sse(int bit_field, int *buf, int nodes_length){
    __m128i *ptr = (__m128i*) buf;
    __m128i s = _mm_set1_epi32(bit_field);
    int uid;
    for(uid=0; uid < nodes_length/4; uid++){
        *ptr++ = s;
    }
}

Hmm. 47 milisekund. Tyle ile w przypadku mmx. To ciekawe że nowoczesny sse2 nie jest szybszy.
A może by tak spróbować zapisywać do pamięci jakoś inaczej? Może na przykład z ominięciem cache?

void fill_sse_nocache(int bit_field, int *buf, int nodes_length){
    __m128i *ptr = (__m128i*) buf;
    __m128i s = _mm_set1_epi32(bit_field);
    int uid;
    for(uid=0; uid < nodes_length/4; uid++){
        _mm_stream_si128(ptr++, s);
    }
}

18 milisekund. Pięciokronie szybciej niż na początku, to już coś. Ciekawe czy da się szybciej. Pełen kod moich testów jest tu.

A gdyby tak mmapować jeden segment z jakiegoś plik który już jest ustawiony na dobrą warość?
No może to już kombinowanie :)

A może jest jakaś szybsza metoda?

UPDATE#1:
Ciekawe, dodanie prefetch do kodu sse3_nocache dwukrotnie wydłuża program :)

void fill_sse2(int bit_field, int *buf, int nodes_length){
    __m128i *ptr = (__m128i*) buf;
    __m128i s = _mm_set1_epi32(bit_field);
    int uid;
    for(uid=0; uid < nodes_length/4; uid++){
        __builtin_prefetch(ptr+2, 1,1);
        _mm_stream_si128(ptr++, s);
    }
}

34ms, ale tego można się było spodziewać.

UPDATE#2:
Nie sprawdziłem tego wcześniej. Ale okazuje się że _mm_stream_pi32 dla MMX jest tak samo szybkie jak dla SSE.

void fill_mmx2(int bit_field, int *buf, int nodes_length){
    __m64 m =  _mm_set1_pi32(bit_field); /*m = */
    __m64 *ptr = (__m64*) buf;
    int uid;
    for(uid=0; uid < nodes_length/2; uid++)
        _mm_stream_pi(ptr++, m);
}

Też 16ms.

UPDATE#3:
Ciekawe, już pakowanie danych po 32 bity instrukcją _mm_stream_si32 nie daje dużego przyspieszenia.

UPDATE#4 Ważne:
No dobra. Wszystkie moje wyniki do śmieci... Okazuje się że pierwsze przelecenie przez tablicę jest bardzo wolne. Prawdopodobnie wynika to z tego że system musi obliczyć tablicę TLB.

Podsumowywując wyniki. Pierwszy przebieg jest bardzo wolny. Kolejne przebiegi używające _mm_stream_si32/_mm_stream_si/_mm_stream_si128 są dwukrotnie szybsze niż odpowiedniki 'konwencjonalne'.