Queues in Python

I hadn't needed a queue in python before. Yesterday I needed one and I wanted to check the standard library for the implementation of a queue. I ran into a nice webpage: FIFO as single linked lists.

Python offer the pop(0) method of standard list to implement fifo. Unfortunately lists pop(0) operation need to perform a copy of the whole content of the list, this is quite inefficient if you need to store a large set of data.

Thus you should not implement a queue doing pop(0) to a list (unless you have just a few elements). This implementation has N^2 running time!:

#!/usr/bin/python

LIMIT = 10000000

f = list()
for i in xrange(LIMIT):
  f.append(i)
while len(f):
  f.pop(0)

The right way to do it nowadays is:

#!/usr/bin/python

from collections import deque

LIMIT = 10000000

q = deque()
for i in xrange(LIMIT):
  q.appendleft(i)
while len(q):
  q.pop()

In the webpage FIFO as single linked lists I found a very nice implementation and it runs almost as fast as the previous implementation reversing and copying only once, later I will show an example where the performance is much worse. Amortized algorithms are really pretty. What I liked of this example is that I hadn't seen a class inheriting from list before. This example also shows how you can implement a queue by using a single linked list (or a stack).

#!/usr/bin/python

# Code written by Jeremy Fincher

class ListSubclassFifo(list):
    __slots__ = ('back',)
    def __init__(self):
        self.back = []
    def enqueue(self, elt):
        self.back.append(elt)
    def dequeue(self):
        if self:
            return self.pop()
        else:
            self.back.reverse()
            self[:] = self.back
            self.back = []
            return self.pop()

LIMIT = 10000000

f = ListSubclassFifo()
for i in xrange(LIMIT):
  f.enqueue(i)
while len(f):
  f.dequeue()

If you change the test, then deque is much faster than ListSubclassFifo. A hint:

f = ListSubclassFifo()
for i in xrange(LIMIT/5):
  for j in xrange(5):
    f.enqueue(i)
  for j in xrange(5):
    f.dequeue()

Conclusion: use deque.

Discussion (3) Loading... Vote up! Vote down!

interview-cuda-cpu-gpus

I'm very curious about processing with GPUs. CUDA seems to be a very nice implementation available from Nvidia. This is a rather new technology.

I found a nice interview and here are some parts of it:

... GPUs and CPUs are very different. If you built a hybrid of the two, it would do both kinds of tasks poorly instead of doing both well

our next products will support double precision

The bigger picture is going to be that when CUDA tools arrive that allow you to write regular CUDA code that runs on the CPU as well as the GPU. Then it does run everywhere and we can start adding GPUs or CPU cores to increase performance

What Intel does well is not just building good CPUs, it's the fact that they're a vertically integrated manufacturing company - Intel's in the business of turning sand into money

I think that if we were to compete with Intel, we would need to become a vertically integrated company and have our own fabs

We have to keep an eye on Intel's Ct for multi-cores, too.

I'd like to do something with CUDA next year.

Discussion Loading... Vote up! Vote down!

Debugging STL code with GDB

I wanted to debug a small C++ program that uses the STL. I didn't know how to look into STL vectors and I really wanted to do it. I tried with Eclipse and I didn't like to use a GUI. Not just because I stay away from GUIs but because it was not helpful for inspecting STL objects. It seems there is an extension for that. If you know about it please let me know.

Eclipse + C++, no thanks.

Almost every time I try a GUI to debug a program I end up using vim and GDB again. I guess I'll use a GUI when I need it, but today is not that day.

I wanted to know how to debug using GDB so I searched the WEB for tips and I found two of them to be interesting.

First, there is a nice collection of GDB scripts updated for GCC 3.3 and GCC 3.4. I couldn't get them to work and I would get this error:

