imul, які ніколі не выконваецца

На гэтым тыдні я атрымаў адзін каментар на рэв’ю. Я напісаў total = count * 2, а каментар прасіў замест гэтага count << 1, бо зрух танней за множанне. Я не спрачаўся. Мне не было чым. Я пішу на Java кожны працоўны дзень і ні разу не адкрываў class-файл, каб паглядзець, што javac з яго робіць.

Так я яго адкрыў. Усё, што ніжэй, знята на OpenJDK 7 b147, зборцы IcedTea 2.0, якая трапіла ў дыстрыбутывы ў кастрычніку. Прагон прыбіты да аднаго ядра госця kvm. У сёмай версіі шматузроўневая кампіляцыя выключана, таму ўсю работу робіць серверны кампілятар з парогам CompileThreshold у 10000.

Што javac захоўвае

Два метады, праз радок:

static int byMul(int x)   { return x * 2; }
static int byShift(int x) { return x << 1; }

І javap -c па class-файле:

  static int byMul(int);        static int byShift(int);
       0: iload_0                    0: iload_0
       1: iconst_2                   1: iconst_1
       2: imul                       2: ishl
       3: ireturn                    3: ireturn

Па чатыры байткоды. Адрозніваюцца два з чатырох: адна інструкцыя кладзе на стэк канстанту, другая яе забірае. На гэтым пласце каментар з рэв’ю мае рацыю.

javac сёе-тое перапісвае, проста не гэта. return 2 * 3 кампілюецца ў bipush 6. Прачытаны з іншага класа static final int прыязджае як iconst_4, а не як чытанне поля. javac робіць тыя перапісванні, якія прадпісвае мова, а арыфметыку пакідае таму, хто будзе выконваць байткод.

javac розніцу захоўвае. Ніжэй яе ўжо не змерыць: інтэрпрэтатар двух варыянтаў не адрознівае, а серверны кампілятар піша для абодвух адну інструкцыю.

Што бачыць інтэрпрэтатар

Калі розніца жыве ніжэй за javac, яна павінна жыць у інтэрпрэтатары, які ідзе па байткодзе па адной інструкцыі. Я прагнаў абодва цыклы пад -Xint, дзесяць мільёнаў выклікаў на раўнд, пятнаццаць раўндаў, раўнды mul і shift чаргуюцца ўнутры адной jvm, каб дрэйф краў абодва. Медыяны ў мікрасекундах:

mul   median 241716 us
shift median 240751 us

Shift выходзіць хутчэйшым на 0.4 працэнта. Скрыпт паўтарае той жа замер тры разы: mul хутчэйшы на 4.7 працэнта, потым на 8.4, потым shift хутчэйшы на 2.6. Раўнды ўнутры аднаго прагону разышліся ад 199267 да 301291, так што ніводзін з гэтых прасветаў нічога не значыць.

Прычына ў дыспетчарызацыі. Кожны шаблон байткода канчаецца на movzbl 0x1(%r13),%ebx і jmp *(%r10,%rbx,8), гэта значыць на звароце да табліцы і ўскосным пераходзе ў наступны шаблон. Я вываліў абодва шаблоны праз -XX:+PrintInterpreter, чакаючы блізнятаў. Арыфметыка ў кожным адна інструкцыя, але шаблон зруху на адну перасылку даўжэйшы, бо лічыльнік зруху абавязаны прайсці праз %cl. Тое, што зрух эканоміць у ALU, ён аддае назад у пачатку ўласнага шаблона.

Кампілятар прыходзіць пасярод цыкла

Тыя ж цыклы без -Xint, па сто мільёнаў выклікаў на раўнд. Гэтыя раўнды не чаргуюцца, усе дзевяць раўндаў mul ідуць першымі:

mul   median 34629 us
shift median 34635 us

Гэта 0.35 нанасекунды на ітэрацыю супраць 24.2 у інтэрпрэтатары, суадносіны 70. Па чатырох прагонах яны леглі паміж 66 і 71, прычым амаль увесь рух прыходзіць з боку інтэрпрэтатара: яго медыяна зрушылася на шэсць працэнтаў, скампіляваная менш чым на адзін.

Пераход відаць, калі друкаваць кожны раўнд замест медыяны. Дванаццаць раўндаў па мільёне выклікаў, у мікрасекундах:

10012  386  370  381  370  381  342  356  342  342  354  342

Нулявы раўнд даражэйшы за плато прыкладна ў трыццаць разоў. І ён таксама не цалкам інтэрпрэтаваны. Мільён інтэрпрэтаваных выклікаў каштуе каля 24200 мікрасекунд, а гэты каштаваў 10012, гэта значыць кампілятар дагнаў цыкл проста на хаду. -XX:+PrintCompilation на той жа камандзе паказвае, як менавіта:

37    1             Doubling::byMul (4 bytes)
39    1 %           Doubling::roundMul @ 9 (47 bytes)
45    2             Doubling::roundMul (47 bytes)

Знак % азначае on-stack replacement. Кадр ужо стаяў на стэку, калі рантайм падмяніў код на скампіляваны з уваходам па байткодзе 9, а гэта галава цыкла. Я лічыў, што метад спачатку кампілюецца, а наступны выклік атрымлівае хуткую версію. У доўгага цыкла наступнага выкліку няма, таму jvm яго і не чакае.

Што атрымлівае машына

-XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print друкуе гатовы код, калі сабраць плагін hsdis супраць binutils. Зборка заняла ў мяне больш часу, чым сам замер. Абодва метады:

byMul:   mov %esi,%eax        shl $1,%eax   ;*imul
byShift: mov %esi,%eax        shl $1,%eax   ;*ishl

