Предвиждане на клонове в Java

1. Въведение

Branch Prediction е интересна концепция в компютърните науки и може да окаже дълбоко въздействие върху производителността на нашите приложения. И все пак той обикновено не е добре разбран и повечето разработчици му обръщат много малко внимание.

В тази статия ще проучим какво точно представлява, как влияе на нашия софтуер и какво можем да направим по въпроса.

2. Какво представляват тръбопроводите с инструкции?

Когато пишем която и да е компютърна програма, ние пишем набор от команди, които очакваме компютърът да изпълнява последователно.

Ранните компютри биха работили по един. Това означава, че всяка команда се зарежда в паметта, изпълнява се изцяло и само когато е изпълнена, следващата ще се зареди.

Инструкционните тръбопроводи са подобрение в това отношение. Те позволяват на процесора да разделя работата на парчета и след това да изпълнява паралелно различни части. Това би позволило на процесора да изпълни една команда, докато зарежда следващата, готова за работа.

По-дългите тръбопроводи вътре в процесора не само позволяват опростяване на всяка част, но и позволяват паралелно да се изпълняват повече части от нея. Това може да подобри цялостната производителност на системата.

Например, бихме могли да имаме проста програма:

int a = 0; a += 1; a += 2; a += 3;

Това може да бъде обработено от конвейер, състоящ се от сегменти Извличане, декодиране, изпълнение, съхранение като:

Тук можем да видим как цялостното изпълнение на четирите команди се изпълнява паралелно, като по този начин прави цялата последователност по-бърза.

3. Какви са опасностите?

Определени команди, които процесорът трябва да изпълни, ще създадат проблеми за конвейерната обработка . Това са команди, при които изпълнението на една част от тръбопровода зависи от по-ранни части, но където тези по-ранни части все още не са били изпълнени.

Клоновете са специфична форма на опасност. Те карат изпълнението да върви в една от двете посоки и не е възможно да се знае в коя посока, докато клонът не бъде разрешен. Това означава, че всеки опит за зареждане на командите покрай клона не е безопасен, защото няма как да знаем откъде да ги заредим.

Нека променим нашата проста програма, за да въведем клон:

int a = 0; a += 1; if (a < 10) { a += 2; } a += 3;

Резултатът от това е същият както преди, но в средата му въведохме оператор if . Компютърът ще види това и няма да може да зарежда команди след това, докато не бъде разрешен . Като такъв потокът ще изглежда по следния начин:

Веднага можем да видим въздействието, което това оказва върху изпълнението на нашата програма, и колко стъпки на часовника са били необходими за изпълнение на същия резултат.

4. Какво е браншова прогноза?

Branch Prediction е подобрение на горепосоченото, където нашият компютър ще се опита да предскаже по какъв път ще отиде клон и след това да действа по съответния начин.

В горния ни пример процесорът може да предвиди, че ако (a <10) е вероятно да е истина , и така ще действа така, сякаш инструкцията a + = 2 е следващата за изпълнение. Тогава това би накарало потока да изглежда по следния начин:

Веднага можем да видим, че това е подобрило ефективността на нашата програма - сега тя отнема девет отметки, а не 11, така че е 19% по-бърза.

Това обаче не е без риск. Ако предвиждането на клона се обърка, то ще започне да поставя на опашка инструкции, които не трябва да се изпълняват. Ако това се случи, компютърът ще трябва да ги изхвърли и да започне отначало.

Нека обърнем условното си, така че да е фалшиво :

int a = 0; a += 1; if (a > 10) { a += 2; } a += 3;

Това може да изпълни нещо като:

Сега това е по-бавно от предишния поток, въпреки че правим по-малко! Процесорът неправилно предвиди, че клонът ще оцени на true , започна да поставя в опашка инструкцията a + = 2 и след това трябваше да я изхвърли и да започне отначало, когато клонът беше оценен на false.

5. Реално въздействие върху кода

Сега, след като знаем какво е прогнозиране на бранша и какви са ползите, как може да ни повлияе? В крайна сметка говорим за загуба на няколко процесорни цикъла на високоскоростни компютри, така че със сигурност няма да бъде забележимо.

