A gdyby użyć tego:

https://godbolt.org

Jak wrzucam sobie tam kod:

#include <cstdint>

inline uint64_t rotl(const uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}


uint64_t s[2] = {1,2};

uint64_t next(void) {
const uint64_t s0 = s[0];
uint64_t s1 = s[1];
const uint64_t result = s0 + s1;

s1 ^= s0;
s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
s[1] = rotl(s1, 37); // c

return result;
}

To ma sens analiza tego:

movq s(%rip), %rax
movq s+8(%rip), %rsi
movq %rax, %rdx
movq %rax, %rcx
addq %rsi, %rax
xorq %rsi, %rdx
rolq $24, %rcx
movq %rdx, %rdi
xorq %rdx, %rcx
rorq $27, %rdx
salq $16, %rdi
movq %rdx, s+8(%rip)
xorq %rdi, %rcx
movq %rcx, s(%rip)
ret

Jak rozumiem wszystko to są standardowe nazwy instrukcji? Więc wystarczy zsumować ich
cykle? Mogę założyć, że movq to 2 cykle, xorq to 1 cykl, salq to 1 cykl?

do góry

Swoją drogą jak biorę wartości z tych tabel:

https://www.agner.org/optimize/instruction_tables.pd
f

Mam brać pod uwagę sumę Ops i Latency?

do góry

On Monday, May 15, 2023 at 6:02:33 PM UTC+2, o...@g...com wrote:
> Swoją drogą jak biorę wartości z tych tabel:
>
> https://www.agner.org/optimize/instruction_tables.pd
f
>
> Mam brać pod uwagę sumę Ops i Latency?

Pytałeś już o to dwa lata temu. I nie, ops i latency to dwie **kompletnie** różne
rzeczy - przeczytaj dokładnie opisy kolumn.

