LINUX.ORG.RU
Форум — Web-development  

Неожиданно разная скорость вычисления дизъюнкции в зависимости от перестановок операндов

 , ,


0

2

Когда коту делать нечего, он микрооптимизирует код. И столкнулся с таким случаем.

Первый случай:

var a = 'Android'
a === 'Android' || a === 'android'
// 186 367 955.14 ops/s ± 0.37%

var a = 'Android'
a.toLowerCase() === 'android'
// 948 396 966.94 ops/s ± 0.68%

Второй случай:

var a = 'Android'
a === 'android' || a === 'Android'
// 964 766 563.52 ops/s ± 0.23%

var a = 'Android'
a.toLowerCase() === 'android'
// 959 593 276.92 ops/s ± 0.18%

Казалось бы в первом случае, в примере с ||, проверяется первое равенство и сразу возвращается результат, согласно кратким вычислениям. А во втором случае ещё должно второе равенство провериться, потом || и только потом результат вернуться, так что по идее второй случай, с ||, должен быть медленнее первого, но получается наоборот! Второй случай быстрее почти в пять раз! Где тут собака зарыта? На toLowerCase не обращайте внимания, хотел сравнить дизъюнкцию с ним, а получил неожиданные результаты и пришлось сравнивать уже дизъюнкции между собой!

★★★★

Последнее исправление: mydibyje (всего исправлений: 1)
← самый простой вариант обновляемой страницы
Можете посоветовать VPS/VDS физически расположенные на Урале и ДВ? →
Ответ на: комментарий от thesis

Справедливое замечание, проверил в консоли браузера:

(() => {
  const a = 'Android';
  const getA = (ab) => {return ab === 'Android' || ab === 'android';};
  console.time("engine");
  for(var i = 0; i < 1000 * 1000 * 1000; i++) {getA(a);}
  console.timeEnd("engine");
})();

// 2016.114013671875 ms

(() => {
  const a = 'Android';
  const getA = (ab) => {return ab === 'android' || ab === 'Android';};
  console.time("engine");
  for(var i = 0; i < 1000 * 1000 * 1000; i++) {getA(a);}
  console.timeEnd("engine");
})();
// 506.461181640625 ms
mydibyje ★★★★
() автор топика
Ответ на: комментарий от mydibyje

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

vbr ★★★★
()
Последнее исправление: vbr (всего исправлений: 2)
Ответ на: комментарий от mydibyje

Глянул у себя - в лисе одинаково, в хромом пятикратная разница, причем «медленный» вариант отрабатывает в полтора раза медленнее, чем в лисе.
Фу.

thesis ★★★★★
()
Ответ на: комментарий от static_lab

Более того, первый вариант оказывается на 1% медленнее даже если добавлен побочный эффект:

// setup
let c = 0;

const a = 'Android';

const cmp = (s1, s2) => {
	++c;
	return s1 === s2;
};

// case 1
cmp(a, 'Android') || cmp(a, 'android');

// case 2
cmp(a, 'android') || cmp(a, 'Android');

// teardown
console.log(c);
static_lab ★★★★★
()
Последнее исправление: static_lab (всего исправлений: 2)
Ответ на: комментарий от static_lab

Поделал варианты Aa, aA, AA, aa - тоже забавные результаты.

Под node вообще вариант a === 'android' || a === 'android' стабильно самый медленный у меня выходит.

Под js91 Aa самый медленный.

Только под quickjs предсказуемо Aa и AA самые быстрые. Если не считать, что его «самая быстрость» относительно Гугла и Мозиллы сама по себе никакая не быстрость.

Toxo2 ★★★★
()
Ответ на: комментарий от Toxo2

В смысле - такое: 

$cat 2.js

let c = [];
let t = ['Aa', 'aA', 'AA', 'aa'];
const a = 'Android';
const interval = 1000;
for(c[0] = 0, now = Date.now(); (Date.now() - now) < interval; ++c[0])
    {a === 'Android' || a === 'android';}
for(c[1] = 0, now = Date.now(); (Date.now() - now) < interval; ++c[1])
    {a === 'android' || a === 'Android';}
for(c[2] = 0, now = Date.now(); (Date.now() - now) < interval; ++c[2])
    {a === 'Android' || a === 'Android';}
for(c[3] = 0, now = Date.now(); (Date.now() - now) < interval; ++c[3])
    {a === 'android' || a === 'android';}
