LINUX.ORG.RU

Эмулируем сопроцессор через школокалькулятор с обратной польской записью

 


0

5

Не хочется спускать на тормозах срач из Есть ли современный аналог DDD? (да и тупняк в /dev подзапарил).

В тред кастуются mv, xiomar_georgios и все желающие.

Чтобы дать хоть какой-то (мизерный) шанс общелиспу, предлагаю следующую задачу:

«Эмулируем сопроцессор через школокалькулятор с обратной польской записью».

Дано:

На вход подаётся файл фиксированного размера, содержащего дерево двоичных операторов и их операндов. Операнды представлены как 32-битные значения с плавающей точкой (float), операторы - как двоичные константы такой же размерности, что и операнды, эндианнесность - нативная. Операторы состоят из множества («сложить», «вычесть», «умножить»). (Делить не будем во избежание нуля).

На выход - записываем итоговый результат вычислений в любом (хоть двоичном дампе в файл) виде.

В отношении входящих данных гарантируется их корректность.

Пример входных данных в буквенном псевдокоде:

[-] [+] [0.2][0.1][*] [0.3][0.4]

каждое значение обозначено квадратными скобками и занимает 32 бита, запись выше означает выражение ((0,2 + 0,1) - (0,3 * 0,4)).

Ограничений на объём потребляемой памяти и размер стэка нет. Эталонная архитектура - amd64.

Победителем признаётся та реализация, которая будет уделывать конкурентов в лоскуты на гигабайтном входном файле, с минимальной параметризацией на смену типа под double и 32/64-ех битное беззнаковое целое. При смене типа операнда размерность оператора так же меняется!

Итоговые весы выглядят так:

0,4 * разница в double
0,2 * разница в float
0,2 * разница в uint32_t
0,2 * разница в uint64_t

Пример расчёта:

А обгоняет Б в два раза на целочисленных операциях, сливает вдвое на double и поровну на float.

А к Б : 0,4 * 0,5 + 0,2 * 1,0 + 0,2 * 2,0 + 0,2 * 2,0 = 1,2
Б к А : 0,4 * 2 + 0,2 * 1,0 + 0,2 * 0,5 + 0,2 * 0,5 = 1,2

Реализации эквиваленты, ничья.

Адепты раста, хаскеля и похапе, включая суровых сибирских разработчиков на VBA так же приглашаются к участию.

P.S. Так и знал, что в чём-нить обосрусь.

Считаем, что двоичные значения операторов не принадлежат множеству допустимых значений операндов. Для плавающих [+,-,*] = [&infin, -&infin, NaN], для беззнаковых целых - (UINTN_MAX, UINTN_MAX-1, UINTN_MAX-2).

★★★★★

Последнее исправление: LamerOk (всего исправлений: 2)

Ответ на: комментарий от monk

Не ожидал такого от racket’а, признаю. У меня это выглядит как-то так, и результат я толком не улучшу.

На 1гб-блобе.

[~/Git/rpn-fast] > time ../rpn/target/release/rpn-eval   
0.44561768
../rpn/target/release/rpn-eval  2.89s user 0.35s system 98% cpu 3.284 total
[~/Git/rpn-fast] > time racket rpn.rkt                
0.44561767578125
racket rpn.rkt  4.44s user 0.40s system 97% cpu 4.945 total

На 8гб-блобе.

[~/Git/rpn-fast] > time racket rpn.rkt          
-0.7228966355323792
racket rpn.rkt  27.91s user 11.34s system 69% cpu 56.432 total
[~/Git/rpn-fast] > time ../rpn/target/release/rpn-eval 
-0.72289664
../rpn/target/release/rpn-eval  22.92s user 11.81s system 63% cpu 54.863 total

Все упирается в производительность simd, самые горячие инструкции – movss, mulss, movd; они отъедают в сумме 60% процессорного времени, если верить выхлопу perf. Ввиду неявки остальных участников предлагаю поделить первое место, было довольно интересно.

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

На 1гб-блобе.

Это понятно. Racket запускается 0.5..1 секунду. Для очень коротких задач Racket можно только через Racketd использовать.

Все упирается в производительность simd

И в скорость чтения с диска. У меня cat input.txt > /dev/null примерно 20 секунд работает.

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

Эм, а это разве решение на ракете/лиспе или что там. А не на ассемблере?

Так что решение на Racket.

...

(define-λ! calc calc-type #:labels (item lplus lminus lmult next read-loop not-last)
  (push rbx)
  (push r12)
  (push r13)
  (push r14)
  (push r15)
  (xor r15 r15)
  (mov r12 (imm64 plus))
  (mov r13 (imm64 minus))
  (mov r14 (imm64 mult))
  (xor rax rax)
  (:! read-loop)
  (mov rdi (imm64 fd))
  (mov rsi (imm64 buf))
  (mov rbx (imm64 buf-size))
  (mov rdx rbx)
  (mov rax (imm64 read))
  (call rax)
  (cmp rax rbx)
  (je (rel8 not-last))
  (mov r15 (imm64 1))
  (:! not-last)
  (shr rax (imm8 (if (= width 4) 2 3)))
  (mov rcx rax)
  (mov rsi (imm64 buf))
  (:! item)
  (mov (if (= bits 32) eax rax) (mref bits rsi))
  (cmp rax r12)
  (je (rel8 lplus))
  (cmp rax r13)
  (je (rel8 lminus))
  (cmp rax r14)
  (je (rel8 lmult))
  (push rax)
  (jmp (rel8 next))

...

Ok.

im-0
()
Ответ на: комментарий от monk

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

И это решение похоже на то, имхо, что если ваш бинарник с асмом на рокете, возьмет например питонист и просто сделает subprocess.run или как-там в питоне дочерний процесс запустить. И вот это будет не менее легальное и показывающее мощь и скорость языка решение, чем Ваше.

Это имхо. Может я конечно что-то не понимаю.

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

А где скачать входные данные для обработки? Или каждый сам себе их подгатавливает.

Вот про три оператора я понял, про то что файла должно быть 4 тоже (по типу данных) тоже понял.

А сами данные какие должны быть в файлах?

Просто все под копирку с единым паттерном «[-] [+] [0.2][0.1][*] [0.3][0.4]» но с разными цифрами?

Или паттерн может быть случайным. А если случайным то это уже вносит неточность в бенчмарк-эксперимент.

В общем все должны запускать на одном и том же наборе данных а не на своих. Да, 8га тянуть сложно. Нужен скрипт который для всех жалающих сгенерит эталоннын данные.

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

А если случайным то это уже вносит неточность в бенчмарк-эксперимент.

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

Таким образом ты получишь сравнение разных реализаций на одних и тех же данных.

Все равно результаты разных людей не сравнить, так как у каждого человека свой процессор.

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

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

Так если задача такая. «Есть данные в файле в формате, подготовленном для обработки ассемблерными командами конкретного процессора». Если бы исходные данные были текстовые или вычисления требовались без потери точности, а не тупо addss/subss/mulss, то писал бы без ассемблерных вставок.

И это решение похоже на то, имхо, что если ваш бинарник с асмом на рокете, возьмет например питонист и просто сделает subprocess.run или как-там в питоне дочерний процесс запустить.

Моя программа не зависит от внешних бинарников и не требует наличия ассемблера (as/gas/…) в системе.

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

В общем все должны запускать на одном и том же наборе данных а не на своих. Да, 8га тянуть сложно. Нужен скрипт который для всех жалающих сгенерит эталоннын данные.

Скрипт есть. Компилируешь https://github.com/Siborgium/rpn и запускаешь «target/release/rpn-gen 100000000 | target/release/rpn-encode». Получаешь input.txt на 8ГБ. Если число поменьше, то и файл будет поменьше.

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

Есть данные в файле в формате, подготовленном для обработки ассемблерными командами конкретного процессора

Я вполне могу чего-то не понимать, но перечитал топик темы и ничего про ассм не увидел. Это «Эталонная архитектура - amd64.» - тоже не про ассм, на сколько могу судить.

Да данные не текстовые а бинарные, но это не ассм тоже, это просто чтение файла по байтам сразу же в нативные типы высокоуровневого языка, без трансляции «текстовое представление -> нативный тип»

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

это просто чтение файла по байтам сразу же в нативные типы высокоуровневого языка

Так в том-то и дело, что не высокоуровневого, а ассемблера. Нативные типы для Racket: scheme_float_type, scheme_double_type, scheme_integer_type, scheme_bignum_type. Нативный тип для SBCL: LispObject. Если бы было указано, что в файле нативные типы используемого языка, вопросов бы не было. Но в задаче указаны ассемблерные float, double, dword, qword.

без трансляции «текстовое представление -> нативный тип»

Если язык низкоуровневый и использует типы ассемблера, то да. А в Racket (без низкоуровневых вставок) мне придётся каждое число разбирать на байты и собирать из них значение, с которым можно работать. И также в любом другом высокоуровневом языке от PL/I до Паскаля.

monk ★★★★★
()

Там царь выложил код калькулятора: https://godbolt.org/z/-8Jqw3

Зависимости boost и fmt.

В Debian это:

sudo apt install libfmt-dev libboost-all-dev

Собирать так, флаги из godbolt и в конце -lfmt -lstdc++fs для зависимостей

g++ main.cpp -o tsar_calc -std=gnu++2a -Ofast -march=native -Wall -Wextra -fwhole-program -fno-finite-math-only -lfmt -lstdc++fs 

У меня из Linux только одноплатник с sdcard, так что не могу потестить, если кто будет сравнивать напишите сюда, интересны результаты.

@monk @Siborgium

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

Царь предложил эталонный вариант сборки:

git clone https://github.com/boostorg/hana.git
git clone https://github.com/fmtlib/fmt.git

g++ -I./hana/include -I./fmt/include -DFMT_HEADER_ONLY ...прочие флаги из godbolt
Забыл написать о том как юзать ./proga float < input.blob
соответственно вместо флоат могут быть: 
./proga float|double|uint64_t|uint32_t < input.blob

Я проверял только на float - вроде работает.
fsb4000 ★★★★★
()
Последнее исправление: fsb4000 (всего исправлений: 1)
Ответ на: комментарий от fsb4000

libboost-all-dev

Прикольно. Он за собой fortran и python вытянул.

Я проверял только на float - вроде работает.

$ ./tsar_calc float < input.txt
Ошибка сегментирования
$ target/release/rpn-eval
-1.3917632
$ wc -c input.txt
7999999996 input.txt
monk ★★★★★
()
Ответ на: комментарий от monk

Если собрать с -g -O0, тогда

(gdb) run float < input.txt
Starting program: tsar_calc float < input.txt

Program received signal SIGSEGV, Segmentation fault.
0x0000555555560d2b in <lambda(auto:3)>::<lambda(auto:4)>::operator()<float>(float) const (this=0x7fffffffe070, value=0.247834086) at main.cpp:68
68          auto push = [&](auto value) { *top++ = value; };

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

Исправил программу (сделал mmap на 1ГБ, а не на 10).

$ time ./tsar_calc float < input.txt
-1.3917632

real    0m46,385s
user    0m18,768s
sys     0m5,867s
$ time target/release/rpn-eval
-1.3917632

real    0m27,420s
user    0m19,815s
sys     0m5,601s
$ time racket rpn.rkt f32
-1.3917632102966309

real    0m28,806s
user    0m23,699s
sys     0m4,493s

По общему времени выполнения в два раза медленнее как rust’а, так и racket’а.

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

спасибо за тесты.

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

https://www.linux.org.ru/forum/development/15428662?cid=15430104

А модеры злые, лочат темы…

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

Результаты царя на 992M файле:

$ time ./rpn_eval_cpp float < input.txt 
3.0492005

real    0m1,193s
user    0m1,152s
sys     0m0,041s


$ time ./rpn_eval_cpp_clang float < input.txt 
3.0492005

real    0m1,163s
user    0m1,106s
sys     0m0,056s


$ time ./rpn-eval 
3.0492005

real    0m1,890s
user    0m1,745s
sys     0m0,145s

$ time racket rpn.rkt 
3.0492005348205566

real    0m1,981s
user    0m1,802s
sys     0m0,178s

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

Странные результаты. Причём разница меньше 0,1 секунды между rust и racket меня удивляет ещё больше, чем высокая скорость c++.

Предполагаю другую структуру файла… Можно этот файл куда-нибудь выложить?

Или может быть запуск с tmpfs. Скорость обработки в 1ГБ в секунду как бы намекает. У меня только чтение 8ГБ файла через cat или dd 25 секунд занимает.

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

Может быть. У меня это выглядит как-то так, в целых три раза медленнее. Однако, стоит отметить, что маппить stdin – интересная идея.

[~/Git/rpn-tsar] > time ./rpn-tsar float < input.txt
-0.72289664
./rpn-tsar float < input.txt  16.77s user 22.24s system 44% cpu 1:28.35 total
Siborgium ★★★★★
()
Ответ на: комментарий от monk

Позапускайте несколько раз…

Я на Windows проверил программу Siborgium на 100M на старом AMD FX.

Первый запуск:

$ time ./rpn-eval.exe
1.8637608

real    0m1,274s
user    0m0,000s
sys     0m0,062s

Не первый запуск

$ time ./rpn-eval.exe
1.8637608

real    0m0,432s
user    0m0,000s
sys     0m0,031s

Зачем вызывать delete если программа сама завершается? (комментарий)

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

Если input.txt целиком помещается в оперативку, то вариант с mmap быстрее (после второго запуска). Если не помещается, то особо не помогает.

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

Ключ-то именно в «помещается в оперативку». Поэтому на 8гб результаты, на мой взгляд, точнее – один файл, читается с диска, никаких плюшек.

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

Поэтому на 8гб результаты, на мой взгляд, точнее

Формально, в постановке задачи «на гигабайтном входном файле» и архитектура amd64. То есть косвенно утверждается, что файл обязан помещаться в память.

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

С чисткой кэша (перед каждым тестом sync; echo 3 > /proc/sys/vm/drop_caches) получается

$ time ./tsar_calc float < input.txt
-6.5364475

real    0m4,426s
user    0m2,343s
sys     0m0,518s
$ time racket rpn.rkt
-6.536447525024414

real    0m4,466s
user    0m3,182s
sys     0m0,776s
$ time target/release/rpn-eval
-6.5364475

real    0m3,532s
user    0m2,505s
sys     0m0,737s

Если Racket запускать через racketd, то

$ time racketd-client compiled/rpn_rkt.zo
-6.536447525024414

real    0m3,872s
user    0m0,001s
sys     0m0,005s

monk ★★★★★
()
Последнее исправление: monk (всего исправлений: 1)
Ответ на: комментарий от fsb4000
$ time ./tsar_calc float < input.txt
-6.5364475

real    0m2,763s
user    0m2,241s
sys     0m0,294s
monk ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.