Почему тернарный оператор с двумя константами быстрее, чем оператор с переменной? - PullRequest
Новая
       4

Почему тернарный оператор с двумя константами быстрее, чем оператор с переменной?

11 голосов
/ 16 июня 2020

В Java у меня есть два разных оператора, которые достигают sh одного и того же результата с помощью тернарных операторов, а именно:

  1. num < 0 ? 0 : num;
  2. num * (num < 0 ? 0 : 1);

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

final long startTime = System.currentTimeMillis();

Random rand = new Random();
float[] results = new float[100000000];
for (int i = 0; i < 100000000; i++) {
    float num = (rand.nextFloat() * 2) - 1;
    results[i] = num < 0 ? 0 : num;
    //results[i] = num * (num < 0 ? 0 : 1);
}

final long endTime = System.currentTimeMillis();

System.out.println("Total Time: " + (endTime - startTime));
  1. 1,232 секунды
  2. 1,023 секунды (каждое среднее по 5 запускам)

Почему при использовании второго оператора происходит такое значительное ускорение? Кажется, включает ненужное умножение и такое же сравнение. Первый создает ветвь, а второй - нет?

Ответы [ 3 ]

14 голосов
/ 21 июня 2020

Во-первых, давайте перепишем тест с JMH , чтобы избежать распространенных ошибок тестирования . 

public class FloatCompare {

    @Benchmark
    public float cmp() {
        float num = ThreadLocalRandom.current().nextFloat() * 2 - 1;
        return num < 0 ? 0 : num;
    }

    @Benchmark
    public float mul() {
        float num = ThreadLocalRandom.current().nextFloat() * 2 - 1;
        return num * (num < 0 ? 0 : 1);
    }
}

JMH также предполагает, что код умножения работает намного быстрее: 

Benchmark         Mode  Cnt   Score   Error  Units
FloatCompare.cmp  avgt    5  12,940 ± 0,166  ns/op
FloatCompare.mul  avgt    5   6,182 ± 0,101  ns/op

Теперь пора задействовать perfasm profiler (встроенный в JMH), чтобы увидеть сборку, созданную JIT-компилятором. Вот наиболее важные части вывода (комментарии мои):

cmp метод: 

  5,65%  │││  0x0000000002e717d0: vxorps  xmm1,xmm1,xmm1  ; xmm1 := 0
  0,28%  │││  0x0000000002e717d4: vucomiss xmm1,xmm0      ; compare num < 0 ?
  4,25%  │╰│  0x0000000002e717d8: jbe     2e71720h        ; jump if num >= 0
  9,77%  │ ╰  0x0000000002e717de: jmp     2e71711h        ; jump if num < 0

mul метод: 

  1,59%  ││  0x000000000321f90c: vxorps  xmm1,xmm1,xmm1    ; xmm1 := 0
  3,80%  ││  0x000000000321f910: mov     r11d,1h           ; r11d := 1
         ││  0x000000000321f916: xor     r8d,r8d           ; r8d := 0
         ││  0x000000000321f919: vucomiss xmm1,xmm0        ; compare num < 0 ?
  2,23%  ││  0x000000000321f91d: cmovnbe r11d,r8d          ; r11d := r8d if num < 0
  5,06%  ││  0x000000000321f921: vcvtsi2ss xmm1,xmm1,r11d  ; xmm1 := (float) r11d
  7,04%  ││  0x000000000321f926: vmulss  xmm0,xmm1,xmm0    ; multiply

Ключевое отличие состоит в том, что в методе mul нет инструкций перехода. Вместо этого используется инструкция условного перемещения cmovnbe.

cmov работает с целочисленными регистрами. Поскольку выражение (num < 0 ? 0 : 1) использует целочисленные константы с правой стороны, JIT достаточно умен, чтобы генерировать условное перемещение вместо условного перехода.

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

Если мы изменим тест таким образом, чтобы одна ветвь преобладала над другой, например, заменив 

ThreadLocalRandom.current().nextFloat() * 2 - 1

на 

ThreadLocalRandom.current().nextFloat() * 2 - 0.1f

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