var avg = ((c.reduce((a, b) => a + b)) / c.length);
for(var i = 0; i < 4; i++)
    console.log(c[i], t[i], ((c[i] / avg) * 100).toFixed(2), c[i] > avg ? 'better' : 'worse');
и вывод: 
$ node 2.js 
21770756 Aa 97.31 worse
22986390 aA 102.74 better
21726825 AA 97.11 worse
23008372 aa 102.84 better
$ js91 2.js 
20301281 Aa 101.26 better
19836506 aA 98.94 worse
20220929 AA 100.86 better
19834743 aa 98.93 worse
$ qjs 2.js 
8465483 Aa 106.37 better
7430329 aA 93.36 worse
8514123 AA 106.98 better
7425265 aa 93.30 worse
У Гугла какая-то максимально хитрая оптимизация видимо.

Toxo2 ★★★★
()
Ответ на: комментарий от futurama

Это на первом прогоне, прогнал несколько раз, результаты ниже в миллисек. Получается ФФ правильнее обрабатывает short-circuit evaluation, чем Хром.
Конечно, как заметили в начале темы, хотелось бы увидеть выхлоп байткода от Ignition и последующий маш.код от Turbofan по этому куску, но не знаю как. 🤷‍♂️

function aA() {
  const a = 'Android';
  const getA = (ab) => {return ab === 'android' || ab === 'Android';};
  console.time("ms");
  for(let i = 0; i < 1000 * 1000 * 1000; i++) {getA(a);}
  console.timeEnd("ms");
}
for(let i = 0; i < 10; i++) aA();

function Aa() {
  const a = 'Android';
  const getA = (ab) => {return ab === 'Android' || ab === 'android';};
  console.time("ms");
  for(var i = 0; i < 1000 * 1000 * 1000; i++) {getA(a);}
  console.timeEnd("ms");
}
for(let i = 0; i < 10; i++) Aa();
№Chrome AaChrome aAFirefox AaFirefox aA
1.201450710191022
2.427851833154359
3.25325333194324
4.25125233024323
5.25325433114340
6.25125433024429
7.25425733134377
8.25226933014335
9.25325933004321
10.25125733134314
mydibyje ★★★★
() автор топика
Последнее исправление: mydibyje (всего исправлений: 2)
Ответ на: комментарий от mydibyje

На ноде кстати, понятно как смотреть байткод, кстати он у обеих функций одинаков, значит дело в маш.коде и скорее всего оптимизированном, а вот в браузере непонятно что делать с флагом --js-flags="--print-bytecode", ведь интересен браузер в первую очередь.

//script.js
const a = 'Android';
function aA(a){
  return a === 'android' || a === 'Android';
}
function Aa(a){
  return a === 'Android' || a === 'android';
}
aA(a);
Aa(a);

$ node --print-bytecode --print-bytecode-filter=aA script.js

41 S> 00000296735446F6 @    0 : 13 00             LdaConstant [0]
50 E> 00000296735446F8 @    2 : 6c 03 00          TestEqualStrict a0, [0]
      00000296735446FB @    5 : 98 07             JumpIfTrue [7] (0000029673544702 @ 12)
      00000296735446FD @    7 : 13 01             LdaConstant [1]
69 E> 00000296735446FF @    9 : 6c 03 01          TestEqualStrict a0, [1]
83 S> 0000029673544702 @   12 : a9                Return

А вот как смотреть оптимизированный маш.код не разобрался, флаг --print-opt-code (все флаги смотреть через node --v8-options) есть, но не выводит ничего. Приходится пользоваться --print-code, который выводит портянку на 3500 строк.

mydibyje ★★★★
() автор топика
Последнее исправление: mydibyje (всего исправлений: 2)
Ответ на: комментарий от mydibyje

Оказалось, что флаг --print-opt-code таки работает 🎉, но только если выполнение функции требует времени.

//script.js
const a = 'Android';
const getA = (b) => {return b === 'android' || b === 'Android';};
console.time("ms");
for(var i = 0; i < 1000 * 1000 * 1000; i++) {getA(a);}
console.timeEnd("ms");

$ node --print-opt-code --print-opt-code-filter=getA  script.js > aA.txt

Теперь можно сравнивать.

