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)

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

кресты являются сями

Скомпилируешь C11 на плюсовом компиляторе – приходи, расскажешь. Пока что – нет.

заявляет, что это не медленнее

«Пропаганда» вообще ничего про mmap и файлы не говорит, потому что оно все платформо-зависимое. Приведи примеры, на ровном месте я тоже могу многого наговорить.

векторов и станадартных средств у тебя нет

Сильное заявление. Чем подкрепишь? Или оно опять «ворованное».

Аллокатор ворованный

Здрасте, кто в здравом уме пишет свой аллокатор? Все нормальные люди системный используют обычно. Если ты про jemalloc, то он давно уже не используется в расте.

вектора ворованные

Спасибо, посмеялся.

Кодоген ворованный

Можешь на cranelift скомпилировать, если LLVM ворованный. Должно завестись.

рантайм - ворованный

У кого тогда не ворованный?

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

О, да у нас нонейм опять обосрался и не знает, что абсолютно неважно что там есть в gnu - там есть что угодно, даже паскаль и жава. Следует ли из этого что-то? Нет. В школу.

Глупому царю в школе одному скучно без комментаторов с ЛОРа? Терпи!

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

GCC’s RTL is usually written in a form which looks like a Lisp S-expression:

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

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

Во-первых никакого лиспа в принципе нет. Это уже шизофрения.

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

Глупый нонейм так быстро обделался? Ну ничего. Мыть полы и завидовать - это твоё призвание. Терпи.

Когда царь уже напишет в своём великом, написанном на С++, блоге, что он опять не обосрался?

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

Скомпилируешь C11 на плюсовом компиляторе – приходи, расскажешь. Пока что – нет.

К чему ты вырсал эти потуги нелепые? Что они значат и что из них следует.

«Пропаганда» вообще ничего про mmap и файлы не говорит, потому что оно все платформо-зависимое. Приведи примеры, на ровном месте я тоже могу многого наговорить.

Зачем ты врубаешь идиота? Пропаганда заявляет «быстро без unsafe» - ты обделался. Никаких сносок на то, что «ммап» и прочее не входит не было.

Здрасте, кто в здравом уме пишет свой аллокатор? Все нормальные люди системный используют обычно. Если ты про jemalloc, то он давно уже не используется в расте.

Ну всё, тут уже можно заканчивать. Пациента не спасти. Маня, нету никакого системного аллокатора - системный аллокатор - это mmap/brk мёртвый.

То, что ты украл - это аллокатор из libc, т.е. аллокатор сишной стандартной либы. Как можно нести такую херню - я не представляю.

К тому же, очевидно что ты ничего не напишешь и воруешь. А люди пишут, в том числе они и написали glibc, как и написали тот же jemalloc, который ты так же пытался украсть.

xiomar_georgios
()
Ответ на: комментарий от O02eg

Меня мало волнует скулёжь какие-то обгадившися нонеймов-поломоев. Ко мне обращаться и спрашивать что-то с меня может только равный мне. Нонейм-поломой равным мне не является.

xiomar_georgios
()
Ответ на: комментарий от ugoday

Меня, ты совсем поплыл? Пошел формализовать с-выражения и доказывать, что они были в каком-то лиспе. Как придёшь - ты сядешь в лужу. Хотя ты не придёшь.

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

AST всю жизнь так записывались.

Набрасывать так набрасывать.

Только лисперы ...
... деревья рисуют списками (s-expressions). Так что не надо про всех.

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

anonymous
()
Ответ на: комментарий от xiomar_georgios

Ко мне обращаться и спрашивать что-то с меня может только равный мне.

Таких идиотов ещё поискать нужно.

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

… деревья рисуют списками (s-expressions). Так что не надо про всех.

В каком месте это список?

xiomar_georgios
()
Ответ на: комментарий от O02eg

Маня, поэтому ты, нонейм-поломой за мною бегаешь. Ты мне нахрен ненужен, а вот я тебе нужен. Потому сам с собою - ты никто. Бегая вокруг меня - ты пытаешься хоть в каком-то виде попрыгать вокруг большего.

