Направете Java бърза: Оптимизирайте!

Според пионерския учен Доналд Кнут „Преждевременната оптимизация е коренът на всяко зло“. Всяка статия за оптимизацията трябва да започне, като посочи, че обикновено има повече причини да не се оптимизира, отколкото да се оптимизира.

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

  • Оптимизацията прави кода по-труден за разбиране и поддръжка

  • Някои от представените тук техники увеличават скоростта, като намаляват разширяемостта на кода

  • Оптимизирането на кода за една платформа всъщност може да го влоши на друга платформа

  • Много време може да бъде отделено за оптимизиране, с малка печалба в производителността и може да доведе до замъглено кодиране

  • Ако сте прекалено обсебени от оптимизирането на кода, хората ще ви наричат ​​маниак зад гърба ви

Преди да оптимизирате, трябва внимателно да обмислите дали изобщо трябва да оптимизирате. Оптимизацията в Java може да бъде неуловима цел, тъй като средите за изпълнение варират. Използването на по-добър алгоритъм вероятно ще доведе до по-голямо увеличение на производителността от всяко количество оптимизации на ниско ниво и е по-вероятно да доведе до подобрение при всички условия на изпълнение. Като правило трябва да се обмислят оптимизации на високо ниво, преди да се правят оптимизации на ниско ниво.

И така, защо да оптимизираме?

Ако е толкова лоша идея, защо изобщо да се оптимизира? Е, в идеален свят не бихте го направили. Но реалността е, че понякога най-големият проблем на една програма е, че тя изисква просто твърде много ресурси и тези ресурси (памет, цикли на процесора, честотна лента на мрежата или комбинация) могат да бъдат ограничени. Кодовите фрагменти, които се появяват многократно в дадена програма, вероятно са чувствителни към размера, докато кодът с много итерации на изпълнение може да бъде чувствителен към скоростта.

Направете Java бърза!

Като интерпретиран език с компактен байт код, скоростта или липсата му е това, което най-често се появява като проблем в Java. Ще разгледаме предимно как да накараме Java да работи по-бързо, вместо да я поберем в по-малко пространство - въпреки че ще посочим къде и как тези подходи влияят на паметта или мрежовата честотна лента. Фокусът ще бъде върху основния език, а не върху Java API.

Между другото, едно нещо, което няма да обсъждаме тук, е използването на естествени методи, написани на C или сглобяване. Въпреки че използването на местни методи може да даде крайно подобрение на производителността, това се прави с цената на независимостта на платформата на Java. Възможно е да се напишат както Java версия на метод, така и собствени версии за избрани платформи; това води до повишена производителност на някои платформи, без да се отказва възможността да се изпълнява на всички платформи. Но това е всичко, което ще кажа по въпроса за замяната на Java с C код. (Вижте съвета за Java, „Писане на местни методи“ за повече информация по тази тема.) В тази статия фокусът ни е върху това как да направим Java бърза.

90/10, 80/20, хижа, хижа, поход!

Като правило 90 процента от времето за изпълнение на програмата се изразходва за изпълнение на 10 процента от кода. (Някои хора използват правилото 80 процента / 20 процента, но опитът ми в писането и оптимизирането на търговски игри на няколко езика през последните 15 години показа, че формулата 90 процента / 10 процента е типична за програми, жадни за изпълнение, тъй като малко задачи са склонни да да се изпълнява с голяма честота.) Оптимизирането на останалите 90 процента от програмата (където са изразходвани 10 процента от времето за изпълнение) няма осезаем ефект върху производителността. Ако сте успели да накарате 90% от кода да се изпълни два пъти по-бързо, програмата ще бъде само с 5% по-бърза. Така че първата задача при оптимизирането на кода е да се идентифицират 10-те процента (често това е по-малко от това) на програмата, която консумира по-голямата част от времето за изпълнение. Това не еВинаги там, където очаквате.

Общи техники за оптимизация

Има няколко често използвани техники за оптимизация, които се прилагат независимо от използвания език. Някои от тези техники, като глобалното разпределение на регистрите, са сложни стратегии за разпределение на машинните ресурси (например регистрите на процесора) и не се прилагат за байтови кодове на Java. Ще се съсредоточим върху техниките, които основно включват преструктуриране на код и заместване на еквивалентни операции в даден метод.

Намаляване на силата

