Jump to content

script fillArray(array[], value=0) - rýchle vynulovanie arrayu


Tanga

Recommended Posts

Ahojky, chcel by som vám ukázať jeden stock čo som nakódil, fillArray(), ktorý dokáže vynulovať pole, resp. nastaviť každý prvok v poli na nejakú hodnotu.

Je to užitočné v tom, že je to rýchlejšie než použitie loopu, pomer rýchlosti sa odvíja od počtu prvkov, kde pre 100 prvkové pole je fillArray() 18x rýchlejší, pre 1000 a viac prvkové ~65krát rýchlejší.

Použitie

main() {
	new pole[] = {1,2,3,4};
	fillArray(pole, 55); // nastavi kazdu hodnotu v poli na 55
	for (new i; i < sizeof (pole); i++) // vypise cele pole, teda 4 riadky s textom "55"
		printf("%d", pole[i]);                       
}

Pre viac-rozmerné polia treba použiť cyklus fillArray()ov.

main() {
	pole[][] = {{1,2}, {3,4}};

	for (new i; i < sizeof (pole); i++)
		fillArray(pole[i]); // default hodnota je 0, toto teda vynuluje cele pole
                          
	for (new i; i < sizeof (pole); i++)
		for (new j; j < sizeof (pole[]); j++)
			printf("%d", pole[i][j]);
}

 

Speedtest

Ťažko sa získavajú grafy pre rôzne veľkosti polí (lebo pawn nemá polia s dynamickou veľkosťou), ale pár manuálnymi pokusmi som zistil, že s kódom nižšie je fillArray() rýchlejší okolo 18x pre polia o veľkosti 100 prvkov, pre polia okolo 1000 prvkov okolo 70 krát rýchlejší a pre viac (až po 10 000 000 prvkové polia) to už osciluje medzi 60-65-70krát.

Získal som:

[19:45:51] Klasicka metoda: 74012 tickov
[19:45:52] fillArray() metoda: 1075 tickov

 

Pre kód:

main() {
    #define MAX 1234567
    new pole[2000];
    
    new tick = GetTickCount();
    
    for (new i; i < MAX; i++)
        for (new j; j < sizeof(pole); j++)
            pole[j] = 1;
  
    printf("Klasicka metoda: %d tickov", GetTickCount() - tick);
    
    tick = GetTickCount();
    
    for (new i; i < MAX; i++)
        fillArray(pole, 2);
        
    printf("fillArray() metoda: %d tickov", GetTickCount() - tick);
}

 

Kód

(môžete copy-paste do modu)

stock fillArray(array[], value = 0, size = sizeof(array)) {
  new cip;    
    
  size *= 4; 
  cip = get_code_relative_address();    
    
  #emit load.s.alt cip
  #emit lctrl 6
  #emit add
  #emit add.c 56
  #emit stor.s.pri cip
  #emit load.s.alt size
  #emit sref.s.alt cip        
         
  #emit load.s.alt array
  #emit load.s.pri value
  #emit fill 0
}

stock get_code_relative_address() {
  new dat, cod;   
  
  #emit lctrl 1 
  #emit neg   
  #emit add.c 12
  #emit stor.s.pri cod
  #emit lref.s.pri cod
  #emit stor.s.pri cod    
    
  #emit lctrl 1
  #emit neg  
  #emit add.c 16 
  #emit stor.s.pri dat
  #emit lref.s.pri dat
  #emit stor.s.pri dat    
    
  return cod - dat;    
}


Resp., aktuálna verzia (aj s pár vysvetľujúcimi komentmi) tu.

Ó, Majstre! Uč ma!

Krátke vysvetlenie pre tých, čo vedia čo znamená slovo "assembler", ale nevedia čítať emit.

Spoiler

Kód je založený na inštrukcii fill

#emit fill number

ktorá má tri parametre:
Pri - (primarny pawn register) -pointer, kde začať fillovať
Alt - (alternate pawn register) - hodnota, ktorou naplniť všetky bunky
number - počet bajtov, ktoré naplniť (musí byť násobok buniek..), musí to byť konštantný integer -> znemožňuje prácu s poliami o rôznych veľkostiach

Kód fillArray() jednoducho len využíva inštrukciu fill a za behu pomocou CIP (Code instruction pointer), upraví code sekciu módu - parameter number inštrukcie fill nastaví na príslušnú velkosť arrayu a potom vykoná fill.

Ešte dodatok k rýchlosti algoritmu, pri speedteste som napísal "podivné" časové výsledky. Podľa mojich odhadov majú obidva algoritmy lineárnu zložitosť (O(n)), ale je tam nejaký overhead, tipujem pri inštrukcii lctrl, alebo fill, ktorý sa manifestuje hlavne pri menšom počte prvkov poľa, preto sa lineárnosť neukazuje pri menších poliach.

 


 

Edited by Tanga
podrobnejší speedtest
  • Paráda! (+1) 1
  • Líbí se mi to! (+1) 3
Link to comment
Share on other sites

Nechce se mi to testovat, ale je to napr rychlejsi nez toto?

 

new Pole[] = {1,2,3,4},pole[sizeof(Pole)];//"pole" je vytvoreno pouze jednou, jde tedy o to testovat jen ten druhy radek v cyklu

Pole = pole;

 

Edited by ATomas
Link to comment
Share on other sites

Vďaka za komenty, inak, v hlavnom príspevku som trochu detajlnejšie popísal speedtest.

před 11 hodinami, IllidanS4 said:

O instrukci FILL jsem neměl ani tušení, ale tohle je fascinující použití. Jenom by mě zajímalo, koho mohlo napadnout ji navrhnout tak, že velikost bude pevný parametr.

Teší ma pozitívny ohlas. :p
Čo sa týka pevného parametra, dôvod je ten že v pawn neexistujú polia s dynamickou veľkosťou a tiež inštrukcia fill sa generuje kompilerom len v jednom prípade, pri vytvorení poľa. V jedinom prípade teda kde sa fill použije je počet buniek (veľkosť poľa) známy.

 

před 10 hodinami, ATomas said:

Nechce se mi to testovat, ale je to napr rychlejsi nez toto?

 


new Pole[] = {1,2,3,4},pole[sizeof(Pole)];//"pole" je vytvoreno pouze jednou, jde tedy o to testovat jen ten druhy radek v cyklu

Pole = pole;

 

Pre teba som to teda otestoval, s rovnakým kódom ako vyššie (akurát pre "klasické nulovanie" som nahradil Pole = pole) je fillArray() 4x pomalší pre polia o veľkosť 100 - 100 000 prvkov. Pre milión prvkov už majú rovnakú rýchlosť a pre 10 miliónov je fillArray() 1.2krát rýchlejší.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...