Benchmark         Mode  Cnt  Score   Error  Units
FloatCompare.cmp  avgt    5  5,793 ± 0,045  ns/op
FloatCompare.mul  avgt    5  5,764 ± 0,048  ns/op
4 голосов
/ 21 июня 2020
• 1000 целочисленные константы. В C этот конкретный код можно переписать как !(num < 0). Это преобразование может создать код без ветвей, который превзойдет код ветвления, сгенерированный для (num < 0 ? 0 : num) на современных процессорах, даже с дополнительным кодом операции умножения. Обратите внимание, однако, что довольно легко создать код без ветвей и для (num < 0 ? 0 : num), а вот компилятор / JIT-генератор java этого не сделает.
2 голосов
/ 21 июня 2020

Я обнаружил, почему второе утверждение занимает больше времени, но я не могу объяснить, почему это происходит, если это имеет смысл. Тем не менее, я считаю, что это должно дать более полное представление о проблеме, которая у нас есть. переменная из тернарной операции. Он имеет прямое отношение к возврату целого числа или числа с плавающей запятой из тернарной операции. Это сводится к следующему: возврат числа с плавающей запятой из тернарной операции «значительно» медленнее, чем возврат целого числа.

Я не могу объяснить почему, но, по крайней мере, это root причина.

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

        Random rand = new Random();
        final int intOne = 1;
        final int intZero = 0;
        final float floatOne = 1f;
        final float floatZero = 0f;

        final long startTime = System.nanoTime();

        float[] results = new float[100000000];
        for (int i = 0; i < 100000000; i++) {
            float num = (rand.nextFloat() * 2) - 1;
//            results[i] = num < 0 ? 0 : num;
//            results[i] = num * (num < 0 ? 0 : 1);

//            results[i] = num < 0 ? 0 : 1;
//            results[i] = (num < 0 ? 0 : 1);
//            results[i] = (num < 0 ? 0 : num);
//            results[i] = 1 * (num < 0 ? 0 : num);

//            results[i] = num < 0 ? 0 : one;
//            results[i] = num < 0 ? 0 : 1f;
//            results[i] = (num < 0 ? 0 : one);
//            results[i] = (num < 0 ? 0 : 1f);
//            results[i] = (num < 0 ? 0 : 1);

//            results[i] = (num < 0 ? 0f : 1f);
//            results[i] = (num < 0 ? 0 : 1);
//            results[i] = (num < 0 ? floatZero : floatOne);
//            results[i] = (num < 0 ? intZero : intOne);

//            results[i] = num < 0 ? intZero : intOne;

//            results[i] = num * (num < 0 ? 0 : 1);
//            results[i] = num * (num < 0 ? 0f : 1f);
//            results[i] = num < 0 ? 0 : num;
        }

        final long endTime = System.nanoTime();

        String str = (endTime - startTime) + "\n";
        System.out.println(str);
        Files.write(Paths.get("test.txt"), str.getBytes(), StandardOpenOption.APPEND);

По причинам, go я не буду вдаваться в это сейчас, но вы можете прочитать про здесь , я использовал nanoTime() вместо currentTimeMillis(). Последняя строка просто добавляет полученное значение времени к текстовому документу, чтобы я мог легко добавлять комментарии.

