Busy? That is an understatement!

These days I am so busy that I really do not know what to do first. I need to finish my tasks for IPSC, optimally today's evening. I need to read 3 more scientific articles (5 done so far) and watch several presentations for tomorrow's exam from my networking class. Next Friday we are submitting a paper to CoNEXT. On 13th, I need to submit the final version of my candidacy exam proposal. On 20th, there is my candidacy exam for which I need to prepare (and beta-test) my presentation. One day after, I am submitting my networking class miniproject report. Finally, on 6th June I need to submit my project report. Did I forgot something? Oh well, there will be Java class exam (I do not know yet) for which I will need to judge a hundred sheets of paper handwritten in French, probably with the deadline roughly 10 days.

So, can you beat me? Do you have more (or more tighter) deadlines?

Rejected!

My paper to HotSDN about why rules should not rule was rejected. Certainly I am not in so bad mood as after the rejection from my first love. But that is maybe because I was prepared for paper rejections -- it is certainly not easy to get into a conference/workshop. So should I divorce with the idea? Maybe. It seems that I am playing on somebody else's ground and maybe there is not enough space. Anyway, I will let it be for now -- I have a lot of other things to do.

EPFL Vivapoly's RLC run

Le jeudi j'ai participé à Vivapoly course à pied. La longueur était 3.5km, assez court. Mon plan était de terminer dans 16 minutes. Mais ce n'était pas possible. J'ai terminé et 17 minutes et 30 secondes -- exactement 5 minutes par kilomètre.

Codejam fail

Comme d'habitude, mes competences en programmation ne sont pas satisfaisants. J'ai fini sur 806e place et je n'ai pas avancer à 3e ronde. Mais j'ai gagné un tee-shirt :-)

Vous povuvez voir les problèmes et résultats.

P=NP?

Based on the http://www.win.tue.nl/~gwoegi/P-versus-NP.htm I would like to take a new approach on deciding P=NP. Indeed, after sketching through the list, it seems that P=NP does not have a definite answer and its validity depends on some random variable.
Thus, the P=NP holds approximately 50% of the time.

Want to re-check my findings?

> wget 'http://www.win.tue.nl/~gwoegi/P-versus-NP.htm'
> NO=`cat P-versus-NP.htm | grep '\[Not equal\]' | wc -l`
> YES=`cat P-versus-NP.htm | grep '\[Equal\]' | wc -l`
> echo "100*$YES/($YES+$NO)" | bc -l

The result is that P=NP for approximately 51.7% of the papers, therefore under the assumption of uniform distribution we may conclude that P=NP holds roughly half of the times you try to solve it :-)

Google translate

Google translate vous donne parfois des résultats étranges. Mais cette traduction est beaucoup trop.

Jour férié? Pas pour moi.

Aujourd'hui est un jour férié en Suisse. Mais je n'ai pas eu le temps. Je prépare des problèmes de IPSC tout le jour. IPSC est une internationale compétition de programmation et je suis l'un des organisateurs. Vous êtes invités à participer le Samedi 2er juillet.

Going français

In order to practice my french, I decided to try to use it also on this blog. You may guess that I will write only a simple texts and with heavy help of dictionaries and Google translate. Moreover, there will be probably a ton of errors. So if you parle français, I will be glad to receive any feedback/corrections to my posts. And if you do not speak french, I guess you can use Google translate as well to translate my posts. If nothing else, you may get very funny results, especially if translating to a less common language.

Latex figures disappearing? Why not...

Latex is a fine system but sometimes it have its own quirks. For example yesterday I spend at least one hour trying to figure out where are my figures. Figures are parsed, but then, nothing is placed on the page. Even latex logs were not helping. Today, I know what was the problem -- I had one figure which is together with the previous figure longer than one page. This is normal case for figures. However, I am using the two-column style, the first figure is spanning two columns, the second one just one column. And apparently, if you combine all these aspects together you get -- nothing. Big nothing instead of second figure. And more interestingly, big nothing instead of all successive figures. So, beware of the long figures!

To hash, to map?

As the question in the title says, in this post I will be comparing the two C++ std library algorithms, unordered_map (formerly known as hash_map) and map. The focal point of the comparison is the memory -- which algorithm is more effective? For this purpose, I created a simple program which inserts N random keys into the data structure. Then I needed to obtain a memory information. At the first glance, it seemed that

mallinfo().uordblks

will be sufficient. However, after going through a painful excercise with the std::vector, it seems that vector (and therefore probably also unordered_map) use some other weird technique -- instead of malloc()-ing the data, the vector mmap()-s some memory blocks! Thus, the real memory usage is more like

int mem = mallinfo().hblkhd + mallinfo().uordblks;

Anyway, here is the program:

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
using namespace std;

#define HASH 0

#if HASH
  #include <unordered_map>
  typedef unordered_map<int, int> mymap;
  const char* text = "hash";
#else
  #include <map>
  typedef map<int, int> mymap;
  const char* text = "map";
#endif

const int Ki = 1000;
const int Mi = 1000 * Ki;

