Ottimizzare il codice C - strlen

no, non è gesù bambino

Prima di cominciare volevo ringraziare ancora una volta tutti i presenti alla cena pidduista di ieri sera e facebook che ci ha permesso di organizzarla.
Spero vi siate divertiti e comunque ricordo che non siamo riusciti a fare un minimo di cresta e quindi questo natale sarà ancora più povero.

Molti si chiedevano che fine ha fatto jiimbo, perchè non scrive più etc…beh jiimbo dopo aver dato 100 euro ad un avvocato per scrivere una lettera di 10 righe, battuta tralaltro in malomodo e con l’ausilio di sole due dita, aveva ben pensato di non scrivere nulla se non dietro pagamento (sennò qui tutti ce guadagnano meno che io).

Dopo l’altra sera però, dopo il calore dimostrato dai nostri fan, non posso non adempiere ai miei doveri ed ho deciso quindi di tornare a scrivere (si ma niente di serio, la solita sbroda tecnica).

In questo periodo chi mi conosce sa che sto tribbolando con la tesi così tanto che se me lo avessero detto prima sarei andato a parare le pecore a sei anni, ma si sa…a noi pidduisti piace tribbolare. Argomento? Stringhe e codifiche, più o meno quelle cose che dopo un po’ ti rendono pazzo furioso e ti fanno perdere contatto con la realtà.

Ho sperimentato personalmente l’halting problem e mi sono imbattuto in così tante bizzarie del C che oramai sono portato a pensare che se dio esiste veramente abbia scritto tutto in C (il C è potere, il java è costipazione). Da questa riflessione su la vita l’universo e tutto quanto ho deciso di scrivere qualcosa che possa far capire quanto ottimizzare il codice significhi in termini di tempo.

Tutti sanno che quando si deve scrivere codice performante in genere si scrive in C perchè è il linguaggio che ti permette di controllare ogni aspetto della programmazione e si sa che “un grande potere portà con se una grande responsabilità”. Spetta a noi quindi ottimizzare il più possibile il codice e spesso si fanno errori grossolani che rendono le nostre procedure inutilizzabili.

Tra i vari aspetti quello che forse in genere viene tralasciato è quello dell’utilizzo improprio di strlen (la funzione che ritorna la lunghezza della stringa (sempre che questa sia terminata da (altrimenti solo cristo lo sa))). Come sempre un bell’esempio è meglio di tante chiacchiere. Il programma che trovate esegue le seguenti procedure:

• Esempio di vita reale: legge un file e, scorrendolo carattere per carattere, ne genera tutte le sottostringhe che partono dal carattere corrente fino alla fine della stringa.
• Esempio banale: scorre il file carattere per carattere e conta i caratteri rimanenti da leggere.

/*
 * Casapiddu's code production
 * strlen_optimize.c
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>

int read_file(char *filename, char **textt, long *length)
{
  	char *text;
  	long t;
  	FILE *infile;

  	infile = fopen(filename, "rb");

	if (infile == NULL) {
		return 1;
	}

  	// store input file length
  	if (fseek(infile, 0, SEEK_END) !=0) {
		return 1;
	}
  	*length = ftell(infile);

  	// alloc memory for text
  	text = (char *) malloc ((*length) * sizeof(char) + 1);
	if (text == NULL) {
		return 1;
	}

  	//read text in one sweep
  	rewind(infile);
  	t = fread(text, sizeof(char), (size_t) *length, infile);
  	if (t != *length) {
	 	return 1;
	}
	text[*length] = '';
  	*textt = text;
  	fclose(infile);

  	return 0;
}

int substring_naive (char *str, long start, long offset, char **ret_substring) 
{
	char *ret;
	long end_pos = (start + offset < strlen(str)) ? start + offset : strlen(str) - 1;
	long i;
	ret = (char *) malloc ((end_pos - start + 2) * sizeof(char));
	
	i = start;
	for (i; i <= end_pos; i++) {
 		ret[i - start] = str[i];
	}
	ret[end_pos - start + 1] = '';
	*ret_substring = ret;
	
	return 0;
}

int substring (char *str, long start, long offset, long length, char **ret_substring) 
{
	char *ret;
	long end_pos = (start + offset < length) ? start + offset : length - 1;
	long i;
	ret = (char *) malloc ((end_pos - start + 2) * sizeof(char));
	
	i = start;
	for (i; i <= end_pos; i++) {
 		ret[i - start] = str[i];
	}
	ret[end_pos - start + 1] = '';
	*ret_substring = ret;
	
	return 0;
}

int main (int argc, char **argv)
{
	char *buffer;
	char *tmp_buffer;
	long length;
	long i;
	long j;
	time_t startTime, endTime;
	
	if (read_file(argv[1], &buffer, &length)) {
		printf("Error reading file.\n");
		exit(1);
	}

	time(&startTime);
	i = 0;	
	for (i; i < strlen(buffer); i++) {		
		substring_naive (buffer, i, strlen(buffer) - i - 1, &tmp_buffer);
		free(tmp_buffer);
	}
	time(&endTime);
	printf("Naive elapsed time: %f\n", difftime(endTime, startTime));
	
	time(&startTime);
	i = 0;	
	for (i; i < length; i++) {
		substring (buffer, i, length - i - 1, length, &tmp_buffer);
		free(tmp_buffer);
	}
	time(&endTime);
	printf("Smart elapsed time: %f\n", difftime(endTime, startTime));
	
	time(&startTime);
	i = 0;
	for (i; i < strlen(buffer); i++) {
		j = strlen(buffer) - i;
	}
	time(&endTime);
	printf("Naive monkey elapsed time: %f\n", difftime(endTime, startTime));
	
	time(&startTime);
	i = 0;
	for (i; i < length; i++) {
		j = length - i;
	}
	time(&endTime);
	printf("Smart monkey elapsed time: %f\n", difftime(endTime, startTime));
}

Di entrambe le procedure viene eseguita prima la versione con chiamate a strlen inutili e poi la versione ottimizzata. Il primo esempio ovviamente è quello da prendere più in considerazione visto che il secondo a meno di qualche problema cerebrale nessuno lo scriverebbe in quel modo (però fa scena vedere il gap ).

Per compilare basta gcc strlen_optimize.c
I miei risultati sulle prime 5000 righe di questo file sono:

• Naive elapsed time: 815.000000
• Smart elapsed time: 612.000000
• Naive monkey elapsed time: 88.000000
• Smart monkey elapsed time: 0.000000 (insomma molto ma molto poco)

P.S.: L’esempio riportato è su un file e quindi la lunghezza ce la prendiamo nel momento in cui lo portiamo in memoria. In caso di stringhe basta sostituire il

	for (i = 0; i < strlen(str); i++) { }

con

	while (str[i] != '') { i++; }

Se invece è necessario richiamare strlen, e lo si deve fare in più punti, è bene salvarsi il risultato in una variabile in modo da evitare le altre chiamate inutili.

Come sempre have fun and love C!

Mi sono accorto che è sol invictus (natale insomma) quindi sostituite i vari ieri sera con l’altroieri sera e tanti auguri a nome di tutti i pidduisti!

About these ads