Тая ж арыфметыка, адзін mov і адзін shl, унутры целаў па 32 байты кожнае. У калонцы каментара стаіць байткод, з якога інструкцыя атрымалася. У першым радку там напісаны imul побач са зрухам.

Цыклы атрымаліся цікавейшымі. Я выразаў з абодвух лістынгаў адрасы і параўнаў, па 103 інструкцыі з кожнага боку. diff выдае два радкі. Абодва адрозніваюцца толькі каментаром:

55c55
< add    $0x10,%esi         ;*imul
---
> add    $0x10,%esi         ;*ishl
64c64
< mov    %r11d,%ebx         ;*imul
---
> mov    %r11d,%ebx         ;*ishl

Гарачы цыкл гэта 32 інструкцыі і 90 байтаў. За адзін праход ён робіць шаснаццаць ітэрацый зыходніка. Множання ў ім няма, выкліку byMul таксама няма. Множанне стала бягучым значэннем, якое расце на 32 за праход і жыве адразу ў трох рэгістрах са зрухам па фазе. У акумулятар трапляюць шаснаццаць яго копій, пятнаццаць складаннем і адна перасылкай, якая акумулятар зацірае, а старое змесціва вяртаецца наступным радком. Канстанту 240, што папраўляе суму, прыносіць add $0xf0. Сума 2 * i па шаснаццаці запар ідучых i роўная 32 першым значэнням плюс 240. Гэта роўна тое, што кампілятар запісаў.

Сапраўдная інструкцыя множання ва ўсім скампіляваным метадзе роўна адна. Яна стаіць паміж movabs $0x20c49ba5e353f7cf і sar $0x7, гэта значыць гэта дзяленне на 1000, палічанае множаннем на магічную канстанту. Гэта мой жа радок замеру, які пераводзіць нанасекунды ў мікрасекунды. Множанне з майго зыходніка не выконваецца ніколі. Тое, якое выконваецца, прыйшло з кода замеру.

Шаснаццаць множанняў ператварыліся ў шаснаццаць копій аднаго бягучага значэння і канстанту. Множанне, якое засталося, належыць кода замеру.

Бенчмарк, які я выкінуў

Першая версія нічога не сумавала. Яна выклікала byMul(i) і выкідала вынік:

discarded   4934   8684      0      0      0      0

Нуль мікрасекунд пачынаючы з другога раўнда. Я падняў цыкл да двух мільярдаў ітэрацый, а ён усё роўна друкаваў нулі. Непатрэбны выклік без пабочнага эфекту мёртвы. Цыкл вакол яго сыходзіць разам з ім. У дызасэмблеры гэтага main застаўся адзін цыкл і ніводнага згадвання byMul. На нулі ў мяне сышло паўгадзіны, перш чым я скеміў, што замяраю пусты цыкл.

Дзе відаць парог

Мне хацелася ўбачыць, як спрацоўвае лічыльнік на 10000. Тысяча выклікаў на раўнд даходзіць да яго прыкладна да дзясятага раўнда, таму я прагнаў дзвесце такіх раўндаў і стаў шукаць прыступку. Яна здарылася на раўндзе 76. Я запусціў тую ж каманду яшчэ раз і атрымаў 101, потым 66, потым 69, потым 91.

Рухаецца не лічыльнік. -Xbatch прымушае паток, які выклікае, дачакацца кампілятара замест чаргі. Пад гэтым сцягам прыступка ў кожным прагоне выпадае на раўнд 11. І яна пераязджае роўна туды, куды загадвае лічыльнік: CompileThreshold=20000 ставіць яе на раўнд 21, 5000 на раўнд 6, а пяцьсот выклікаў на раўнд вяртаюць яе на 21.

round 8   41 us
     51    1    b        Doubling::byMul (4 bytes)
round 9   2181 us
     53    2    b        Doubling::roundMul (47 bytes)
round 10   28 us
round 11   0 us

Раўнд 9 нясе 2181 мікрасекунду, бо byMul кампілюецца ўнутры замяранага цыкла. roundMul кампілюецца на ўваходзе ў раўнд 10, да старту таймера, таму яго ўласныя дзве мілісекунды нідзе не відаць. Раўнд 10 усё яшчэ інтэрпрэтуецца: лічыльнік спрацаваў на ўваходзе, а ўжо запушчаны кадр дасядае ў інтэрпрэтатары да канца. Раўнд 11 першы скампіляваны. Яго тысяча ітэрацый каштуе менш за мікрасекунду, што цэлалікавае дзяленне друкуе як нуль. Без сцяга код прыязджае тады, калі да яго дабярэцца паток кампілятара, тут гэта на пяцьдзясят-дзевяноста раўндаў пазней.

Лічыльнік спрацоўвае кожны раз на адным і тым жа раўндзе. Калі з’явіцца скампіляваны код, вырашае паток кампілятара. Тут гэта на пяцьдзясят-дзевяноста раўндаў пазней.

Чаго я не правяраў

Я мераў толькі * 2. Множанне на канстанту, якая не ступень двойкі, гэта асобнае пытанне. Множанне на зменную гэта яшчэ адно. Ні таго, ні другога я не адкрываў. Я збіраўся параўнаць кліенцкі кампілятар і выявіў, што ў гэтай 64-бітнай зборцы -client няма зусім. Гэта азначала б 32-бітны jdk. Туды я не пайшоў.

Каментар з рэв’ю быў справядлівы ў сваіх межах. Ён цэліў у той пласт, дзе розніца бачная вокам. На гэтай машыне пласт пад ім браў за той жа зыходнік у 70 разоў больш, пакуль да яго не дайшоў кампілятар. Я не ведаю, за колькі сапраўдны шлях запыту набірае 10000 выклікаў. Вось гэты лік мне і патрэбны наступным.