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!