OT Programmazione 2014

[MItaly]

Si prospetta proprio un bel programma: ottima strutturazione con separazione dei task; divisione fra elaborazione dei dati e presentazione; geniale inclusione di un unico sistema di scripting di facile comprensione. Un progetto da manuale insomma

Non a caso per metà l'ho scritto io

Purtroppo, e già in italiano mi preoccupo del fuori tema. Titoli di 2 parole, mai visti prima

Se non sono indiscreto, che traccia hai scelto?

Comunque oggi si è visto come le stringhe C++ usate malamente possano costare veramente tanto... al di là di un'altra serie di bachi mostruosi (per cui attualmente questa routine di caricamento di un modello viene chiamata tipo 3 volte per ogni ordine che si carica), c'era una routine di pre-parsing del file (per estrarre solo alcune informazioni sul contenuto) che portava via circa 13 secondi per un modello da 5 MB (~12 decompressa).

Salta fuori che il collo di bottiglia era roba del tipo if(line.substr(0, 4)=="ABC ") ripetuta per qualche volta; rimossi i temporary (e quindi tre allocazioni dinamiche per ogni riga di un file da decine di migliaia di righe) più qualche altra ottimizzazione il runtime è passato da 13 a 1 secondo.

Altra roba notevole: quanto costano i branch misprediction sulle architetture attuali! Nel più inner loop di tutti gli inner loop di un algoritmo piuttosto complesso a cui sto lavorando c'è sostanzialmente la scansione dei pixel in diagonale di una piccola bitmap, fatta partendo da ogni y dell'immagine.
Per fare questo, sostanzialmente c'era una cosa del tipo

for(int y=a; y<limit; ++y)
{
    offset.y=y;
    for(double r; ; ++r)
    {
        Point p = r*direction + offset;
        if(p.x > img.width || p.y >img.height || p.x<0 || p.y<0)
            break;
        Pixel px=img.pixel(p.x, p.y);
        if(px)
        {
            // eccetera
        }
    }
}

Ora, facendo profiling è saltato fuori che i colli di bottiglia erano le coppie cmp/jump: l'if(px) è costosa (perché l'immagine ha un andamento non ben prevedibile dal branch predictor) ma inevitabile; invece, precalcolando fuori il limite corretto di r (invece di fare il controllo sulla posizione risultante) e rimuovendo così la necessità del primo if è venuto fuori un incremento di prestazioni di tutto l'algoritmo di un buon 30%

[Scara95]

Non a caso per metà l'ho scritto io

Se non sono indiscreto, che traccia hai scelto?

Tecnologia pervasiva, ma ho parlato in sostanza della società disinformata, non preparata alla tecnologia che si forma idee scorrette su alcuni argomenti e si espone a rischi inconsapevoli.

Comunque oggi si è visto come le stringhe C++ usate malamente possano costare veramente tanto... al di là di un'altra serie di bachi mostruosi (per cui attualmente questa routine di caricamento di un modello viene chiamata tipo 3 volte per ogni ordine che si carica), c'era una routine di pre-parsing del file (per estrarre solo alcune informazioni sul contenuto) che portava via circa 13 secondi per un modello da 5 MB (~12 decompressa).

Salta fuori che il collo di bottiglia era roba del tipo if(line.substr(0, 4)=="ABC ") ripetuta per qualche volta; rimossi i temporary (e quindi tre allocazioni dinamiche per ogni riga di un file da decine di migliaia di righe) più qualche altra ottimizzazione il runtime è passato da 13 a 1 secondo.

Non preoccuparti, succede in molti linguaggi: spesso le operazioni con le stringhe vengono sottovalutate, e pensa che sei fortunato che in C++ sono mutabili, in molti linguaggi sono immutabili e non ti dico che può venirne fuori in mani inconsapevoli. Il fatto è che pochi se ne rendono conto purtroppo.

Altra roba notevole: quanto costano i branch misprediction sulle architetture attuali! Nel più inner loop di tutti gli inner loop di un algoritmo piuttosto complesso a cui sto lavorando c'è sostanzialmente la scansione dei pixel in diagonale di una piccola bitmap, fatta partendo da ogni y dell'immagine.
Per fare questo, sostanzialmente c'era una cosa del tipo

for(int y=a; y<limit; ++y)
{
    offset.y=y;
    for(double r; ; ++r)
    {
        Point p = r*direction + offset;
        if(p.x > img.width || p.y >img.height || p.x<0 || p.y<0)
            break;
        Pixel px=img.pixel(p.x, p.y);
        if(px)
        {
            // eccetera
        }
    }
}