const int TESTS = 5;
int test_sizes[TESTS] = {Ki, 10 * Ki, 100 * Ki, Mi, 10 * Mi};

int main() {
  mymap mapa;
  for (int t = 0; t < TESTS; t++) {
    while (mapa.size() < test_sizes[t]) {
      int k = rand();
      mapa[k]++;
    }
    // total memory (malloc + mmap)
    int mem = mallinfo().hblkhd + mallinfo().uordblks;
    printf("%s: Items: %d, Mem: %d, per-entry: %.1f\n", text, 
          test_sizes[t], mem, mem * 1.0 / test_sizes[t]);

  }
}

And the results:
(Note that  2 integers (key&value) consume 8 bytes).

map: Items: 1000, Mem: 48000, per-entry: 48.0
map: Items: 10000, Mem: 480000, per-entry: 48.0
map: Items: 100000, Mem: 4800000, per-entry: 48.0
map: Items: 1000000, Mem: 48000000, per-entry: 48.0
map: Items: 10000000, Mem: 480000000, per-entry: 48.0

hash: Items: 1000, Mem: 46016, per-entry: 46.0
hash: Items: 10000, Mem: 441504, per-entry: 44.2
hash: Items: 100000, Mem: 4211808, per-entry: 42.1
hash: Items: 1000000, Mem: 40454240, per-entry: 40.5
hash: Items: 10000000, Mem: 463691872, per-entry: 46.4

The conclusion? Both hashing and binary trees use roughly the same amount of memory (hashing a bit less but it is fluctuating as the hash-table is resized). And the overhead is quite big -- 5 to 6 times for the integer key-value pair.

Howto: install dctcp (or new kernel) in debian

As I was fighting with DCTCP (datacenter TCP) installation last week, here is the recipe on how to win this battle. Some of the steps are trivial but some of them like reading the old tactics and ensuring that you really won are not an obvious steps for new generals.


Prepare for the battle:
[ ~ ]>sudo apt-get install kernel-package libncurses5-dev fakeroot


Get instructions for operation "dctcp":
[ ~ ]>mkdir dctcp
[ ~ ]>cd dctcp
[ ~/dctcp ]>wget  http://www.stanford.edu/~alizade/Site/DCTCP_files/dctcp-2.6.38.3-rev1.1.0.tgz
[ ~/dctcp ]>tar -xvvf dctcp-2.6.38.3-rev1.1.0.tgz


Get the battle plan:
[ ~/dctcp ]>wget http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.38.3.tar.bz2
[ ~/dctcp ]>tar jxvf linux-2.6.38.3.tar.bz2


Prepare supplies:
[ ~/dctcp ]>cp dctcp-2.6.38.3-rev1.1.0/dctcp-2.6.38.3-rev1.1.0.patch linux-2.6.38.3
[ ~/dctcp ]>cd  linux-2.6.38.3
[ ~/dctcp/linux-2.6.38.3] patch -p1 < dctcp-2.6.38.3-rev1.0.0.patch


Read old battle tactic:
[ ~/dctcp/linux-2.6.38.3 ]>cp /boot/config-x.y.z-amd64 .config
[ ~/dctcp/linux-2.6.38.3 ]>make oldconfig


Begin the battle:
[ ~/dctcp/linux-2.6.38.3 ]>fakeroot make-kpkg clean
[ ~/dctcp/linux-2.6.38.3 ]>fakeroot make-kpkg kernel_image

Battlefield after the battle:
[ ~/dctcp/linux-2.6.38.3 ]>cd ..
[ ~/dctcp ]>sudo dpkg -i linux-image-2.6.38.3_2.6.38.3-10.00.Custom_amd64.deb


Ensure the victory by signing boot contracts:
[ ~/dctcp ]>cd /boot
[ /boot ]>sudo mkinitramfs -o initrd.img-2.6.38.3 2.6.38.3
[ /boot ]>sudo update-grub
[ /boot ]>sudo reboot

Codejam R1B

Today's codejam was excellent. I must say the problems were nice. One easy, one technical where you needed to be careful about a lot of conditions and finally one hard which was quite interesting:

"I have a set of positive integers S. Can you find two non-empty, distinct subsets with the same sum?
Small dataset:  |S|=20. Each number in S will be a positive integer less than 10⁵
Large dataset: |S|=500. Each number in S will be a positive integer less than 10¹²"

I did only manage to solve the easy input. However, asking Misof about the solution, it seems that the trick was to use Birthday paradox. Assuming that the resulting numbers are of size 10¹⁴, it should suffice to generate 10⁷(different) random subsets and we have a collision. I must admit I love that idea. It is so unconventional for a problem in contests such like this to really depend on randomness/probability but here it actually makes sense as the number of random subsets is quite large but we can process ten million random subsets quite fast. Great job, problemsetters!

First edition of "bike to work"

Yesterday I finally managed to test how hard can it be to simply bike to work. And how long it takes. For those of you who voted for my time (i.e. nobody), my time from Chavornay to EPFL is 1:40. Not that bad, the average is cca 19km/h.

