Когда я занялся изучением Java, одной из первых задач, которую я пытался решить было определение четных/нечетных чисел. Я знал несколько способов как это сделать, но решил поискать «правильный» способ на просторах интернета. Информация по всем найденным ссылкам говорила мне об единственно правильном решении вида x % 2, с целью получения остатка от деления. Если в остатке 0 — число четное, если в остатке 1 — нечетное.

Со времен ZX Spectrum я помнил еще один способ и он связан с представлением числа в двоичной системе. Любое число в десятичной системе можно записать как сумму степеней двойки. Например, для одного байта, а это 8 бит, любое число в десятичной системе может быть представлено как сумма чисел 128+64+32+16+8+4+2+1.

Это просто последовательность степеней двойки. При переводе числа в двоичную систему, если нам нужно учитывать число, в двоичном представлении это будет единица, если не нужно, то это будет 0.

Например:

10 = 1010 (8+0+2+0)
13 = 1101 (8+4+0+1)
200 = 11001000 (128+64+0+0+8+0+0+0)

Сразу можно обратить внимание на то, что нечетное число может дать только нулевая степень двойки со значением 1, все остальные степени двойки будут четные по определению. Это автоматически означает, что с точки зрения двоичной системы счисления, если мы хотим проверить любое число на четность, нам не нужно проверять все число, какое бы большое оно не было. Нам нужно проверить только первый бит (самый правый). Если он 0, то число четное, так как все остальные биты дают четное число, и наоборот, если в самом правом бите единица, то число гарантировано нечетное, потому что все остальные биты дают только четное значение.
Чтобы проверить только правый бит в числе, можно использовать несколько способов. Один из них бинарный AND.

AND


Бинарное И (AND) работает по следующему правилу. Если вы применяете к какому-либо числу, назовем его оригинальным, логическое AND с числом 0, то результат такой операции всегда 0. Таким образом можно обнулять ненужные вам биты. Если вы применяете к оригиналу 1, то вы получаете оригинал.

В двоичной системе это легко записать так:

0 AND 0 = 0 (обнуляем оригинал)
1 AND 0 = 0 (обнуляем оригинал)
0 AND 1 = 0 (не меняем оригинал)
1 AND 1 = 1 (не меняем оригинал)

Отсюда вытекают несколько простых правил.

Если мы к любому числу применим операцию AND всех единиц (все биты включены), то получим это же самое изначальное число.

Если мы к любому числу применим AND всех нолей (все биты выключены), то получим 0.

Например:

Если мы к байту 13 применим AND 0, то получим 0. В десятичном виде это выглядит как 13 AND 0 = 0

Если мы к байту 200 применим AND 0, то получим 0, или записывая кратко 200 AND 0 = 0
То же самое наоборот, применим к 13 все включенные биты, для байта это будет восемь единиц, и получим оригинал. В двоичной системе 00001101 AND 11111111 = 00001101 или в десятичной системе 13 AND 255 = 13

Для 200 будет соответственно 11001000 AND 11111111 = 11001000 или в десятичной системе 200 AND 255 = 200

Проверка бинарным способом


Для проверки числа на четность нам достаточно проверить только самый правый бит. Если он 0, то число четное, если 1, то не четное. Зная, что с помощью AND мы можем какие-то биты оставить оригинальными, а какие-то мы можем обнулить, мы можем просто обнулить все биты кроме самого правого. Например:

13 в двоичной системе это 1101. Применим к нему AND 0001 (обнуляем все биты, последний оставляем оригинальный). Меняем в числе 1101 все биты на 0 кроме последнего и получаем 0001. Мы получили только последний бит из нашего изначального числа. В десятичной системе это будет выглядеть как 13 AND 1 = 1.

То же самое с числом 200, в двоичном виде 11001000. Применим к нему AND 00000001, по той же схеме, обнуляем все биты, последний оставляем как есть, получаем 00000000, при этом левые 7 нулей мы обнулили командой AND, а последний 0 мы получили из оригинального числа. В десятичной системе это выглядит как 200 AND 1 = 0