Это типичная реакция. Здесь нет ничего такого.

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

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

Дальше не буду развивать тему. И тебе не советую, последствия настигнут и вполне обоснованные.

Всё, молчу-молчу. :)

anonymous
()
Ответ на: комментарий от xiomar_georgios

Под «системным аллокатором» я и подразумевал аллокатор из libc. Ты действительно не понимаешь, что сишная библиотека – де-факто стандарт, и ее используют так или иначе 99.9% прикладных программ?

люди пишут

Люди действительно пишут, вот только никто не пишет аллокатор ради одной программы. Зачем изобретать велосипед, если платформа предоставляет готовый аллокатор? Кроме того, есть полностью ржавый аллокатор.

пропаганда заявляет

Так. Во-первых, говоря «пропаганда заявляет», вставляй ссылочку на конкретную цитату. Во-вторых, как кресты, так и раст стремятся достичь бесплатных/крайне дешевых относительно времени исполнения кода абстракций. Абстракции пишутся над чем-то, и я не обязан, вообще говоря, их использовать. Хочу – пишу байты по рандомному адресу, и никто мне не запретит такую программу сделать. То, что она будет падать – другой вопрос.

что из них следует

кресты являются сями

Ну-ка расшифруй тогда вот это.

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

Под «системным аллокатором» я и подразумевал аллокатор из libc. Ты действительно не понимаешь, что сишная библиотека – де-факто стандарт, и ее используют так или иначе 99.9% прикладных программ?

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

Пиши правильно - ворованный libc-аллокатор.

Люди действительно пишут, вот только никто не пишет аллокатор ради одной программы.

Т.е. на твоём недоязычке написана одна программа? Сильно.

Кроме того, есть полностью ржавый аллокатор.

Маня, ты адекватен? Это говно, в противном случае ты бы не воровал чужое, если бы было своё.

К тому же, никакого недоязычка там нет. На твоём говне аллокатор не написать. Поэтому а) это ворованная реализация, просто перепаста какого-то примитивного говна. б) она состоит на 99% из unsafe и ворованного рантайма.

Так. Во-первых, говоря «пропаганда заявляет», вставляй ссылочку на конкретную цитату.

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

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

Полная чушь. Ты просто украл концепцию и приписал её себе. Никакого зерокоста у тебя нет. Тебя поимела пропаганда. Именно поэтому ты побежал выкидывать все абстракции.

Абстракции пишутся над чем-то, и я не обязан, вообще говоря, их использовать.

Обязан. В противном случае твоё недоязычок теряет смысл к существованию.

Хочу – пишу байты по рандомному адресу, и никто мне не запретит такую программу сделать. То, что она будет падать – другой вопрос.

Хочу - это про С/С++. Твоя методичка отрицает хочу. Она говорит, что ты можешь жрать дерьмо и писать быстрые программы. Ты же отрицаешь это - зачем?

Ну-ка расшифруй тогда вот это.

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

Во-вторых это ничего не значит. Это мелкие различия. Си это базовый язык для С++. В С++ всё си, а уже поверх этого набраны какие-то надстройки.

Просто формально они выделены в отдельный язык. Но это не отдельный язык.

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

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

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

Зачем? Бери лучшее, достойное. Если ты способен декларировать за собою выбор - ты не потерян. По крайней мере на уровне деклараций.

Можешь не отвечать на всю херню - всё равно у тебя заранее слабая позиция. Просто ответь - зачем? Что вами движет? Зачем себя обрекать на жалкое существование? Или ты веришь, что оно не жалкое? Как это происходит. Как вас вербуют? Расскажи.

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

libc не является системной и никакой это не системный аллокатор.

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

https://www.gnu.org/software/libc/

The GNU C Library project provides the core libraries for the GNU system and GNU/Linux systems, as well as many other systems that use Linux as the kernel.

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

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

Здесь лишь сказано, что она является частью системы. Частью системы так же является баш. Либо инит. Либо компилятор. Ничего из это не является системным в том контексте, в котором обсуждалось здесь.

К тому же, glibc - это не libc, клоун. libc часть glibc. Поэтому, клоун, ты обделался даже тут.

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

