Przyśpieszenie pętli przy dostepie do słownika w każdej iteracji

0

Ma ktoś jakieś pomysły jak przyśpieszyć podany kod wkluczając następujące możliwości:

  1. list comprehension
  2. pre alokacja listy
  3. deque
  4. pisanie tego w innym języku - chodzi mi tutaj o 100% Pythona

Przy założeniach, że liczba elementów w słowniku jest dynamiczna (podawana przez użytkownika) wiec optymalizacja typu
a_list = data["a"] i potem odwoływanie się do a_list (żeby unikać dostępu przez słownik) również nie jest możliwa (chyba, że jest sposób, żeby to zrobić dynamicznie)

Kolejne założenie to, że dane są też dynamiczne, a "string" i 123 jest dla uproszczenia, w rzeczywistości to są różne dane

import time
start_time = time.perf_counter()

data = {
    "a": [],
    "b": [],
}
for i in range(10_000_000):
    data["a"].append("string")
    data["b"].append(123)

print("It took: ", time.perf_counter() - start_time)
3

W podanym przez Ciebie przykładzie zdaje się, że większość czasu powinnno zejść nie na dostęp do słownika, a na uruchomienie .append() - skąd zatem pomysł aby optymalizować akurat dostęp do słownika?

(tzn. moje przypuszczenie jest takie, że nawet gdyby dostęp do słownika zajmował 0 ns, nie wpłynęłoby to znacząco na ogólny czas działania Twojego programu, bo większość czasu spędza on na .append())

0

Co tu jest bottleneckiem to już nie ma znaczenia tak naprawdę. Bo chodzi mi po prostu o przyśpieszenie tego, a dostęp do słownika pozwala na przyśpieszenie tego o około 10-20%. Tutaj szukam każdej możliwej optymalizacji bo jest to core aplikacji i podobna pętla jest uruchamiana biliony razy.
Można nawet zrobić a_append = data["a"].append i to też przyśpiesza, problem mam taki, że te dane są dynamiczne, więc nie wiem ile zmiennych zrobić za wczasu

6

Co tu jest bottleneckiem to już nie ma znaczenia tak naprawdę.

No raczej ma znaczenie, bo trzeba ten bottleneck usunąć. A tak stawiasz zadanie "Przyspieszyć kody, który mam, ale nie pokażę go, pokaże coś innego co myślę, że jest takie samo".
Ciężko zgadywać jaki problem ten kod ma rozwiązywać.

W pythonie przerabiałem temat wczytywania małych danych (góra kilkaset mega) na różne sposoby:

  • Pandas, Numpy, Dask, ...
  • ładowanie bezpośrednio do bazy in memory (testowałem sqallite3, duckdb, monetdb, ... )
  • cythonizacja
  • wydzielenie funkcjonalności do biblioteki w C przykrytej pythonem

Generalnie python był zbyt wolny na moje potrzeby, a powodem bottlenecku była dynamiczna natura pythona i to w jaki sposób obsługuje typy danych, w szczególności sprawdzanie typów i konwersja danych zachodząca na styku pythona i warstw pośrednich (czy to konwersja do wywołania biblioteki C, czy wstawianie danych do bazy in-memory).

Chcesz pisać kod szybko -> python jest dobrym wyborem.
Chcesz żeby działało szybko -> python nie jest dobrym wyborem.

0

No dobrze, nie musisz o tym pisać bo to jest oczywiste. Wiem jak rozwiązuje się problemy z wydajnością i wszystko co mogłem już zrobiłem. To jest już ostateczny kod, do przyśpieszenia bo reszta już zoptymalizowana.

Python jest nie do wymiany z tego powodu, że te dane potem są wykorzystywane w Pythonie i ładowanie ich zajęło by więcej czasu niż ta pętla.

Zadałem konkretne pytanie o konkretny mały fragment kodu i nie potrzebuję oczywistości w stylu "gdzie jest bottleneck", "python nie jest szybki" itd. Owszem można to napisać komuś początkującemu ale nie komuś kto wyraźnie zaznaczył, które sposoby odpadają

