Performance em Java

Aqui eu acho o primeiro milhão de números primos.

import java.util.*;
class Sieve2 {
    private BitSet bs;
    public void findPrimes (int n) {
        bs = new BitSet (n+1);
        int sq = (int) Math.sqrt (n);
        // Ao final desta rotina, todos os bits marcados serão primos, e os
        // bits desmarcados serão números compostos.
        bs.set (0, n - 1, true); // marcando todos os bits como primos...
        // Agora vamos achar o primeiro bit primo, e desmarcar todos os bits 
        // que são múltiplos dele. Vamos começar por 3
        int x = 2;
        while (x <= sq) {
            for (int i = x + x; i <= n; i += x) { 
                bs.clear (i);
            }
            // Devemos achar o próximo bit setado que seja maior que x
            x = bs.nextSetBit (x + 1);
        }
    }
    public boolean isPrime (int n) {
        return bs.get (n);
    }
    public int nextPrime (int n) {
        return bs.nextSetBit (n + 1); // -1 se não houver um próximo
    }
    public int countPrimes() {
        return bs.cardinality();
    }
    public static void main(String[] args) {
        Sieve2 s = new Sieve2();
        // Isto aqui força a máquina virtual a compilar o algoritmo
        for (int i = 0; i < 100; ++i) {
            s.findPrimes (1000); 
        }
        // Agora sim, vamos calcular os primos que vão de 2 a 15485851. 
        long t = System.currentTimeMillis();
        s.findPrimes (15485851);
        System.out.println ("Achar os primos levou " + (System.currentTimeMillis() - t) + " milissegundos.");
        // Vamos contar os primos encontrados.
        System.out.println ("Ha " + s.countPrimes() + " primos neste intervalo." );
    }
}

Rodando o programa acima em um Intel Core2Duo 1.86MHz levou 1125 ms com as opções default do java, e 469 ms com a opção “-server”.

OK?

1. Dispare a escrita no System.out em outra thread;
2. Faça um cache dos primos já encontrados. Aí vc só precisa dividir o número por eles.

entanglement:

Aqui eu acho o primeiro milhão de números primos.

import java.util.*;
class Sieve2 {
    private BitSet bs;
    public void findPrimes (int n) {
        bs = new BitSet (n+1);
        int sq = (int) Math.sqrt (n);
        // Ao final desta rotina, todos os bits marcados serão primos, e os
        // bits desmarcados serão números compostos.
        bs.set (0, n - 1, true); // marcando todos os bits como primos...
        // Agora vamos achar o primeiro bit primo, e desmarcar todos os bits 
        // que são múltiplos dele. Vamos começar por 3
        int x = 2;
        while (x <= sq) {
            for (int i = x + x; i <= n; i += x) { 
                bs.clear (i);
            }
            // Devemos achar o próximo bit setado que seja maior que x
            x = bs.nextSetBit (x + 1);
        }
    }
    public boolean isPrime (int n) {
        return bs.get (n);
    }
    public int nextPrime (int n) {
        return bs.nextSetBit (n + 1); // -1 se não houver um próximo
    }
    public int countPrimes() {
        return bs.cardinality();
    }
    public static void main(String[] args) {
        Sieve2 s = new Sieve2();
        // Isto aqui força a máquina virtual a compilar o algoritmo
        for (int i = 0; i < 100; ++i) {
            s.findPrimes (1000); 
        }
        // Agora sim, vamos calcular os primos que vão de 2 a 15485851. 
        long t = System.currentTimeMillis();
        s.findPrimes (15485851);
        System.out.println ("Achar os primos levou " + (System.currentTimeMillis() - t) + " milissegundos.");
        // Vamos contar os primos encontrados.
        System.out.println ("Ha " + s.countPrimes() + " primos neste intervalo." );
    }
}

Rodando o programa acima em um Intel Core2Duo 1.86MHz levou 1125 ms com as opções default do java, e 469 ms com a opção “-server”.

OK?

Bah brigado!!!

bem que a gurisada na PUCRS tinha comentado sobre um algoritimo que mantem uma lista de todos os primos, e depois apenas checa contra eles!

Obrigado!

Bom, pensei que você tinha que manter a funcionalidade da função isPrime(), e por isso tinha descartado o crivo.

Depois acho que vou converter esse algoritmo do Entaglement para C++ e comparar as performances. Acho muito provável que o C++ ganhe, mas não é bom afirmar nada antes de testar.