И понякога това е вярно. Но понякога това може да направи изненадващо разликата в работата на нашите приложения. Зависи много от това какво точно правим. По-конкретно, това зависи от това колко правим за кратко време.

5.1. Броячи записи в списъка

Нека се опитаме да броим записи в списък. Ще генерираме списък с числа, след което ще преброим колко от тях са по-малко от определена граница. Това е много подобно на горните примери, но го правим в цикъл, а не само като една инструкция:

List numbers = LongStream.range(0, top) .boxed() .collect(Collectors.toList()); if (shuffle) { Collections.shuffle(numbers); } long cutoff = top / 2; long count = 0; long start = System.currentTimeMillis(); for (Long number : numbers) { if (number < cutoff) { ++count; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} {} numbers in {}ms", count, top, shuffle ? "shuffled" : "sorted", end - start);

Имайте предвид, че определяме времето само за цикъла, който извършва броенето, защото това е, което ни интересува. И така, колко време отнема това?

If we're generating sufficiently small lists, then the code runs so fast that it can't be timed — a list of size 100,000 still shows a time of 0ms. However, when the list gets large enough that we can time it, we can see a significant difference based on whether we have shuffled the list or not. For a list of 10,000,000 numbers:

  • Sorted – 44ms
  • Shuffled – 221ms

That is, the shuffled list takes 5x longer to count than the sorted list, even though the actual numbers being counted are the same.

However, the act of sorting the list is significantly more expensive than just performing the counting. We should always profile our code and determine if any performance gains are beneficial.

5.2. Order of Branches

Following the above, it seems reasonable that the order of branches in an if/else statement should be important. That is, we could expect the following to perform better than if we re-ordered the branches:

if (mostLikely) { // Do something } else if (lessLikely) { // Do something } else if (leastLikely) { // Do something }

However, modern computers can avoid this issue by using the branch prediction cache. Indeed, we can test this as well:

List numbers = LongStream.range(0, top) .boxed() .collect(Collectors.toList()); if (shuffle) { Collections.shuffle(numbers); } long cutoff = (long)(top * cutoffPercentage); long low = 0; long high = 0; long start = System.currentTimeMillis(); for (Long number : numbers) { if (number < cutoff) { ++low; } else { ++high; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} numbers in {}ms", low, high, end - start);

This code executes in around the same time – ~35ms for sorted numbers, ~200ms for shuffled numbers – when counting 10,000,000 numbers, irrespective of the value of cutoffPercentage.

This is because the branch predictor is handling both branches equally and correctly guessing which way we're going to go for them.

5.3. Combining Conditions

What if we have a choice between one or two conditions? It might be possible to re-write our logic in a different way that has the same behavior, but should we do this?

As an example, if we are comparing two numbers to 0, an alternative approach is to multiply them together and compare the result to 0. This is then replacing a condition with a multiplication. But is this worthwhile?

Let's consider an example:

long[] first = LongStream.range(0, TOP) .map(n -> Math.random()  Math.random() < FRACTION ? 0 : n) .toArray(); long count = 0; long start = System.currentTimeMillis(); for (int i = 0; i < TOP; i++) { if (first[i] != 0 && second[i] != 0) { ++count; } } long end = System.currentTimeMillis(); LOG.info("Counted {}/{} numbers using separate mode in {}ms", count, TOP, end - start);

Our condition inside the loop can be replaced, as described above. Doing so actually does affect the runtime:

  • Separate conditions – 40ms
  • Multiple and single condition – 22ms

So the option that uses two different conditions actually takes twice as long to execute.

6. Conclusion

Видяхме какво е прогнозиране на клонове и как може да окаже влияние върху нашите програми. Това може да ни даде някои допълнителни инструменти в нашия пояс, за да гарантираме, че нашите програми са възможно най-ефективни.

Както винаги обаче, трябва да не забравяме да профилираме нашия код, преди да правим големи промени . Понякога може да се случи, че извършването на промени, които да подпомогнат прогнозирането на клонове, струва повече по други начини.

Примери за случаите от тази статия са достъпни в GitHub.