Таким образом, применяя команду AND 1 к любому числу мы получаем, либо 0, либо 1. И если результат равен 0, то число четное. При 1 число нечетное.

В Java бинарное AND записывается как &. Соответственно, 200 & 1 = 0 (четное) и 13 & 1 = 1 (нечетное).

Отсюда вытекает, как минимум, два способа определения четных чисел.

X % 2 — через остаток от деления на два
X & 1 — через бинарное AND

Такие бинарные операции как OR, AND, XOR обрабатываются процессором за минимальное время. А вот операция деления это задача нетривиальная, и для того чтобы ее выполнить, процессору необходимо обработать множество инструкций, по сути выполнить целую программу. Однако, существуют операции бинарного сдвига влево и вправо, позволяющие, например, быстро делить число на 2. Вопрос в том, используют ли эту оптимизацию компиляторы и существует ли разница между этими двумя сравнениями, которые по факту делают то же самое.

Кодинг


Напишем программу, которая будет в цикле обрабатывать 9000000000 чисел по порядку, и определять их принадлежность к четному/нечетному через определение остатка от деления.

public class OddEvenViaMod {
        public static void main (String[] args) {
                long i=0;
                long odds=0;
                long evens=0;
                do {
                if ((i % 2) == 0) {
                        evens++;
                        }
                else {
                        odds++;
                        }
                i++;
                } while (i<9000000000L);
                System.out.println("Odd " + odds);
                System.out.println("Even " + evens);
        }
}

И напишем точно такую же, но поменяем буквально два символа, проверяя тоже самое через бинарное AND.

public class OddEvenViaAnd {
        public static void main (String[] args) {
                long i=0;
                long odds=0;
                long evens=0;
                do {
                if ((i & 1) == 0) {
                        evens++;
                        }
                else {
                        odds++;
                        }
                i++;
                } while (i<9000000000L);
                System.out.println("Odd " + odds);
                System.out.println("Even " + evens);

Теперь нам нужно как-то сравнить эти две программы.

Ресурсы в Linux. CPU


На создание любой операционной системы потрачено гигантское количество часов, в частности на честное распределение ресурсов между программами. С одной стороны это хорошо, так как запуская две программы, вы можете быть уверены, что они будут работать параллельно, но с другой стороны, когда вам нужно проверить производительность программы, бывает крайне необходимо ограничить или хотя бы уменьшить внешнее влияние на программу со стороны других программ и операционной системы.

Первое, с чем предстоит разобраться — это процессор. ОС Linux для каждого процесса хранит побитовую маску, в которой указано, какие ядра могут использоваться приложением, а какие нет. Посмотреть и поменять эту маску можно командой taskset.

Например, посмотрим количество ядер у моего процессора:

[user@localhost]# grep -c processor /proc/cpuinfo
4

В моем компьютере установлен процессор с 4-мя ядрами. Это хорошо, потому что одно из них я собираюсь выделить под свои нужды.

Посмотрим, все ли из них используются на данный момент, командой top:

[user@localhost]# top

Нажимаем «1», чтобы посмотреть информацию по каждому ядру отдельно:

top - 13:44:11 up 1 day, 23:26,  7 users,  load average: 1.48, 2.21, 2.02
Tasks: 321 total,   1 running, 320 sleeping,   0 stopped,   0 zombie
%Cpu0  :  7.7 us,  6.8 sy,  0.0 ni, 85.5 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu1  :  9.2 us,  4.2 sy,  0.0 ni, 86.6 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu2  :  7.6 us,  3.4 sy,  0.0 ni, 89.1 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu3  :  8.4 us,  4.2 sy,  0.0 ni, 87.4 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
KiB Mem : 16210820 total,   296972 free, 10072092 used,  5841756 buff/cache
KiB Swap: 16777212 total, 16777212 free,        0 used.  5480568 avail Mem
....

Тут мы видим, что все ядра используются примерно одинаково. (us и sy и id показатели примерно равны для каждого ядра).

Теперь попробуем посмотреть то же самое командой taskset.

[user@localhost]# taskset -p 1
pid 1's current affinity mask: f

Битовая маска «F» в шестнадцатеричной системе означает 15 в десятеричной, или 1111 в двоичной (8+4+2+1). Все биты включены, а значит все ядра используются процессом с PID 1.
В ОС Linux, когда один процесс порождает другой системным вызовом clone, то битовая маска на момент клонирования копируется с родителя. Это означает, что если мы поменяем эту маску для нашего init процесса (в моем случае это systemd), то при запуске любого нового процесса через systemd этот новый процесс будет запущен уже с новой маской.

Поменять маску для процесса можно этой же командой, перечислив номера ядер CPU, которые мы хотим оставить используемыми для процесса. Допустим, мы хотим оставить нашему процессу ядра 0,2,3, а ядро 1 мы хотим отключить для нашего systemd процесса. Для этого нам надо выполнить команду:

[user@localhost]#  taskset -pc 0,2,3 1
pid 1's current affinity list: 0-3
pid 1's new affinity list: 0,2,3

Проверяем:

[user@localhost]# taskset -p 1
pid 1's current affinity mask: d

Маска изменилась на «D» в шестнадцатеричной системе счисления, что равно 13 в десятеричной и равно 1101 в двоичной (8+4+0+1).

С этого момента любой процесс, который будет клонирован процессом systemd будет автоматически иметь маску 1101 использования CPU, а значит ядро с номером 1 использоваться не будет.

Запрещаем использование ядра всем процессам


Запрет основному процессу в Linux использования одного ядра отразится только на новых процессах, созданных этим процессом. Но у меня в системе уже не один процесс, а целое множество, такие как crond, sshd, bash и прочие. Если мне необходимо запретить всем процессам использования одного ядра, то я должен выполнить команду taskset для каждого запущенного процесса.

Для получения списка всех процессов воспользуемся API, которое нам дает ядро, а именно /proc файловая система.

Далее в цикле мы смотрим PID каждого запущенного процесса и меняем для него и всех тредов маску:

[user@localhost]# cd /proc; for i in `ls -d [0-9]*`; do taskset -a -pc 0,2,3 $i; done
pid 1's current affinity list: 0,2,3
pid 1's new affinity list: 0,2,3
...

Так как в ходе выполнения программы, какие-то процессы могли успеть породить другие процессы, то лучше эту команду запустить несколько раз.

Проверим результат нашей работы командой top:

[user@localhost]# top
top - 14:20:46 up 2 days, 3 min,  7 users,  load average: 0.19, 0.27, 0.57
Tasks: 324 total,   4 running, 320 sleeping,   0 stopped,   0 zombie
%Cpu0  :  8.9 us,  7.7 sy,  0.0 ni, 83.4 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu1  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu2  :  9.5 us,  6.0 sy,  0.0 ni, 84.5 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu3  :  8.4 us,  6.6 sy,  0.0 ni, 85.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
KiB Mem : 16210820 total,   285724 free, 10142548 used,  5782548 buff/cache
KiB Swap: 16777212 total, 16777212 free,        0 used.  5399648 avail Mem

Как видим картина немного поменялась, теперь для ядра 0,2,3 в среднем параметры us,sy,id у нас одинаковые, а для ядра 1 наше потребление ядра в userspace и sys равно 0, и ядро простаивает на все 100% (idle 100). Ядро 1 более не используется нашими приложениями и на очень небольшой процент используется на данный момент ядром.

Теперь задача тестирования производительности сводится к тому, чтобы запустить наш процесс на свободном ядре.

Память


Выделенная процессу физическая память может быть легко отнята у любого процесса. Этот механизм называется swap. Если ОС Linux имеет место для swap, она будет это делать в любом случае. Единственный способ запретить ОС отнимать память у нашего процесса, как и у любых других процессов, это полностью отключить раздел swap, что мы и сделаем:

[user@localhost]$ sudo swapoff -a
[user@localhost]$ free -m
              total        used        free      shared  buff/cache   available
Mem:          15830        7294        1894         360        6641        7746
Swap:             0           0           0

Мы выделили 1 ядро процессора, которое не используется, и так же убрали у ядра Linux возможность делать swap памяти.

Диск


Для того чтобы снизить влияние диска на запуск нашего процесса, создадим диск в памяти и скопируем все необходимые файлы на этот диск.

Создаем директорию и монтируем файловую систему:

[user@localhost]$ sudo mkdir /mnt/ramdisk;
[user@localhost]$ mount -t tmpfs -o size=512m tmpfs /mnt/ramdisk
[user@localhost]$ chown user: /mnt/ramdisk

Теперь надо разобраться с тем, что и как мы планируем запускать. Для того чтобы запустить нашу программу нам надо для начала откомпилировать наш код:

[user@localhost]$ javac OddEvenViaMod.java

Затем надо запустить его:

[user@localhost]$ java OddEvenViaMod

Но в нашем случае мы хотим запустить процесс на том ядре процессора, который не используется никаким другим процессом. Поэтому запускаем его через taskset:

[user@localhost]# taskset -c 1 time java OddEvenViaMod

В наших тестах нам необходимо замерять время, поэтому наша строка запуска превращается в

taskset -c 1 time java OddEvenViaMod

ОС Linux поддерживает несколько форматов запускаемых файлов, и самый распространённый из них ELF формат. Этот формат файла позволяет сказать ОС, чтобы она не запускала ваш файл, а запустила другой файл. На первый взгляд звучит не очень логично и понятно. Представим, что я запускаю игру Сапер, а запускается у меня игра Марио — это выглядит как вирус. Но в этом есть логика. Если моя программа требует какую-либо динамическую библиотеку, например libc, или же любую другую, это означает, что ОС должна сначала загрузить эту библиотеку в память, а уже после этого загрузить и запустить мою программу. И вроде бы логично такой функционал поместить в саму операционную систему, но операционная система работает в защищенной области памяти и должна содержать в себе настолько мало функционала, насколько это возможно и необходимо. Поэтому ELF формат предусматривает возможность сказать ОС, что мы хотим загрузить некую другую программу, а уже эта «другая» программа загрузит все необходимые библиотеки и нашу программу и запустит все это дело.

Итак, нам необходимо запустить 3 файла, это taskset, time, java.

Проверим первый из них:

[user@localhost]$ whereis taskset
taskset: /usr/bin/taskset /usr/share/man/man1/taskset.1.gz

Bash будет запускать файл /usr/bin/taskset, проверяем что внутри:

[user@localhost]$ file /usr/bin/taskset
/usr/bin/taskset: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=7a2fd0779f64aa9047faa00f498042f0f0c5dc60, stripped

Это ELF файл, о котором я писал выше. В ELF файле помимо самой программы присутствуют различные заголовки. Запуская этот файл ОС проверяет его заголовки, и если в файле существует заголовок «Requesting program interpreter», то ОС запустит файл именно из этого заголовка, а изначально запускаемый файл передаст в качестве аргумента.

Проверяем, существует ли в нашем ELF файле этот заголовок:

[user@localhost]$ readelf -a /usr/bin/taskset  | grep -i interpreter
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]

Заголовок существует, а это значит, что запуская файл /usr/bin/taskset на самом деле мы запускаем /lib64/ld-linux-x86-64.so.2.

Проверим, что это за файл:

[user@localhost]$ ls -lah /lib64/ld-linux-x86-64.so.2
lrwxrwxrwx 1 root root 10 May 21  2019 /lib64/ld-linux-x86-64.so.2 -> ld-2.17.so

Это сим линк на файл /lib64/ld-2.17.so. Проверяем его:

[user@localhost]$ file /lib64/ld-2.17.so
/lib64/ld-2.17.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=a527fe72908703c5972ae384e78d1850d1881ee7, not stripped

Как видим это другой ELF файл, который ОС будет запускать. Смотрим заголовки у него:

[user@localhost]$ readelf -a /lib64/ld-2.17.so  | grep -i interpreter
[user@localhost]$

Видим, что у этого ELF файла такого заголовка нет, значит ОС запустит этот файл и передаст управление ему. А уже этот файл откроет наш файл /usr/bin/taskset, прочитает оттуда информацию по всем необходимым библиотекам. Список необходимых библиотек так же находится в заголовках ELF файла. Мы можем посмотреть этот список командой ldd или readelf, что одно и то же:

[user@localhost]$ ldd /usr/bin/taskset
	linux-vdso.so.1 =>  (0x00007ffc4c1df000)
	libc.so.6 => /lib64/libc.so.6 (0x00007f4a24c4e000)
	/lib64/ld-linux-x86-64.so.2 (0x00007f4a2501b000)

[user@localhost]$ readelf -a /usr/bin/taskset  | grep NEEDED
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]

