Информация об изменениях

Сообщение Re[25]: C# - from indians by indians от 06.06.2015 20:08

Изменено 07.06.2015 9:30 Evgeny.Panasyuk

Старый текст
Новый текст
Разница

EP>C++ версия скомпилированная в JavaScript и запущенная в Firefox:
EP>

EP>Elapsed = 0.0960432s

EP>

EP>UPD: Иногда бывает даже вот так:
EP>

EP>Elapsed = 0.0744424s

Исходный main:

int main()
{
    constexpr auto N = 1u << 24;
    vector<Complex> v, u;
    v.reserve(N);
    generate_n(back_inserter(v), N, random_complex);
    u = v;
    random_shuffle(begin(v), end(v));
    random_shuffle(begin(u), end(u));

    benchmark([&]
    {
        transform(begin(v), end(v), begin(u), begin(v), [](auto x, auto y) { return x*y; });
    });

    volatile auto anti_opti = accumulate(begin(v), end(v), Complex{});
    (void)anti_opti;
}

А вот main из .js отформатированный сторонней утилитой. Имена идентификаторов это то что я разревёрсил, до этого были одно-двух буквенные:

function main() {
    var a = 0,
        b = 0,
        c = 0,
        d = 0,
        e = 0,
        f = 0,
        g = 0,
        h = 0,
        i = 0,
        j = 0,
        l = 0,
        m = 0,
        n = 0,
        o = 0,
        q = 0,
        s = 0,
        t = 0.0,
        u = 0.0,
        v = 0.0,
        w = 0.0;
    s = r;
    r = r + 80 | 0;
    j = s + 16 | 0;
    i = s;
    l = s + 8 | 0;
    o = s + 48 | 0;
    m = s + 60 | 0;
    c = s + 36 | 0;
    d = s + 40 | 0;
    f = s + 44 | 0;
    g = s + 32 | 0;
    mem_as_Int32[o >> 2] = 0;
    q = o + 4 | 0;
    mem_as_Int32[q >> 2] = 0;
    h = o + 8 | 0;
    mem_as_Int32[h >> 2] = 0;
    mem_as_Int32[m >> 2] = 0;
    n = m + 4 | 0;
    mem_as_Int32[n >> 2] = 0;
    mem_as_Int32[m + 8 >> 2] = 0;
    e = Pn(268435456) | 0;
    mem_as_Int32[o >> 2] = e;
    mem_as_Int32[q >> 2] = e;
    mem_as_Int32[h >> 2] = e + 268435456;
    e = j + 8 | 0;
    b = 16777216;
    do {
        t = +(rand() | 0) / 1.0e3 + -1.0e3;
        mem_as_Float64[j >> 3] = t;
        t = +(rand() | 0) / 1.0e3 + -1.0e3;
        mem_as_Float64[e >> 3] = t;
        a = mem_as_Int32[q >> 2] | 0;
        if (a >>> 0 < (mem_as_Int32[h >> 2] | 0) >>> 0) {
            if (!a) a = 0;
            else {
                mem_as_Int32[a + 0 >> 2] = mem_as_Int32[j + 0 >> 2];
                mem_as_Int32[a + 4 >> 2] = mem_as_Int32[j + 4 >> 2];
                mem_as_Int32[a + 8 >> 2] = mem_as_Int32[j + 8 >> 2];
                mem_as_Int32[a + 12 >> 2] = mem_as_Int32[j + 12 >> 2]
            }
            mem_as_Int32[q >> 2] = a + 16
        } else Dc(o, j);
        b = b + -1 | 0
    } while ((b | 0) != 0);
    Cc(m, mem_as_Int32[o >> 2] | 0, mem_as_Int32[q >> 2] | 0);
    mem_as_Int32[c >> 2] = mem_as_Int32[o >> 2];
    mem_as_Int32[d >> 2] = mem_as_Int32[q >> 2];
    mem_as_Int32[i + 0 >> 2] = mem_as_Int32[c + 0 >> 2];
    mem_as_Int32[j + 0 >> 2] = mem_as_Int32[d + 0 >> 2];
    random_shuffle(i, j);
    mem_as_Int32[f >> 2] = mem_as_Int32[m >> 2];
    mem_as_Int32[g >> 2] = mem_as_Int32[n >> 2];
    mem_as_Int32[i + 0 >> 2] = mem_as_Int32[f + 0 >> 2];
    mem_as_Int32[j + 0 >> 2] = mem_as_Int32[g + 0 >> 2];
    random_shuffle(i, j);
    high_resolution_clock::now(i);
    a = mem_as_Int32[o >> 2] | 0;
    c = mem_as_Int32[q >> 2] | 0;
    if ((a | 0) != (c | 0)) {
        b = mem_as_Int32[m >> 2] | 0;
        while (1) {
            u = +mem_as_Float64[a >> 3];
            g = a + 8 | 0;
            w = +mem_as_Float64[g >> 3];
            v = +mem_as_Float64[b >> 3];
            t = +mem_as_Float64[b + 8 >> 3];
            mem_as_Float64[a >> 3] = u * v - w * t;
            mem_as_Float64[g >> 3] = w * v + u * t;
            a = a + 16 | 0;
            if ((a | 0) == (c | 0)) break;
            else b = b + 16 | 0
        }
    }
    high_resolution_clock::now(l);
    e = l;
    f = mem_as_Int32[e >> 2] | 0;
    e = mem_as_Int32[e + 4 >> 2] | 0;
    a = i;
    g = mem_as_Int32[a >> 2] | 0;
    a = mem_as_Int32[a + 4 >> 2] | 0;
    l = zc(2664, 8, 10) | 0;
    a = xp(f | 0, e | 0, g | 0, a | 0) | 0;
    a = zc(Le(l, (+(a >>> 0) + 4294967296.0 * +(P | 0)) / 1.0e9) | 0, 24, 1) | 0;
    Ld(j, a + (mem_as_Int32[(mem_as_Int32[a >> 2] | 0) + -12 >> 2] | 0) | 0);
    l = kj(j, 7520) | 0;
    l = mc[mem_as_Int32[(mem_as_Int32[l >> 2] | 0) + 28 >> 2] & 15](l, 10) | 0;
    ij(j);
    Me(a, l) | 0;
    we(a) | 0;
    a = mem_as_Int32[m >> 2] | 0;
    if (!a) a = mem_as_Int32[o >> 2] | 0;
    else {
        b = mem_as_Int32[n >> 2] | 0;
        if ((b | 0) != (a | 0)) mem_as_Int32[n >> 2] = b + (~((b + -16 - a | 0) >>> 4) << 4);
        Qn(a);
        a = mem_as_Int32[o >> 2] | 0
    }
    if (!a) {
        r = s;
        return 0
    }
    b = mem_as_Int32[q >> 2] | 0;
    if ((b | 0) != (a | 0)) mem_as_Int32[q >> 2] = b + (~((b + -16 - a | 0) >>> 4) << 4);
    Qn(a);
    r = s;
    return 0
}