Вот последний текстовый документ, он включает в себя весь процесс того, как я пришел к такому выводу: 


    num < 0 ? 0 : num       // standard "intuitive" operation
    1576953800
    1576153599
    1579074600
    1564152100
    1571285399
    
    num * (num < 0 ? 0 : 1)    // strange operation that is somehow faster
    1358461100
    1347008700
    1356969200
    1343784400
    1336910000
    
    // let's remove the multiplication and focus on the ternary operation
    
    num < 0 ? 0 : 1     // without the multiplication, it is actually slower...?
    1597369200
    1586133701
    1596085700
    1657377000
    1581246399
    
    (num < 0 ? 0 : 1)     // Weird, adding the brackets back speeds it up
    1797034199
    1294372700
    1301998000
    1286479500
    1326545900
    
    (num < 0 ? 0 : num)     // adding brackets to the original operation does NOT speed it up.
    1611220001
    1585651599
    1565149099
    1728256000
    1590789800
    
    1 * (num < 0 ? 0 : num)    // the speedup is not simply from multiplication
    1588769201
    1587232199
    1589958400
    1576397900
    1599809000
    
    // Let's leave the return value out of this now, we'll just return either 0 or 1.
    
    num < 0 ? 0 : one  // returning 1f, but from a variable
    1522992400
    1590028200
    1605736200
    1578443700
    1625144700
    
    num < 0 ? 0 : 1f   // returning 1f as a constant
    1583525400
    1570701000
    1577192000
    1657662601
    1633414701
    
    // from the last 2 tests we can assume that returning a variable or returning a constant has no significant speed difference.
    // let's add the brackets back and see if that still holds up.
    
    (num < 0 ? 0 : floatOne)  // 1f as variable, but with ()
    1573152100
    1521046800
    1534993700
    1630885300
    1581605100
    
    (num < 0 ? 0 : 1f)  // 1f as constant, with ()
    1589591100
    1566956800
    1540122501
    1767168100
    1591344701
    // strangely this is not faster, where before it WAS. The only difference is that I now wrote 1f instead of 1.
    
    (num < 0 ? 0 : 1)  // lets replace 1f with 1 again, then.
    1277688700
    1284385000
    1291326300
    1307219500
    1307150100
    // the speedup is back!
    // It would seem the speedup comes from returning an integer rather than a float. (and also using brackets around the operation.. somehow)
    
    // Let's try to confirm this by replacing BOTH return values with floats, or integers.
    // We're also keeping the brackets around everything, since that appears to be required for the speedup
    
    (num < 0 ? 0f : 1f)
    1572555600
    1583899100
    1595343300
    1607957399
    1593920499
    
    (num < 0 ? 0 : 1)
    1389069400
    1296926500
    1282131801
    1283952900
    1284215401
    
    // looks promising, now lets try the same but with variables
    // final int intOne = 1;
    // final int intZero = 0;
    // final float floatOne = 1f;
    // final float floatZero = 0f;
    
    (num < 0 ? floatZero : floatOne)
    1596659301
    1600570100
    1540921200
    1582599101
    1596192400
    
    (num < 0 ? intZero : intOne)
    1280634300
    1300473900
    1304816100
    1285289801
    1286386900
    
    // from the looks of it, using a variable or constant makes no significant difference, it definitely has to do with the return type.
    
    // That said, this is still only noticeable when using brackets around the operation, without them the int operation is still slow:
    
    num < 0 ? intZero : intOne
    1567954899
    1565483600
    1593726301
    1652833999
    1545883500
    
    // lastly, lets add the multiplication with num back, knowing what we know now.
    
    num * (num < 0 ? 0 : 1)    // the original fast operation, note how it uses integer as return type.
    1379224900
    1333161000
    1350076300
    1337188501
    1397156600
    
    results[i] = num * (num < 0 ? 0f : 1f)  // knowing what we know now, using floats should be slower again.
    1572278499
    1579003401
    1660701999
    1576237400
    1590275300
    // ...and it is.
    
    // Now lets take a look at the intuitive solution
    
    num < 0 ? 0 : num      // the variable num is of type float. returning a float from a ternary operation is slower than returning an int.
    1565419400
    1569075400
    1632352999
    1570062299
    1617906200

Все это по-прежнему вызывает вопрос: Почему тернарная операция, возвращающая float, медленнее, чем операция, возвращающая int? И int, и float являются 32-битными. Без тернарной операции float не особенно медленны, мы можем видеть это, потому что мы можем умножить возвращаемый int на переменную float, и это не замедлит его. У меня нет ответа на это.

Что касается того, почему скобки ускоряют операцию: я не эксперт, но предполагаю, что это, вероятно, связано с тем, что интерпретатор замедляет код: 

results[i] = num < 0 ? 0 : 1;

Здесь интерпретатор видит results массив типа float и просто заменяет целые числа на float в качестве «оптимизации», таким образом, ему не нужно преобразовывать между типами. 

results[i] = (num < 0 ? 0 : 1);

Здесь скобки заставляют интерпретатор вычислять все в них, прежде чем делать что-либо еще, это приводит к int. Только ПОСЛЕ этого результат будет преобразован в число с плавающей запятой, чтобы он мог поместиться в массив, преобразование типа совсем не медленное.

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

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

...