mydibyje ★★★★
() автор топика
Последнее исправление: mydibyje (всего исправлений: 2)
Ответ на: комментарий от dsxl

aA:
с подсветкой:
https://pastebin.com/KPhMxbKN
прямая ссылка:
https://pastebin.com/raw/KPhMxbKN

Aa:
https://pastebin.com/Q3Zxr3Ck
https://pastebin.com/raw/Q3Zxr3Ck

Пока не сравнивал.

mydibyje ★★★★
() автор топика
Последнее исправление: mydibyje (всего исправлений: 1)

Бенчмарки из однострочных циклов на JS не релевантны. Ты просто теряешь время на вещи, которые не имеют смысла.

https://mrale.ph/ - тут можно почитать много интересного, как JIT устроен.

Vit ★★★★★
()
Последнее исправление: Vit (всего исправлений: 1)
Ответ на: комментарий от Vit

https://mrale.ph/ - тут можно почитать много интересного, как JIT устроен.

А где там прочитать почему в случае 'Aa' оно не создаёт full embedded object для строки 'android', в случае 'aA' - создаёт?

Так-то по большому счёту - ничего не имеет смысла. Тем более в IT. Но любопытно же.

Toxo2 ★★★★
()
Последнее исправление: Toxo2 (всего исправлений: 1)
Ответ на: комментарий от Toxo2

А где там прочитать почему в случае ‘Aa’ оно не создаёт full embedded object для строки ‘android’, в случае ‘aA’ - создаёт?

Тут какой-то очень вырожденный случай. Сколько я не пытался его зарефакторить, медленный кейс всегда сравнивался в скорости с быстрым. А если заменить миллиард итераций на миллион, то картина меняется на противоположную. Это всё очень интересно, бесспорно, но с практической точки зрения лучше изучить те статьи из блога.

dsxl ★
()
Ответ на: комментарий от dsxl

зарефакторить

Экак вас...

---

Похоже я уже начал понимать это игру )

1. Объект на 'android' в версии 'Aa' скорее всего потому и не создается, что поскольку функция кончается на первом операнде, то до второго и не доходит.

2. Там дальше пояснения о причинах деоптимизации Insufficient type feedback for compare operation - видимо опять же потому, что функция не видит 'android' (ибо кончается раньше) и решает, что не знает тип переменной.

Тут вроде бы есть противоречие... Что смущает.

Но вот такая фигня (эдакое передергивание типа): 

const getAa1 = (b) => {bb = b; b = 'android'; b = bb; return b === 'Android' || b === 'android';};
Совершенно точно делает версию Аа равной по скорости версии аА.

Итого - из консоли MSEdge: 

(() => {
  const a = 'Android';
  const getA = (ab) => {return ab === 'Android' || ab === 'android';};
  console.time("engine");
  for(var i = 0; i < 1000 * 1000 * 1000; i++) {getA(a);}
  console.timeEnd("engine");
})();
VM44:6 engine: 1203.757080078125 ms
(() => {
  const a = 'Android';
  const getA = (ab) => {bb = ab; ab = 'android'; ab = bb; return ab === 'Android' || ab === 'android';};
  console.time("engine");
  for(var i = 0; i < 1000 * 1000 * 1000; i++) {getA(a);}
  console.timeEnd("engine");
})();
VM131:6 engine: 388.130859375 ms

Toxo2 ★★★★
()
Последнее исправление: Toxo2 (всего исправлений: 2)
Ответ на: комментарий от dsxl

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

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

Vit ★★★★★
()

Попробовал запустить через benchmarkjs, результаты почти одинаковые. Думаю.

<!DOCTYPE html><html><head>
  <meta charset="utf-8">
  <script src="https://cdn.jsdelivr.net/npm/lodash@4.17.21/lodash.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/platform@1.3.6/platform.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/benchmark@2.1.4/benchmark.min.js"></script>
</head><body>
<script>
var suite = new Benchmark.Suite;
const android = 'Android';

// add tests
suite.add('short-circuit', function() {
  //let android = 'Android';
  return android === 'Android' || android === 'android';
})
.add('expected long time', function() {
  //let android = 'Android';
  return android === 'android' || android === 'Android';
})

// add listeners
.on('cycle', function(event) { console.log(String(event.target)); })
.on('complete', function() { console.log('Fastest is ' + this.filter('fastest').map('name')); })
// run async
.run({ 'async': true });
</script>
</body></html>

