Zrównoleglamy ;-)

Mój program wyliczający podobne posty działał dość znośnie do wczoraj, kiedy to nagle zaczął zmieniać za każdym razem podobne posty. Kilka godzin debugowania pokazało, że serwery Google zaczęły zwracać dziwne listy postów na Bloggerze, udało mi się to obejść, ale się na tyle rozochociłem, że postanowiłem przerobić tak program do wyliczania tych podobnych postów by korzystał ze wszystkich rdzeni/procesorów w komputerze ;-)

Program ma wyliczyć podobieństwo między każdą parą postów, coś w tym stylu:

	post 1	post 2	post 3	post 4	post 5
post 1	waga 1 z 1	waga 1 z 2	waga 3 z 1	waga 4 z 1	waga 5 z 1
post 2	waga 1 z 2	waga 2 z 2	waga 3 z 2	waga 4 z 2	waga 5 z 2
post 3	waga 1 z 3	waga 2 z 3	waga 3 z 3	waga 4 z 3	waga 4 z 3
post 4	waga 1 z 4	waga 2 z 3	waga 3 z 4	waga 4 z 4	waga 5 z 4
post 5	waga 1 z 5	waga 2 z 5	waga 3 z 5	waga 4 z 5	waga 5 z 5

Ale, że nie trzeba tak naprawdę liczyć podobieństwa postu z samym sobą ;-) oraz, że wyliczenie podobieństwa postu 1 z 2 i postu 2 z 1 bazują na tych samych wartościach (ale nie są takie same), to tak naprawdę trzeba rozważyć takie pary (zaznaczone na żółto):

	post 1	post 2	post 3	post 4	post 5
post 1	waga 1 z 1	waga 1 z 2	waga 3 z 1	waga 4 z 1	waga 5 z 1
post 2	waga 1 z 2	waga 2 z 2	waga 3 z 2	waga 4 z 2	waga 5 z 2
post 3	waga 1 z 3	waga 2 z 3	waga 3 z 3	waga 4 z 3	waga 4 z 3
post 4	waga 1 z 4	waga 2 z 3	waga 3 z 4	waga 4 z 4	waga 5 z 4
post 5	waga 1 z 5	waga 2 z 5	waga 3 z 5	waga 4 z 5	waga 5 z 5

Wcześniej działało to tak, że były 2 pętle, jedna w drugiej, które szły po wszystkich postach i liczyły co trzeba tylko wtedy jeśli to jeszcze nie było policzone.
Sęk w tym, że działało to na 1 wątku.

Ale przecież nie musiało ;-)
Dlatego wprowadziłem pewne zmiany, pierwszą było zamienienie takiego kodu:

for (final Post currentPost:list) {
  // jeśli currentPost nie był jeszcze inicjalizowany to go przygotuj
  for (final Post comparPost:list) {
     // licz i działaj
  }
  // na podstawie podobieństw między currentPost a całą resztą
  // przygotuj listę 5 najbardziej podobnych
}

W coś takiego:

List<Pair> pairs = new ArrayList<Pair>();
for (int i=0; i<list.size(); i++ { 
  final Post currentPost = list.get(i);
  for (int j=i+1; j<list.size(); j++) {
     final Post comparPost = list.get(j);
     pairs.add(new Pair(currentPost, comparPost));
  }
}
for (Pair pair:pairs) {
  // prowadź niecną działalność wyliczeniową
  // na podstawie podobieństw między currentPost a całą resztą
  // przygotuj listę 5 najbardziej podobnych
}

W pierwszych dwóch pętlach przygotowywana jest lista, której elementy są rozłożone w taki sposób w naszej "tablicy":

	post 1	post 2	post 3	post 4	post 5
post 1		1	2	3	4
post 2			5	6	7
post 3				8	9
post 4					10
post 5

A stąd już blisko do zrównoleglenia ;-)

