Wednesday, April 5, 2006

Dalla documentazione di Doxygen....

/*! \class WindowsNT
* \brief Windows Nice Try.
* \author Bill Gates
* \author Several species of small furry animals gathered together
* in a cave and grooving with a pict.
* \version 4.0
* \date 1996-1998
* \bug It crashes a lot and requires huge amounts of memory.
* \bug The class introduces the more bugs, the longer it is used.
* \warning This class may explode in your face.
* \warning If you inherit anything from this class, you're doomed.
*/
class WindowsNT {};

Saturday, April 1, 2006

A volte gli umani ancora...

Ci sono alcuni tipi di ottimizzazione che per un umano sono "evidenti", per una macchina no. Trovo molto interessanti i problemi nel campo della correttezza (ovvero cercatr di insegnare ad un computer a dimostrare se un sorgente è o meno corretto, se presenta certi errori, in generale capire cosa fa). Il problema gemello è quello dell'ottimizzazione (si tratta per il computer di capire cosa fa il tuo codice e di modificarlo in uno equivalente più veloce)
Per esempio prendiamo questa funzione:
int func(){
    int i;
    int x =  2<<10;
    for ( i=0; i < MAX; ++i){
        if (i>= 0 &&  sqrt(i) >= 0)
            x/=i;
    }
}
Ad occhio si vede benissimo che il check dell'if è oltremodo pesante. *sai* che i è sempre maggiore o uguale di 0. Si può anche farne una dimostrazione formale abbastanza agevole.
In pratica la guardia dell'if è inutile. Il check sul >= 0 non serve e meno ancora sqrt. Nessuno dei due ha effetti collaterali (per il primo si vede, è facile, ma per il secondo bisogna sapere come è fatta sqrt, a sboccio non si modo di sapere che non setta un globale ad i, che stampa qualcosa o che ha un altro effetto collaterale, per cui effettivamente non si può semplicemente eliminarla senza cambiare la semantica del programma.
Dicevo. Senza ottimizzare, questo compila tenendo tutta la guardia dell'if:
L3:
cmpl    $0, -16(%ebp)
js      L4
cvtsi2sd        -16(%ebp), %xmm0
sqrtsd  %xmm0, %xmm0
movapd  %xmm0, %xmm1
leal    LC0-"L00000000001$pb"(%ebx), %eax
movsd   (%eax), %xmm0
ucomisd %xmm0, %xmm1
jae     L7
jmp     L4

C'è il primo confronto i>= 0
cmpl    $0, -16(%ebp)
js      L4


e c'è pure il confronto con la radice (sta usando dei registri mmx).
Bene... tutta la sezione L3 in effetti si può semplicemente togliere. Ora in questo caso è semplicemente banale fare l'ottimizzazione. E in effetti tutto il codice completo per la funzione di cui sopra ottimizzato è:
.text
.globl _func
_func:
pushl   %ebp
movl    %esp, %ebp
xorl    %eax, %eax
L2:
addl    $1, %eax
cmpl    $10, %eax
jne     L2
popl    %ebp
ret
.subsections_via_symbols
Lungo da solo quanto il controllo. E questo è quasi esattamente quello che avrebbe scritto un programmatore:
Piccolo preludio, azzera il primo registro. Poi nel loop, incrementa il primo registro (addl $1, %eax), confrontalo con il valore guardia (nel sorgente MAX era una define a 10 ; cmpl $10, %eax), se è minore o uguale torna a L2 (jne L2). Esci.
Ha ottimizzato perfino x/=i. Siccome vede che con x non ci faccio nulla, allora dice: che lo calcolo a fare? Fa solo il ciclo. Fosse stato più furbo non avrebbe fatto manco quello. Stupido io a prendere l'esempio fatto male.
Modifichiamo quindi la funzione in modo che ritorni x, e che quindi x vada calcolato.
Ecco... vediamo che a questo punto non è più tanto furbo:
.text
.globl _func
_func:
pushl   %ebp
movl    %esp, %ebp
pushl   %ebx
xorl    %ecx, %ecx
movl    $2048, %eax
pxor    %xmm1, %xmm1
jmp     L2
L3:
testl   %ecx, %ecx
js      L11
L2:
cvtsi2sd        %ecx, %xmm0
sqrtsd  %xmm0, %xmm0
ucomisd %xmm1, %xmm0
jb      L11
cltd
idivl   %ecx
L11:
addl    $1, %ecx
cmpl    $9, %ecx
jle     L3
popl    %ebx
popl    %ebp
ret
.subsections_via_symbols

