Mnożenie liczb 64-bitowych i 128-bitowych w Pythonie i w C++

Question

Ostatnio interesuję się działaniem różnych generatorów liczb pseudolosowych. Podstawowym typem takiego generatora jest generator LCG:

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

Wszędzie czytam, że z uwagi na architekturę procesorów mnożenie liczb 128-bitowych jest wolne, nawet dwa razy wolniejsze niż 64-bitowych. Umiem programować trochę tylko w Pythonie i testuję sobie takich generator:

import time

x = 83345345

def LCG(x):
    x = (x * 254195286038525845401606965623589319477 + 128946049852079881334078718521384768725) & 340282366920938463463374607431768211455
    #x = (x * 16653299995733013301 + 9999278969724736725) & 18446744073709551615
    return x

start=time.time()

for i in range(20000000):

    x=LCG(x)

end=time.time()
a=end-start
print (a)

I nieważne, czy użyję 64-bitowych stałych, czy 128-bitowych, dostaję podobne czasy. Podejrzewam, że to przypadłość Pythona, bo wszyscy w publikacjach używają C i C++ i przy tak nisko poziomowych językach pewnie będzie to widoczne, że procesor wyraźnie gorzej radzi sobie z arytmetyką 128-bitową.

Testuję też taki mixer bitów:

import time

x = 83345345

def PCG(x):
    count1 = x >> 122
    x1 = (x ^ (x >> 64)) & 18446744073709551615
    low64 = (x1 >> count1) | (x1 << (64 - count1)) & 18446744073709551615
    x2 = (x >> 64) & 18446744073709551615
    count2 = low64 & 63
    high64 = (x2 >> count2) | (x2 << (64 - count2)) & 18446744073709551615
    x = (high64 << 64) | low64
    return x

def LCG(x):
    x = (x * 254195286038525845401606965623589319477 + 128946049852079881334078718521384768725) & 340282366920938463463374607431768211455
    return x

start=time.time()

for i in range(20000000):

    x=PCG(LCG(x))

end=time.time()
a=end-start
print (a)

Autorce wyszło, że, pomimo, że cały generator jest 128-bitowy (jego pełna nazwa to PCG XSL RR RR 128 (LCG):

https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf

Działa on dwa razy szybciej niż to:

import time

x = 83345345

def XSLRR(x):
    count = x >> 122
    x64 = (x ^ (x >> 64)) & 18446744073709551615
    x = (x64 >> count) | (x64 << (64 - count)) & 18446744073709551615
    return x

def LCG(x):
    x = (x * 254195286038525845401606965623589319477 + 128946049852079881334078718521384768725) & 340282366920938463463374607431768211455
    return x

start=time.time()

for i in range(20000000):

    x=XSLRR(LCG(x))

end=time.time()
a=end-start
print (a)

Bo wersja XSLRR ucina połowę bitów w tym mixerze. Ja widzę, że PCG produkuje tylko 40% więcej bitów w tym samym czasie. Czy powinienem założyć, że w C++ wersja PCG będzie jednak dwa razy szybsza?

Answer 1

Porównywanie czasu działania tak niskopoziomowych instrukcji w języku tak wysokiego poziomu jak Python, mija się trochę z celem. Po drodze występuje tak wiele warstw abstrakcji oraz operacji (w Pythonie), że wyniki będą niemiarodajne.

Jeśli chcesz zrobić to rzetelnie, obawiam się że jedynie zmiana na C/C++ lub nawet asm (to ostatnie IMHO nie będzie konieczne), da jakieś sensowne rezultaty.

Wprawdzie możesz szukać  implementacji określonych typów binarnych (np w numpy czy stosując bytes/bytesarray... ), ale chyba to sztuka dla sztuki.

Comments

Tak też myślałem. Pytanie, czy faktycznie przynajmniej to mnożenie liczb 64-bitowych i 128-bitowych ktoś może potwierdzić? Czy to są aż tak duże różnice?