0

Znalazłem jedną optymalizację o 10% (dla przypadku z tematu, dla realnych danych może się różnić):
Dzięki nie odwoływaniu się do methody "append" za pomocą data["a"].append() tylko data["a_append"]() zyskujemy czas. I o tego typu zabawy mi chodzi w temacie

import time
start_time = time.perf_counter()

data = {
    "a": [],
    "b": [],

}
data["a_append"] = data["a"].append
data["b_append"] = data["b"].append

for _ in range(10_000_000):
    data["a_append"]("string")
    data["b_append"](123)

print("It took: ", time.perf_counter() - start_time)
3
anonimowy napisał(a):

No dobrze, nie musisz o tym pisać bo to jest oczywiste. Wiem jak rozwiązuje się problemy z wydajnością i wszystko co mogłem już zrobiłem. To jest już ostateczny kod, do przyśpieszenia bo reszta już zoptymalizowana.

Dzielę się tylko swoimi doświadczeniami. Skoro wyczerpałeś możliwości na poziomie kodu, to pozostaje zmiana architektury, wszak rozwiązania nie kończą się na kodzie.
Nie obraź się, ale używanie time.perf_counter() pokazuje, że skupiasz się na czasie wykonania bloku kodu, co jest (moim zdaniem) bardzo słabym podejściem, przy takich mikro optymalizacjach.

Skoro ten problem z wydajnością występuje, to naturlane pytanie: O ile % chciałbyś poprawić (jakie są kryteria "sukcesu przyspieszania pętli")?

Python jest nie do wymiany z tego powodu, że te dane potem są wykorzystywane w Pythonie i ładowanie ich zajęło by więcej czasu niż ta pętla.

No ale co stoi na przeszkodzie by wydzielić tę krytyczną funkcjonalność do osobnego komponentu, z którym mógłbyś interfejsować z poziomu pythona?

Zadałem konkretne pytanie o konkretny mały fragment kodu i nie potrzebuję oczywistości w stylu "gdzie jest bottleneck", "python nie jest szybki" itd. Owszem można to napisać komuś początkującemu ale nie komuś kto wyraźnie zaznaczył, które sposoby odpadają

Jeśli jest to realny problem wydajnościowy, to odrzucanie x10 w innej technologii na rzecz +10% w pythonie(piję to do zachwytów wydajnościowych przy przejściu z 3.10 na 3.11) jest mało racjonalne z perspektywy technologii. Można też spróbować odpalić na Graalu: https://www.graalvm.org/22.2/reference-manual/python i zobaczyć czy będzie jakiś "wystarczający" uzysk.

Chętnie bym się dowiedział ile tak naprawdę można uzyskać z tego Graala przy realnej aplikacji w pythonie :)

0
yarel napisał(a):
anonimowy napisał(a):

No ale co stoi na przeszkodzie by wydzielić tę krytyczną funkcjonalność do osobnego komponentu, z którym mógłbyś interfejsować z poziomu pythona?

To, że musiałbyś całość przenieść do innego języka a całość jest większa niż ta pętla. Jeśli natomiast chciałbyś przenieść samą pętlę to narzut na przekazanie danych jest większy niż oszczędność czasu na pętli.

To jest bardziej zadanie na mikro optymalizacje niż na zmianę architektury/języka itd.

2

Włozenie kodu do funkcji przyspieszyło go jeszcze o około 5 %

import time

start_time = time.perf_counter()

data = {
    "a": [],
    "b": [],
}

def doit(list):
    data["a_append"] = data["a"].append
    data["b_append"] = data["b"].append
    for i in list:
        data["a_append"]("string")
        data["b_append"](123)

list = range(10_000_000)

doit(list)

print("It took: ", time.perf_counter() - start_time)

0

Można jeszcze trochę przyspieszyć stosując pre alokację tablic i jest jeszcze jax, który pozwala na jit kompilację, tyle że pierwsze uruchomienie jest znacznie wolniejsze, chyba że jest z cachowany kod już.