Ricompare la radice quadrata ( sqrtsd %xmm0, %xmm0 ). Il programmatore che avesse scritto l'assembly a mano avrebbe scritto [ nel caso in cui questo loop sia molto ricorrente ] un codice significativamente più veloce.
Ammesso che questo mio esempio è del tutto cretino, è vero che il compilatore in genere sa su quale architettura certe istruzioni sono più sgamate, ma è vero ancora che le tecniche per le dimostrazioni formali sono ancora relativamente poco usate (anche perchè suddette dimostrazioni dilatano di moltissimo il tempo di compilazione, sono *molto* difficili da scrivere, e rischiano di portare bachi su bachi con errori minimi). Questo è parte di quasi tutti gli ambienti, non solo del gcc.
Come dire... l'umano sulle cose "furbe" resta più furbo, anche se sulla forza bruta non ha speranza.

Friday, March 31, 2006

Some good news too... (YASP)

Those who do not like seeing high their CPU usage stats when doing things like networking, should consider buying a Mac Intel. However I think this is due to the tremendous raw power of these machines than to changes in how MacOS X deals with networking.
I've always said that to me it is OK if CPU monitoring tools tell that the CPU is doing heavy work even if the system is only downloading something from the net. In fact although CPU values are high, the system is fast as ever, so I wasn't concerned.
Well, on MacIntel you don't even see high CPU usage stats.

Thursday, March 30, 2006

Killer: test 1 (passed)

This is the first test to understand what makes my MacIntel GUI terribly slow when some software run.

I wrote a small C++ program on that purpose. It makes some operations on matrices, but it does them in a quite inefficient way. When we multiply two matrices, it creates two vector objects, allocates memory for them, multiplies them, stores the result, and destroys them.

Of course this is not what you would be doing when implementing a matrix library, but we are trying to understand which software bugs are more problematic on the MacIntel and aren't on the PPC (in my previous post I told running some buggy sw on the Powerbook wasn't an issue, but made the MacIntel almost unusable).

This software does a lot of computations (it multiplies two quite large matrices of "points" -- structures of three doubles). Points use vectorial product. It does a lot of allocation and deallocation of small area of memory and I added I/O making it log the result each time it multiplies two points (that is a lot of I/O, since when we multiply two 500 element matrices it makes 500*500*500 point multiplications).