me@host:~/gdb_stl_utils$ gdb
GNU gdb 6.8-debian
(cut...)
This GDB was configured as "i486-linux-gnu".
/home/me/.gdbinit:1: Error in sourced command file:
/home/me/.gdb/gdb_stl_utils:21: Error in sourced command file:
The address where /home/me/.gdb/StlStdContainers.o has been loaded is missing.

So, I didn't use them today. Anyway, I am starting to discover how powerful GDB is. I guess I will need to use the scripting facilities of GDB someday.

Fortunately, this message saved my day. It is nice to be able to call functions from GDB. The idea is to code a custom function that allows you to print what you want to inspect.

So, I just used the following functions.

void
dump (const vector <string> &v)
{
  int c = 0;
  for(vector<string>::const_iterator i(v.begin()); i != v.end(); ++i)
    cerr << '[' << (c++) << ']' << " => \"" << *i << "\"" << endl;
}

void
dump (const string &s)
{
  cerr << "\"" << s << "\"" << endl;
}

And this is a sample session:

   me@host:~work$ gdb ./a.out
   GNU gdb 6.8-debian
   Copyright (C) 2008 Free Software Foundation, Inc.
   License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
   This is free software: you are free to change and redistribute it.
   There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
   and "show warranty" for details.
   This GDB was configured as "i486-linux-gnu"...
   (gdb) list 118
   113       {
   114         cerr << "space:" << i << " ";
   115         loop(j,space[i].size())
   116           cerr << " " << space[i][j];
   117         cerr << endl;
   118       }
   119
   120       int m = 51;
   121
   122       loop(i, space[0].size())
   (gdb) break 120
   Breakpoint 1 at 0x80492ff: file MatchString.cpp, line 120.
   (gdb) run
   Starting program: ~/work/a.out
   0 => TIK
   1 => PPPO
   2 => OP
   space:0  0
   space:1  3
   space:2  1

