r4 - 14 Sep 2006 - 22:03:42 - Sergej ZnamenskijYou are here: TWiki >  Refaldevel Web > TppBackend > ЛенивостьВOpenTS
Попробовал написать примерчик, который проще чем TRefal Permutations и, может быть, более искусственный. Однако он позволяет понять некоторые интересные моменты.

Небольшое пояснение: пример я писал на T++, но с использованием T-Refal рантайма. Т.е. по сути руками делал то, что в светлом будущем должно генерироваться компилятором. Причина в том, что в рантайме пока много неясного и вносить правки в компилятор, на мой взгляд рано.

Пример делает следующее:

Функция make(N) строит выражение:

(N(fib(N)))(N-1(fib(N-1)))...(1(fib(1)))

fib(N) вычисляет N-ое число фибоначчи.

Программа строит выражение при помощи функции make(), а затем выводит каждый терм этого выражения который имеет вид:

(M(fib(M))), где M%2 = 0

Очевидно, что на обычном рефале (не Т) данная программа будет работать ровно столько же, сколько программа полностью распечатывающая результат make() без всяких дополнительных условий.

При переходе к T-Refal ожидается, что за счет ленивости fib(нечетное_число) вычисляться не будут и мы получим ускорение даже на одном процессоре.

Таким образом тестирование я проводил так:

  1. Запускал программу распечатывающую весь результат make()
  2. Запускал программу распечатывающую только четные термы
  3. Сравнивал время счета

Результаты получились интересные:

trefal_task.png

Для числа 21 время счета при распечатывании всех термов: 6.285 (Tasks activated: 92732)

Для числа 21 время счета при распечатывании четных термов: 3.873 (Tasks activated: 57311)

Все как и ожидалось. А теперь посчитаем

Для чила 21 время счета при распечатывании нечетных термов: 6.265 (Tasks activated: 92732)ALERT!

Более того, такое же время и количество заданий мы получим распечатав всего один терм - 21-ый

А дело здесь вот в чем: в OpenTS задания сваливаются в очередь LIFO. я нарисовал картинку показывающую как происходят вызовы в описываемом примере. Синие стрелки это вход функции, красные - выход, красные пунктирные тоже выход но через TPtr. Из рисунка видно, что fib() сваливаются в очередь в таком порядке:

fib(1) ... fib(20), fib(21)

А вот вынимаются с хвоста. Т.е. что бы посчитать fib(21), нужно сначала посчитать fib(20), fib(19) ... fib(1) т.е. все задания.

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

-- PhilK - 28 Feb 2005

Пара вопросов:

  1. Правильно я понял, что если строить выражение с другой стороны (поменять местами вызовы fib(N) и make(N-1)), то 21-ый терм будет выдаваться быстро?
  2. Что это за очередь? По одной на каждом узле? В какой момент решается, что задание надо добавить в очередь?

-- Anton Orlov - 05 Mar 2005

  1. Да. Что бы 21-ый терм считался быстро, достаточно вызвать make(1) а дальше внутри make увеличиваем аргумент а не уменьшаем и до 21 а не до 0. Тогда make(21) упадет у нас в очередб последним и соответсвенно будет первым посчитан.
  2. Насколько я понимаю, очередь одна. В момент вызова т-функции она попадает в очередь. Дальше она там лежит до тех пор, пока кто-то не попросит ее результат или не попросят результат тех функций, которые попали в очередь до нее. Что бы добраться до них, придется посчитать и нашу не зависимо от того, нужна она или нет.

-- PhilK - 10 Mar 2005

Show attachmentsHide attachments
Topic attachments
I Attachment Action Size Date Who Comment
pngpng trefal_task.png manage 8.1 K 01 Mar 2005 - 00:30 PhilK Вызовы функций в программе
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r4 < r3 < r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback