Visualizza il feed RSS

Titolo provvisorio...

It's a "long long" way to Tipperary...

Valuta questo inserimento
di pubblicato il 04-04-2012 alle 03:49 (4119 Visite)
Prendo in prestito per il titolo il ritornello - con modifica - di una delle più note marcette militari anglosassoni, assurta a simbolo della prima guerra mondiale (con una curiosità che piacerà al buon Antonio: la medesima melodia, con ben poche variazioni, viene correntemente usata anche per l'inno dell'università dell'Oregon "Mighty Oregon") per tornare sul tema degli standard e dialetti del linguaggio C.

Sovente ricevo richieste d'aiuto da studenti e programmatori alle prime armi, alle prese con problemini didattici che richiedono l'uso di numeri interi relativamente grandi (per un comune calcolatore, s'intende). Naturalmente esistono fior di librerie C per l'uso di interi con precisione arbitraria: ad esempio l'arcinota MIRACL presente nei migliori repositories di freeware e shareware fin dagli anni Ottanta, oppure MAPM, oppure la MPFR dell'INRIA e GMP, ma anche le implementazioni di riferimento contenute nei gloriosi Snippets di Bob Stout (RIP). Se però la questione spesso non merita l'uso di una libreria dedicata, nondimeno simili esercizi possono beneficiare dall'uso di interi a 64 o 128 bit. E qui sta il busillis.

Per spiegare meglio la questione, facciamo un salto indietro nel tempo. Il linguaggio C, come tutti ben sappiamo, nasce negli anni Settanta su DEC PdP-11 ed è concepito sostanzialmente come un macroassembler "portabile" e flessibile. Tale linguaggio è "figlio del suo tempo" sotto molti aspetti: si tratta in realtà di un linguaggio decisamente unico nel suo genere, a mezza via tra il low level e i veri e propri linguaggi di alto livello.

Taluni arcaismi e compromessi implementativi si sono mantenuti pressoché invariati nel corso della sua intera storia. Ne sono un esempio eclatante i pochi e semplici modificatori del C (short, long), che ben presto si rivelano del tutto insufficienti a trattare simultaneamente l'intera gamma di ampiezze numeriche e registri dei core più diffusi: 4, 8, 16, 24, 32, 64, 80 bit e oltre, per tacere di architetture - magari Harvard, ossia con memorie dati e istruzioni fisicamente separate - con ampiezze di parola che non sono una potenza intera del due (es. 9, 12, 14, 20, 31 bit, e non dimentichiamo i bit array booleani indirizzabili bit a bit gestiti esplicitamente da molti core...). Tanto è vero che negli ultimi trent'anni quasi nessun compilatore C, per quanto di basso profilo qualitativo, si è fatto mancare soluzioni coerenti e robuste per trattare in modo esplicito con questa molteplicità. Soluzioni che di norma ritraducono internamente le primitive, generiche designazioni del C rimappandole su tipi custom (spesso accessibili in modo trasparente) che riflettono le ampiezze di parola gestibili dalla piattaforma.

In considerazione di questa vera e propria selva di estensioni proprietarie, e della sostanziale irriducibilità di una simile complessità a poche e semplici astrazioni valide ovunque, lo standard del linguaggio ISO/IEC 9899:1990 (familiarmente C'89 o anche C'90, che indicano esattamente il medesimo linguaggio, ponendo l'accento unicamente sull'anno di promulgazione dello standard ANSI o piuttosto sul successivo recepimento da parte di ISO), che dopo trent'anni risulta ancora di fatto il più seguito ed utilizzato come riferimento di base per i compilatori, si limita saggiamente a raccomandare la seguente catena di relazioni d'ordine deboli tra i tipi interi:

Formula LaTeX: \text{short int}\leq\text{int}\leq\text{long int}

Nella seconda metà degli anni Novanta molti compilatori C/C++, in testa i più diffusi per il piccolo mondo dei PC (Microsoft e Borland, quest'ultimo in particolare dalla versione 4.x) supportano già pienamente con le loro estensioni proprietarie interi a 64 bit su tutte le piattaforme Intel e compatibili; allo stesso modo, negli stessi anni, nel mondo GNU il compilatore GCC ha introdotto le sue analoghe estensioni, parimenti proprietarie e arbitrarie, per realizzare i medesimi scopi.

Limitandoci al mondo dei PC, che ha comunque la necessità di districarsi almeno tra interi a 8 (tramite i char, tipicamente, ma questo è già un escamotage poco simpatico e confligge in qualche modo con Unicode), 16, 32, e ben presto 64 e 128 bit, le "scuole di pensiero" valide per la definizione di interi a 64 bit sono sempre state sostanzialmente due: il modificatore long long (da cui il titolo, of course!), introdotto da GCC, e l'equivalente tipo __int64 (si noti il doppio underscore iniziale, tipicamente riservato ai simboli interni del compilatore) indipendentemente supportato da MSVC e Borland da tempo immemorabile.

Se ciò non bastasse, i tre diversi modelli di sottoarchitetture a 64 bit esistenti aggiungono ulteriore confusione ad uno scenario già poco chiaro nella didattica e nella comunicazione.

Ripeto il concetto per i lettori più distratti: compilatore permettendo, l'uso di interi a 64 bit è possibile senza alcun problema da circa vent'anni or sono, e su hardware per nulla esotico, già a partire da i386, i486 e parenti stretti a 32 bit puri. Io stesso usavo ampiamente __int64 con Borland C/C++ 4.x, tanto per pescare vicino, tra sorgenti archiviati ma ancora a portata di mano (1996 o giù di lì). Repetita juvant, perché curiosamente ancor oggi non manca chi appare fermamente quanto erroneamente convinto di assurde limitazioni a tale possibilità, confondendo evidentemente il supporto hardware ad applicazioni full 64 bit (questo sì limitato solo ad alcuni flavor dei SO mainstream windows e linux, e relative piattaforme hardware) col mero impiego di aritmetica intera estesa a 64 bit, a sua volta ampiamente supportata dai principali compilatori su quasi tutte le piattaforme PC ancora realisticamente accessibili - incluso un buon numero di macchine legacy.

Tale estensione, a livello concettuale, deve pensarsi come esattamente identica (ma con prestazioni comparativamente assai migliori, trattandosi di aritmetica intera) al supporto del floating point IEEE 754 emulato, già cavallo di battaglia di numerosi compilatori C per DOS e perfettamente funzionante su tutti i processori all'epoca privi di coprocessore matematico Intel o Weitek on-chip o onboard.

Appare lapalissiano che l'unica concreta differenza riscontrabile tra full 64 bit e aritmetica estesa a 64 bit sarà un leggero degrado prestazionale nel secondo caso, peraltro ampiamente accettabile ai fini didattici (e non solo).

Abbiamo quindi a che fare, come quasi sempre accade nella pluridecennale storia del linguaggio C, con soluzioni diverse e indipendenti al medesimo problema, con dialetti tra loro incompatibili - anche se, nel caso in specie, è sufficiente una manciata di direttive #define per rendere il codice "portabile" tra tutti i vari compilatori coinvolti.

I due standard del linguaggio C successivi, in particolare il cosiddetto C'99 ossia ISO/IEC 9899:1999, hanno operato delle scelte piuttosto arbitrarie riguardo all'accoglimento delle estensioni de facto: ben lungi dall'essere una vacua questione di principio e di prestigio, vi sono pragmaticamente legate importanti questioni aziendali di preservazione e refactoring di centinaia di milioni di LOC prodotte nel decennio precedente - si pensi solo, per avere un'idea, ai milioni di linee di codice delle API di Windows 95, 98, NT e relative interfacce.

Per chi desiderasse approfondire, è pubblicamente disponibile il "rationale" che accompagna lo standard, oggi a sua volta superato dal C'11 promulgato appena pochi mesi fa, nel dicembre del 2011.
Pur non nascondendo la presenza di varie proposte e critiche accese su tale punto, il documento sopra linkato presenta per tale scelta unidirezionale motivazioni largamente discutibili. Si veda anche questa storica discussione.

Per quanto ci riguarda, e sempre restando al mondo dei PC (ribadisco: non esiste cross-compilatore che non abbia da sempre la sua soluzione specifica al problema, in barba a qualsiasi standard postumo poco meditato!) osserverei invece che una forma come int64_t o simile appare comunque più robusta e in linea con le più diffuse norme di stile. Ad esempio, la normativa MISRA C 2004 contiene anche la seguente regola, che cito testualmente:
6.3 (advisory): typedefs that indicate size and signedness should be used in place of the basic types.

Numerosi progetti di cross-compiler fin dalla fine degli anni Ottanta si adeguano nativamente a questa fondamentale direttiva di buon senso, introducendo ad esempio tipi booleani ampi esattamente 1 bit sulle piattaforme che li supportano nativamente (tipicamente come bitarray embedded nel set di registri) e più in generale rimappando totalmente i primitivi, inespressivi tipi di base del C per gestire la complessità delle piattaforme più disparate.

In effetti, e qui si ha definitivamente la sensazione di una certa contraddizione interna, lo stesso standard C'99 ai paragrafi 7.8 e soprattutto 7.18 definisce due header, portabili e ampiamente preferenziali per simili definizioni: metodo - non a caso - integralmente basato su una norma di stile del tutto identica a quella accolta da MISRA e da numerose altre normative. Vengono dunque in ultima analisi raccomandate definizioni come int64_t e uint64_t contenute nello header minimale stdint.h e nella sua estensione (che lo include) inttypes.h, alternativamente supportati ad oggi da quasi tutti i compilatori per PC maggiormente diffusi (con l'unica eccezione di Visual C/C++, almeno fino alla versione 2008).

Per la stesura di nuovo codice o il refactoring di sorgenti esistenti, la Via Regia dunque consiste nell'usare le definizioni contenute nell'header stdint della boost library, sempre più in odore di santità, o altro equivalente. In questo modo una typedef come int64_t o uint64_t sarà sottesa ad un articolato sistema di direttive di compilazione condizionale che la rendono pressoché universalmente valida, a maggior ragione se ci si limita ai più diffusi compilatori per PC mainstream.

Ricapitolando, sempre riguardo ai PC e simili:
1) MSVC e parenti stretti fanno uso unicamente di __int64, fino alla versione 2008 inclusa (_MSC_VER <= 1500). Per compilare nuovo codice basato su uint64_t e affini con versioni precedenti del compilatore, nulla vieta di usare gli header provvisti con la Boost library o da altre fonti, ovviamente;

2) I compilatori Borland antecedenti al Developer Studio 2006 escluso (__BORLANDC__ < 1400) sono nella situazione appena esposta, mentre i successivi supportano sia la sintassi Microsoft, sia gli header previsti dal C'99;

3) Digital Mars, Open Watcom, Intel supportano indistintamente lo standard de facto Microsoft (__int64, ad esempio nei rispettivi winnt.h), come pure stdint.h e/o inttypes.h.

4) Per i vari porting di GCC, vale ovviamente il supporto a long long int e in seguito stdint.h e inttypes.h. Tali estensioni sono state introdotte in origine - molti anni prima dello standard C'99 - proprio da tale famiglia di compilatori: ad esempio, già nel GCC 2.x definizioni come LONG_LONG_MAX e simili erano semplicemente parte di limits.h.

Per meglio esemplificare il concetto, propongo un banale header di chiaro intento didascalico, senza alcuna pretesa se non quella di illustrare quanto qui accennato.

codice:
#ifndef __INT64BIT_H__
#define __INT64BIT_H__

#include <stdio.h>
#include <limits.h>
#include <float.h>

#if defined(__BORLANDC__)
    const char Compiler[] = "** Compiled with Borland C++"
                            "                              **";
 #if __BORLANDC__ >= 1400
     #include <stdint.h>
 #elif defined(_UI64_MAX)
     /* __BORLANDC__ >= 0x400 */
     typedef unsigned __int64 uint64_t;
     #define UINT64_MAX _UI64_MAX
     #define INT64_MAX _I64_MAX
     #define INT64_MIN _I64_MIN
 #endif
 #ifndef PRIu64
     #define PRIu64 "I64u"
     #define PRId64 "I64d"
 #endif