Now comes the interesting part:

   Breakpoint 1, MatchString::placeWords (this=0xbfe49633, matchString=@0xbfe495f0,
       matchWords=@0xbfe495e4) at MatchString.cpp:120
   120       int m = 51;
   (gdb) call dump(MatchString)
   A syntax error in expression, near `)'.
   (gdb) call dump(matchString)
   "TOP"
   (gdb) call dump(matchWords)
   [0] => "TIK"
   [1] => "PPPO"
   [2] => "OP"
   (gdb)

I liked this simple method. I think I will use it for simple programs. It is nice to know that you can modify the dump function and have it print data structures using ranges. It also works with nested structures.

I'd like to ask the following question:

Discussion Loading... Vote up! Vote down!

knuth-interview

This is a nice interview with Don Knuth:

http://www.informit.com/articles/article.aspx?p=1193856

I know that important applications for parallelism exist–rendering graphics, breaking codes, scanning images, simulating physical and biological processes, etc. But all these applications require dedicated code and special-purpose techniques, which will need to be changed substantially every few years.

When reading it remember that he only cares about fundamental stuff, not about trends.

I currently use Ubuntu Linux, on a standalone laptop–it has no Internet connection. I occasionally carry flash memory drives between this machine and the Macs that I use for network surfing and graphics; but I trust my family jewels only to Linux.

No Internet in his computer. I really understand how this works. I really love how this guy does things in batch. Reading articles of the same subject in batch is a very good thing to do.

On the other hand, I willingly put myself in God's hands with respect to how much more I'll be able to do before cancer or heart disease or senility or whatever strikes.

He has accomplished a lot and he still wants to accomplish more. I've noticed that a lot of people I know start thinking they are too old for anything when they are 30!

Almost every biography of every person whom you would like to emulate will say that he or she did many things against the "conventional wisdom" of the day.

This interview is a very good thing to read.

Discussion (2) Loading... Vote up! Vote down!

compressed-swap

Today I noticed this project: compcache:Compressed Caching for Linux.

It allows you to specify an amount of RAM that will be used as a swap device, with compressed pages.

This is a trend that we will start seeing, at least while fast cheap persistent storage becomes common.

If I test this soon in a small device I'll post the results.

Discussion (1) Loading... Vote up! Vote down!

caffeine

I've been working a lot lately. I am quite happy because I managed to cut down caffeine intake (almost to zero). I sleep well most of the time (I need 8/9 hours to feel OK).

Now when I drink some coffee I feel it tastes very good but there is a downside: When I drink caffeine (even if it is just a little) I cannot fall asleep easily. when I was used to it I could even drink a Coke before going to sleep. Sometimes you read that a little caffeine is good for your health but I guess that now that I don't drink it I will not be able to drink any.

Discussion (2) Loading... Vote up! Vote down!

growing-a-language

This is a good thing to watch:

Video
http://video.google.com/videoplay?docid=-8860158196198824415
Talk
http://www.cs.virginia.edu/~evans/cs655/readings/steele.pdf

This guy is quite a geek. In his talk he speaks with short words. I wish I could do that here.


I tried to write very short words in this post but it is very hard. There are many English words that have just one syllable. In Spanish most simple words have more than one.

Discussion Loading... Vote up! Vote down!

gcc4.3

Estuve leyendo los cambios en GCC 4.3 y hay varias cosas interesantes.

macro __COUNTER__
para generar identificadores únicos.
Integración con la librería MPFR
Lo que hace innecesario definir constantes como COSENO_30 para evitar el llamado a la función cos.
-Warray-bounds
opción para chequear algunos desbordamientos de buffers (no es posible chequearlos todos).
Constantes binarias
Como 0b1100, las había querido usar antes. Creo hace muchos años las usaba en Borland C++.
Soporte experimental para el modo paralelo
Esto se ve interesante para probar.

Nota personal:

Discussion Loading... Vote up! Vote down!

No Country for Old Men

I think watching the movie No Country for Old Men was a good experience. Destiny, Luck, Free will, etc are always good topics for a movie.

Links:

Discussion Loading... Vote up! Vote down!

Sweeney Todd: The Demon Barber of Fleet Street

I really liked the movie Sweeney Todd: The Demon Barber of Fleet Street. I'll will never visit a barber! :-)

I'll give it 10/10.

Links:

Discussion (2) Loading... Vote up! Vote down!

verbose-diffs

I find this command useful:

 svn diff --diff-cmd=diff -x -U10 

Sometimes having more lines of unified context is very useful. For instance, when you're trying to merge some -and not all- the code by hand from a branch. I am somehow used to reading patches in diff format. Note that this is not subversion specific, the important command is diff.

This is an example of the results:

Using svn diff, you get:

Index: sendsend.c
===================================================================
--- sendsend.c	(revision 602)
+++ sendsend.c	(working copy)
@@ -8,6 +8,7 @@
 #include <netinet/in.h>
 #include <arpa/inet.h>
 #include <netdb.h>
+#include <sched.h>
 
 /* netcat -u is dying when the remote UDP port is not listening */
 
@@ -23,7 +24,14 @@
     struct timeval tv;
     int retval;
     char buf[LEN];
+    struct sched_param param;
 
+    param.sched_priority = 30;
+    if(sched_setscheduler(0, SCHED_FIFO, &param)==-1){
+      perror("sched_setscheduler failed");
+    }
+
+
     if (argc != 3) {
         fprintf(stderr,"options:  hostname port\n");
         exit(1);
@@ -50,7 +58,7 @@
       FD_SET(0, &rfds);
 
       tv.tv_sec = 0;
-      tv.tv_usec = 100000; /* 100 ms */
+      tv.tv_usec = 500000; /* 1/2 sec */
 
       retval = select(1, &rfds, NULL, NULL, &tv);

Using svn diff --diff-cmd=diff -x -U10, you get:

Index: sendsend.c
===================================================================
--- sendsend.c	(revision 602)
+++ sendsend.c	(working copy)
@@ -1,35 +1,43 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
 #include <errno.h>
 #include <string.h>
 #include <sys/types.h>
 #include <sys/socket.h>
 #include <netinet/in.h>
 #include <arpa/inet.h>
 #include <netdb.h>
+#include <sched.h>
 
 /* netcat -u is dying when the remote UDP port is not listening */
 
 #define LEN 512
 
 int main(int argc, char *argv[])
 {
     int sockfd;
     struct sockaddr_in their_addr;
     struct hostent *he;
     int numbytes;
     fd_set rfds;
     struct timeval tv;
     int retval;
     char buf[LEN];
+    struct sched_param param;
+
+    param.sched_priority = 30;
+    if(sched_setscheduler(0, SCHED_FIFO, &param)==-1){
+      perror("sched_setscheduler failed");
+    }
+
 
     if (argc != 3) {
         fprintf(stderr,"options:  hostname port\n");
         exit(1);
     }
 
     if ((he=gethostbyname(argv[1])) == NULL) {
         perror("gethostbyname");
         exit(1);
     }
@@ -43,21 +51,21 @@
     their_addr.sin_port = htons(atoi(argv[2]));
     their_addr.sin_addr = *((struct in_addr *)he->h_addr);
     memset(their_addr.sin_zero, '\0', sizeof their_addr.sin_zero);
 
     while (1)
     {
       FD_ZERO(&rfds);
       FD_SET(0, &rfds);
 
       tv.tv_sec = 0;
-      tv.tv_usec = 100000; /* 100 ms */
+      tv.tv_usec = 500000; /* 1/2 sec */
 
       retval = select(1, &rfds, NULL, NULL, &tv);
 
       if (retval == -1)
       {
         if (errno != EINTR)
         {
           perror("select");
           exit(1);
         }

You might find this a little exaggerated but I found this useful while integrating some changes by hand from a branched source.

Links:

Discussion Loading... Vote up! Vote down!

Observando Acontecimientos Politicos

Estos días he estado mirando páginas y escuchando diferentes fuentes que enlazo al final de esta entrada. Y no es para menos. Es el incidente internacional más importante y grave que he vivido últimamente en Colombia.

A manera de resumen, presento algunas conclusiones (opiniones) resumidas:

Políticas:

Conclusiones logísticas:

http://imgs.xkcd.com/comics/duty_calls.png

Los enlaces:

Discussion (4) Loading... Vote up! Vote down!

pelicula-soy-leyenda

La película me gustó. Nada del otro mundo, pero tiene unos momentos de suspenso y acción interesantes. No se puede contar casi nada sin adelantar situaciones de la película.

Calificación : 7/10.

Enlaces:

Discussion Loading... Vote up! Vote down!

reddit

I like http://programming.reddit.com. You find a lot of silly discussions there, but there are many good ones, too. I think I got the link from Juan Manuel.

Links:

Discussion Loading... Vote up! Vote down!

The Prestige

I saw the Prestige. I liked this movie.

I'll give it an 8/10.

Links:

Discussion Loading... Vote up! Vote down!

Diarios de Motocicleta

I saw Diarios de Motocicleta. I think it is a good movie.

I'll give it an 8/10.

Discussion Loading... Vote up! Vote down!

Up with strtol

I just read a post via reddit bashing atoi(3).

Some time ago I wrote some example code for strtol(3) and I think it is not hard to use. I'd better use a wrapper to strtol(3) than using C++ and templates where they are not needed.

#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <errno.h>

int
main(int argc, char *argv[])
{
    int base;
    char *endptr, *str;
    long val;
    if (argc < 2) {
        fprintf(stderr, "Usage: %s str [base]\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    /* the string that holds the number */
    str = argv[1];
    base = (argc > 2) ? atoi(argv[2]) : 10; /* ok, let's use atoi here :) */

    errno = 0;
    val = strtol(str, &endptr, base);

    /* check for errors */
    if ((errno == ERANGE && (val == LONG_MAX || val == LONG_MIN))
            || (errno != 0 && val == 0)) {
        perror("strtol");
        exit(EXIT_FAILURE);
    }
    if (endptr == str) {
        fprintf(stderr, "No digits were found\n");
        exit(EXIT_FAILURE);
    }

    /* if we got here we have a number! */
    printf("strtol() returned %ld\n", val);
    if (*endptr != '\0')        /* it doesn't have to be an error */
        printf("Further characters after number: %s\n", endptr);
    exit(EXIT_SUCCESS);
}

Note that I use atoi(3) in the example just to make it simpler. My point is that if you want to use strtol, you might want to write a wrapper. You'll lose some functionality but there is no free lunch.

#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <errno.h>

/* a simple wrapper */
int
strtol_wrapper(char *str, long *result, int base)
{
  char *endptr;
  long val;

  errno = 0;

  val = strtol(str, &endptr, base);

  if (errno || endptr == str || *endptr)
    return 1;

  *result = val;

  return 0;
}

/* this is a simpler example that only uses base 10 */
int
main(int argc, char *argv[])
{
  long val;

  if (argc < 2) {
    fprintf(stderr, "Usage: %s str\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  if (strtol_wrapper(argv[1], &val, 10))
  {
    fprintf(stderr, "sorry, not a valid number\n");
    /* perror("strtol"); */
    exit(EXIT_FAILURE);
  }

  printf("our number is %ld\n", val);
  exit(EXIT_SUCCESS);
}

You could also make a wrapper to provide something similar to OpenBSD's strtonum(3).

If you find a bug, please leave a comment and I'll fix it ASAP.

Discussion (4) Loading... Vote up! Vote down!

Overview of HPC computing / Top500

This is a very nice talk : http://www.youtube.com/watch?v=zTIKUxO9kf4.

A lot of software will be rewritten to take advantage of multi-core machines, and in this talk Jack Dongarra gives a nice example of how to keep more processors busy in a multi-core machine changing the algorithm. He also discusses the trends in the TOP500 benchmark, what it is, and its history. I didn't know that half of the entries get discarded every 6 months because new machines make it into the list!

He also talks about cell processors, the Blue Gene computer, self-tuning, fault tolerance, and many other interesting things.

A company from India made it in the top 10 of the TOP500 list. This is the same company that launched a U$2500 car recently.

Note for us eekfun users:

This link doesn't work yet, but it will soon : http://eekfun.com/youtube/zTIKUxO9kf4/#act-up. Once it works, we will be able to link to eekfun instead of youtube, the eekfun page will embed the video and allow us to check who else has written about the same video. Once it works, I'll update this post.

Discussion Loading... Vote up! Vote down!

Simple usleep test of the PREEMPT_RT Realtime Linux Patches

I am happy with the PREEMPT_RT patches (Real-time Linux). I need a timer to execute a task every 40 milliseconds. The base for this the timer is usleep(3) (let's not use nanosleep(3)).

Here is the source code of the test. The idea is to sample 10000 calls to usleep to check how long they take without the patches, with the patches, and with the patches and real-time priority. All the tests are run as root.

We care about the worst case and we want a good average.

System idle

$ ./test 
 max:13.684 min:2.02 avg:2.10364
$ ./test 
 max:13.993 min:2.016 avg:2.08508

Worst case: missed abut 12 milliseconds.

Heavy load.

Let's make the system busy with 10 instances of yes > /dev/null &. This will be our definition for heavy load.

$ ./test 
 max:24.141 min:2.016 avg:2.07188
$ ./test 
 max:12.711 min:2.017 avg:2.06129
$ ./test 
 max:12.665 min:2.016 avg:2.0828

Worst case: missed abut 22 milliseconds.

System idle (no real-time priority).

$ ./test 
 max:2.197 min:2.026 avg:2.0406
$ ./test 
 max:2.085 min:2.026 avg:2.04062
$ ./test 
 max:2.22 min:2.026 avg:2.04087

Just using the patches helps a lot. This systems is by far slower and in the worst case we missed the deadline for 0.197 milliseconds (197 microseconds) – compare 0.197 to 22 miliseconds!

System busy (no real-time priority).

$ ./test 
 max:2.998 min:2.027 avg:2.02964
$ ./test 
 max:2.129 min:2.027 avg:2.02938
$ ./test 
 max:2.101 min:2.027 avg:2.02945
$ ./test 
 max:2.116 min:2.027 avg:2.02944

In the worst case we lost one millisecond.

System busy (real-time priority 10).

$ ./test 10
 Using realtime priority: 10
 max:2.043 min:2.027 avg:2.02842
$ ./test 10
 Using realtime priority: 10
 max:2.092 min:2.027 avg:2.02842
$ ./test 10
 Using realtime priority: 10
 max:2.043 min:2.027 avg:2.02842

In the worst case we missed 92 microseconds (about 0.1 milliseconds). Not bad at all for this CPU.

You should not use a RT priority above 50 because signals don't get delivered and a program waiting for a signal can lock the machine.

In the worst (real) case we missed 92 microseconds (0.092 milliseconds).

As you can see the PREEMPT_RT patch helps a lot. I won't have issues with the timer I need.

Links:

Discussion Loading... Vote up! Vote down!

No Mas FARC / Que hablen los desmovilizados

No más FARC. Que hablen como desmovilizados, pero que no vuelvan a matar ni a secuestrar.

Me gustó ir ayer a la marcha. Estuve en la concentración de la 127, que aunque no tuvo mucho cubrimiento de los medios, también estuvo muy llena. Me sorprendió ver tantas personas en este punto de concentración.

Hace mucho tiempo no asistía a una marcha. Algo así como 10 años. Antes no se veían tantas cámaras como ahora. Se siente un poco incómodo, pero supongo que toca acostumbrarse.

Salvo una señora que tenía un escueto cartel a mano que decía "Adelante Presidente", el mensaje de la marcha, donde yo estuve, era claro: No más FARC. Algunos gritos contra Chávez, pero no tenían mucho eco. Me alegra haber asistido a la marcha.

Creo que muchas personas de diferentes creencias y opiniones se juntaron sin pelear, como pasó en la plaza de Bolívar. A pesar de lo que dicen las encuestas, con respecto al presidente actual, creo que muchos no deseamos una nueva re-elección.

Fue muy discutido el apoyo de Mancuso a la marcha en su sitio web. No me importa mucho lo que recomiende o no este personaje, pero creo que las críticas contra este apoyo tiene algo negativo.

La desmovilización de guerrilleros y paramilitares en Colombia (que desafortunadamente dista de ser perfecta) implica que estos sean recibidos por la sociedad y que puedan expresar sus opiniones abiertamente (como todos podemos). El que sean recibidos no implica que sean amados, pero se espera que vivan dentro de las normas de un estado de derecho.

Es mejor quejarnos porque Mancuso apoya la marcha en su sitio web, que enterarnos de que 20 manifestantes fueron cohibidos (o asesinados). Creo que acá hay un poco de progreso.

Creo que es mejor ver desmovilizados de las AUC marchando que matando gente. Creo que es mejor ver desmovilizados de las FARC marchando que secuestrando gente.

Creo que sería un gran avance leer, soportar, y criticar las ideas de las FARC en una página WEB que ver en televisión las pruebas de supervivencia (maltrato, tortura) que envían.

En Colombia hay fuentes (principales) fuentes de violencia:

Esperemos que las cosas mejoren.

Discussion (2) Loading... Vote up! Vote down!

Loading... Vote up! Vote down!

Last update: 2007-06-28 (Rev 11825)

svnwiki $Rev: 12966 $