#include <windows.h>

#include <bitset>
#include <iostream>
#include <cmath>


using namespace std;

template <int N> 
class Sieve2 {
private:
    bitset<N+1> bs;
public:
    Sieve2 () { }
    void findPrimes() {
        int sq = (int) sqrt ((double) N);
        bs.set(); // seta todos os bits para 1

        int x = 2;
        while (x <= sq) {
            for (int i = x + x; i <= N; i += x) { 
                bs [i] = false;
            }
            // Devemos achar o próximo bit setado que seja maior que x
            x = nextSetBit (x + 1);
        }
    }
    bool isPrime (int i) { return bs[i]; }
    int countPrimes() { return bs.count(); }
private:
    int nextSetBit (int n) {
        while (n <= N && !bs[n]) {
            n++;
        }
        return n;
    }
};

int main (int argc, char *argv[]) {
    DWORD dw = GetTickCount();
    static Sieve2<15485851> sieve2;
    sieve2.findPrimes();
    cout << "Achar os primos levou " << GetTickCount() - dw << " ms" << endl;
    cout << sieve2.countPrimes() << endl;
}

De fato, levou 1609 ms com as opções padrões do compilador C++ (Microsoft Visual Studio 2008 ),
e 109 ms com a opção -O2 (otimização ligada), usando a mesma máquina supracitada. (O programa foi rodado e compilado sob Windows).

O curioso é que, com as opções padrão, o Java ganha do C++ (incrível mas é verdade).
Usando as opções de otimização (-server para o Java e -O2 para o C++) então o C++ ganha do Java.

Alguém consegue pegar meu programa e adaptá-lo de modo que o crivo de Eratóstenes tenha apenas números ímpares? Se conseguir fazer isso, já que o programa começa a exibir sintomas de que é dependente da velocidade de acesso à memória, talvez ele fique ainda mais rápido, já que seria gasta apenas metade da memória para o BitSet (que gasta 1 bit por número).

Acho que rodar um programa C++, ou mesmo um programa C, sem ligar otimizações do compilador hoje em dia é bobagem. Geralmente as opções padrão não otimizam absolutamente nada, e procuram priorizar instruções portáveis para qualquer processador lá da década do 286.

Se alguém for ler o assembly gerado pelo Microsoft Visual C++ sem otimização, ele se parece com um programa que um aprendiz de linguagem Assembly faria - bem simples, bobo e sem grandes coisas estranhas.

Se a otimização for ligada, o código é bem mais difícil de compreender. Ele começa a ter uns “achados” que você tem alguma dificuldade de entender.

Agora, se for usar o Intel C++ Compiler (icc), você simplesmente não consegue entender o código gerado. Os algoritmos de “register scheduling” são bem complexos e garantem que o código gerado seja quase incompreensível, mesmo para olhos treinados.

Fiz o algoritimo em C puro, e eis os resultados:

(Nota to jogando os resultados fora em /dev/null para o I/O de disco não atrapalhar os resultados…)

/*
 *  Primes.bitmaped.c
 *  
 *
 *  Created by Marcos Sartori on 30/10/2009.
 *  Copyright 2009 Marcos Sartori Computer Systems. All rights reserved.
 *
 */

#define TRUE -1
#define FALSE 0

#define MAX 15485863
#define MIN 0

#include <stdio.h>
#include <math.h>

typedef unsigned char bitmap_t; 

bitmap_t primes[((MAX+1)>>3)+1];


static inline bitmap_t bitAt(bitmap_t* aBitmap, unsigned int index)
{
	return aBitmap[index>>3]&(1<<(index&7));
}

static inline void setBitAt(bitmap_t* aBitmap, unsigned int index, int value)
{
	if (value) aBitmap[index>>3]=aBitmap[index>>3]|(1<<(index&7));
	else aBitmap[index>>3]=aBitmap[index>>3]&(~(1<<(index&7)));
}

int nextSetBitAt(bitmap_t* aBitmap, unsigned int begIndex, unsigned int size)
{
	unsigned register int i;
	
	for ( i = begIndex ; i<size ; i++)
		if(bitAt(aBitmap, i)) return i;
	return -1;
}

void setPrimes(bitmap_t* aBitmap, unsigned int max)
{
	unsigned register int i, z, j;
	
	for (i = 2 ; i<max ; i++) setBitAt(aBitmap, i, TRUE);
	
	j = sqrt(max);
	z=2;
	while (z <= j){
		for (i=z+z ; i<max ; i+=z)
			setBitAt(aBitmap, i, FALSE);
		z=nextSetBitAt(aBitmap, z+1, max);
	}
}