VDSO — это прилинкованный участок памяти не относящийся к библиотекам, потому отсутствует в ELF файле в качестве необходимой библиотеки.

Отсюда понятно, что программа /lib64/ld-2.17.so ответственна за запуск всех программ, которые ее требуют, а это все программы с динамически прилинкованными библиотеками.

Если мы запускаем /usr/bin/taskset — это абсолютно то же самое, что мы запустим /lib64/ld-2.17.so с агрументом /usr/bin/taskset.

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

[user@localhost]$ cp /lib64/libc-2.17.so /mnt/ramdisk/
[user@localhost]$ cp /lib64/ld-2.17.so /mnt/ramdisk/
[user@localhost]$ cp /usr/bin/taskset /mnt/ramdisk/

То же самое делаем для time, требования к библиотекам у которой точно такие же (ld и libc мы уже скопировали).

[user@localhost]$ cp /usr/bin/time /mnt/ramdisk/

Для java все немного сложнее, так как java требует много различных библиотек, которые можно долго копировать. Чтобы немного упростить себе жизнь, я скопирую всю директорию с моей java openjdk на диск в памяти и создам сим линк. Безусловно, обращения к диску в таком случае останутся, но их будет меньше.

[user@localhost]$ cp -R /usr/lib/jvm/java-1.8.0-openjdk-1.8.0.222.b10-0.el7_6.x86_64 /mnt/ramdisk/