#endif

#if defined(_MSC_VER)
    const char Compiler[] = "** Compiled with Visual C/C++"
                            "                             **";
 #if _MSC_VER > 1500
     #include <stdint.h>
 #elif defined(_UI64_MAX)
     /* _MSC_VER >= 900 */
     typedef unsigned __int64 uint64_t;
     #define UINT64_MAX _UI64_MAX
     #define INT64_MAX _I64_MAX
     #define INT64_MIN _I64_MIN
 #endif
 #ifndef PRIu64
     #define PRIu64 "I64u"
     #define PRId64 "I64d"
 #endif
#endif

#if defined(__WATCOMC__)
    const char Compiler[] = "** Compiled with Open Watcom"
                            "                              **";
    #include <inttypes.h>
#endif

#if defined(__DMC__)
    const char Compiler[] = "** Compiled with Digital Mars"
                            "                             **";
    #include <inttypes.h>
#endif

#endif /* __INT64BIT_H__ */
In chiusura, propongo di sfruttare l'header appena presentato con un algoritmo decisamente elementare, ma assolutamente non disprezzabile, per l'esplorazione esaustiva delle prime decine di numeri di Fibonacci.
Con le solite, noiosamente ovvie premesse che in casi del genere il non plus ultra prestazionale è costituito dall'uso di una LUT, ossia una tabella pregenerata, seguito dall'uso di una formula diretta come quella di Binet facilmente adattata al caso (ad esempio, secondo le indicazioni degli Snippets C, derivate direttamente dal secondo volume del TAoCP di D. E. Knuth).