int isPrime(unsigned int aNumber)
{
	if((!aNumber&1)&&(aNumber!=2)) return FALSE;
	
	return bitAt(primes, aNumber);
}

int main(int argc, char** argv)
{
	unsigned register int i;
	setPrimes(primes, MAX+1);
	
	for (i=MIN; i<=MAX; i++)
		if(isPrime(i)) printf("%d\n", i);
	
	return 0;
}

Macbook-de-Marcos-Sartori:Developer marcos$ time gcc -O2 Primes.bitmaped.c -o Primes.bitmaped.opt

real	0m0.403s
user	0m0.058s
sys	0m0.026s
Macbook-de-Marcos-Sartori:Developer marcos$ time gcc Primes.bitmaped.c -o Primes.bitmaped

real	0m0.072s
user	0m0.035s
sys	0m0.024s
Macbook-de-Marcos-Sartori:Developer marcos$ time ./Primes.bitmaped > /dev/null
real	0m0.969s
user	0m0.949s
sys	0m0.006s
Macbook-de-Marcos-Sartori:Developer marcos$ time ./Primes.bitmaped.opt > /dev/null

real	0m0.477s
user	0m0.469s
sys	0m0.006s
Macbook-de-Marcos-Sartori:Developer marcos$

E jah vou adaptar ele para fazer apenas os impares tambem!

Antes que eu me esqueça, usando o anterior isPrime(), eu tinha feito uma versão com threads, que de 5 segundos o tempo de execução caia para 2.