Переименуем старую директорию, добавляя ей окончание .default

[user@localhost]$ sudo mv /usr/lib/jvm/java-1.8.0-openjdk-1.8.0.222.b10-0.el7_6.x86_64{,.default}

И создадим симлинк:

[user@localhost]$ sudo ln -s /mnt/ramdisk/java-1.8.0-openjdk-1.8.0.222.b10-0.el7_6.x86_64 /usr/lib/jvm/

Как запустить бинарный файл мы уже знаем, через аргумент к файлу /lib64/ld-2.17.so, который запускается на самом деле. Но как заставить программу /lib64/ld-2.17.so загружать подгружаемые библиотеки из указанной нами директории? man ld нам в помощь, из которого мы узнаем, что если объявить переменную окружения LD_LIBRARY_PATH, то программа ld будет подгружать библиотеки из указанных нами директорий. Теперь у нас есть все данные чтобы подготовить строку запуска Java приложения.

Запускаем несколько раз подряд и проверяем:

[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod
Odd 4500000000
Even 4500000000
10.66user 0.01system 0:10.67elapsed 99%CPU (0avgtext+0avgdata 20344maxresident)k
0inputs+64outputs (0major+5229minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod
Odd 4500000000
Even 4500000000
10.65user 0.01system 0:10.67elapsed 99%CPU (0avgtext+0avgdata 20348maxresident)k
0inputs+64outputs (0major+5229minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod
Odd 4500000000
Even 4500000000
10.66user 0.01system 0:10.68elapsed 99%CPU (0avgtext+0avgdata 20348maxresident)k
0inputs+64outputs (0major+5229minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod
Odd 4500000000
Even 4500000000
10.65user 0.01system 0:10.67elapsed 99%CPU (0avgtext+0avgdata 20348maxresident)k
0inputs+96outputs (0major+5234minor)pagefaults 0swaps
[user@localhost ramdisk]$

В ходе выполнения программы, мы можем запустить top и убедиться, что программа работает на нужном ядре CPU.

[user@localhost ramdisk]$ top
...
%Cpu0  : 19.7 us, 11.7 sy,  0.0 ni, 68.6 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu1  :100.0 us,  0.0 sy,  0.0 ni,  0.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu2  :  9.8 us,  9.1 sy,  0.0 ni, 81.1 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu3  : 14.0 us,  9.0 sy,  0.0 ni, 77.1 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 s
...

Как видим результаты в большинстве случаев похожи. К сожалению, влияние ОС на ядро CPU полностью убрать мы не можем, поэтому результат все еще зависит от конкретных задач внутри ядра Linux на момент запуска. Поэтому лучше использовать медиану значений нескольких запусков.

В нашем случае мы видим, что программа на java обрабатывает 9000000000 с проверкой на четность через остаток от деления за 10.65 секунд на одном ядре CPU.

Проведем этот же тест с нашей второй программой, которая делает то же самое через бинарное AND.

[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd
Odd 4500000000
Even 4500000000
4.02user 0.00system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20224maxresident)k
0inputs+64outputs (0major+5197minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd
Odd 4500000000
Even 4500000000
4.01user 0.00system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20228maxresident)k
0inputs+64outputs (0major+5199minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd
Odd 4500000000
Even 4500000000
4.01user 0.01system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20224maxresident)k
0inputs+64outputs (0major+5198minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd
Odd 4500000000
Even 4500000000
4.02user 0.00system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20224maxresident)k
0inputs+64outputs (0major+5198minor)pagefaults 0swaps

Теперь мы можем с уверенностью сказать, что сравнение на четность через бинарное AND занимает 4.02 секунды, а значит по сравнению с проверкой через остаток от деления, работает в 2.6 раза быстрее, как минимум на openjdk версии 1.8.0.

Oracle Java vs Openjdk


Я загрузил и распаковал java jdk с сайта oracle в директорию /mnt/ramdisk/jdk-13.0.2

Компилируем:

[user@localhost ramdisk]$ /mnt/ramdisk/jdk-13.0.2/bin/javac OddEvenViaAnd.java

Запускаем:

[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaAnd
Odd 4500000000
Even 4500000000
10.39user 0.01system 0:10.41elapsed 99%CPU (0avgtext+0avgdata 24260maxresident)k
0inputs+64outputs (0major+6979minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaAnd
Odd 4500000000
Even 4500000000
10.40user 0.01system 0:10.42elapsed 99%CPU (0avgtext+0avgdata 24268maxresident)k
0inputs+64outputs (0major+6985minor)pagefaults 0swaps

Компилируем вторую программу:

[user@localhost ramdisk]$ /mnt/ramdisk/jdk-13.0.2/bin/javac OddEvenViaMod.java

Запускаем:

[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaMod
Odd 4500000000
Even 4500000000
10.39user 0.01system 0:10.40elapsed 99%CPU (0avgtext+0avgdata 24324maxresident)k
0inputs+96outputs (0major+7003minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaMod
Odd 4500000000
Even 4500000000
10.40user 0.00system 0:10.41elapsed 99%CPU (0avgtext+0avgdata 24316maxresident)k
0inputs+64outputs (0major+6992minor)pagefaults 0swaps

Время выполнения тех же исходников в jdk от oracle одинаковое для остатка от деления и бинарного AND, что выглядит нормальным, но это время одинаково плохое, которое было показано в openjdk на остатке от деления.

Python


Попробуем сравнить то же самое на языке Python. Сначала вариант с остатком от деления на 2:

odd=0
even=0
for i in xrange(100000000):
	if i % 2 == 0:
		even += 1
	else:
		odd += 1
print "even", even
print "odd", odd

Запускаем:

[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_mod.py
even 50000000
odd 50000000
11.69user 0.00system 0:11.69elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k
0inputs+0outputs (0major+1220minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_mod.py
even 50000000
odd 50000000
11.67user 0.00system 0:11.67elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k
0inputs+0outputs (0major+1220minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_mod.py
even 50000000
odd 50000000
11.66user 0.00system 0:11.66elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k
0inputs+0outputs (0major+1220minor)pagefaults 0swaps

Теперь тоже самое с бинарным AND:

odd=0
even=0
for i in xrange(100000000):
	if i & 1 == 0:
		even += 1
	else:
		odd += 1
print "even", even
print "odd", odd

Запускаем:

[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and.py
even 50000000
odd 50000000
10.41user 0.00system 0:10.41elapsed 99%CPU (0avgtext+0avgdata 4588maxresident)k
0inputs+0outputs (0major+1221minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and.py
even 50000000
odd 50000000
10.43user 0.00system 0:10.43elapsed 99%CPU (0avgtext+0avgdata 4588maxresident)k
0inputs+0outputs (0major+1222minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and.py
even 50000000
odd 50000000
10.43user 0.00system 0:10.43elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k
0inputs+0outputs (0major+1222minor)pagefaults 0swaps

Результаты показывают, что AND быстрее.

На просторах интернета уже много раз писали, что глобальные переменные в Python работают медленней. Я решил сравнить время выполнения последней программы с AND и точно такой же, но обернутой в функцию:

def main():
	odd=0
	even=0
	for i in xrange(100000000):
		if i & 1 == 0:
			even += 1
		else:
			odd += 1
	print "even", even
	print "odd", odd

main()

Запускаем в функции:

[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and_func.py
even 50000000
odd 50000000
5.08user 0.00system 0:05.08elapsed 99%CPU (0avgtext+0avgdata 4592maxresident)k
0inputs+0outputs (0major+1222minor)pagefaults 0swaps
[user@localhost ramdisk]$
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and_func.py
even 50000000
odd 50000000
5.08user 0.00system 0:05.09elapsed 99%CPU (0avgtext+0avgdata 4592maxresident)k
0inputs+0outputs (0major+1223minor)pagefaults 0swaps

Как видим, одно и тоже сравнение на четность в Python через бинарное AND в функции обрабатывается 100000000 чисел на одном ядре CPU за ~ 5 секунд, такое же сравнение через AND без функции занимает ~ 10 секунд, и сравнение без функции через остаток от деления занимает ~ 11 секунд.

Почему Python программа в функции работает быстрее чем без нее, уже описывалось не раз и связанно с областью видимости переменных.

В Python есть возможность дизассемблировать программу на внутренние функции, которые Python использует при интерпретировании программы. Посмотрим какие функции использует Python для варианта с функцией odd_and_func.py:

[user@localhost ramdisk]# python
Python 2.7.5 (default, Jun 20 2019, 20:27:34)
[GCC 4.8.5 20150623 (Red Hat 4.8.5-36)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> def main():
...     odd=0
...     even=0
...     for i in xrange(100000000):
...             if i & 1 == 0:
...                     even += 1
...             else:
...                     odd += 1
...     print "even", even
...     print "odd", odd
...
>>> import dis
>>> dis.dis(main)
  2           0 LOAD_CONST               1 (0)
              3 STORE_FAST               0 (odd)

  3           6 LOAD_CONST               1 (0)
              9 STORE_FAST               1 (even)

  4          12 SETUP_LOOP              59 (to 74)
             15 LOAD_GLOBAL              0 (xrange)
             18 LOAD_CONST               2 (100000000)
             21 CALL_FUNCTION            1
             24 GET_ITER
        >>   25 FOR_ITER                45 (to 73)
             28 STORE_FAST               2 (i)

  5          31 LOAD_FAST                2 (i)
             34 LOAD_CONST               3 (1)
             37 BINARY_AND
             38 LOAD_CONST               1 (0)
             41 COMPARE_OP               2 (==)
             44 POP_JUMP_IF_FALSE       60

  6          47 LOAD_FAST                1 (even)
             50 LOAD_CONST               3 (1)
             53 INPLACE_ADD
             54 STORE_FAST               1 (even)
             57 JUMP_ABSOLUTE           25

  8     >>   60 LOAD_FAST                0 (odd)
             63 LOAD_CONST               3 (1)
             66 INPLACE_ADD
             67 STORE_FAST               0 (odd)
             70 JUMP_ABSOLUTE           25
        >>   73 POP_BLOCK

  9     >>   74 LOAD_CONST               4 ('even')
             77 PRINT_ITEM
             78 LOAD_FAST                1 (even)
             81 PRINT_ITEM
             82 PRINT_NEWLINE

 10          83 LOAD_CONST               5 ('odd')
             86 PRINT_ITEM
             87 LOAD_FAST                0 (odd)
             90 PRINT_ITEM
             91 PRINT_NEWLINE
             92 LOAD_CONST               0 (None)
             95 RETURN_VALUE

И проверим то же самое без использования функции в нашем коде:

>>> f=open("odd_and.py","r")
>>> l=f.read()
>>>
>>> l
'odd=0\neven=0\nfor i in xrange(100000000):\n\tif i & 1 == 0:\n\t\teven += 1\n\telse:\n\t\todd += 1\nprint "even", even\nprint "odd", odd\n'
>>> k=compile(l,'l','exec')
>>> k
<code object <module> at 0x7f2bdf39ecb0, file "l", line 1>
>>> dis.dis(k)
  1           0 LOAD_CONST               0 (0)
              3 STORE_NAME               0 (odd)

  2           6 LOAD_CONST               0 (0)
              9 STORE_NAME               1 (even)

  3          12 SETUP_LOOP              59 (to 74)
             15 LOAD_NAME                2 (xrange)
             18 LOAD_CONST               1 (100000000)
             21 CALL_FUNCTION            1
             24 GET_ITER
        >>   25 FOR_ITER                45 (to 73)
             28 STORE_NAME               3 (i)

  4          31 LOAD_NAME                3 (i)
             34 LOAD_CONST               2 (1)
             37 BINARY_AND
             38 LOAD_CONST               0 (0)
             41 COMPARE_OP               2 (==)
             44 POP_JUMP_IF_FALSE       60

  5          47 LOAD_NAME                1 (even)
             50 LOAD_CONST               2 (1)
             53 INPLACE_ADD
             54 STORE_NAME               1 (even)
             57 JUMP_ABSOLUTE           25

  7     >>   60 LOAD_NAME                0 (odd)
             63 LOAD_CONST               2 (1)
             66 INPLACE_ADD
             67 STORE_NAME               0 (odd)
             70 JUMP_ABSOLUTE           25
        >>   73 POP_BLOCK

  8     >>   74 LOAD_CONST               3 ('even')
             77 PRINT_ITEM
             78 LOAD_NAME                1 (even)
             81 PRINT_ITEM
             82 PRINT_NEWLINE

  9          83 LOAD_CONST               4 ('odd')
             86 PRINT_ITEM
             87 LOAD_NAME                0 (odd)
             90 PRINT_ITEM
             91 PRINT_NEWLINE
             92 LOAD_CONST               5 (None)
             95 RETURN_VALUE

Как видим, в варианте с объявленной функцией, Python использует внутренние функции с постфиксом FAST, например STORE_FAST, LOAD_FAST, а в варианте без объявления функции, Python использует внутренние функции STORE_NAME и LOAD_NAME.

Данная статья имеет мало практического смысла и нацелена скорее на понимание некоторых особенностей Linux, и компиляторов.

Всем добра!