Смещает биты быстрее, чем умножение и деление на Java?.NET? [закрытый]
Я написал быструю программу, чтобы найти эти семена:
import java.lang.*;
import java.util.*;
import java.io.*;
public class RandomWords {
public static void main (String[] args) {
Set wordSet = new HashSet();
String fileName = (args.length > 0 ? args[0] : "/usr/share/dict/words");
readWordMap(wordSet, fileName);
System.err.println(wordSet.size() + " words read.");
findRandomWords(wordSet);
}
private static void readWordMap (Set wordSet, String fileName) {
try {
BufferedReader reader = new BufferedReader(new FileReader(fileName));
String line;
while ((line = reader.readLine()) != null) {
line = line.trim().toLowerCase();
if (isLowerAlpha(line)) wordSet.add(line);
}
}
catch (IOException e) {
System.err.println("Error reading from " + fileName + ": " + e);
}
}
private static boolean isLowerAlpha (String word) {
char[] c = word.toCharArray();
for (int i = 0; i < c.length; i++) {
if (c[i] < 'a' || c[i] > 'z') return false;
}
return true;
}
private static void findRandomWords (Set wordSet) {
char[] c = new char[256];
Random r = new Random();
for (long seed0 = 0; seed0 >= 0; seed0++) {
for (int sign = -1; sign <= 1; sign += 2) {
long seed = seed0 * sign;
r.setSeed(seed);
int i;
for (i = 0; i < c.length; i++) {
int n = r.nextInt(27);
if (n == 0) break;
c[i] = (char)((int)'a' + n - 1);
}
String s = new String(c, 0, i);
if (wordSet.contains(s)) {
System.out.println(s + ": " + seed);
wordSet.remove(s);
}
}
}
}
}
У меня это работает в фоновом режиме, но уже найдено достаточно слов для классической панграммы:
import java.lang.*;
import java.util.*;
public class RandomWordsTest {
public static void main (String[] args) {
long[] a = {-73, -157512326, -112386651, 71425, -104434815,
-128911, -88019, -7691161, 1115727};
for (int i = 0; i < a.length; i++) {
Random r = new Random(a[i]);
StringBuilder sb = new StringBuilder();
int n;
while ((n = r.nextInt(27)) > 0) sb.append((char)('`' + n));
System.out.println(sb);
}
}
}
Пс. -727295876, -128911, -1611659, -235516779.
11 ответов
Большинство современных компиляторов делают больше, чем просто преобразовывают, умножают или делят на степень двойки для операций сдвига. При оптимизации многие компиляторы могут оптимизировать умножение или деление с постоянной времени компиляции, даже если это не степень 2. Часто умножение или деление можно разложить на серию сдвигов и сложений, и если эта серия операций будет быстрее чем умножение или деление, компилятор будет использовать его.
Для деления на константу компилятор часто может преобразовать операцию в умножение на «магическое число» с последующим сдвигом. Это может значительно сэкономить время, так как умножение часто выполняется намного быстрее, чем операция деления.
Книга Генри Уоррена, «Восторг хакера», содержит массу информации по этой теме, которая также довольно хорошо освещена на сопутствующий сайт:
См. Также обсуждение (со ссылкой или двумя) в:
В любом случае, все это сводится к тому, чтобы позволить компилятору взять забота о утомительных деталях микрооптимизации. Прошло много лет с тех пор, как вы перехитрили компилятор, сделав собственные изменения.
Большинство компиляторов при необходимости преобразует умножение и деление в битовые сдвиги. Это одна из самых простых оптимизаций. Таким образом, вы должны делать то, что удобнее для чтения и подходит для данной задачи.
Я ошеломлен, когда только что написал этот код и понял, что сдвиг на единицу на самом деле медленнее, чем умножение на 2!
(РЕДАКТИРОВАТЬ: изменил код, чтобы он не переполнялся после предложения Майкла Майерса , но результаты те же! Что здесь не так?)
import java.util.Date;
public class Test {
public static void main(String[] args) {
Date before = new Date();
for (int j = 1; j < 50000000; j++) {
int a = 1 ;
for (int i = 0; i< 10; i++){
a *=2;
}
}
Date after = new Date();
System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds");
before = new Date();
for (int j = 1; j < 50000000; j++) {
int a = 1 ;
for (int i = 0; i< 10; i++){
a = a << 1;
}
}
after = new Date();
System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds");
}
}
Результат:
Умножение на 639 миллисекунд
Перемещение 718 миллисекунд
Если компилятор (константа времени компиляции) или JIT (константа времени выполнения) знает, что делитель или multiplicand - это степень двойки, и выполняется целочисленная арифметика, она преобразует его в сдвиг для вас.
Это зависит от оборудования. Если мы говорим о микроконтроллере или i386, то переключение может быть быстрее, но, как указано в нескольких ответах, ваш компилятор обычно выполняет оптимизацию за вас.
На современном оборудовании (Pentium Pro и выше) конвейерная обработка делает это совершенно несущественным, и отклонение от проторенного пути обычно означает, что вы теряете гораздо больше оптимизаций, чем можете получить.
Микрооптимизации - это не только пустая трата времени , их также чрезвычайно сложно получить правильно.
Вы почти наверняка можете положиться на оптимизацию умножения буквальной степени двойки для операции сдвига. Это одна из первых оптимизаций, которую изучат студенты, изучающие конструкцию компиляторов. :)
Однако я не думаю, что на это есть гарантия. Ваш исходный код должен отражать ваше намерение , а не пытаться указывать оптимизатору, что делать. Если вы увеличиваете количество, используйте умножение. Если вы перемещаете битовое поле из одного места в другое (подумайте о манипуляции с цветом RGB), используйте операцию сдвига. В любом случае ваш исходный код будет отражать то, что вы на самом деле делаете.
Люди ошибаются в этих случаях.
99%, когда они пытаются пересмотреть современные (и все будущие) компиляторы.
99,9%, когда они одновременно пытаются пересмотреть современные (и все будущие) JIT.
99,999%, когда они пытаются пересмотреть современные (и все будущие) оптимизации ЦП
Программируйте таким образом, чтобы точно описывать то, что вы хотите достичь, а не то, как это сделать. Будущие версии JIT, VM, компилятора и ЦП могут быть независимо улучшены и оптимизированы. Если вы укажете что-то настолько маленькое и конкретное, вы потеряете все преимущества будущих оптимизаций.
Практически любая среда, достойная внимания, оптимизирует это за вас. А если этого не произойдет, вам нужно зажарить рыбу покрупнее. Серьезно, не теряйте ни секунды на размышления об этом. Вы узнаете, когда у вас возникнут проблемы с производительностью. И после того, как вы запустите профилировщик, вы будете знать, что его вызывает, и должно быть достаточно ясно, как это исправить.
Вы никогда не услышите, чтобы кто-нибудь сказал, что «мое приложение было слишком медленным, тогда я начал случайную замену x * 2 с x << 1 , и все было исправлено! " Проблемы с производительностью обычно решаются путем поиска способа выполнять на порядок меньше работы, а не путем поиска способа выполнять ту же работу на 1% быстрее.
Я бы спросил: «Что вы делаете, чтобы это имело значение?». Сначала разработайте свой код для удобства чтения и сопровождения. Вероятность того, что выполнение стандартного умножения со сдвигом битов будет иметь значение для производительности, ОЧЕНЬ мала.
На компьютерах, которые я тестировал, целочисленные деления выполняются в от 4 до 10 раз медленнее , чем другие операции.
Когда компиляторы могут заменять деления на числа, кратные 2, и вы не видите разница, деление на число, не кратное 2, происходит значительно медленнее.
Например, у меня есть (графическая) программа с много-много-много делений на 255. На самом деле мои вычисления таковы:
r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23;
Я могу гарантировать, что они намного быстрее, чем мои предыдущие вычисления:
r = ((top.R - bottom.R) * alpha + (bottom.R * 255)) / 255;
так что нет, компиляторы не могут выполнять все трюки оптимизации.
Обратите внимание, что сдвиг вниз и деление будут (в Java, конечно) давать разные результаты для отрицательных, нечетных чисел.
int a = -7;
System.out.println("Shift: "+(a >> 1));
System.out.println("Div: "+(a / 2));
Печать:
Shift: -4
Div: -3
Поскольку в Java нет чисел без знака, это невозможно для компилятора Java чтобы оптимизировать это.