LINUX.ORG.RU

Быстрая Scheme в численных расчетах

 ,


3

6

Многие реализации CL грешат тем, что вещественные числа «приводятся к указателю», как только эти числа покидают пределы функции. То есть, происходит то, что называется в Java и .NET боксингом. А как с этим обстоит дело в Scheme и Racket? Можно ли сделать так, чтобы вещественные числа возвращались без преобразования? Вообще, возможно ли такое в динамическом языке в принципе?

Вопрос возник в связи с тем, что я слышал о том, что некоторые реализации схемы, такие как Stalin, очень и очень быстры. Нид хэлп, buddhist

★★★★★

Честно говоря, я никогда не упирался в производительность такого рода. В «обычных» реализациях боксинг, конечно же, есть, но вроде бы хорошие компиляторы умеют нормально приводить типы.

По поводу Stalin: он слишком сырой, а в рамках вещественной арифметики еще и полон неточностей.

Я бы посоветовал попробовать Bigloo или Gambit. Bigloo почти сравним со Сталиным по скорости.

buddhist ★★★★★ ()

Вообще, возможно ли такое в динамическом языке в принципе?

По-моему, runtime specialization это умеет.

tailgunner ★★★★★ ()

у racket'а помоему еще и постоянные проверки на переполнения производятся чтобы если переполнится заменить int на bignum

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

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

buddhist ★★★★★ ()

В Схеме, соответствующей стандарту (с полноценным numeric tower) быстрая арифметика невозможна (и боксинг тут не при чем). В Bigloo (наплевавшем на стандарт) все намного лучше.

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

The Lisp Way:

Многие реализации лисп-отвёрток грешат тем, что если их перенацелить с шляпки одного шурупа на шляпку другого, они приводят шурупы к гвоздям. То есть, происходит то, что в называв Java и .NET «использованием крепежа». А как с этим обстоит дело в Scheme и Racket? Можно ли сделать так, чтобы шурупы не проверялись на тождество винтам и гвоздям? Вообще, возможно ли такое в динамическом языке в принципе?

http://www.inria.fr/indes/Manuel.Serrano/publi/sf-icfp96.ps.gz — вот статья Фили-Серрано по поводу оптимизаций проверок шурупов на схожесть с гвоздями, связанных с анализом шестигранных и крестовидных пазов на шляпках, возможных при этом приведений к гвоздям и замене прикручивания шурупов по краям на болты с шайбами.

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

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

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

В лиспе передаются объекты. Не все объекты могут быть представлены в машинном слове (из-за необходимости боксинга, например).

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

Я знаю. Просто очень уж забавно выглядит со стороны:

- А как мне замутить несколько функций для работы с числами с плавающей точкой?
- Вот тут у нас есть о-о-очень умная статья-а-а...

Тем более, что правильным ответом на вопрос ТС будет "(declare (type ..." и К°, а правильная статья висит в гугле чуть ли не на глагне: http://www.lrde.epita.fr/dload/papers/verna.06.imecs.pdf

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

Читай не то, что хочешь прочесть, а то, что написано:

> Многие реализации CL
> реализации CL
> CL

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

Т.е. ТС интересовался схеомй только с точки зрения потенциально большей эффективности по сравнению с CL.

Да и потом, телепаты мы или нет? Это лор или где?

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

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

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

Хорошо, давай для CL, да и чтобы работало с Clozure CL, 64 бита.

Задача. Функция f вызывает g. Нужно из g вернуть вещественное значение в f без боксинга. Можно использовать дополнительные структуры, такие как массивы, и прописывать их типы в declare.

Критерий приема решения. При запуске тестовой функции через time в Clozure CL не должен быть задействован сборщик мусора. Тестовую функцию нужно многократно вызывать в цикле, а результат, например, складывать.

Примечание. Подчеркиваю, что речь идет не об SBCL или LispWorks, а именно о Clozure CL.

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

Исправление:

«Критерий приема решения. При запуске тестовой функции через time в Clozure CL не должна выделяться память. [..]»

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

Хорошо, давай для CL,
Задача.

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

и чтобы работало с Clozure CL, 64 бита.

А полы тебе не помыть?

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

Ути-пути. Давно ли Racket и Stalin стали «Clozure CL, 64 бита»©™ ?

Когда лёгким двжиением руки подменяешь тему, всегда есть риск, что молнию «заест». ;)

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

Я? Разве? И где же? ;)

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

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

Есть еще, конечно, вариант, что тебя интересовал _исключительно_ возврат значения без боксинга, но такой варинат означает, что ты вообще практически ничего не знаешь о системе типов в лиспах...

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

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

Ой-ой, беда-то какая?!! Никто не хочет с тобой лепить куличики по твоим правилам?! Ай-яй-яй...

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

Подчеркиваю, что речь идет не об SBCL или LispWorks, а именно о Clozure CL.

Не знаю про Clozure, но у SBCL, как я понимаю, тут не очень всё хорошо. С некоторых пор (на x86 и x86-64) он хранит single и double float константы в «сыром» (то есть не боксированном) виде и сразу загружает их в SSE регистры после чего все операции с плавающими числами внутри одной функции производятся с помощью SSE инструкций. С другой стороны, там где, например, gcc делает для f

movss %xmm0, some_long_in_rodata(%rip)

и выходит из функции, после чего именно xmm0 используется в вызывающей g, SBCL (при любых оптимизациях) для f ещё делает

movd %rdx, %xmm0
shl %rdx, $32
or %rdx, $26

то есть вытаскивает значение из xmm0 в rdx, сдвигает 32 бита в старшую часть слова и добавляет тег:

CL-USER> sb-vm:single-float-widetag
26