I ta optymalizacja często jest w C++ wykorzystywana, bo tam też ciągłe realokowanie nowego bufora niepotrzebnie inicjuje konstruktory i destruktory, przerzuca pamięci, bo w poprzednim buforze zabrakło miejsca.

import time
start_time = time.perf_counter()

data = {
    "a": [None]*10_000_000,
    "b": [None]*10_000_000,
}

def doit(list):
    for i in list:
        data["a"][i] = "string"
        data["b"][i] = 123

list = range(10_000_000)
doit(list)

print("It took: ", time.perf_counter() - start_time)

/ed
Ewentualnie można spróbować wygenerować nową tablicę i ją połączyć z aktualną.

def concatenate(l):
    data["a"] += ["string" for _ in l]
    data["b"] += [123 for _ in l]

l = range(10_000_000)

concatenate(l)
0
anonimowy napisał(a):

Ma ktoś jakieś pomysły jak przyśpieszyć podany kod wkluczając następujące możliwości:

  1. list comprehension
  2. pre alokacja listy
  3. deque
  4. pisanie tego w innym języku - chodzi mi tutaj o 100% Pythona

Tak z ciekawości - dlaczego chcesz to wykluczyć ?

0

Użyj https://numba.pydata.org/ mało inwazyjne a przyspiesza kod

1

Z ciekawości zerknałem co oferuje Graal dla pythona i tak na oko x5 szybciej, bez żadnej modyfikacji kodu.

screenshot-20230522150201.png

1

Tak z ciekawości pobawiłem się jeszcze w zagadnienia optymalizacyjne i wyszło mi cos takiego. Nie wiem czy to pomoze w przyspieszeniu realnego kodu i da sie je zastosować, ale ten przykładowy jest troche przyspieszony. Wyniki sa dość ciekawe podam je ponizej. Zapisywalem kazdy kod w odzdzielnym pliku odpalałem wszystkie za pomoca hyperfine. (Ostrzegam nazwy plików sa przypadkowe ^^)
benchmark.png

A o to kody poszczególnych plików zeby mozna bylo sobie samemu porównać

#file.py
def task():
    data = {
        "a": [],
        "b": [],
    }
    a_append = data["a"].append
    b_append = data["b"].append
    li = range(10_000_000)

    for _ in li:
        s1 = "text"
        s2 = 123
        a_append(s1)
        b_append(s2)

    return data


p=task()

#cext.py
def doit(lst, data):
    s1 = "string"
    s2 = 123

    data["a_append"] = data["a"].append
    data["b_append"] = data["b"].append
    for i in lst:
        data["a_append"](s1)
        data["b_append"](s2)
    return data


def task():
    data = {
        "a": [],
        "b": [],
    }
    li = range(10_000_000)

    return doit(li, data)


task()

#panda.py
data = {
    "a": [],
    "b": [],
}

def doit(list):
    data["a_append"] = data["a"].append
    data["b_append"] = data["b"].append
    for i in list:
        data["a_append"]("string")
        data["b_append"](123)

list = range(10_000_000)

doit(list)
#run.py
def task():
    data = {
        "a": [],
        "b": [],
    }
    li = range(10_000_000)

    a_list = data["a"]
    b_list = data["b"]
    a_append = a_list.append
    b_append = b_list.append

    for _ in li:
        s1 = "string"
        s2 = 123
        a_append(s1)
        b_append(s2)

    return data

task()

Jesli klucze i wartosci w słowniku byly by dymiczne to byloby takie cos znowu:

#wtime.py
def task():
    data = {
        "a": [],
        "b": [],
        # Additional dynamic keys
        "c": [],
        "d": [],
    }
    li = range(10_000_000)

    keys = ["a", "b", "c", "d"]

    for key in keys:
        lst = data[key]
        append_method = lst.append

        for _ in li:
            value = "string" # some dynamic value , can come from any function
            append_method(value)

    return data

task()

Czasy wychodza dosyć ciekawe np wychodzi na to że najszybciej python operuje na zmiennych lokalnych.

1 użytkowników online, w tym zalogowanych: 0, gości: 1