The time for going back is not known yet. It was quite late when I went back and the weather outlook did not look very enjoyable so I decided to take a train from Cossonay. And indeed it was a good decision -- just when the train arrived, the first drops of rain appeared.

First Swiss bike trip

Last weekend, after I arrived back from the US, I decided to use remaining half-day for my first real bike trip. As I was time-restrained, I selected a track near my home. From Chavornay, I went to Baulmes when the real fun begins. By the real fun I mean a 10% ascent of total height 600 meters. Maybe you think that 600 meters is nothing. Well, just get on a bike and try it, it is not as easy as it seems to be. Anyway, at the top I arrived at Col de l'Aiguillon and then enjoyed a nice downhill run to L'Auberson. After that I continued to St Croix where I missed the correct turn so I had to go back. From St Croix I went thorough LaSagne (although there were no lasagne to see on the street) and mountain bike path back to Baulmes and then Chavornay.

After the trip, I had a feeling that my muscles will be complaining at least for a week (they were quite complaining on that mountain bike path). But to my astonishment, they were complaining just mildly the next day and then they decided to go back to the work. So, it seems to me that the next time I should shoot for something higher. Let us say 1000m of main ascent. For the unfortunate people that were not going on that trip (i.e. everyone minus me), the photos are here.



View Larger Map

NSDI 12

As you may know, I was in the USA previous week. Unfortunately, it wasn't sightseeing trip. In fact, I attended NSDI 12 networking conference which was held in San Jose. The conference was splendid -- there were many high-quality papers and presentations. The ones I enjoyed most were Jellyfish, ultra-low latency for datacenters and multipath tcp. And of course our paper about testing openflow applications (here I extremely enjoyed the fact that I was not the presenter).



In total, it was a good stay. Unfortunately, there were not many occasions to do the sightseeing. In fact, I had just one afternoon to do it. After a brief visit to Google where we met my advisor's former advisor, I was left with a couple of hours to spend. However, after making a quick poll, I realized that there is really nothing in San Jose. Edit -- really big nothing -- not only there is nothing to see but it is spread in traditional Californian way all over the place. So I decided to visit San Francisco instead. To go there, I took a train with which I was not very impressed. Even for express trains, it takes ages to go the 80 kilometers. And by ages I mean more than hour and half. Plus the american trains are roughly two decades late -- when was the last time you saw a diesel locomotive? If I skip trains from Banska Bystrica to Zilina which are not electrified probably due to more than twenty tunnels on that route, I do not remember when I last saw such train.

Anyway, San Francisco is interesting city. Skyscrapers, old trams, chinatown and a hill in the middle of the city which does not affect the perfect square layout of roads. The only thing I do not understand is how can they drive these very steep streets. If you are interested in some pictures, you can find them at usual place.

May, the month of love

Or not? Well, certainly not for me. I did not fall in love with this-month's Swiss weather from the beginning. The first weekend and it is rainy? Prognosis for the next one? Probably rainy although no one is sure.
So, instead of exploring the beauties of Switzerland, I sit in my room and do other (less useful) stuff like writing this blog, making lunch and catching up with my french homework. So, stay tuned for more blog entries.

my phone

	my Phone	iPhone
Manufacturer	Motorola	Apple
Weight	86g	135g
Battery	You do not even remember when was the last time you charged the battery	You remember very well when was the last time you forgot to charge battery
Input	touch buttons (does work with everything)	touch screen (does not work with anything other than fingers)
Calendar integration	Google calendar integrated via SMS	calendar app
Productivity	No time wasted (seriously, there is nothing you can waste time on)	Excessively wastes time (Angry Birds, etc.)
Music	my tunes (free)	iTunes (paid)
USB compatibility out of the box	no (needs driver)	no (needs proprietary cable)
Fragility	breaks everything else easily	breaks easily

[edit: evidently I am violating a trademark :-), see http://www.myphone.pl/ ]

Butterflies everywhere

The headline is the best characterization of Papiliorama in Kerzers. I went to this "sightseeing excursion" because it was a rainy day. And it was a splendid decision which made my day much more brighter. The sheer amount of the butterflies was amazing, certainly not countable by a single person. And the colors -- blue, red, green, yellow, brown, ... You name it - you got it. Plus if you have not enough, you can see some night animals and visit a jungle.

Want to see more? Check it out at
http://people.ksp.sk/~ppershing/foto/index.php?spgmGal=2012/2012-04-22-exkurzia-papiliorama-Kerzers

Beta-testing bike (old)

I really did not have time to write this down and now it is a bit late. Anyway, my first bike experience of this season was a beta-test of my new bike back in Slovakia. I started from my home, then continued to Harmanec by quite busy roads (although when it was possible, I used parallel roads through the villages). But that was just the preparation for the main part -- ascent from Harmanec to Kordiky by a paved road in the woods. The ascent was only 400m but still it was quite a workout. The most enjoyable part of the trip was of course the descent. As you can see from the graph, it was quite fast and I certainly warmed up my brakes.

View Larger Map

(Note that the x-axis is time, the descent was not so steep as the graph suggest, it was only fast).