C Rotieren in der ASCII-Tabelle

blöderidiot · 22. Januar 2017

nullPtr schrieb:
Ich möchte der Vollständigkeit halber noch hinzufügen, daß man auch eine Version bauen kann, die ganz ohne langsame Division oder Speicherzugriff auskommt:

OK! Man müßte auch eine entsprechende Version ohne if machen können, mit bedingter Ganzzahlmultiplikation.

Das sollte meinen Vermutungen nach ...

Können wir ja mal testen:

Code:

use strict;
use Inline 'C';
use Benchmark qw(:all);

my $c = 0;
my $results = timethese(-10,     {
      lookup => sub { rot_lut(++$c%10+'0') },
      modulo => sub { rot_mod(++$c%10+'0') },
      ifcond => sub { rot_if (++$c%10+'0') },
      mulcond=> sub { rot_mul(++$c%10+'0') },
   });
cmpthese( $results );
__END__
__C__
 int rot_lut(int ch) {
   static int lut[] = {5,6,7,8,9,0,1,2,3,4};
   return lut[ch - '0'] + '0';
 }

 int rot_mod(int ch) {
    return  (ch + 5 - '0') % 10 + '0';
 }

 int rot_if(int ch)  {
    return ch > '4' ? ch - 5 : ch + 5;
 }

 int rot_mul(int ch) {
    return ch + 5*(((ch<='4')<<1)-1);
 }

Im Prinzip ist im Mittel 'bedingte Ganzzahlmultiplikation' knapp am schnellsten vor Deiner if-Version, gefolgt von der Lookup-Tabelle mit Modulo als Schlusslicht. Hier zwei Durchläufe:

ifcond: 10 wallclock secs (10.55 usr + 0.00 sys = 10.55 CPU) @ 9487330.71/s (n=100091339)
lookup: 11 wallclock secs (10.49 usr + 0.00 sys = 10.49 CPU) @ 9451580.74/s (n=99147082)
modulo: 10 wallclock secs (10.49 usr + 0.00 sys = 10.49 CPU) @ 9363248.14/s (n=98220473)
mulcond: 11 wallclock secs (10.57 usr + 0.00 sys = 10.57 CPU) @ 9560431.03/s (n=101053756)
Rate modulo lookup ifcond mulcond
modulo 9363248/s -- -1% -1% -2%
lookup 9451581/s 1% -- -0% -1%
ifcond 9487331/s 1% 0% -- -1%
mulcond 9560431/s 2% 1% 1% --

und

Benchmark: running ifcond, lookup, modulo, mulcond for at least 10 CPU seconds...
ifcond: 11 wallclock secs (10.52 usr + 0.00 sys = 10.52 CPU) @ 9514385.84/s (n=100091339)
lookup: 10 wallclock secs (10.53 usr + 0.00 sys = 10.53 CPU) @ 9505350.33/s (n=100091339)
modulo: 11 wallclock secs (10.50 usr + 0.00 sys = 10.50 CPU) @ 9354330.76/s (n=98220473)
mulcond: 11 wallclock secs (10.57 usr + 0.00 sys = 10.57 CPU) @ 9560431.03/s (n=101053756)
Rate modulo lookup ifcond mulcond
modulo 9354331/s -- -2% -2% -2%
lookup 9505350/s 2% -- -0% -1%
ifcond 9514386/s 2% 0% -- -0%
mulcond 9560431/s 2% 1% 0% --

Aber auf einem anderen Rechner (hier i7-3770K) und einem anderen C-Compiler (hier Linux gcc 4.8) kann es schon wieder anders aussehen.

BAGZZlash · 22. Januar 2017

Naja, bedingte Ganzzahlmultiplikation enthält im Kompilat genauso auch ein "if" (also cmp mit je o.ä.).

Das Testsetup ist aber auch etwas krude. Die Unterschiede dürften nicht statistisch signifikant sein. Dennoch Hut ab, dass Du das gemacht hast!

blöderidiot · 22. Januar 2017

BAGZZlash schrieb:
Naja, bedingte Ganzzahlmultiplikation enthält im Kompilat genauso auch ein "if" (also cmp mit je o.ä.).

Weder noch. Mein gcc in -O3-Mode schafft beides ohne if. Er verwendet die x86-Instruktion CMOVE[L|G], also "conditional move" nach dem vorhergehenden Vergleich "ch < 4" bzw. "ch >= 4".

Code:

 int rot_if(int ch) {
    return ch > '4' ? ch - 5 : ch + 5;
 }

wird zu:

Code:

rot_if:
.LFB14:
    .loc 1 27 0
    .cfi_startproc
.LVL11:
    .loc 1 28 0
    leal    -5(%rdi), %eax
    leal    5(%rdi), %edx
    cmpl    $53, %edi
    cmovl    %edx, %eax
    .loc 1 29 0
    ret

und

Code:

 int rot_condmult(int ch) {
    return ch + 5 * (((ch <= '4') << 1) - 1);
 }

wird zu

Code:

rot_condmult:
.LFB15:
    .loc 1 31 0
    .cfi_startproc
.LVL12:
    .loc 1 32 0
    cmpl    $52, %edi
    movl    $-5, %edx
    movl    $5, %eax
    cmovg    %edx, %eax
    addl    %edi, %eax
    .loc 1 33 0
    ret

Die direkten 'movl'-Befehle zum Laden der '5' bei 'rot_condmult' sind auf der Maschine wohl schneller als die indirekten 'leal'-Befehle von 'rot_if'.Daher die geringen, aber immer vorhandenen Unterschiede.

BAGZZlash · 22. Januar 2017

blöderidiot schrieb:
Weder noch.

Sowohl, als auch. In allen Varianten gibt's 'ne cmp-Spielart. Dass die bedingten mov-Befehle dann die Verzweigung mit eingebaut haben, ändert nichts am ITTT-Prinzip. Dass die moderneren Befehle jedoch ein paar Takzyklen sparen mögen, streite ich nicht ab, insofern: Alles gut.

nullPtr · 22. Januar 2017

@blöderidiot:
Mit welchen Flags kompiliert denn das Perl-Inline-C-Modul den C-Code?

blöderidiot · 22. Januar 2017

nullPtr schrieb:
@blöderidiot:
Mit welchen Flags kompiliert denn das Perl-Inline-C-Modul den C-Code?

Soweit ich sehen kann (mit Config => BUILD_NOISY => 1) nimmt er -O2. Ich habe es zwar geschafft, -O3 unterzujubeln (CCFLAGS => ($Config{ccflags}." -O3"), aber nicht -O2 wegzubekommen. Nun stehen beide (erst -O3, dann -O2) in der Kommandozeile des C-Compilers. Hmmmm ....

Suche

C Rotieren in der ASCII-Tabelle

blöderidiot

Captain

BAGZZlash

Lt. Junior Grade

blöderidiot

Captain

BAGZZlash

Lt. Junior Grade

nullPtr

Lieutenant

blöderidiot

Captain

Ähnliche Themen