xiomar_georgios
()

Вы бы привели ссылки откуда скачать набор данных для тестовых запусков. Или (если гиг лень хостить) то ссылки на скрипт на которым вы сгенерили входные данные. Думаю будет правильно что все участники будут работать с одними и теми же данными.

anonymous
()

Так и запишем: адепты C++ ничего полезнее калькулятора придумать не могут.

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

Ты не прав!..

Они даже калькулятор нормально придумать не могут. Тем более, представить код.

anonymous
()
Ответ на: комментарий от ugoday

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

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

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

ugoday ★★★★★
()
Ответ на: комментарий от Siborgium
$ cargo build --release
    Updating crates.io index
  Downloaded rand v0.3.23
  Downloaded rand v0.4.6
  Downloaded libc v0.2.66
   Compiling libc v0.2.66
   Compiling rand v0.4.6
   Compiling rand v0.3.23
   Compiling rpn v0.1.0 
error[E0599]: no method named `to_ne_bytes` found for type `f32` in the current scope
  --> src/rpn-eval.rs:14:27
   |
14 |     let plus = DEFINES[0].to_ne_bytes();
   |                           ^^^^^^^^^^^

error[E0599]: no method named `to_ne_bytes` found for type `f32` in the current scope
  --> src/rpn-eval.rs:15:28
   |
15 |     let minus = DEFINES[1].to_ne_bytes();
   |                            ^^^^^^^^^^^

error[E0599]: no method named `to_ne_bytes` found for type `f32` in the current scope
  --> src/rpn-eval.rs:16:31
   |
16 |     let multiply = DEFINES[2].to_ne_bytes();
   |                               ^^^^^^^^^^^

error[E0599]: no function or associated item named `from_ne_bytes` found for type `f32` in the current scope
  --> src/rpn-eval.rs:39:31
   |
39 |                 let v = Type::from_ne_bytes(raw);
   |                         ------^^^^^^^^^^^^^
   |                         |
   |                         function or associated item not found in `f32`

error: aborting due to 4 previous errors

Что делаю не так?

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

И, судя по коду, у тебя вот этот кусок задания не выполняется:

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

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

У тебя ((0,2 + 0,1) - (0,3 * 0,4)) записывается как

[0.2] [0.1] [+] [0.3] [0.4] [*] [-]
monk ★★★★★
()
Ответ на: комментарий от monk
$ cargo build --release --features u32 --no-default-features
   Compiling rpn v0.1.0 (/home/monk/Программирование/rust/rpn)
error[E0599]: no method named `abs` found for type `u32` in the current scope
  --> src/rpn-gen.rs:25:45
   |