Ora, facendo profiling è saltato fuori che i colli di bottiglia erano le coppie cmp/jump: l'if(px) è costosa (perché l'immagine ha un andamento non ben prevedibile dal branch predictor) ma inevitabile; invece, precalcolando fuori il limite corretto di r (invece di fare il controllo sulla posizione risultante) e rimuovendo così la necessità del primo if è venuto fuori un incremento di prestazioni di tutto l'algoritmo di un buon 30%

Ma lui è gentile: ti pre-carica un sacco di roba che non userai ma dovrai consumare lo stesso solo per migliorare le prestazioni
Sei TU che vanifichi I SUOI SFORZI scrivendo quella brutta roba complicata u.u
Potevi fare a meno di scriverla!

[MItaly]

Tecnologia pervasiva, ma ho parlato in sostanza della società disinformata, non preparata alla tecnologia che si forma idee scorrette su alcuni argomenti e si espone a rischi inconsapevoli.

Boh, non mi sembra fuori tema, era molto aperto come titolo.

Non preoccuparti, succede in molti linguaggi: spesso le operazioni con le stringhe vengono sottovalutate, e pensa che sei fortunato che in C++ sono mutabili, in molti linguaggi sono immutabili e non ti dico che può venirne fuori in mani inconsapevoli. Il fatto è che pochi se ne rendono conto purtroppo.

Era quello che dicevo ad un mio collega, ma secondo lui invece con le stringhe immutabili si possono fare diverse ottimizzazioni per casi come questo (tipo: substr potrebbe restituire semplicemente una slice - il puntatore punta a metà della stringa "originale" e il count viene adattato).
D'altra parte, nulla impedirebbe di farlo anche con stringhe modificabili in copy-on-write, anche se in C++ ci sono un po' di ostacoli ad implementarlo per substr (ad esempio, se non erro c_str() deve eseguire in tempo costante, e questo non è possibile senza allocare una nuova stringa nel caso di slice), e in generale anche le implementazioni che usavano il copy-on-write si sono convertite alla "short string optimization" perché con i constraint imposti dallo standard per il multithreading la cosa diventava più complicata.

Ma lui è gentile: ti pre-carica un sacco di roba che non userai ma dovrai consumare lo stesso solo per migliorare le prestazioni
Sei TU che vanifichi I SUOI SFORZI scrivendo quella brutta roba complicata u.u
Potevi fare a meno di scriverla!

Seriamente: tutte le varie cache, branch prediction, esecuzione speculativa & co. sono delle figate clamorose a livello di speedup, ma introducono una quantità di "stato nascosto" spesso difficile da dominare a priori. Lascia un po' atterriti come ormai l'unico modo sicuro per sapere se del codice gira veloce è fare profiling, visto che gli effetti per così dire "non classici" dei processori attuali spesso determinano miglioramenti o peggioramenti in velocità di diversi ordini di grandezza.

Related:
http://blogs.msdn.com/b/oldnewthing/.../10533875.aspx
http://stackoverflow.com/q/11227809/214671

[Scara95]

Boh, non mi sembra fuori tema, era molto aperto come titolo.

Si vedrà...

Era quello che dicevo ad un mio collega, ma secondo lui invece con le stringhe immutabili si possono fare diverse ottimizzazioni per casi come questo (tipo: substr potrebbe restituire semplicemente una slice - il puntatore punta a metà della stringa "originale" e il count viene adattato).
D'altra parte, nulla impedirebbe di farlo anche con stringhe modificabili in copy-on-write, anche se in C++ ci sono un po' di ostacoli ad implementarlo per substr (ad esempio, se non erro c_str() deve eseguire in tempo costante, e questo non è possibile senza allocare una nuova stringa nel caso di slice), e in generale anche le implementazioni che usavano il copy-on-write si sono convertite alla "short string optimization" perché con i constraint imposti dallo standard per il multithreading la cosa diventava più complicata.

Ha ragione, se non si prevedono stringhe terminate da NULL. Tuttavia ha torto in un altro punto: in altri casi (che sono più comunemente usate dai principianti tra l'altro) le stringhe immutabili rischiano di rendere peggio. Mi spiego meglio: nel caso si concatenino 2 stringhe i panorami possibili sarebbero questi:

Non hai memoria libera adiacente al blocco -> devi allocare una nuova stringa.

Hai memoria libera adiacente al blocco
|
-usi stringhe terminate da 0 -> non puoi sfruttare il blocco in quanto non c'è modo di unire le stringhe
|
-usi stringhe non terminate -> perdi compatibilità diretta con stragrande maggioranza librerie -> puoi sfruttare il blocco
-|
--devi usare una struttura dedicata (i.e. {size; string_pointer}) che copierai ad ogni passaggio funzione

In sostanza poi finiresti sempre e comunque con l'allocare una nuova stringa (nel caso della concatenazione)
N.B. il problema delle stringhe terminate o non si ripresenta uguale nel caso di substr.