short-circuit x 951,813,125 ops/sec ±0.21% (65 runs sampled)
expected long time x 948,475,779 ops/sec ±0.40% (63 runs sampled)
Fastest is short-circuit
mydibyje ★★★★
() автор топика
Ответ на: комментарий от mydibyje

Там внутри какая-то особая магия. Если «в лоб», то по-прежднему простое перекладывание туда/сюда значения входящего параметра помогает V8 определиться с типом и не отключать оптимизации. 

const a = 'Android';
const getAa1 = (b) => {return b === 'Android' || b === 'android';};
const getaA2 = (b) => {return b === 'android' || b === 'Android';};
const getAaHack = (b) => {bb = b;  b = bb; return b === 'Android' || b === 'android';};

var _ = require('lodash/core');
var ben = require('benchmark');
ben.options.maxTime = 0;
ben.options.delay = 0;
ben.options.async = true;
var suite = new ben.Suite;

suite
  .add('Aa', () => {getAa1(a)})
  .add('aA', () => {getaA2(a)})
  .add('AaHack', () => {getAaHack(a)})
  .on('cycle', function(event) { console.log(String(event.target)); })
  .on('complete', function() { console.log('Fastest is ' + this.filter('fastest').map('name')); })
  .run()
  ;

let c = [];
let t = ['Aa', 'aA', 'AaHack'];
const interval = 1000;
for(c[0] = 0, now = Date.now(); (Date.now() - now) < interval; ++c[0])
    {getAa1(a);}
for(c[1] = 0, now = Date.now(); (Date.now() - now) < interval; ++c[1])
    {getaA2(a);}
for(c[2] = 0, now = Date.now(); (Date.now() - now) < interval; ++c[2])
    {getAaHack(a);}
var avg = ((c.reduce((a, b) => a + b)) / c.length);
for(var i = 0; i < c.length; i++)
    console.log(c[i], t[i], ((c[i] / avg) * 100).toFixed(2), c[i] > avg ? 'better' : 'worse');
В целом-то спорить о практическом смысле такого хака нет повода, но если уж влезть на пень с желанием получить Aa==aA именно в этом месте, то работает точно.

Toxo2 ★★★★
()
Ответ на: комментарий от Toxo2
  1. Объект на ‘android’ в версии ‘Aa’ скорее всего потому и не создается, что поскольку функция кончается на первом операнде, то до второго и не доходит.
  1. Там дальше пояснения о причинах деоптимизации Insufficient type feedback for compare operation - видимо опять же потому, что функция не видит ‘android’ (ибо кончается раньше) и решает, что не знает тип переменной.

Тут вроде бы есть противоречие… Что смущает.

Немного не так. Нода собирает статистику, какие ветки достижимы, а какие нет. В варианте aA приходится делать обе проверки, а в варианте Aa нода увидела, что до второй выполнение никогда не доходит. Поэтому вторая проверка была выкинута и строка и ‘android’ тоже. Но нода же думает, что раз код написан, то он всё-таки может быть нужен. Поэтому вместо выкинутой второй ветки вставляется переход на неоптимизированную версию со всеми проверками.

Но деоптимизации не происходит, так как строка ‘android’ никогда не поступает на вход.

Так почему же вариант Aa тогда работает медленнее, если он такой оптимизированный? Да хрен его знает. Как я сказал, всё равно пример из пальца высосан. Напиши нормально и проблема исчезает.

Вот тут скорость одинаковая. Замени миллиард на миллион - будет Aa быстрее, как и должно быть по логике.

const count = 1_000_000_000;

function aA(a) {
    return a === 'android' || a === 'Android';
}

function Aa(a) {
    return a === 'Android' || a === 'android';
}

for(let i = 0; i < 10; i++) {
    {console.time('aAA'+i); let sum = 0; for(let j = 0; j < count; j++) if (aA('Android')) sum++; if (sum != count) throw new Error('LOL'); console.timeEnd('aAA'+i);}
    {console.time('AaA'+i); let sum = 0; for(let j = 0; j < count; j++) if (Aa('Android')) sum++; if (sum != count) throw new Error('LOL'); console.timeEnd('AaA'+i);}

    console.log();
}
dsxl ★
()
← самый простой вариант обновляемой страницы
Web-development
Можете посоветовать VPS/VDS физически расположенные на Урале и ДВ? →