25 |             print!("{} ", rng.gen::<Type>().abs());
   |                                             ^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0599`.
error: Could not compile `rpn`.

To learn more, run the command again with --verbose.
$ cargo build --release --features u64 --no-default-features
   Compiling rpn v0.1.0 (/home/monk/Программирование/rust/rpn)
error[E0308]: mismatched types
  --> src/defines.rs:30:33
   |
30 | pub const DEFINES: [Type; 3] = [MAX, MAX - 1, MAX - 2];
   |                                 ^^^ expected u64, found u32

error: aborting due to previous error
monk ★★★★★
()
Ответ на: комментарий от monk

rust надо совсем последний ставить, а не штатный.

Собственно, всё, что надо знать про кодинг на этом вашем русте. Сколько лет прошло, а оно всё еще в активной разработке и ставить надо самую последнюю бету. Даже на ноде всё проще.

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

Реализация - говно. Во-первых на вот этом:

[-] [+] [0.2][0.1][*] [0.3][0.4]
она сломается.
Во-вторых, она считает линейно, а это уже не интересно. Там надо избавляться как-то от ветвлений, что-то придумывать со стеком, чтобы всё скатилось к векторизации, например.

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

на вот этом … она сломается.

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

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

Так напиши. Или его реализация на Rust автоматически выигрывает в связи с неявкой остальных претендентов. :-)

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

Так напиши.

Если бы умел, был бы если не Царём, то Боярином точно.

Или его реализация на Rust автоматически выигрывает в связи с неявкой остальных претендентов.

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

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

Прямая польская нотация разве через стек вычисляется?

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

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

Прямая польская нотация разве через стек вычисляется?

Здесь в задаче обратная написана. Она через стек. В примере — прямая. Там тоже стек

[-] [+] [0.2][0.1][*] [0.3][0.4]
push -
push -
push 0.2
; сверху число и сейчас число
pop, pop, calc, push 0.3
push *
push 0.3
pop; pop; calc; push 0.12
pop; pop; calc
monk ★★★★★
()
Ответ на: комментарий от monk

Здесь в задаче обратная написана. Она через стек. В примере — прямая. Там тоже стек

На самом деле достаточно 3-х указателей.

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

Неудобно, если арность операторов будет не 2.

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

Залей код куда-нибудь, интересно будет сравнить результаты. На моем ноуте мой код на 8гб-блобе (недолго сомневаясь, сгенерировал миллиард чисел) работал примерно минуту, с текущим коммитом 30-40 секунд.

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

Можно подробнее? Никогда не слышал про иные способы вычисления выражений в полизе иначе как через стек.

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

Надо какой-нибудь null для значений

Указатели
c - оператор, a,b - операнды
1.Идём по буферу ищем последовательность с,a,b 
  [-][*][/][15][-][7][+][1][1][3][+][2][+][1][1]
   ^с ^a? fail->
      ^c ^a? fail->
  [-][*][/][15][-][7][+][1][1][3][+][2][+][1][1]
         ^c ^a ^b? fail->  
...
  [-][*][/][15][-][7][+][1][1][3][+][2][+][1][1]
                      c  a  b
Считаем
  [-][*][/][15][-][7][n][2][n][3][+][2][+][1][1]
                 <-с?    b  
Идём влево, если возможно.
  [-][*][/][15][-][7][n][2][n][3][+][2][+][1][1]
                c  a     b  
Считаем
  [-][*][/][15][n][5][n][n][n][3][+][2][+][1][1]
         c  a      b        
  [-][*][n][3][n][n][n][n][n][3][+][2][+][1][1]
   a? c     b     
fail, ищем вправо, меняем b на a
  [-][*][n][3][n][n][n][n][n][3][+][2][+][1][1]
      c     a                 b    
Считаем...
  [-][n][n][9][n][n][n][n][n][n][+][2][+][1][1]
   с        a                    b? fail    
Ищем заново
  [-][n][n][9][n][n][n][n][n][n][+][2][+][1][1]
                                 с  a  b?     
                                       c  a  b
  [-][n][n][9][n][n][n][n][n][n][+][2][n][2][n]
                                 c  a     b
  [-][n][n][9][n][n][n][n][n][n][n][4][n][n][n]
   c        a                       b
  [n][n][n][5][n][n][n][n][n][n][n][n][n][n][n]   
            b
Нихрена нет, выводим b                            
Короче со стеком проще, чем елозить туда-сюда по буферу.

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

У меня чуть медленнее получается…

$ time target/release/rpn-eval
1.8798405

real    0m30,487s
user    0m20,005s
sys     0m5,920s
$ time racket test.rkt
1.8798404932022095

real    0m53,863s
user    0m21,378s
sys     0m6,687s

Что за время, которое попадает в real, но не user и не sys?

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

Что за время, которое попадает в real, но не user и не sys?

Ждёт IO или заблокировано ещё на чём-то.

mv ★★★★★
()

Победителем признаётся та реализация, которая будет уделывать конкурентов в лоскуты на гигабайтном входном файле

ЧТД. «Язык лучше» - это «уделывает конкурентов в лоскуты», причём, по времени исполнения. Причём, на CPU. Причём, на примитивной задаче, которую, вероятно, ТС ещё может осилить.

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

Компилируется Racket’ом. Никаких внешних ассемблеров не использует. Более того, один файл для всех четырёх форматов данных. Разве такое сделаешь на ассемблере?

Так что решение на Racket. Привязанное к Sys V AMD64 ABI.

monk ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.