[C# / X# ] Cosmos - C# Open Source Managed Operating System

[71106]

Ritengo che una singola MOV da o verso la memoria sia assai più lenta di una IDIV.

Che un compilatore trasformi una divisione in uno shift quando il divisore è potenza di due è normale, credo che qualunque architettura riesca a fare uno shift in un solo colpo di clock.

Che motivazioni riportava la roba che hai letto circa questa lentezza?

[cdimauro]

@fano: passi la moltiplicazione per potenze di due, ma lo shift a destra NON è equivalente alla divisione quando hai a che fare con interi con segno. Quindi... OCCHIO!

Riguardo ai tuoi problemi con quel pezzo di codice, sarebbe più utile un dump del binario generato.

[fano]

Originariamente inviato da 71106

Ritengo che una singola MOV da o verso la memoria sia assai più lenta di una IDIV.

Quale mov? Questa 'mov eax,dword ptr [val]'? Beh credo che sia impossibile farlo direttamente su 'val' la shift...

Originariamente inviato da 71106

Che un compilatore trasformi una divisione in uno shift quando il divisore è potenza di due è normale, credo che qualunque architettura riesca a fare uno shift in un solo colpo di clock.

Che motivazioni riportava la roba che hai letto circa questa lentezza?

Dicevano che l'operazione DIV è in realtà implementata come una serie di sottrazioni quindi effettivamente - anche usando la logica - non può essere più veloce di uno shift binario
Possibile però che i processori moderni abbiano ancora questo problema?

Originariamente inviato da cdimauro

@fano: passi la moltiplicazione per potenze di due, ma lo shift a destra NON è equivalente alla divisione quando hai a che fare con interi con segno. Quindi... OCCHIO!

Beh il numero che passavo alla funzione era positivo (il solito 42 ) quindi forse "fingeva" che fosse non segnato? Da notare anche l'istruzione 'cdq' che se ho capito bene lo trasformava in un long (forse unsigned long?).

Mah io resto nel dubbio che fare CDQ + SAR invece che semplicemente IDIV (come fa il compilatore C#) faccia poi tutta sta differenza... tu cosa ne dici?

Originariamente inviato da cdimauro

Riguardo ai tuoi problemi con quel pezzo di codice, sarebbe più utile un dump del binario generato.

Attendendo un po' ottenevo il solito "stack corruption", ma io ho davvero difficoltà a capire come operare con lo stack quando faccio qualcosa ad ESP tutto esplode! Perché? In ESP c'era un float ("intero" a 4 byte), l'ho "mosso" dentro XMM0 e quindi io ci scrivo un altro valore che male ci sarebbe?

Comunque ho cambiato il codice facendo una Push dentro ESP non ho capito perché ho dovuto "muovere" lo stack di 4 se no non funzionava, comunque ottengo il valore coretto "-42.0" peccato che l'asserzione fallisce dicendo che "-42.0" != "-42.0".

      // There is no direct float negate instruction in SSE simply we do a XOR with  0x80000000 to flip the sign bit
      XS.SSE.MoveSS(XMM0, ESP, sourceIsIndirect: true);
      //XS.SSE.MoveSS(XMM1, "__floatsignbit", sourceIsIndirect: true);
      //XS.Set(ESP, 0x80000000);
      XS.Add(ESP, 4);
      XS.Push(0x80000000);
      XS.SSE.MoveSS(XMM1, ESP, sourceIsIndirect: true);

      XS.SSE.XorPS(XMM0, XMM1);
      XS.SSE.MoveSS(ESP, XMM0, destinationIsIndirect: true);

La domanda è che differenza c'è tra fare una MOV in ESP e una PUSH in ESP?

[71106]

Originariamente inviato da fano

Quale mov? Questa 'mov eax,dword ptr [val]'? Beh credo che sia impossibile farlo direttamente su 'val' la shift...

Qualunque MOV. La memoria virtuale richiede che un singolo lookup verso la memoria fisica causi in realta' tre lookup, con una frequenza di clock piu' lenta di quella del processore. E' ovvio che non si puo' sostituire l'istruzione MOV con qualcos'altro, altrimenti la stessa Intel l'avrebbe gia' fatto.

Dicevano che l'operazione DIV è in realtà implementata come una serie di sottrazioni quindi effettivamente - anche usando la logica - non può essere più veloce di uno shift binario

Che io sappia i circuiti divisori si implementano con reti combinatorie, quindi il computo (per quanto possa essere intricato) avviene sempre in un solo colpo di clock. Un colpo di clock richiede esattamente lo stesso tempo, tanto per le divisioni quanto per gli shift. Forse mi sbaglio riguardo ai divisori?

[71106]

Originariamente inviato da 71106

Che io sappia i circuiti divisori si implementano con reti combinatorie, [...]

Primo link che ho trovato su Google: http://a2.pluto.it/a2/a2278.htm#almlanchor21100

Gli ho solo dato un'occhiata, ma il tipo mi sembra riuscire nell'implementazione di un divisore senza usare microcodice, solo una rete combinatoria.

[ingframin]

Originariamente inviato da 71106

Primo link che ho trovato su Google: http://a2.pluto.it/a2/a2278.htm#almlanchor21100

Gli ho solo dato un'occhiata, ma il tipo mi sembra riuscire nell'implementazione di un divisore senza usare microcodice, solo una rete combinatoria.

Che io sappia i processori moderni usano o il metodo di Newton-Raphson o il metodo di Goldschmidt che entrambi richiedono più o meno cicli di clock in base alla precisione richiesta.

Il circuito combinatorio di quel documento illustra in linea di principio come si fa la divisione con un circuito combinatorio, ma quella soluzione è troppo lenta per i processori moderni.
Attenzione che a disegnare i blocchettini negli schemi non ci vuole niente, poi però i segnali si devono propagare in un mezzo fisico e li escono le magagne e ciò che funziona su carta funziona sempre meno bene (da cui scaturisce la minchiata che ho scritto nella mai firma, che in realtà tanto minchiata non è...).

[edit]
Wikipedia riporta anche quest'altro metodo:
https://en.wikipedia.org/wiki/Divisi...m#SRT_division
ma non so se effettivamente è ancora usato da Intel o no.
Le look up table velocizzano molto i calcoli ma quanto spazio occupano sul silicio!

[fano]

Allego questo PDF come si può vedere per processori vecchi DIV e MUL potevano anche occupare 46 cicli (!) mentre SHL / SHR ne occupano quasi sempre solo 1:

http://www.agner.org/optimize/instruction_tables.pdf

quindi sì sembrerebbe un'ottimizzazione che ha senso fare anche con le CPU di oggi mi chiedo perché C# non lo faccia non sembra troppo complessa da implementare o mi perdo qualcosa?

Comunque tornando al mio problema:

 // There is no direct float negate instruction in SSE simply we do a XOR with 0x80000000 to flip the sign bit
XS.SSE.MoveSS(XMM0, ESP, sourceIsIndirect: true);
//XS.SSE.MoveSS(XMM1, "__floatsignbit", sourceIsIndirect: true); 
//XS.Set(ESP, 0x80000000); 
XS.Add(ESP, 4); 
XS.Push(0x80000000); 
XS.SSE.MoveSS(XMM1, ESP, sourceIsIndirect: true);
XS.SSE.XorPS(XMM0, XMM1);
XS.SSE.MoveSS(ESP, XMM0, destinationIsIndirect: true);

Perché non sta funzionando? Il risultato è -42.0 come atteso, ma l'asserzione fallisce: non capisco!
Quando il valore era una constante scritta nella sezione "DATA" funzionava alla perfezione...

[71106]

Originariamente inviato da ingframin

Attenzione che a disegnare i blocchettini negli schemi non ci vuole niente, poi però i segnali si devono propagare in un mezzo fisico e li escono le magagne e ciò che funziona su carta funziona sempre meno bene (da cui scaturisce la minchiata che ho scritto nella mai firma, che in realtà tanto minchiata non è...).

Minchia... Se ho capito bene, mi sono perso il periodo storico in cui il clock dei processori mainstream e' divenuto talmente elevato da non consentire la propagazione del segnale alle reti combinatorie troppo lunghe.

[ingframin]

Originariamente inviato da fano

Allego questo PDF come si può vedere per processori vecchi DIV e MUL potevano anche occupare 46 cicli (!) mentre SHL / SHR ne occupano quasi sempre solo 1:

http://www.agner.org/optimize/instruction_tables.pdf

Mi pare normale, si usa un barrel shifter!

Sul perché c# non lo faccia non so che rispondere Sei sicuro che il codice compilato dal JIT non faccia la sostituzione?

Tieni pure conto che sostituire una divisione intera per due con uno shift a destra ti fa perdere il resto della divisione. Quindi non sono sicuro al 100% che sia una cosa sempre fattibile.

[fano]

Il C++ faceva questa ottimizzazione, C# apparentemente no! Ma appunto non sono cosa intenda Visual Studio con quel "disassemble"... sinceramente avrebbe più senso se mostrasse l'IL invece che ASM x86!

Beh in quel caso particolare io non necessitavo del resto quindi lo shift era perfettamente lecito come sostituto della divisione

[71106]

Originariamente inviato da Antonio23

che vuol dire che ti fa perdere il resto? e' una divisione intera, non ce l'ha il resto.

I processori Intel hanno un bit contenente il resto dell'ultima operazione che ne ha prodotto uno, il bit e' testabile tramite jump condizionati. Le istruzioni (I)DIV popolano quel bit, gli shift chiaramente no.

Va da se' che e' un problema per il compilatore e che il programmatore C# non se ne deve minimamente preoccupare.

[71106]

Originariamente inviato da Antonio23

ah, non lo sapevo. ho sempre lavorato con architetture molto piu' spartane

Ho i ricordi offuscati... Ho appena ricontrollato qui, pag. 284 del vol. 2A (Instruction Set Reference). Il bit a cui mi riferivo e' il CF ("Carry Flag", testabile tramite JC e JNC), tuttavia sia DIV che IDIV lo lasciano invariato poiche' giustamente il resto puo' essere arbitrariamente grande. Viceversa, il resto viene memorizzato nel registro general-purpose D (DX, EDX, o RDX, a seconda della modalita' del processore).

[fano]

Comunque in caso di resto di divisione per 2 credo - di nuovo - ci sia qualche ottimizzazione possibile invece che fare la IDIV (o l'istruzione apposita per ottenere il resto che in x86 ci sarà sicuramente ) forse un & 2?

In ogni caso assembler mi sta facendo totalmente impazzire!
Ricapitoliamo sto cercando di negare un valore floating point faccio 2 test la negazione di un numero positivo che mi torna lo stesso numero negato (42 ==> -42) e l'inverso (-42 ==> 42).

Questa è la prima versione che funziona perfettamente:

// There is no direct float negate instruction in SSE simply we do a XOR with 0x80000000 to flip the sign bit
XS.SSE.MoveSS(XMM0, ESP, sourceIsIndirect: true);
XS.SSE.MoveSS(XMM1, "__floatsignbit", sourceIsIndirect: true); 
XS.SSE.MoveSS(XMM1, ESP, sourceIsIndirect: true);
XS.SSE.XorPS(XMM0, XMM1);
XS.SSE.MoveSS(ESP, XMM0, destinationIsIndirect: true);

__floatsignbit è definito in un altro file completamente diverso (CosmosAssembler.cs) nel kernel c'è una sezione DATA dove ci sono tutte le constanti __floatsignbit finisce in fondo insieme alle altri costanti che introdotto per convertire unsigned int in float ecc...

La seconda versione è analoga semplicemente la constante è dichiarata dentro il metodo Execute() (poco prima del codice che vedete) invece che essere in un file a caso: l'unica differenza è che nel kernel __floatsignbit si trova non più in fondo in una posizione random sempre dentro la stessa sezione data.
Ebbene in questo caso come per magia (!) il primo test funziona, ma il secondo no... dicendo - senza alcuna vergogna che -42.0 != -42.0

Questa è la III versione in cui la constante è "pushata" nello stack:

// There is no direct float negate instruction in SSE simply we do a XOR with 0x80000000 to flip the sign bit
XS.SSE.MoveSS(XMM0, ESP, sourceIsIndirect: true);
XS.Add(ESP, 4);
XS.Push(0x80000000);
XS.SSE.MoveSS(XMM1, ESP, sourceIsIndirect: true);
XS.SSE.XorPS(XMM0, XMM1);
XS.SSE.MoveSS(ESP, XMM0, destinationIsIndirect: true);

ancora una volta il I test funzione, ma il secondo no (-42.0 != -42.0).

Prima che vi emozionate tutti lo so che gli operatori == e != non funziona con i float ed infatti uso questa routinetta fornitami gentilemente dalla Microsoft per testare se sono uguali ha sempre funzionato per tutti i test che ho fatto (e funziona anche per -42.0 quando la constante è dichiarata dentro CosmosAssembler.cs):

        /* The single== equality operator is so imprecise to not be really ever useful we should be happy if the two values are "similar" */
        private static bool SinglesAreEqual(Single left, Single right)
        {
            // Define the tolerance for variation in their values
            Single difference = (Single) Math.Abs(left * .00001);

            if (Math.Abs(left - right) <= difference)
                return true;
            else
                return false;
        }

Cosa ne pensate? Avete qualche idea?

[fano]

Con oggi sono entrato ufficialmente nel gruppo direttivo di Cosmos "CoreDev - The Inner Sanctum":
https://github.com/orgs/CosmosOS/teams/coredev

Beh devo dire che è una bella soddisfazione

Ovviamente non è che mi poteva andare bene non riuscivano ad aggiungermi Github diceva che io NON esisto che ho conflitti con sto tizio:
https://github.com/undefined

Poi si scopre qual era il problema? Il mio userId di github è fanoI (con la i), ma loro scrivevano fanol (con la elle!) per forza che non mi arrivava nessuna notifica

Detto questo abbiamo deciso quali sono i piani dopo il merge del mio lavoro sui float (e la chiusura di più PR possibili) e il termine del lavoro sul memory manager (RAT) passeremo da .NET a .NET core questo dovrebbe permetterci di avere molti, molti meno plug da sviluppare così da poterci concentrare sul vero lavoro che è scrivere il kernel in C#!

Si è subito però scatenato un dibattito compiliamo anche IL2CPU con .NET core? Temiamo che ci saranno problemi con reflection e feature avanzate dato che .NET core è ancora immaturo. D'altro canto il grosso vantaggio sarebbe che usando .NET core potremmo molto più facilmente rendere possibile compilare Cosmos su MacOS e su Linux!

Voi cosa ne pensate?

[Shirov]

Originariamente inviato da fano

Comunque in caso di resto di divisione per 2 credo - di nuovo - ci sia qualche ottimizzazione possibile invece che fare la IDIV (o l'istruzione apposita per ottenere il resto che in x86 ci sarà sicuramente ) forse un & 2?

Mi inserisco solo perchè recentemente, spulciando nei miei appunti del passato, ho trovato questo:

"divisione per 2 x86:
sar eax, 1"

francamente non ricordo quasi nulla dell'argomento per cui non garantisco che possa in effetti essere utile al discorso.

EDIT: sorry ho letto di fretta a te interessava il discorso del resto. Come non detto.

[fano]

Il trucco vale per tutti i multipli di 2 quindi: divisione per 4 == shift a destra di 2!

Per il modulo sempre per multipli di 2:
x % 2n == x & (2n - 1)

quindi per esempio: x % 4 == x & 3

https://en.wikipedia.org/wiki/Modulo_operation

Comunque mi sono installato la release 1.0 di .Net Core e la buona notizia è che la / 2 è ora ottimizzata con uno shift come atteso!

S'aggiunga: Ottimizzazione divisione con costanti.
(Che casino )

Io mi sono predisposto già a compilare Cosmos con .Net Core, ma mi sa che i lavori sul gestore di memoria RAT si protrarranno per le lunghe

[WarDuck]

Edit.

[fano]

Allora vi aggiorno un po':

1. RAT è stato integrato nel main branch e dopo i primi bachetti (fixati) ora Cosmos ha il suo bravo gestore di memoria
2. L'integrazione di Cosmos col Net Core runtime procede su un suo branch separato (https://github.com/CosmosOS/Cosmos/tree/NetCore) il grosso dei problemi che stiamo avendo è dovuto all'immaturità della cosa sembra Visual Studio si incasini tra PCL, Net Core, Net Standard... se non ci capisce lui figurarsi noi

E per quanto riguarda me?
Visto che c'è grande richiesta di fare grafica su Cosmos e si stanno già forkando 13 GUI diverse () si è deciso che doveva esserci una soluzione pulita e funzionante dentro Cosmos e che me ne sarei occupatp io.

Questa è la nostra idea:
https://github.com/fanoI/Cosmos/wiki...Graphic-Revamp

ma prima di arrivarci abbiamo un altro grosso problema ci sono attualmente 2 driver in Cosmos per pilotare la VGA:

1. VGADriver modalità testuale e modalità grafica fino a 320x200@256 colori
2. VBEDriver modalità grafica fino a 1600x1200@truecolor

Hanno ambedue dei problemini il primo manco tanto un problemino: non funziona proprio! Il secondo non è davvero un driver VBE, ma è l'implementazione di VBE secondo Bochs quindi non è la cosa vera che dovrebbe andare su tutte le schede video dal 2000 in poi...
(a parte il nome VBE funziona però! Ma già non funziona su VmWare l'emulatore più diffuso quindi non serve a nulla quel driver )

Il driver VGA è questo:
https://github.com/CosmosOS/Cosmos/b...s/VGAScreen.cs

che sembra grosso modo derivare da questo codice C:
http://files.osdev.org/mirrors/geeze...aphics/modes.c

Il mio kernel di test fa semplicemente questo:

    VGA.SetGraphicsMode(ScreenSize.Size320x200, ColorDepth.BitDepth8);
    VGA.SetPixel(42, 42, 0x000003); // 3 dovrebbe essere il colore "ciano"

Bochs scrive che il cambio di modo è effettuato, ma lo schermo resta tristemente nero

Avere due possibili driver (uno solo avrebbe girato a run time) era interessante anche per capire che l'idea di Canvas era veramente fatta bene cioè per esempio ho VmWare e disegno un rettangolo con lo sfigato driver VGA poi uso Bochs e disegno lo stesso rettangolo con il driver VBE che non è VBE e sono a cavallo! Farlo solo con uno rischierei di non avere una cosa universale... quindi magari scriveremo un driver per la GPU di VmWare e scopriamo che Canvas non era veramente venuto.

Avete qualche idea?

[cdimauro]

Ne abbiamo parlato in privato, ma appena posso mi smazzo il lungo PVT e ti rispondo.

Rispondo soltanto a questo, che avevo perso di vista:

Originariamente inviato da fano

Il trucco vale per tutti i multipli di 2 quindi: divisione per 4 == shift a destra di 2!

Assolutamente sì per i numeri senza segno, e no per quelli con segno.

In generale in quest'ultimo caso vale la seguente:

x / 2^n = (x + (2^n - 1 if x < 0 else 0)) >> n

Per il modulo sempre per multipli di 2:
x % 2n == x & (2n - 1)

quindi per esempio: x % 4 == x & 3

https://en.wikipedia.org/wiki/Modulo_operation

Occhio a come il linguaggio definisce le divisioni quando gli operandi hanno il segno. Il modulo potrebbe essere dotato di segno.

[fano]

Mah mi chiedo alla fine, ma vale la pena davvero cambiare le divisioni con gli shift e i moduli con gli and se ci sono tutte queste trappole? Perché la CPU non può farsele da sole queste cose (magari quelle può moderne lo fanno pure, ma si ottimizza per il caso più generico... il 486)?

Nei test che feci ho visto che anche Visual Studia fa questi "giochini" oltre che GCC e Clang quindi sicuramente è un ottimizzazione "benefica" però mi fa pensare sembra così semplice la divisione

Ritornando alla VGA devo forse settare la palette? Ovvero la palette di default dopo il boot mappa tutti i 256 possibili valori sul nero?