mem_as_Int32 и mem_as_Float64 это views одного и того же буфера (есть views и других типов). Heap и stack находятся в этом буфере.

Первый цикл это generate_n:

e = j + 8 | 0;
b = 16777216;
do {
    t = +(rand() | 0) / 1.0e3 + -1.0e3;
    mem_as_Float64[j >> 3] = t;
    t = +(rand() | 0) / 1.0e3 + -1.0e3;
    mem_as_Float64[e >> 3] = t;
    a = mem_as_Int32[q >> 2] | 0;
    if (a >>> 0 < (mem_as_Int32[h >> 2] | 0) >>> 0) {
        if (!a) a = 0;
        else {
            mem_as_Int32[a + 0 >> 2] = mem_as_Int32[j + 0 >> 2];
            mem_as_Int32[a + 4 >> 2] = mem_as_Int32[j + 4 >> 2];
            mem_as_Int32[a + 8 >> 2] = mem_as_Int32[j + 8 >> 2];
            mem_as_Int32[a + 12 >> 2] = mem_as_Int32[j + 12 >> 2]
        }
        mem_as_Int32[q >> 2] = a + 16
    } else Dc(o, j);
    b = b + -1 | 0
} while ((b | 0) != 0);

Тут видно что компилятор в этот же цикл сразу поместил копирование во второй вектор, то есть:

generate_n(back_inserter(v), N, random_complex);
u = v;

избежав двух проходов по памяти первого вектора.

Следующий цикл это transform с легко узнаваемой формулой умножения комплексных чисел:

high_resolution_clock::now(i);
a = mem_as_Int32[o >> 2] | 0;
c = mem_as_Int32[q >> 2] | 0;
if ((a | 0) != (c | 0)) {
    b = mem_as_Int32[m >> 2] | 0;
    while (1) {
        u = +mem_as_Float64[a >> 3];
        g = a + 8 | 0;
        w = +mem_as_Float64[g >> 3];
        v = +mem_as_Float64[b >> 3];
        t = +mem_as_Float64[b + 8 >> 3];
        mem_as_Float64[a >> 3] = u * v - w * t;
        mem_as_Float64[g >> 3] = w * v + u * t;
        a = a + 16 | 0;
        if ((a | 0) == (c | 0)) break;
        else b = b + 16 | 0
    }
}
high_resolution_clock::now(l);

То есть это результат компиляции:

transform(begin(v), end(v), begin(u), begin(v), [](auto x, auto y) { return x*y; });

Несмотря на volatile, компилятор выкинул accumulate. Его можно принудительно добавить (через вывод в результата в cout), но на замер времени это не повлияло.

P.S. Думаю на базе Emscripten можно сделать компилятор из C++ в Java — тогда там наконец "появятся" автоматические структуры

UPD: у компилятора есть опция выводить не "сжатый" код:

main js

function _main() {
 var $$01$i = 0, $$byval_copy2 = 0, $$byval_copy3 = 0, $0 = 0, $1 = 0, $10 = 0, $14 = 0.0, $18 = 0.0, $19 = 0, $2 = 0, $24 = 0, $3 = 0, $34 = 0.0, $35 = 0, $36 = 0.0, $37 = 0.0, $39 = 0.0, $4 = 0, $49 = 0, $5 = 0, $51 = 0, $54 = 0, $55 = 0, $57 = 0, $6 = 0, $60 = 0, $61 = 0, $62 = 0, $67 = 0, $72 = 0, $76 = 0, $78 = 0, $8 = 0, $80 = 0, $86 = 0, $88 = 0, $__first1$01015$i$i$i = 0, $__first2$01114$i$i$i = 0, $end$i = 0, $f$idx$val$idx$val$i = 0, $f$idx$val$idx2$val$i = 0, $u = 0, $v = 0, sp = 0;
 sp = STACKTOP;
 STACKTOP = STACKTOP + 80 | 0;
 $$byval_copy3 = sp + 16 | 0;
 $$byval_copy2 = sp;
 $end$i = sp + 8 | 0;
 $v = sp + 48 | 0;
 $u = sp + 60 | 0;
 $0 = sp + 36 | 0;
 $1 = sp + 40 | 0;
 $2 = sp + 44 | 0;
 $3 = sp + 32 | 0;
 HEAP32[$v >> 2] = 0;
 $4 = $v + 4 | 0;
 HEAP32[$4 >> 2] = 0;
 $5 = $v + 8 | 0;
 HEAP32[$5 >> 2] = 0;
 HEAP32[$u >> 2] = 0;
 $6 = $u + 4 | 0;
 HEAP32[$6 >> 2] = 0;
 HEAP32[$u + 8 >> 2] = 0;
 $8 = __Znwj(268435456) | 0;
 HEAP32[$v >> 2] = $8;
 HEAP32[$4 >> 2] = $8;
 HEAP32[$5 >> 2] = $8 + 268435456;
 $10 = $$byval_copy3 + 8 | 0;
 $$01$i = 16777216;
 do {
  $14 = +(_rand() | 0) / 1.0e3 + -1.0e3;
  HEAPF64[$$byval_copy3 >> 3] = $14;
  $18 = +(_rand() | 0) / 1.0e3 + -1.0e3;
  HEAPF64[$10 >> 3] = $18;
  $19 = HEAP32[$4 >> 2] | 0;
  if ($19 >>> 0 < (HEAP32[$5 >> 2] | 0) >>> 0) {
   if (!$19) $24 = 0; else {
    HEAP32[$19 + 0 >> 2] = HEAP32[$$byval_copy3 + 0 >> 2];
    HEAP32[$19 + 4 >> 2] = HEAP32[$$byval_copy3 + 4 >> 2];
    HEAP32[$19 + 8 >> 2] = HEAP32[$$byval_copy3 + 8 >> 2];
    HEAP32[$19 + 12 >> 2] = HEAP32[$$byval_copy3 + 12 >> 2];
    $24 = $19;
   }
   HEAP32[$4 >> 2] = $24 + 16;
  } else __ZNSt3__16vectorI7ComplexNS_9allocatorIS1_EEE21__push_back_slow_pathIS1_EEvOT_($v, $$byval_copy3);
  $$01$i = $$01$i + -1 | 0;
 } while (($$01$i | 0) != 0);
 __ZNSt3__16vectorI7ComplexNS_9allocatorIS1_EEE6assignIPS1_EENS_9enable_ifIXaasr21__is_forward_iteratorIT_EE5valuesr16is_constructibleIS1_NS_15iterator_traitsIS8_E9referenceEEE5valueEvE4typeES8_S8_($u, HEAP32[$v >> 2] | 0, HEAP32[$4 >> 2] | 0);
 HEAP32[$0 >> 2] = HEAP32[$v >> 2];
 HEAP32[$1 >> 2] = HEAP32[$4 >> 2];
 HEAP32[$$byval_copy2 + 0 >> 2] = HEAP32[$0 + 0 >> 2];
 HEAP32[$$byval_copy3 + 0 >> 2] = HEAP32[$1 + 0 >> 2];
 __ZNSt3__114random_shuffleINS_11__wrap_iterIP7ComplexEEEEvT_S5_($$byval_copy2, $$byval_copy3);
 HEAP32[$2 >> 2] = HEAP32[$u >> 2];
 HEAP32[$3 >> 2] = HEAP32[$6 >> 2];
 HEAP32[$$byval_copy2 + 0 >> 2] = HEAP32[$2 + 0 >> 2];
 HEAP32[$$byval_copy3 + 0 >> 2] = HEAP32[$3 + 0 >> 2];
 __ZNSt3__114random_shuffleINS_11__wrap_iterIP7ComplexEEEEvT_S5_($$byval_copy2, $$byval_copy3);
 __ZNSt3__16chrono12steady_clock3nowEv($$byval_copy2);
 $f$idx$val$idx$val$i = HEAP32[$v >> 2] | 0;
 $f$idx$val$idx2$val$i = HEAP32[$4 >> 2] | 0;
 if (($f$idx$val$idx$val$i | 0) != ($f$idx$val$idx2$val$i | 0)) {
  $__first1$01015$i$i$i = $f$idx$val$idx$val$i;
  $__first2$01114$i$i$i = HEAP32[$u >> 2] | 0;
  while (1) {
   $34 = +HEAPF64[$__first1$01015$i$i$i >> 3];
   $35 = $__first1$01015$i$i$i + 8 | 0;
   $36 = +HEAPF64[$35 >> 3];
   $37 = +HEAPF64[$__first2$01114$i$i$i >> 3];
   $39 = +HEAPF64[$__first2$01114$i$i$i + 8 >> 3];
   HEAPF64[$__first1$01015$i$i$i >> 3] = $34 * $37 - $36 * $39;
   HEAPF64[$35 >> 3] = $36 * $37 + $34 * $39;
   $__first1$01015$i$i$i = $__first1$01015$i$i$i + 16 | 0;
   if (($__first1$01015$i$i$i | 0) == ($f$idx$val$idx2$val$i | 0)) break; else $__first2$01114$i$i$i = $__first2$01114$i$i$i + 16 | 0;
  }
 }
 __ZNSt3__16chrono12steady_clock3nowEv($end$i);
 $49 = $end$i;
 $51 = HEAP32[$49 >> 2] | 0;
 $54 = HEAP32[$49 + 4 >> 2] | 0;
 $55 = $$byval_copy2;
 $57 = HEAP32[$55 >> 2] | 0;
 $60 = HEAP32[$55 + 4 >> 2] | 0;
 $61 = __ZNSt3__124__put_character_sequenceIcNS_11char_traitsIcEEEERNS_13basic_ostreamIT_T0_EES7_PKS4_j(2664, 8, 10) | 0;
 $62 = _i64Subtract($51 | 0, $54 | 0, $57 | 0, $60 | 0) | 0;
 $67 = __ZNSt3__124__put_character_sequenceIcNS_11char_traitsIcEEEERNS_13basic_ostreamIT_T0_EES7_PKS4_j(__ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd($61, (+($62 >>> 0) + 4294967296.0 * +(tempRet0 | 0)) / 1.0e9) | 0, 24, 1) | 0;
 __ZNKSt3__18ios_base6getlocEv($$byval_copy3, $67 + (HEAP32[(HEAP32[$67 >> 2] | 0) + -12 >> 2] | 0) | 0);
 $72 = __ZNKSt3__16locale9use_facetERNS0_2idE($$byval_copy3, 7520) | 0;
 $76 = FUNCTION_TABLE_iii[HEAP32[(HEAP32[$72 >> 2] | 0) + 28 >> 2] & 15]($72, 10) | 0;
 __ZNSt3__16localeD2Ev($$byval_copy3);
 __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE3putEc($67, $76) | 0;
 __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5flushEv($67) | 0;
 $78 = HEAP32[$u >> 2] | 0;
 if (!$78) $86 = HEAP32[$v >> 2] | 0; else {
  $80 = HEAP32[$6 >> 2] | 0;
  if (($80 | 0) != ($78 | 0)) HEAP32[$6 >> 2] = $80 + (~(($80 + -16 - $78 | 0) >>> 4) << 4);
  __ZdlPv($78);
  $86 = HEAP32[$v >> 2] | 0;
 }
 if (!$86) {
  STACKTOP = sp;
  return 0;
 }
 $88 = HEAP32[$4 >> 2] | 0;
 if (($88 | 0) != ($86 | 0)) HEAP32[$4 >> 2] = $88 + (~(($88 + -16 - $86 | 0) >>> 4) << 4);
 __ZdlPv($86);
 STACKTOP = sp;
 return 0;
}

Re[25]: C# - from indians by indians