The verdict is positive. It is running right now (it hasn't yet finished) but the computer is perfectly usable.

Now I'm going to write a software that allocates and deallocates large areas of memory and then one that leaks a lot of memory. I do think, memory leaks are the cause of the "GUI slowness". However I still don't understand why the powerbook (that has 1/3 the RAM my iMac has) had no troubles.

Here I post the source of this simple software. Keep in mind that this was designed to be inefficient (don't use it, it sucks).

#include <cstdlib>
#include <iostream>
#include <ostream>
#include <fstream>

std::ofstream LOG;

struct Point{
        double x;
        double y;
        double z;
        Point() :
                x(0.0),
                y(0.0),
                z(0.0) {}
        Point(double l_x, double l_y, double l_z) :
                x(l_x),
                y(l_y),
                z(l_z) {}
        static Point random(){
                Point p(
                    rand()/(double)RAND_MAX,
                    rand()/(double)RAND_MAX,
                    rand()/(double)RAND_MAX
                );
                return p;
        }
};

std::ostream& operator<<(std::ostream& out, const Point& p){
    out << "(" << p.x << "," << p.y << "," << p.z << ")" ;
    return out;
}

Point operator*(const Point& op1, const Point& op2){
        Point res(
            op1.y * op2.z - op1.z * op2.y,
            op1.z * op2.x - op1.x * op2.z,
            op1.x * op2.y - op1.y * op2.x
        );
        LOG << res << std::endl;
        return res;
}

Point operator+(const Point& op1, const Point& op2){
        Point res(
            op1.x + op2.x,
            op1.y + op2.y,
            op1.z + op2.z
        );
        return res;
}

template<typename T, size_t size>
class Vector{
public:
        Vector(){
                mem_ = new T[size];
        }
        
        Vector(const Vector<T, size>& o){
            mem_ = new T[size];
            for(size_t i=0; i<size; ++i){
                mem_[i]=o.mem_[i];
            }
        }
        
        ~Vector(){
                delete [] mem_;
        }
        
        T& operator[](size_t i){
                return mem_[i];
        }
        
        const T& operator[](size_t i) const{
                return mem_[i];
        }
private:
        T* mem_;
    Vector<T, size>& operator=(const Vector<T, size>&);
};

template<typename T, size_t size>
T operator*(const Vector<T, size>& op1, const Vector<T, size> &op2){
        T acc;
        for(size_t i=0; i<size; ++i){
                acc = acc + op1[i]*op2[i];
        }
        return acc;
}

template<typename T, size_t size>
class Matrix{
public:
        Matrix(){
                mem_ = new T[size*size];
                for(size_t i=0; i<size; ++i){
                        for(size_t j=0; j<size; ++j){
                                get(i,j)=T::random();
                        }
                }
        }
        Matrix(const Matrix<T, size>& o){
                mem_ = new T[size*size];
                for(size_t i=0; i<size*size; ++i){
                    mem_[i] = o.mem_[i];
                }
        }
        ~Matrix(){
                delete [] mem_;
        }
Matrix<T, size>& operator=(const Matrix<T, size>& o){               
                for(size_t i=0; i<size*size; ++i){
mem_[i] = o.mem_[i];
                }
return (*this);
}
        T& get(size_t i, size_t j){
                return mem_[j*size + i];
        }
        
        const T& get(size_t i, size_t j) const{
                return mem_[j*size + i];
        }
        
        Vector<T, size> col(size_t j) const{
                Vector<T, size> v;
                for(size_t i=0; i<size; ++i){
                        v[i] = get(i,j);
                }
                return v;
        }
        
        Vector<T, size> row(size_t i) const{
                Vector<T, size> v;
                for(size_t j=0; j<size; ++j){
                        v[j] = get(i,j);
                }
                return v;
        }
private:
        T* mem_;
};

template<typename T, size_t size>
Matrix<T, size> operator*(Matrix<T, size>& op1, 
                                                  Matrix<T, size>& op2)
{
        Matrix<T, size> res;
        for(size_t i=0; i<size; ++i){
                for(size_t j=0; j<size; ++j){
                        res.get(i,j) = op1.row(i) * op2.col(j);
                }
        }
        return res;
}
int main(){
        const size_t SIZE = 500;
LOG.open("log.txt");
        Matrix<Point, SIZE> m1;
        Matrix<Point, SIZE> m2;
        Matrix<Point, SIZE> res;
res= m1*m2;
LOG.close();
}

Multitasking on MacIntel fails in presence of bugs

Right at the moment (as you may have learnt from some of my previous posts) I'm working on numerical libraries. I'm developing a (hopefully) efficient version of the aks algorithm to test primality.

I'm not here to describe AKS, nor to describe multitasking or any particular algorithm. It is sufficient to say that they are programs that make extensive use of the CPU.

On my old Powerbook G4 when I run a CPU expensive task the GUI keeps responding. Of course the task uses a lot of CPU: opening a new application takes more time, and so other tasks do. However applications respond as usual. The computer is noy "hung".

This is one of the things I love more of MacOS. The system remains usable even if under heavy stress. This is no longer true. My brand new iMac Core Duo simply becomes unusable. Applications do not respond (they reaction time can be counted in tens of seconds). This is plainly unacceptable. Of course this does not happen normally: it happens only with some software (and buggy software). However the very same program does not create problems on my Powerbook (the machine slows but remains usable).

This makes me think there is something in the scheduler that just does not work as expected and is fooled by some bugs in the software.

I want to make clear that well written software has't this problem. I can run heavy compilations and have the CPU (both cores) 100% and the system is responsive as usual. It gets stuck when something goes wrong.

The software that hung the mac had bugs (it's iper-alpha and I'm still working on it). But while the old MacOS X PPC responded to me relatively quickly (allowing me for example to kill the bugged software), the new MacOS X Intel seems to prefer letting the bugged software finish. The point is that those bug should not slow the system to that point (and in fact the PowerBook wasn't slowed): they were just a couple of memory leaks.

Now I'm trying to develop a software that has the similar behaviour to the one I'm writing (that is to say uses lots of memory, lots of computation and lots of logging -> I/O), to see what of the three things that stresses more the system. Appearently it is memory.

edit: I just wrote a heavy computation/loging software. This has no troubles at all. You can read what does it do here
Anyway sorry for being allarmistic. I'm trying to figure out what the problem is.

Tuesday, March 28, 2006

Look, I'm Universal!

A PPC Application

ppc-app-2006-03-28-05-02.png

A Universal App

universal-app-2006-03-28-05-02.png

I have not yet found an Intel only Mac application.

Now we show some unix executables. The first one is a script.

s-unix-2006-03-28-05-02.png

This one is universal

universal-unix-2006-03-28-05-02.png

and this is Intel Only

intel-unix-2006-03-28-05-02.png

Of course you can build universal unix executables, as you've seen.

Sunday, March 26, 2006

gmp 4.2 on MacIntel

Good news. With gmp 4.2 assembly optimization works. That means that you can get decent performances. For values of decent that are *below* those of an old Prescott and just a bit better than those of a plain Pentium M with the same clock.

The problem is that (for example) you can't run make check. This makes me thing something is broken. However, I can't understand what. However I've been told that "MacIntels" are not supported by gmp-4.2 . So consider twice before buying a MacIntel if you need to work with gmp.

And you can't use c++ too. For some reason there is an error with the generation of an assembly optimization. The answer from the developers has been "gmp-4.2 is not supported on MacIntels" (however I am not really able to consider this a solution to the problem, but unfortunately I'm not skilled enought to fix things by myself).

In fact the second core is not used at all, so this result is quite predictable. Moreover I used shared libraries instead of static ones (for the very good reasons that the guys at apple don't ship the gcc with the static version of libgcc and of crt0.o, so there is no easy way to do it).

In the end I assume MacOS X on Intel is young and probably not as optimized as a FreeBSD (just to name one). These are the results:

iMac 2 GHz 2 GB

***** GMPbench version 0.1 ***** 
Using default CFLAGS = "-O3 -fomit-frame-pointer -I../gmp-4.2" 
Using default CC = "gcc" 
Using default LIBS = "-lgmp -L../gmp-4.2/.libs" 
Using compilation command: gcc -O3 -fomit-frame-pointer -I../gmp-4.2 foo.c -o foo -lgmp -L../gmp-4.2/.libs 
You may want to override CC, CFLAGS, and LIBS 
Using gmp version: 4.2 
Compiling benchmarks 
Running benchmarks 
Category base 
Program multiply 
multiply 128 128 
GMPbench.base.multiply.128,128 result: 9530908 
multiply 512 512 
GMPbench.base.multiply.512,512 result: 1150785 
multiply 8192 8192 
GMPbench.base.multiply.8192,8192 result: 12500 
multiply 131072 131072 
GMPbench.base.multiply.131072,131072 result: 228 
multiply 2097152 2097152 
GMPbench.base.multiply.2097152,2097152 result: 9.62 
GMPbench.base.multiply result: 12463 
Program divide 
divide 8192 32 
GMPbench.base.divide.8192,32 result: 306090 
divide 8192 64 
GMPbench.base.divide.8192,64 result: 104119 
divide 8192 128 
GMPbench.base.divide.8192,128 result: 66800 
divide 8192 4096 
GMPbench.base.divide.8192,4096 result: 20668 
divide 8192 8064 
GMPbench.base.divide.8192,8064 result: 268859 
divide 131072 8192 
GMPbench.base.divide.131072,8192 result: 435 
divide 131072 65536 
GMPbench.base.divide.131072,65536 result: 242 
divide 8388608 4194304 
GMPbench.base.divide.8388608,4194304 result: 0.796 
GMPbench.base.divide result: 5617.3 
GMPbench.base result: 8367.1 
Category app 
Program rsa 
rsa 512 
GMPbench.app.rsa.512 result: 2755 
rsa 1024 
GMPbench.app.rsa.1024 result: 478 
rsa 2048 
GMPbench.app.rsa.2048 result: 72.6 
GMPbench.app.rsa result: 457.26 
GMPbench.app result: 457.26 
GMPbench result: 1956 

gmp on MacIntel and on G4

My iMac should be "twice as fast" as the iMac G5. Ok, that good.
This is true if you use apple software (i suppose they did the test correctly) and if you benchmark with SPEC suites. That's good.And the iMac is fast. I have never used a faster mac (however, I never used a G5 too). Applications open with no need to wait and so on. I can even play 3d games with rosetta.

However right at the moment I have to use gmp. And gmp says that my brand new iMac is not even twice as fast as my "old" PB G4 1.5 GHz. That is a desktop. I know, gmp on Mac Intel uses no assembly code. And the iMac is 1.5 x slower.

But I don't care how much my CPU is fast if the software I have to run is not optimized for it. Today they released gmp 4.2. I'm gonna try it and see if now the assembly issue is fixed.

iMac 2 GHz 2 GB
***** GMPbench version 0.1 ***** 
Using default CFLAGS = "-O3 -fomit-frame-pointer -I/opt/local/include" 
Using default CC = "gcc" 
Using default LIBS = "-lgmp -L/opt/local/lib" 
Using compilation command: gcc -O3 -fomit-frame-pointer -I/opt/local/include foo.c -o foo -lgmp -L/opt/local/lib 
You may want to override CC, CFLAGS, and LIBS 
Using gmp version: 4.1.4 
Compiling benchmarks 
Running benchmarks 
Category base 
Program multiply 
multiply 128 128 
GMPbench.base.multiply.128,128 result: 3388942 
multiply 512 512 
GMPbench.base.multiply.512,512 result: 283065 
multiply 8192 8192 
GMPbench.base.multiply.8192,8192 result: 2753 
multiply 131072 131072 
GMPbench.base.multiply.131072,131072 result: 43.6 
multiply 2097152 2097152 
GMPbench.base.multiply.2097152,2097152 result: 1.73 
GMPbench.base.multiply result: 2883.1 
Program divide 
divide 8192 32 
GMPbench.base.divide.8192,32 result: 116928 
divide 8192 64 
GMPbench.base.divide.8192,64 result: 72789 
divide 8192 128 
GMPbench.base.divide.8192,128 result: 36886 
divide 8192 4096 
GMPbench.base.divide.8192,4096 result: 5076 
divide 8192 8064 
GMPbench.base.divide.8192,8064 result: 66084 
divide 131072 8192 
GMPbench.base.divide.131072,8192 result: 107 
divide 131072 65536 
GMPbench.base.divide.131072,65536 result: 54.0 
divide 8388608 4194304 
GMPbench.base.divide.8388608,4194304 result: 0.159 
GMPbench.base.divide result: 1770.9 
GMPbench.base result: 2259.6 
Category app 
Program rsa 
rsa 512 
GMPbench.app.rsa.512 result: 870 
rsa 1024 
GMPbench.app.rsa.1024 result: 129 
rsa 2048 
GMPbench.app.rsa.2048 result: 18.0 
GMPbench.app.rsa result: 126.41 
GMPbench.app result: 126.41 
GMPbench result: 534.46 

PowerBook G4 1.5 GHz 512 MB
... broken post ...

MacIntel not advised for scientific researchers.

I had problems with almost all scientific libraries I tried.
gmp builds only if you use --host=none-apple-darwin. That means you are disabling assembly optimizations (and you probably wouldn't want to . And that option was correctly set for plain gmp, but not for gmp-cxx-wrappers (Gregory Wrigh has no access to a Mac intel, now he should have fixed it).

cln is plainly broken. That means you can't use GiNaC too. I think someone should buy cln's developers a MacMini Intel.

If you want to use OCaml, you have to use a cvs special version, since the stable does not yet compile. The solution is here.

In fact I had lots of problems. The guys at darwin ports have been really nice (using dp is just the quickest way to install this kind of software), but there are *lots* of troubles. The same installation on my powerbook G4 went just fine (of course the took a lot to finish, but they did finish).

Portfile for ntl on MacIntel was broken too (now it's fixed).

YASP (Yea Another Stupid Post)

I have to admit that this
double-core-2006-03-26-10-21.png
makes me quite proud... I've never had a biproc machine (and this is dual core, but that does not change the point).
I'm looking forward to have some time to install Linux. Non because of Linux itself but because of the twin penguins that should appear when booting. Well.. they should have appeared once. Now distros tend to favour another boot style...