Można teoretycznie oszacować throughput małego kawałka kodu (np. na
https://uica.uops.info), można nawet oszacować dolne ograniczenie latency ze ścieżki
krytycznej. Między Tobą a ISA jest kompilator, runtime, system operacyjny i wg mnie
warto mierzyć czas wykonania dla dużej liczby iteracji, eksprymentując z ustawieniami
kompilatora. Od wielu lat używam tego zestawu makr do mierzenia cykli:
https://github.com/WojciechMula/toys/blob/master/000
helpers/benchmark.h. Możesz zobaczyć w tym repo jak z tego korzystać, np. tutaj:
https://github.com/WojciechMula/toys/blob/master/avx
512-varuint/benchmark.cpp#L41

w.

do góry

poniedziałek, 22 maja 2023 o 19:30:31 UTC+2 Wojciech Muła napisał(a):
> On Monday, May 15, 2023 at 6:02:33 PM UTC+2, o...@g...com wrote:
> > Swoją drogą jak biorę wartości z tych tabel:
> >
> > https://www.agner.org/optimize/instruction_tables.pd
f
> >
> > Mam brać pod uwagę sumę Ops i Latency?
> Pytałeś już o to dwa lata temu. I nie, ops i latency to dwie **kompletnie** różne
rzeczy - przeczytaj dokładnie opisy kolumn.

Fakt, wtedy chodziło mi tylko o rzędy wielkości, bo nie miałem pojęcia ile to w ogóle
zajmuje. Dzisiaj porównuję mój kod z różnymi wersjami xoroshiro:

https://prng.di.unimi.it/xoshiro256plusplus.c

> Można teoretycznie oszacować throughput małego kawałka kodu (np. na
https://uica.uops.info), można nawet oszacować dolne ograniczenie latency ze ścieżki
krytycznej.

Nie wiem, czy czegoś podobnego nie robi Godbolt:

https://godbolt.org/z/7rxMdKerz

[1] [2] [3] [4] [5] [6] Instructions:
1 5 0.50 * movq _ZL1s.0(%rip), %rcx
1 5 0.50 * movq _ZL1s.3(%rip), %rdx
1 1 0.50 leaq (%rdx,%rcx), %rax
1 1 0.50 rolq $23, %rax
1 1 0.25 addq %rcx, %rax
1 5 0.50 * movq _ZL1s.1(%rip), %rsi
1 1 0.25 movq %rsi, %rdi
1 1 0.50 shlq $17, %rdi
1 5 0.50 * movq _ZL1s.2(%rip), %r8
1 1 0.25 xorq %rcx, %r8
1 1 0.25 xorq %rsi, %rdx
1 1 0.25 xorq %r8, %rsi
1 1 1.00 * movq %rsi, _ZL1s.1(%rip)
1 1 0.25 xorq %rdx, %rcx
1 1 1.00 * movq %rcx, _ZL1s.0(%rip)
1 1 0.25 xorq %rdi, %r8
1 1 1.00 * movq %r8, _ZL1s.2(%rip)
1 1 0.50 rolq $45, %rdx
1 1 1.00 * movq %rdx, _ZL1s.3(%rip)
3 7 1.00 U retq

> Między Tobą a ISA jest kompilator, runtime, system operacyjny i wg mnie warto
mierzyć czas wykonania dla dużej liczby iteracji, eksprymentując z ustawieniami
kompilatora.

Tak to obecnie mierzę. Kompiluję z takimi flagami g++ -o test benchmarks_PRNGs.cpp
-Wall -Wextra -O3 -fno-unroll-loops. No i coś tam mi wychodzi. Wyniki różnią się od
tych z Godbolt. Wydaje mi się, że ze względu na mnożenie w moich generatorze niewiele
tutaj można zrobić (przyspieszyć). Tym bardziej, że, jeśli porównuję wyniki xoroshiro
i PCG-DXSM:

static __uint128_t LCG_state = 123456789;

uint64_t next_PCG(void)
{
LCG_state = LCG_state * 0xda942042e4dd58b5 + 1;
uint64_t hi = LCG_state >> 64;
uint64_t lo = LCG_state;

lo |= 1;
hi ^= hi >> 32;
hi *= 0xda942042e4dd58b5ULL;
hi ^= hi >> 48;
hi *= lo;
return hi;
}

To dostaję podobne wyniki do prof. Vigny https://prng.di.unimi.it. PCG jest jakieś
1,5 razy wolniejszy. Zastanawiam się jeszcze tylko, czy mnożenie można jakoś
zoptymalizować. Twórczyni PCG Melissa O'Neil pisała gdzieś, że w jej pomiarach PCG
jest tylko nieznacznie wolniejszy od xoroshiro. Tutaj:

https://github.com/numpy/numpy/pull/13163#issuecomme
nt-496030958

wyszło komuś z Numpy, że na Linuxie PCG jest tylko nieznacznie wolniejszy od
xoroshiro, a na Windowsie różnica jest ponad dwukrotna. Prędkość zależna od
platformy?

> Od wielu lat używam tego zestawu makr do mierzenia cykli:
https://github.com/WojciechMula/toys/blob/master/000
helpers/benchmark.h. Możesz zobaczyć w tym repo jak z tego korzystać, np. tutaj:
https://github.com/WojciechMula/toys/blob/master/avx
512-varuint/benchmark.cpp#L41

Dzięki, ale nie wiem jak tego użyć.

do góry

Tutaj Vignie wyszły podobne wyniki przy użyciu Intel(R) Architecture Code Analyzer,
3.50 cykla dla xoroshiro128++ i 5.53 cykla dla PCG64DXSM:

https://pcg.di.unimi.it/pcg.php

Także, jeśli uzyskuję podobne wyniki, chyba robię pomiary w miarę reprezentatywnie. I
chyba niewiele można tu przyspieszyć. Nie rozumiem tylko dlaczego ludziom z Numpy
wyszły wyrównane wyniki i Melissie O'Neil też takie ponoć wychodzą.

do góry