Намаляването на силата се случва, когато дадена операция се замени с еквивалентна операция, която се изпълнява по-бързо. Най-често срещаният пример за намаляване на якостта е използването на оператора за смяна за умножаване и разделяне на цели числа по степен 2. Например, x >> 2може да се използва вместо x / 4и x << 1замества x * 2.

Елиминиране на общ под израз

Елиминирането на общ подизраз премахва излишните изчисления. Вместо да пише

double x = d * (lim / max) * sx; double y = d * (lim / max) * sy;

общият подизраз се изчислява веднъж и се използва и за двете изчисления:

double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;

Кодово движение

Движението на кода премества код, който извършва операция или изчислява израз, чийто резултат не се променя или е инвариант . Кодът се премества така, че да се изпълнява само когато резултатът може да се промени, вместо да се изпълнява всеки път, когато се изисква резултатът. Това е най-често при цикли, но може да включва и код, повтарящ се при всяко извикване на метод. По-долу е даден пример за инвариантно движение на код в цикъл:

for (int i = 0; i < x.length; i++) x [i] * = Math.PI * Math.cos (y); 

става

двойна пикозия = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i++)x [i] * = picosy;

Развиване на цикли

Развиването на цикли намалява режийните разходи на контролния код на цикъла, като извършва повече от една операция всеки път през цикъла и следователно изпълнява по-малко итерации. Работейки от предишния пример, ако знаем, че дължината на x[]винаги е кратна на две, можем да пренапишем цикъла като:

двойна пикозия = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i += 2) {x [i] * = picosy; x [i + 1] * = picosy; }

На практика развиването на цикли като този - при които стойността на индекса на цикъла се използва в рамките на цикъла и трябва да се увеличава отделно - не води до значително увеличение на скоростта в интерпретираната Java, тъй като в байтовите кодове липсват инструкции за ефективно комбиниране на " +1"в индекса на масива.

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

Включване на компилатора в работа

Съвременните компилатори на C и Fortran произвеждат силно оптимизиран код. Компилаторите на C ++ обикновено произвеждат по-малко ефективен код, но все още вървят по пътя към създаването на оптимален код. Всички тези компилатори са преминали през много поколения под влиянието на силна пазарна конкуренция и са се превърнали в фино усъвършенствани инструменти за изцеждане на всяка последна капка производителност от обикновения код. Те почти сигурно използват всички общи техники за оптимизация, представени по-горе. Но все още има много трикове, за да накарате компилаторите да генерират ефективен код.

javac, JIT и компилатори на роден код

Нивото на оптимизация, което се javacизвършва при компилиране на код в този момент, е минимално. По подразбиране се прави следното:

  • Постоянно сгъване - компилаторът разрешава всички константни изрази, така че да се i = (10 *10)компилира в i = 100.

  • Сгъване на разклонения (през повечето време) - gotoизбягват се ненужни байт кодове.

  • Ограничено премахване на мъртъв код - не се създава код за изявления като if(false) i = 1.

Нивото на оптимизация, което предоставя javac, трябва да се подобри, вероятно драстично, тъй като езикът узрява и доставчиците на компилатори започват да се конкурират сериозно на базата на генериране на код. Java току-що получава компилатори от второ поколение.

След това има компилатори JIT (just-in-time-compiler), които преобразуват Java байт кодове в собствен код по време на изпълнение. Вече са налични няколко и въпреки че те могат да увеличат драстично скоростта на изпълнение на вашата програма, нивото на оптимизация, която могат да извършат, е ограничено, тъй като оптимизацията се извършва по време на изпълнение. Компилаторът на JIT се занимава повече с бързото генериране на кода, отколкото с генерирането на най-бързия код.

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

javacпредлага една опция за изпълнение, която можете да активирате: извикване на -Oопцията, за да накара компилаторът да вгради определени извиквания на метод:

javac -O MyClass

Включването на извикване на метод вмъква кода за метода директно в кода, осъществяващ извикването на метода. Това елиминира режийните разходи за извикване на метода. За малък метод тези режийни разходи могат да представляват значителен процент от времето за изпълнение. Имайте предвид, че само методи, декларирани като или private,, staticили finalмогат да бъдат разгледани за вграждане, тъй като само тези методи са статично разрешени от компилатора. Също така synchronizedметодите няма да бъдат вградени. Компилаторът ще вгражда само малки методи, обикновено състоящи се само от един или два реда код.