Niestety dojście do tego momentu trochę mi zajęło z racji tego co opisałem "na podstawie podobieństw między currentPost a całą resztą przygotuj listę 5 najbardziej podobnych".
Ale jak już miałem taką wersję jak ta druga to sprawa stała się prosta ;-) [chociaż nie do końca bo wyrósł kolejny problem, okazało się, że musiałem jeszcze zmienić użycie HashMap'y w ConcurrentHashMap, bo bez tego coś nie działało, nie leciały wyjątki, ale w pewnym momencie jeden z wątków, a czasem oba zaczynał wisieć na put, podejrzewam, że w HashMap'ie w pewnym momencie w liście elementów z tym samym hash'em mogło dochodzić do tego, że element sam na siebie wskazywał jako na następny]

Ostatecznie kod wygląda tak:

List<List<Pair>> perCPU = new ArrayList<List<Pair>>();

int numOfCPUs = Runtime.getRuntime().availableProcessors();

for (int i=0; i<numOfCPUs; i++) {

perCPU.add(new ArrayList<Pair>());

}

int numOfPairs = 0;
for (int i=0; i<list.size(); i++ { 
  final Post currentPost = list.get(i);
  for (int j=i+1; j<list.size(); j++) {
     final Post comparPost = list.get(j);

     perCPU.get(numOfPairs%numOfCPUs).add(new Pair(currentPost, comparPost));
  }
}

ExecutorService pool = Executors.newFixedThreadPool(numOfCPUs);
ArrayList<Future> listOfResults = new ArrayList<Future>();
for (final ArrayList<Pair> listOfPairs:perCPU) {

    listOfResults.add(pool.submit(new Runnable() {
       public void run() {
          workWithPairs(listOfPairs, howManyDocumentsHasWord);
       }
    }));
}

for (Future future:listOfResults) {
 future.get();
}

pool.shutdown();

Teraz pytanie jak to wygląda z czasem?

Na moim pracowym laptopie (bo mój jedzie do mnie z serwisu, jest teraz w Katowicach i jutro powinien do mnie przyjechać ;-) po to sobie wziąłem nawet Work From Home coby go odebrać) wcześniejsza wersja potrzebowała na przeliczenie 1613 postów (czyli na rozważenie 2601769 par, z których mniej niż połowa była liczona) 26 sekund, obecna wersja to samo robi w 16 sekund ;-) i rozważa 1205128 par, których przygotowanie to 93 ms, a każdy rdzeń (mam 2 w tym laptopie) dostaje do zabawy 602564 pary.

Zyskałem jakieś 40% co nie jest może jakoś szczególnie wielkie ;-)

Zużycie CPU wygląda tak:

A pamięci tak:

Początek i koniec programu gdy CPU nie jest tak mocno wykorzystywany to operacje sieciowe, pobieranie z sieci listy postów i updatowanie zmienionych (które też je pobiera, co trzeba będzie zmienić).

Jak widać udało mi się doprowadzić do sytuacji w której więcej czasu zabierają operacje sieciowe niż liczenie ;-)

Kolejnym krokiem mogłoby być pójście w kierunku Fork/Join choć nie wiem czy ma to sens.

Jak rozumiem działać by to wtedy powinno tak, że wrzucałbym do kolejki zadania do wykonania, a Fork/Join zabierałby sobie z niej tyle ile by potrzebował. W razie jeden z wątków byłby już gotowy to mógłby podkraść część danych drugiemu.

Wydaje mi się, że to by mogło co najwyżej poprawić czytelność kodu (a wcale nie jestem tego pewien).

Najlepsze byłoby wymyślić lepszy algorytm, bo O(n²) nie jest fajne, ale na razie nie mam pomysłu na takowy.

Podobne posty^beta
Wszystkiemu winne są szybkie komputery ;-)
Seks w ujęciu informatycznym ;-) - rozmnażanie ;-)
Bookmarklet do robienia CSV z obligacjami i ich oprocentowaniem ;-)
Bez cukierków i Coli
Java 8 nadchodzi....