Тестирование производительности кода в ОС Linux с примерами

    Когда я занялся изучением 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, и компиляторов.

    Всем добра!
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 8

      +1

      У меня сложилось впечатление, что так много шагов потребовалось, потому что вы мерили не то, что действительно хотели. Хотели померить, какая реализация функции быстрее, а стали мерить все, включая запуск программы. Из-за этого вы очень много боролись с ядром, когда этого не требовалось. Например, копировали файлы в рамдиск, хотя после первого чтения они попадут в файловый кэш и не будут читаться с диска. Искали самый ненагруженный cpu и планировали задачу именно на него и раскидывали с него все остальные существующие userspace процессы на другие cpu — это же сделает планировщик задач при большой нагрузке. И ядро все еще может вытеснить ваш процесс. И если процесс не бездействует, а вы не запускаете другие ресурсоемкие процессы, то вероятность того, что его память будет вытеснена в swap нулевая.


      А могли бы просто старым-добрым способом узнать время перед выполнением функции, прогнать ее множество раз, узнать время, рассчитать дельту. Сделать множество таких замеров и взять минимальное значение — тогда получите максимально правдоподобное значение, которое только возможно получить на системе общего назначения.


      Иногда действительно есть смысл отобрать у планировщика несколько ядер для ресурсоемких вычислений. И это можно сделать даже так, что и ядерные потоки не будут планироваться на эти ядра — это параметр isolcpus. Тогда ваши задачи не сможет вытеснить никто, даже ядро. Правда, если у вас несколько таких изолированных процессов, то и балансировкой этих процессов между изолированными ядрами никто заниматься не будет.

        +1
        Ваша статья явно не для понедельника.
        Не понял заморочки с ramdisk.
        Почему бы включить код непосредственно в ядро как статический модуль?
          0
          Хорошая мысля приходит опосля.
          Так и надо было делать!
          Пишется модуль на Си.
          Модуль включается в статический список и mkinitcpio собирает ядро.
          Потом создаётся qemu-виртуалка с ограниченными ресурсами.
          В ней загружается ядро в single user mode.
          Песочница для запуска готова.
          Только меня смущает использование time, не слишком ли высокоуровневая тулза?!
          0
          Не учтена (не указана или не увидел) область применимости исследования. Имхо, битовые операции — только для целых типов. В области вещественных все немного интереснее… И ещё нюанс: правый бит — только для целых положительных (беззнаковых), а есть ещё и отрицательные (дополнительный код: -2=0b1111111111111110).
            0
            Есть определенные сомнения, что вещественные числа могут быть четными.
              0
              Это в теории, а на практике — бухгалтерии это докажите :)
                0

                А можно примеров из практики?

            0

            Статья хороша как ликбез по Linux — лично я почерпнул что-то новое, за что благодарен автору.


            Но вот именно решение задачи, на примере которой проводились бенчмарки, заставляет немного поволноваться. Причина возможного беспокойства — то, что определение чётности-нечётности работает только для two's complement целых чисел, представленных в памяти последовательностью битов. Здесь есть две вещи которые могу пойти не так:


            • Представление целых чисел со знаком в системе может быть в форме one's complement, при которой отлицательные числа инвертируются (00000001 (+1) -> 11111110 (-1)), что делает невозможным и некорректным определение чётности через бинарное AND единицы с младшим битом. Да, здесь можно справедливо заявить, что one's complement представление уже никем не используется, но нет, и нет. Вероятность мала, но она есть.
            • Числа в используемом языке/библиотеке/whatever могут представляться ну совсем не в виде последовательности битов ограниченной длины. В Common Lisp, который я всей душой люблю, в том числе за его систему типов, нет чётко специфицированного метода хранения bignum-ов, и число может, в зависимости от реализации языка, храниться даже в куче, по частям. Операции же над отдельными битами bignum-ов, в силу их реализации, часто превращаются в непредсказуемые числа, потому что программист мог не учитывать, к примеру, нули в начале числа, коих много, и получить при их инвертировании, к примеру, негативный ответ (вспоминаем, как работает two's complement и one's complement представление). Может случиться и такое, что определённая реализация определённого языка будет использовать младшие биты числа для какой-то своей нужды (что звучит подозрительно, но не значит, что кто-то так не сделает), а не для представления, собственно, низших битов числа, и при этом сможет допустить прямое взаимодействие с ними (нет программ без багов — есть только те, где их пока что не нашли).

            Все эти риски могут рано или поздно выстрелить, потому рекомендация использовать модуло в общем случае для определения чётности относительно оправдана.

            Only users with full accounts can post comments. Log in, please.