iVSwap

[DJ-RaZieL]

Θέλετε να κερδίσετε και το τελευταίο bit από την R.A.M?

 

Θέλετε να μειώσετε δραματικά τους κύκλους λειτουργίας της C.P.U?

 

Είστε προγραμματιστές?

 

Ε, τότε δοκιμάστε το iVSwap (still a beta though...):

 

http://sourceforge.net/projects/ivswap/

 

και φυσικά και το απαραίτητο documentation παρέα:

 

http://www.abaxb2b.com/qtgeo/iVSwap_Documentation.pdf

 

:mrgreen:

[GCMH]

Εξαιρετικό! Μόνο που το εγχειρίδιο σου είναι λίγο μεγάλο...

 

Να το εμπλουτίσεις το πρότζεκτ...

[dop]

Δεν δουλεύει. Δες το παρακάτω:

>
#include <stdio.h>

void bad_swap(int a, int  {
 printf("%s: values were a=%d, b=%d\n", __func__, a, ;
 a = a^b;
 b = b^a;
 a = a^b;
 printf("%s: values are  a=%d, b=%d\n", __func__, a, ;
}

void good_swap(int *a, int * {
 printf("%s: values were a=%d, b=%d\n", __func__, *a, *;
 *a = *a^*b;
 *b = *b^*a;
 *a = *a^*b;
 printf("%s: values are  a=%d, b=%d\n", __func__, *a, *;
}

int main(void) {
 int a = 42;
 int b = 69;
 
 printf("Values before bad_swap()  a=%d, b=%d\n", a, ;
 bad_swap(a, ;
 printf("Values after bad_swap()   a=%d, b=%d\n\n", a, ;

 printf("Values before good_swap() a=%d, b=%d\n", a, ;
 good_swap(&a, &;
 printf("Values after good_swap()  a=%d, b=%d\n", a, ;

 return 0;
}

 

Εσύ υλοποιείς την bad_swap(), ενώ θα έπρεπε να κάνεις την good_swap(). Και ειλικρινά, δεν πιστεύω κατά πόσο χρειάζεται μια βιβλιοθήκη για κάτι τόσο απλό και σύνηθες.

 

Αν το έκανες έτσι ώστε να μπορεί να χειρίζεται τεράστιες user-defined δομές τότε το ξανασυζητάμε. Σίγουρα πάντως για project στο sourceforge δεν είναι.

[DJ-RaZieL]

Να πάρουμε λίγο τα πράγματα με την σειρά τους...

 

Το project δέν θα μπορούσε να μπεί στο sf.net εάν η επιτροπή δεν πίστευε ότι υπάρχει μια αρκετά προφανής χρήση!

Κάθε project περνάει πριν πάρει κάποιος την άδεια, από επιτροπή αξιολόγησης.

Είχα και projects που δέν πέρασαν ποτέ!

Άρα θεωρώ ότι για να πείρα την άδεια με εμπιστεύονται.

Οπότε τί μένει?

Να αποδείξω ότι αυτό που κάνω θα είναι όντως κάπου χρήσιμο.

Εάν διαβάσεις το documentation σίγουρα θα πάρεις μία ιδέα.

Επίσης εφαρμογή ίσως να μπορεί να έχει και σε optimizing για games και τα σχετικά...

Θα προσπαθήσω να αναπτύξω το documentation όταν φυσικά έχω τελειοποιήσει το project μου.

 

Πάμε τώρα στο παράδειγμά σου.

Καταρχάς εγώ όπως ήδη γνωρίζεις τα κάνω compile με τον gcc.

Οπότε με αυτόν έχω μέτρο σύγκρισης.

Επίσης δέν σου ζήτησε κανείς να ξαναγράψεις την βιβλιοθήκη.

Δές καλά τα sources μου και εκείνες τις μικρολεπτομέρειες που έχω πειράξει και κάνε compile οποιοδήποτε παραδειγμά σου με την βιβλιοθήκη μου.

Όχι με δική σου γραφή.

Δηλαδή με λίγα λόγια κάνε εισαγωγή την ivswap.h και μετά μεταγώτισε μαζί με το object file της για να την κάνεις χρήση.

Έτσι θα δείς ότι δουλεύει....

[dop]

Δεν ξαναέγραψα τίποτα: είναι ένα κομματάκι κώδικα από άσκηση που είχα κάνει στο πρώτο έτος.

 

Και γω με τον gcc κάνω compile, εσύ απλώς ξεχνάς ότι τυπώνεις μέσα στην συνάρτηση τα δεδομένα και για αυτό φαίνεται ότι δουλεύει. Αν τυπώσεις τις τιμές ακριβώς μετά την κλήση της ivswap() θα δεις ότι δεν έχει αλλάξει τίποτα.

 

Στην C++ θα μπορούσες να το κάνεις αν τα περνούσες σαν references.

 

Για του λόγου το αληθές, δοκίμασε το παρακάτω (ναι, είναι το δικό σου αρχείο λίγο αλλαγμένο):

>
#include <stdio.h>
#include "headers/ivswap32.h"

int main(void)
{
   int x,y;
   
   printf("Please insert two integer values [Val1,Val2]: ");
   scanf("%i,%i",&x,&y);
   printf("\n");
   printf("*** Current Values ***\n");
   printf("Value1: %i, Value2: %i\n\n",x,y);
   
   iVSwap(x,y);
   printf("Value1: %i, Value2: %i\n\n",x,y);
   
   return 0;
}

 

Είπαμε: αν επιτρέψεις στο εαυτό σου να μην είσαι τόσο περήφανος, τότε μόνον μπορείς να προχωρήσεις παραπέρα. Μάθαινε από τα λάθη σου.

 

ΥΓ τι ακριβώς μικρολεπτομέρειες έχεις πειράξει;

[DJ-RaZieL]

Άκυρο ....

Έχω κάνει κάτι αλλαγές που 8α τις δείς στο επόμενο version απλά νόμιζα ότι ήταν σε αυτό.

Ξέχνατο...

Ναι αυτός είναι ο κώδικας.

 

Περήφανος είμαι γιατί έτσι γεννήθηκα.

Κακό, ξεκακό that's me!

 

Πάμε παρακάτω...

 

Χμμμ...ναι την πάτησα...Θέλει χρήση δεικτών!

 

ΦΤΟΥ!

 

ΟΚ θα το φτιάξω!

[alkisg]

Εχμ... εκτός από το θέμα με τους pointers, μπορείς να κάνεις και μερικά benchmarks για να δείξεις ότι η υλοποίησή σου είναι πιο γρήγορη από ένα κλασσικό

int temp = a;

a = b;

b = temp;

 

Γιατί το παραπάνω (χωρίς compiler optimizations) θέλει 6 προσπελάσεις στη μνήμη, ενώ το

Val1=Val1^Val2;

Val2=Val1^Val2;

Val1=Val1^Val2;

θέλει 9 προσπελάσεις.

 

Επίσης, αν ψάξεις για mem swap θα βρεις ένα σωρό συναρτήσεις σε assembly που δε χρειάζονται παραπάνω RAM για να κάνουν το swap, και επειδή χρησιμοποιούν registers για την ενδιάμεση αποθήκευση είναι όσο γρήγορες γίνεται... Επίσης δουλεύουν και για οσαδήποτε bytes, όχι μόνο για ints.

 

Υ.Γ. αν θες θέσε το σαν challenge στο http://fastcode.sourceforge.net/

[alkisg]

Υ.Γ. #2 δες και το

http://www.azillionmonkeys.com/qed/case3.html

για συγκρίσεις διαφόρων swap.

[DJ-RaZieL]

Χρησιμοποιώ όλα τα δυνατά optimiazations.

 

Το θέμα είναι ότι οι 9 προσπελάσεις όπως λές στο επόμενο version δεν θα είναι παρά 3.

Απλά περίμενε.

 

Υπάρχει μια πάρα πολύ απλή λύση σε αυτό.

Αλλά πρώτα ήθελα να σιγουρευτώ σε άλλα επίπεδα.

 

Σωστός πάντως, θα βρώ και ένα τρόπο να κάνω Benchamarks

[alkisg]

Θες να διαβάσεις 2 θέσεις μνήμης και να γράψεις 2.

Το ελάχιστο δυνατό είναι 4 προσπελάσεις, όχι 3!

[DJ-RaZieL]

Για την ακρίβεια θα έχεις ΚΑΜΙΑ προσπέλαση για τον ακέραιο.

Θα δείς και για τους άλλους τύπους τί θέλω να πετύχω.

 

Απλά υπομονή.

 

Άκουσον μέν, πάταξον δέ.

 

[dop]

Αν έχουμε το απλό προγραμματάκι

>
void normal_swap(int *a, int * {
 int t = *b;
 *b = *a;
 *a = t;;
}

void good_swap(int *a, int * {
 *a = *a^*b;
 *b = *b^*a;
 *a = *a^*b;
}

int main(void) {
 int a = 42;
 int b = 69;
 normal_swap(&a, &;
 good_swap(&a, &;
 return 0;
}

η x86 assembly που παράγεται είναι

>
.globl normal_swap
       .type   normal_swap, @function
normal_swap:
       pushl   %ebp
       movl    %esp, %ebp
       movl    12(%ebp), %edx
       pushl   %ebx
       movl    8(%ebp), %ebx
       movl    (%edx), %ecx
       movl    (%ebx), %eax
       movl    %eax, (%edx)
       movl    %ecx, (%ebx)
       popl    %ebx
       popl    %ebp
       ret
       .size   normal_swap, .-normal_swap
       .p2align 4,,15
.globl good_swap
       .type   good_swap, @function
good_swap:
       pushl   %ebp
       movl    %esp, %ebp
       movl    12(%ebp), %edx
       movl    8(%ebp), %ecx
       movl    (%edx), %eax
       xorl    (%ecx), %eax
       movl    %eax, (%ecx)
       xorl    (%edx), %eax
       movl    %eax, (%edx)
       xorl    %eax, (%ecx)
       popl    %ebp
       ret
       .size   good_swap, .-good_swap
       .p2align 4,,15

 

Από όσο βλέπεις, έχουν ακριβώς τον ίδιο αριθμό instructions (και δεν νομίζω ότι η εντολή για xor να είναι μικρότερη από την movl). Ουσιαστικά, αντικαθιστάς κάποιες move (που δουλεύουν σε registers) με xor (που και αυτές δουλεύουν σε registers).

 

Αν και εξαρτάται το πως είναι υλοποιημένες η xor και η move από τον εκάστοτε κατασκευαστή, είναι ασφαλές να υποθέσω ότι το datapath της move είναι σχετικά μικρότερο από αυτό της xor (που χρειάζεται επιπλέον κύκλο για να παράγει αποτέλεσμα).

 

Έκανα μερικά benchmarks και τα αποτελέσμα είναι τραγικά για την xor. Το παρακάτω προγραμματάκι

>
#include <stdlib.h>

#define NORMAL

void normal_swap(int *a, int * {
 int t = *b;
 *b = *a;
 *a = t;;
}

void xor_swap(int *a, int * {
 *a = *a^*b;
 *b = *b^*a;
 *a = *a^*b;
}

int main(void) {
 size_t i;
 size_t N = 10;
 int a[] = {1,2,3,4,5,6,7,8,9,10};
 
 for (i=0; i<2000000000; ++i)
 {
   size_t j, e = N-1;
   for (j=0; j<e; ++j)
   {
#ifdef NORMAL
#warning Using normal swap
     normal_swap(&a[j], &a[j+1]);
#else
#warning Using normal swap
     xor_swap(&a[j], &a[j+1]);
#endif
   }
 }

 return 0;
}

δίνει 28s για την κλασική swap με pointers και ενδιάμεση προσωρινή τιμή, ενώ για την xor swap δίνει 49s - δηλαδή σχεδόν 2 φορές πιο αργή.

[GCMH]

Να συμφωνήσω με τον alkisg και dop... :oops:

 

Το πρόγραμμα είναι γραμμένο σε Delphi Pascal 7.0 και τα επίμαχα σημεία απ' ευθείας σε γλώσσα μηχανής (assembly).

 

>
program Project1;

{$APPTYPE CONSOLE}

uses
   MMSystem, SysUtils;

var
   Var1, Var2, i, p1, p2: LongWord;

procedure SwapNormal(x1,x2: PLongWord);
asm
   PUSH EBX
   MOV EAX,x1
   MOV EBX,x2

   MOV ECX,[EAX]
   MOV EDX,[EBX]

   MOV [EBX],ECX
   MOV [EAX],EDX

   POP EBX
end;

procedure SwapXOR(x1,x2: PLongWord);
asm
   MOV EAX,x1
   MOV EDX,x2

   MOV ECX,[EDX]

   XOR [EAX],ECX
   XOR ECX,[EAX]
   XOR [EAX],ECX

   MOV [EDX],ECX
end;

begin
   Var1:=$12345678;
   Var2:=$FEDCBA98;

   p1:=timeGetTime;
   for i:=1 to 100000000 do SwapNormal(@Var1,@Var2);
   p2:=timeGetTime;
   Writeln('Normal Swap: '+IntToStr(p2-p1));

   p1:=timeGetTime;
   for i:=1 to 100000000 do SwapXOR(@Var1,@Var2);
   p2:=timeGetTime;
   Writeln('XOR Swap: '+IntToStr(p2-p1));
end.

 

Σε Pentium [email protected] στην κονσόλα, για 100000000 επαναλήψεις παίρνει 871 msec για την SwapNormal και 1400 msec για την SwapXOR...Παρόλο που η λύση με το XOR φαίνεται να έχει μία εντολή λιγότερη. Και στις δύο πάντως χρησιμοποιούνται 14 byte σε εντολές.

 

Αυτά!

[DJ-RaZieL]

Χμμ... με βάλατε σε σκέψεις τώρα γιατί δεν είχα κοιτάξει κάν τον ASSEMBLED κώδικα και συμφωνώ πλήρως με αυτά που λέτε!

 

Το θέμα είναι τι θα γινόταν από θέμα ταχύτητας και μνήμης εάν ήταν όλοι οι τύποι μας register int ...

 

Πιστεύω ότι τότε έχουμε κέρδος μιας και δεν θα χρησιμοποιηθεί καθόλου η R.A.M και επίσης λόγω του ότι είναι διαδικασία bit θα έχουμε ευθύ αποτέλεσμα στην A.L.U.

 

Δεν ξέρω εάν έγινα κατανοητός...

 

C Ya!

[dop]

Δε θα γινόταν τίποτα: όλοι οι σύγχρονοι compilers αγνοούν την λέξη κλειδί register - από μόνοι τους κάνουν πολύ καλύτερο register allocation.