Mam taki problem z czasem realizacji, a mianowicie z wykonaniem tego oto fragmentu kodu:
b = (*bity)[j];
dane += b << pozycja;
bity to wskaźniek do elemntu tablicy który jest vektorem bitów a dane i pozycja to inty;
Cała operacja trwa ok 150 milisekund mi zależy na ok 100 ms, cała reszta kodu już na maxa zoptymalizowana i ze 160ms całości to zajmuje 150.
No cudowne, pokazałeś dwie linijki kodu, prostego jak konstrukcja cepa i oczekujesz "cudownego dotknięcia" forum, które to zoptymalizuje. Tu nie ma czego optymalizować.
#włącz profiler i sprawdź gdzie program spędza najwięcej czasu, ten fragment nie może być problemem, bo powinien się wykonywać poniżej 1ms
#sprawdź jakie masz dostępne optymalizacje kompilatora
#tryb debbug czy release?
#pokaż zdecydowanie więcej kodu i opisz co to ma robić!
#napisałeś, że operacja trwa 150 milisekund. Co ty właściwie zmierzyłeś jak? Może twój miernik po prostu osiągnął minimalną rozdzielczość? Może mówisz o całkowitym czasie wykonania jakiejś pętli!
Ten fragment powinien się wykonywać na procesorze x86 4-5 cykli
Około 40 cykli procesora jeśli będziesz miał pecha i zaliczysz L1 Cache Miss.
Około 600-900 cykli (+ możliwe wywłaszczenie przez OS) jeśli zaliczysz L2/L3 Cache Miss.
Tak czy inaczej, biorąc pod uwagę że procesory mają obecnie koło 3*10^9 cykli na sekundę, nie pisz cudów że przesunięcie bitowe zajmuje jakieś niestworzone ilości czasu
Zapewne kompilator i tak sprowadza to do tej postaci, ale szybciej juz tego nie wykonasz.
#include <iostream>
using namespace std;
int przesun(int dane, int b, int pozycja)
{
__asm {
mov eax, dane
mov ebx, b
mov ecx, pozycja
petla:
shl ebx, 1
dec ecx
jnz petla
add eax, ebx
}
}
int main()
{
cout << przesun(1,2,9);
int c=1;
c += 2 << 9;
cout << endl << c;
cout << endl;
return 0;
}
Takie cos powinno sie wykonywac w bardzo krotkim czasie, niemozliwe ze trwa to 150ms.
petla:
shl ebx, 1
dec ecx
jnz petla
<==>
shl ebx, cl
Dzięki wszystkim za odpowiedzi, nawet tym którzy przed odpowiedzią nie przeczytali mojego posta. Ten właśnie fragment kodu w pętli (kilka milionow razy) trwa najdłużej i zastanawiałem się czy istniej jakiś lepszy(szybszy) sposób na przeprowadzenie przesunięcia. Niestety assembler odpada bo nie chciał bym za miesiąc odnosząc się do tego kodu zastanawiać nad każdą linijką. Rozumiem że odpowiedź brzmi "NIE, nie da się".
Ps.
Nie napisałem czym jest "b" bo uznałem że zdanie "bity to wskaźniek do elemntu tablicy który jest vektorem bitów" jednoznacznie określa że b nie może być niczym innym jak boolem.
nadal nie rozumiesz problemu,prawdopodobnie da się to zoptymalizować, ale nie fragment, który pokazałeś.
Pokaż większy kawałek kodu wszystkie pętle obejmujące ten fragment!
Zmiana kolejności pętli może znacznie przyspieszyć program, generalnie chodzi o to by jak najbardziej sekwencyjnie odnosić się do pamięci, by zaliczać jak najmniej "Cache Miss".
Przykładowo operacje na dużych macierzach, ma bardzo duże znaczenie czy najpierw iterujesz po wierszach czy po kolumnach.
vector<int> wynik;
wynik.reserve(q);
for(;i<q;i++)
{
for(int j=0;j<16;j++)
{
b = (*bity)[j];
dane += b << pozycja;
}
wynik.push_back(dane);
dane = 0;
bity++;
}
Ot i cały kod. Po prostu zamienia vektor bitów na vektor intów z tym że tylko po 16 bitów.
no i teraz ostatnie pytanie bonusowe. Co to dokładnie jest bity?
Jeśli bity to vector<bool> o rozmiarze 16 to twój kod jest bezsensu jeśli chodzi o optymalność!
vector<bool> jest specjalizacja szablonu (troszkę nieszczęśliwą) i ona już trzyma dane w postaci bitów, patrz końcówka opisu vector-a.
Jak widzisz w pełnym kontekście twój kod jest dalece nieoptymalny.
Przypuszczam, że tak naprawdę powinieneś użyć bitset, który ma metodę to_ulong() i idealnie się nadaje do tego co ci potrzebne do optymalizacji.
Jeśli liczba bitów nie jest stała to wyciągnięcie tych danych równie szybko będzie troszkę bardziej skomplikowane.
Liczba bitów nie jest stała, kod ten jest bardzo uproszczony ale int a=b zoptymalizować nie da więc nie wklejałem bezsensu 100 lini kodu bo nikt by tego nie czytał :). Ogólnie jest to algorytm słownikowej ze zmiennej długości słowem. Bity reprezentuje słownik jest to tablica vektorów bitów i chce ta tablice vektórów bitów upakować do intów po 16 bitów na inta (musi być 16 nie 32 aby można było przeprowadzić kolejny etap kompresjii).
no i co z tego, że to_ulong zwraca 32 (albo nawet 64) bity!
to jest szablon, którego parametrem jest liczba bitów. Wygląda na to (tak wykazuje twój kod), że ty zawsze potrzebujesz 16 bitów (lub maksymalnie), więc zastosowanie bitset<16> aż się prosi. Nadmiarowe bity z to_ulong i tak zostaną odrzucone, naprawdę nie masz się co tym przejmować, a zysk będzie z 16 krotny lub większy.
Nawet jeśli się upierasz na vector, to przecież wyraźnie napisałem, że vector<bool> przechowuje dane w bitach, więc twoja konwersja jest stratą czasu, bo dokonujesz skomplikowanej konwersji po miedzy dwoma obiektami, które w pamięci niczym się nie różnią.
Problemem jest jedynie efektywne wydłubanie tego z vector-a (dlatego zalecam bitset bo tam masz to podane na tacy).
Może rzeczywiście ten kod nie do końca oddaje to co miał oddawać jednak, chodzi o to że vektor bitów może mieć 2 a może mieć 60 elementów a ja chce je połączyć po 16 tak aby w pełni zagospodarować dostępne miejsce. Ale dzięki za podpowiedz z tym bitsetem, niestety dopiero uczę się c++. Tylko pytanie czy można te bitsety łączyć ze sobą a potem dzielić? i czy można ustawić wskaźnik na element czegoś takiego.
może lepiej przyznaj się dokładnie co robisz, zamiast kombinować z kontenerami STL. Jakaś kompresja?
Tak kompresja słownikiem o różnej długości słów i nie chce zbędnych 0 między słowami (oprócz tych planowych 16 w każdym incie) więc składam słowa różnej długości w jeden ciąg intów.
pewnie robisz kodowanie Huffmana.
Po pierwsze przemyśl dokładniej jak chcesz przetrzymywać słownik. Wybór vector<bool> był niezbyt trafiony (w dokumentacji nie widzę jak dobrać się do danych bezpośrednio przez wskaźnik na bufor, ale może implementacja dla twojego kompilatora ma jakieś obejście na to). Ja bym zrobił własną strukturę opisującą maskę bitową i ilość bitów.
Możesz też zobaczyć jak inni to zrobili na pewno znajdziesz jakiś przykładowy kod w C i C++.
PS. Jeszcze jedno, pamiętaj, że jest jeszcze pułapka w postaci endiany, jeśli planujesz testować kod na różnych urządzeniach to może to być spora niespodzianka.