и в вызывающей функции g используется уже rdx, чтобы что-то опять посчитать нужно обратно загрузить его в SSE регистр.

С этим можно бороться:

  • Сделать declaim inline для f.
  • Определять нужные функции локально в flet/labels.
  • В CMUCL ещё была блочная компиляция - можно начать блок с помощью declaim start-block и завершить с declaim end-block, без необходимости определять функции локально.

Если говорить вообще, то, да - в чисто динамическом языке, по определению, функции всегда принимают и возвращают top type (реализуемый как указатель на тег размеченного объединения или как тегированный указатель, как в SBCL/Factor), поэтому, вообще говоря, значение какого угодно типа может попасть куда угодно - если не смотреть на тег (если того нет), то функция просто упадёт. Принимать и возвращать значения не top типа могут только примитивные функции (реализуемые в рантайме - они могут разобрать тегированный указатель или посмотреть тег объединения и взять из него значение какого-то специфичного типа). Любой анбоксинг возможен благодаря превращению динамически типизированных программ в статически типизированные (так что есть гарантия того что, например, в эту функцию всегда попадает значение только вот этого типа).

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

Меня интересует агрессивный анбоксинг, который, к сожалению, не всегда возможен, даже если прописаны типы.

А вот интересно, отвлекаясь от данной темы, а как реализуется передача множественных значений (values)? Через кучу или возможны оптимизации через стек? Если так посмотреть, то до черта численных функций, которые возвращают два значения. Было бы разумно это дело оптимизировать, не выделяя память на куче. И если, вдруг, оптимизировано, то почему бы тогда не оптимизировать передачу вещественных значений? Но это больше из области размышлений, чем из практики.

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

Ах да, численные функции возвращают вещественные значения, а они уже в куче. Так что, вопрос про оптимизацию отменяется :)

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

Меня интересует агрессивный анбоксинг, который, к сожалению, не всегда возможен, даже если прописаны типы.

Не всегда возможен в языке со сборкой мусора, ленивостью или параметрически полиморфными типами. Сборщику нужны теги, thunk-и в любом случае тегированы, полное стирание полиморфизма требует whole program optimization / function specialization, при которой code size растёт экспоненциально от source size.

В MLTon и строгом подмножестве GHC с примитивными и строгими UNPACKed типами фиксированная и плавающая арифметика, плоские кортежи и массивы не боксятся. Правда, это подмножество GHC не особо удобно использовать (не считая unboxed массивов), а MLTon сам по себе не особо используется.

а как реализуется передача множественных значений (values)?

disassembly в SBCL подсказывает, что так же как и передача аргументов - первые три values через регистры (edx, edi, esi), остальные - через фрейм на стеке (относительно rbp).

Ах да, численные функции возвращают вещественные значения, а они уже в куче.

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

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

и большие

То есть, большие, конечно, не влезут в регистры, так что в куче в виде какой-нибудь определённой struct bignum.

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

Хорошо, давай для CL, да и чтобы работало с Clozure CL, 64 бита.

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

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

В общем, надо много раз подумать, прежде чем приступить к написанию числодробильни на CL :)

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

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

Ну, почему же. Когда я пишу на C#/F# или Java/Scala, то я обычно знаю, где именно происходит боксинг, хотя Scala может преподнести сюрпризы.

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

Не все возможно на Си, или просто я не знаю, как некоторые вещи там сделать. Например, дискретные (прерываемые) процессы удобно моделировать с помощью продолжений. Эти процессы могут взаимодействовать с интегралами и прочими числовыми функциями. И я ума не приложу, как это все реализовать на Си.

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

Любопытно, а как у питонщиков обстоит с этой областью? А то многие тут носятся со своим NumPy

А у питонщиков, кроме numpy, есть numexpr и cython, и, вполне возможно, будет numpy для PyPy: http://morepypy.blogspot.com/2012/04/numpy-on-pypy-progress-report.html

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

Лисп просто невозможно так поставить %)

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

отсутствие боксинга нельзя гарантировать, даже если ты пишешь на сишке.

Ну здрасьте, приехали. Давайте примеры.

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

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

В чем проблема написать интегралы и прочие числовые функции на си и потом дергать через ффи?

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

Давайте примеры.

Если я не могу привести примеры, это не значит, что можно гарантировать их отсутствие. В стандарте сишки написано, что + на флоатах не боксит ничего внутри?

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

В стандарте сишки написано, что + на флоатах не боксит ничего внутри?

Откуда вообще в Си возьмется боксинг?

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

Откуда вообще в Си возьмется боксинг?

Да не важно, откуда он возьмется, важно запрещает ли его стандарт. Ну для конкретики можно рассмотреть такую ситуацию - я сделал транслятор из си в scheme, соответственно арифметика сишки транслируется в арифметику схемы. боксинг инклудед. вы можете дать гарантии, что ваш код не будет работать из-под такого транслятора (то есть запрещает ли стандарт сишки подобные реализации)?

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

Хотелось бы более разумного и реалистичного примера.

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

В общем, надо много раз подумать, прежде чем приступить к написанию числодробильни на CL :)

Есть пример вот такой (и вот) числодробилки - g++, stalin и ocaml примерно на одном уровне, если верить результатам.

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

Откуда вообще в Си возьмется боксинг?

Да не важно, откуда он возьмется, важно запрещает ли его стандарт.

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

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

Ты просто чемпион адских огнеметчиков. Не знаю, что ты имел в виду под «вашим кодом», но я могу гарантировать одно - ты либо предоставишь стандартную для Си модель памяти (никакого боксинга и numerical tower, все числа фиксированных размеров), либо у тебя ничего не будет работать. Как именно реализуются операции над числами - на Схеме или счетах, совершенно неважно.

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