За съжаление 1.0 версиите на компилатора на javac имат грешка, която ще генерира код, който не може да предаде верификатора на байт кода, когато -Oсе използва опцията. Това е поправено в JDK 1.1. (Проверяващият байт код проверява кода, преди да му бъде разрешено да се изпълни, за да се увери, че не нарушава никакви правила на Java.) Той ще вгради методи, които препращат членове на класа, недостъпни за извикващия клас. Например, ако следните класове се компилират заедно с помощта на -Oопцията

клас A {private static int x = 10; публична статична празнота getX () {return x; }} клас B {int y = A.getX (); }

извикването към A.getX () в клас B ще бъде вградено в клас B, сякаш B е написан като:

клас B {int y = Ax; }

Това обаче ще доведе до генериране на байт кодове за достъп до частната променлива Ax, която ще бъде генерирана в кода на B. Този код ще се изпълни добре, но тъй като нарушава ограниченията за достъп на Java, той ще бъде маркиран от проверяващия при IllegalAccessErrorпървото изпълнение на кода.

Тази грешка не прави -Oопцията безполезна, но трябва да внимавате как я използвате. Ако се извика за един клас, той може да вгради определени извиквания на метода в класа без риск. Няколко класа могат да бъдат вградени заедно, стига да няма потенциални ограничения за достъп. И някои кодове (като приложения) не се подлагат на проверката на байт кода. Можете да игнорирате грешката, ако знаете, че кодът ви ще се изпълнява само без да бъде подложен на проверителя. За допълнителна информация вижте моите често задавани въпроси за javac-O.

Профили

За щастие JDK се предлага с вграден профилатор, който помага да се определи къде прекарва времето в дадена програма. Той ще следи времето, прекарано във всяка рутина, и ще записва информацията във файла java.prof. За да стартирате профила, използвайте -profопцията при извикване на интерпретатора на Java:

java -prof myClass

Или за използване с аплет:

java -prof sun.applet.AppletViewer myApplet.html

Има няколко предупреждения за използването на профила. Изходът на профила не е особено лесен за дешифриране. Също така в JDK 1.0.2 той съкращава имената на методите до 30 знака, така че може да не е възможно да се разграничат някои методи. За съжаление, с Mac няма средства за извикване на профила, така че потребителите на Mac нямат късмет. На всичкото отгоре, страницата за документи на Java на Sun (вж. Ресурси) вече не включва документацията за -profопцията). Ако вашата платформа обаче поддържа -profопцията, HyperProf на Владимир Булатов или ProfileViewer на Грег Уайт могат да бъдат използвани за интерпретиране на резултатите (вж. Ресурси).

Също така е възможно да "профилирате" кода, като вмъкнете изрично време в кода:

long start = System.currentTimeMillis(); // do operation to be timed here long time = System.currentTimeMillis() - start;

System.currentTimeMillis()връща времето за 1/1000 доли от секундата. Някои системи, като например компютър с Windows, имат системен таймер с по-малка (много по-малка) резолюция от 1/1000 от секундата. Дори 1/1 000 от секундата не е достатъчно дълъг, за да може точно да се определи времето за много операции. В тези случаи или при системи с таймери с ниска разделителна способност може да се наложи да определите времето колко време е необходимо за повторение на операцията n пъти и след това да разделите общото време на n, за да получите действителното време. Дори когато е налице профилиране, тази техника може да бъде полезна за синхронизиране на конкретна задача или операция.

Ето няколко заключителни бележки относно профилирането:

  • Винаги определяйте времето преди и след извършване на промени, за да проверите дали поне на тестовата платформа промените са подобрили програмата

  • Опитайте се да направите всеки тест за синхронизация при идентични условия

  • Ако е възможно, измислете тест, който не разчита на потребителски вход, тъй като вариациите в отговора на потребителя могат да доведат до колебание на резултатите

Бенчмарк аплетът

Бенчмарк аплетът измерва времето, необходимо за извършване на операция, хиляди (или дори милиони) пъти, изважда времето, прекарано в извършване на операции, различни от теста (например режийните режими), и след това използва тази информация, за да изчисли колко дълго всяка операция взеха. Той изпълнява всеки тест за приблизително една секунда. В опит да премахне случайни закъснения от други операции, компютърът може да извърши по време на тест, той изпълнява всеки тест три пъти и използва най-добрия резултат. Той също така се опитва да елиминира събирането на боклука като фактор в тестовете. Поради това, колкото повече памет е на разположение на бенчмарка, толкова по-точни са резултатите от бенчмарка.