Si noti, infine, proprio in riferimento alla implementazione contenuta negli Snippets C, che l'uso di interi a 64 bit consente di visualizzare una decina di numeri di Fibonacci in più rispetto al ricorso ai double che caratterizza tale soluzione, i cui limiti di precisione iniziano a mostrarsi già attorno al settantesimo numero (con BCC 5.5.1 si arriva all'ottantaquattresimo usando esplicitamente i long double, che tuttavia per quasi ogni altro compilatore coincidono con i double).

codice:
#include "int64bit.h"

#define MAX_FIBONACCI_64 92

#define HSEP_STAR "************************************************************"
#define HSEP_LINE  "------------------------------------------------------------"

int main(void)
{
    int i;
    uint64_t Fib[2];

    Fib[0] = 0;
    Fib[1] = 1;

    puts("\n" HSEP_STAR);
	puts(Compiler);
	puts(HSEP_STAR "\n");

    puts("Fib[0] = 0\nFib[1] = 1");

    for (i = 0; i < MAX_FIBONACCI_64; ++i)
    {
        int j = i & 1;
        Fib[j] += Fib[j^1];
        printf("Fib[%d] = %" PRIu64 "\n", i +2, Fib[j]);
    }

    return(0);
}
/* EOF: Fib64.c */
Il tutto è stato compilato con:
- Visual Studio Express 2008;
- Borland C/C++ 5.5.1;
- Borland Turbo C++ 2006;
- Digital Mars 7.51;
- Open Watcom 1.8.

Ad usum delphini, gli studenti notino bene che l'algoritmo (per quanto ingenuo rispetto all'uso della formula diretta di Binet) realizza la massima efficienza rinunciando a priori all'uso di dispersive e contorte funzioni ricorsive ed al contempo evita gli sprechi di memoria e/o cicli macchina tipici delle realizzazioni dei newbie. Si ha infatti l'eliminazione di qualsiasi costrutto condizionale nel loop interno, sfruttando semplicemente la parità della variabile di induzione: con tale singolo bit si indicizzano modularmente e in modo alternato le uniche due variabili necessarie, che di volta in volta contengono i due immediati predecessori del numero di Fibonacci corrente, in modo tale che il minore di essi occupa alternativamente la posizione 0 o 1 nell'array. Nulla vieta, allo stesso modo, di usare esplicitamente l'aritmetica dei puntatori in luogo dell'array, con minime modifiche sintattiche (e variazioni prestazionali pressoché nulle).
Risultato: una implementazione in O(N) pulita, brevissima, semplice, elegante e massimamente efficiente, pur trattandosi di una enumerazione esaustiva, limitata unicamente dai tipi interi trattabili nativamente dalla macchina e/o dal compilatore.

Commenti