/*
 *  Prime.threaded.c
 *  
 *  Parallelized version scaning from MIN to MAX using NUM_THREADS threads.
 *
 *  Created by Marcos Sartori on 28/10/2009.
 *  Copyright 2009 Marcos Sartori Computer Systems. All rights reserved.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <math.h>

#define TRUE -1
#define FALSE 0

#define NUM_OF_THREADS 4
#define MIN 0
#define MAX 15485863
#define RESULTS_BUFFER_SIZE (MAX/2)

typedef struct{
	unsigned int first;
	unsigned int last;
	unsigned int threadNumber;
} kernelArgs;

unsigned int results[RESULTS_BUFFER_SIZE];

void* kernel1(kernelArgs *params);
int isPrime(unsigned int aNumber);
int unsignedIntCompare(const void* a, const void* b);
static void printResults();
static int sizeOfResults();

int main (int argc, char* argv)
{
	pthread_t threads[NUM_OF_THREADS-1];
	kernelArgs args[NUM_OF_THREADS];
	
	unsigned register int i;
	
	for (i=0; i<(NUM_OF_THREADS-1) ; i++){
		args[i].first=(i*(MAX/NUM_OF_THREADS))+MIN; args[i].last=((i+1)*(MAX/NUM_OF_THREADS))+MIN-1; args[i].threadNumber=i;
		pthread_create(&threads[i], NULL, kernel1, &args[i]);
	}
	
	args[NUM_OF_THREADS-1].first=((NUM_OF_THREADS-1)*(MAX/NUM_OF_THREADS))+MIN;
	args[NUM_OF_THREADS-1].last=MAX;
	args[NUM_OF_THREADS-1].threadNumber=NUM_OF_THREADS-1;
	kernel1(&args[NUM_OF_THREADS-1]);
	
	for (i=0 ; i<NUM_OF_THREADS-1 ; i++)
		pthread_join(threads[i], NULL);
	
	printResults();
	
	return 0;
}

void* kernel1(kernelArgs* params)
{
	unsigned register int i, z, x;
	z=params->last;
	x=0;
	
	for (i=params->first; i<=z; i++)
		if(isPrime(i)){
			results[x*NUM_OF_THREADS+params->threadNumber]=i;
			x++;
		}
	
	return NULL;
}

static int sizeOfResults()
{
	unsigned register int y, x;
	int ret = 0;
	
	for (y = 0 ; y < RESULTS_BUFFER_SIZE; y+=NUM_OF_THREADS)
		for (x = 0 ; x < NUM_OF_THREADS ; x++)
			if (results[y+x]){
				ret+=NUM_OF_THREADS;
				break;
			}
	return ret;
	
}

int unsignedIntCompare(const void* a, const void* b)
{
	return ( *(unsigned int*)a - *(unsigned int*)b );
}

static void printResults()
{
	unsigned register int z, i;
	
	z = sizeOfResults();
	qsort(results, z, sizeof(results[0]), &unsignedIntCompare);
	for (i = 0 ; i < z ; i++)
		if(results[i]) printf("%d\n", results[i]);
}

int isPrime(unsigned int aNumber)
{
	unsigned register int i, z, j;
	
	if (aNumber<=1) return FALSE;
	if ((!(aNumber&1))&&(aNumber!=2)) return FALSE;
	
	z=aNumber>11?11:aNumber-1; goto loop;
	
sqrt:
	z=sqrt(aNumber); j = TRUE;
loop:
	for (i=3; i<=z; i+=2)
		if (!(aNumber%i)) return FALSE;
	if(!j) goto sqrt;
	
	return TRUE;
}

Macbook-de-Marcos-Sartori:Developer marcos$ time ./Prime > /dev/null

real	0m4.863s
user	0m4.844s
sys	0m0.010s
Macbook-de-Marcos-Sartori:Developer marcos$ time ./Prime.threaded > /dev/null

real	0m2.404s
user	0m2.670s
sys	0m0.042s
Macbook-de-Marcos-Sartori:Developer marcos$

Amigo, você percebeu que “printf (”%d")" não executa em tempo desprezível, mesmo que o printf seja redirecionado para /dev/null? Executar 100000 printfs vai levar vários segundos. Para provar isso, experimente criar um loop de 1000000 printfs, e ver quanto tempo isso leva. Depois, desconte do tempo usado.

entanglement:

Aqui eu acho o primeiro milhão de números primos.

import java.util.*;
class Sieve2 {
    private BitSet bs;
    public void findPrimes (int n) {
        bs = new BitSet (n+1);
        int sq = (int) Math.sqrt (n);
        // Ao final desta rotina, todos os bits marcados serão primos, e os
        // bits desmarcados serão números compostos.
        bs.set (0, n - 1, true); // marcando todos os bits como primos...
        // Agora vamos achar o primeiro bit primo, e desmarcar todos os bits 
        // que são múltiplos dele. Vamos começar por 3
        int x = 2;
        while (x <= sq) {
            for (int i = x + x; i <= n; i += x) { 
                bs.clear (i);
            }
            // Devemos achar o próximo bit setado que seja maior que x
            x = bs.nextSetBit (x + 1);
        }
    }
    public boolean isPrime (int n) {
        return bs.get (n);
    }
    public int nextPrime (int n) {
        return bs.nextSetBit (n + 1); // -1 se não houver um próximo
    }
    public int countPrimes() {
        return bs.cardinality();
    }
    public static void main(String[] args) {
        Sieve2 s = new Sieve2();
        // Isto aqui força a máquina virtual a compilar o algoritmo
        for (int i = 0; i < 100; ++i) {
            s.findPrimes (1000); 
        }
        // Agora sim, vamos calcular os primos que vão de 2 a 15485851. 
        long t = System.currentTimeMillis();
        s.findPrimes (15485851);
        System.out.println ("Achar os primos levou " + (System.currentTimeMillis() - t) + " milissegundos.");
        // Vamos contar os primos encontrados.
        System.out.println ("Ha " + s.countPrimes() + " primos neste intervalo." );
    }
}

Rodando o programa acima em um Intel Core2Duo 1.86MHz levou 1125 ms com as opções default do java, e 469 ms com a opção “-server”.

OK?

bah, mas me diz uma coisa, por que tu teve que desperdiçar aqueles primeiros ciclos para forçar a compilação, e como isso funciona?

pensei que JVM iria compilar o segmento antes de entrar em sua execução…

tipo, um thread vai na frente prevendo posiveis caminhos de execução, e compilando as rotinas e as pondo em cache, e a outra, iri apenas chamar essas rotinas pre compiladas…

A VM não compila todo o código.

Ela usa uma técnica chamada hotspot compilation. Ela procura por pontos “quentes” em seu programa, e só compila esses pontos. Isso torna a compilação mais rápida e mais significativa. Ela também é capaz de fazer otimizações de runtime, nesse momento.

O que o entaglement fez foi forçar diversas chamadas dessa função para que a VM encare aquela função como uma função “quente”, que merece ser compilada. Ele não pode garantir com isso que a compilação ocorrerá, mas há grandes chances de isso acontecer.

Para mais informações: