Регистрация | Войти
Lisp — программируемый язык программирования
RSS
sbcl/ccl time-test :dual-core/x86-64
Ander Skirnir - 09.04.2010 05:48, Сообщений - 24
Не могу понять, это в ccl time криво работает, или я туплю. И как бы там ни было, получается, что ccl здесь справился быстрее ?:

sbcl> (time (progn (delete-negatives-a *a*) nil))

Evaluation took:
0.207 seconds of real time
0.202802 seconds of total run time (0.046801 user, 0.156001 system)
98.07% CPU
412,344,400 processor cycles
0 bytes consed

NIL

ccl> (time (progn (delete-negatives-a *a*) nil))

(PROGN (DELETE-NEGATIVES-A *A*) NIL) took 44,000 microseconds (0.044000 seconds) to run
                    with 2 available CPU cores.
During that period, 46,800 microseconds (0.046800 seconds) were spent in user mode
                    0 microseconds (0.000000 seconds) were spent in system mode
NIL
[#]
А какое определение у delete-negatives-a?
treep - 09.04.2010 09:07
[#]
> (0.046801 user, 0.156001 system)
Вот это меня настораживает: юзерспейсный код отработал те же 0.04 секунды. Все остальное время - system. Смотреть код надо детально.
dmitry_vk - 09.04.2010 09:16
[#]
Код кривоват правда, можно было лучше сделать:

(defun delete-negatives-a (lst)
  (loop (if (and (car lst) (< (car lst) 0))
            (setf lst (cdr lst))
            (return)
)
)

  (let ((iter-ptr lst))
    (loop (when (null (cdr iter-ptr))
            (return lst)
)

          (if (< (cadr iter-ptr) 0)
              (rplacd iter-ptr (cddr iter-ptr))
              (setf iter-ptr (cdr iter-ptr))
)
)
)
)

Кстати, немного оффтоп, но вот такой вызов считается хвостовой рекурсией ?:

(defun delete-negatives-b (lst)
  (if (null lst)
      nil
      (if (< (car lst) 0)
          (delete-negatives-b (cdr lst))
          (cons (car lst) (delete-negatives-b (cdr lst)))
)
)
)


Дело в том, что plt-scheme его сумела соптимизировать как хвосто-рекурсивный, а sbcl - нет. При этом на схеме он еще и шустро миллионный список обрабатывает - в среднем за 250 мс, а на sbcl, понятное дело, stack-overflow.
Ander Skirnir - 09.04.2010 09:31
[#]
Нет, этот вызов не хвостовой. В некоторых схемах добавлен специальный случай для cons - компилятор умеет преобразовывать их в хвостовой рекурсивный вызов. В sbcl такого нет. Надо в delete-negatives-b добавить cons-ячейку в качестве параметра.
dmitry_vk - 09.04.2010 10:26
[#]
Про хвостовую рекурсию:

TR - это рекурсивная запись 0-ого уровня вложенности, которая преобразуется в итеративный процесс, при этом очередным уровнем считается именно вложенность в функцию (которая компилируется в call или jmp), а не в макросы или в специальные формы (в которые превращаются макросы, например cond -> if).

В примере выше не TR, т.к. вложенность 1-ого уровня: if не учитываем, но видим, что рекурсивный вызов вложен в функцию cons. Будь ещё что-то, например (length (cons # то это была бы уже вложенность 2-ого уровня.

gcc сейчас умеет работать как с 0, так и с 1 вариантами. SBCL - только с обычной TR. Поверю вам на слово :) Plt-scheme тоже может.

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


(defun make-random-list (n r)
  (loop for i from 1 to n
        collect (- (/ r 2) (random r))
)
)


(defmacro collect (thing list)
 `(setf ,list (append ,list (list ,thing)))
)


;;; пусть есть список позитивных
;;;          и список негативных
;;;   для каждого элемента в полном списке
;;;     если элемент < 0
;;;     то поместить в список негативных
;;;     иначе поместить в список позитивных
;;;   вернуть значения - позитивные и негативные

(defun tweak-list/positive-negative (list)
  (let ((negative (the list nil))
        (positive (the list nil))
)

    (dolist (element list)
      (if (< element 0)
          (collect element negative)
          (collect element positive)
)
)

    (values positive negative)
)
)


(defun tweak-list/most-positive (list)
  (let ((positive (the list nil)))
    (dolist (element list)
      (if (>= element 0)
          (collect element positive)
)
)

    positive
)
)


* (time (defvar *list* (make-random-list 1000000 1000000)))

Evaluation took:
 0.212 seconds of real time
 0.187201 seconds of total run time (0.156001 user, 0.031200 system)
 88.21% CPU
 337,397,310 processor cycles
 7,999,488 bytes consed
 
*LIST*
* (time (defvar *list!* (tweak-list/most-positive *list*)))


правда последняя строчка не вычисляется - SBCL/Winda/AMD.
treep - 09.04.2010 10:57
[#]
Хотя постоянный setf - это плохо. Но что-то ничего в голову не приходит.
treep - 09.04.2010 11:08
[#]
Антипод push - это я зря, лучше reverse про-push-унного списка.

(defun tweak-list/most-positive (list)
  (let ((positive (the list nil)))
    (dolist (element list)
      (if (>= element 0)
          (push element positive)
)
)

    (reverse positive)
)
)


(time (defvar *list!* (tweak-list/most-positive *list*)))

Evaluation took:
 0.172 seconds of real time
 0.156001 seconds of total run time (0.109200 user, 0.046801 system)
 [ Run times consist of 0.109 seconds GC time, and 0.048 seconds non-GC time. ]
 90.70% CPU
 273,628,732 processor cycles
 8,003,584 bytes consed
treep - 09.04.2010 11:39
[#]
Красиво очень пишете, отличный вариант иммутабельной функции. Хотелось бы еще увидеть что-нибудь красивое структуроразрушающее - с максимальной экономией памяти (не создавать новые списочные ячейки) и процессора.

> постоянный setf - это плохо
А почему? Он же один раз раскроется в (setq negative ...). Вот append же каждый раз будет список проходить от самого начала до конца - это точно не очень хорошо. По идее, порядок чисел в списках нас здесь не должен особо интересовать (ведь он теряется при разделении), поэтому можно вместо collect просто заюзать push.
Ander Skirnir - 09.04.2010 11:58
[#]
Я =    http://t1.gstatic.com/images?q=tbn:5_Q5SCNFwFI8qM:http://www.terminally-incoherent.com/blog/wp-content/uploads/2007/09/slowpoke.gif

Ander Skirnir - 09.04.2010 12:01
[#]
Кстати, если Вас всё-же интересует по какой-то причине порядок, можете делать, как макрос loop при использовании collect - хранить указатель на последнюю списочную ячейку и через неё добавлять новые, затем смещая её - это будет быстрее push + reverse.
Ander Skirnir - 09.04.2010 12:08
[#]
Да мне можно на "ты" :)

>> Кстати, если Вас всё-же интересует по какой-то причине порядок, можете делать, как макрос loop при использовании collect - хранить указатель на последнюю списочную ячейку и через неё добавлять новые, затем смещая её - это будет быстрее push + reverse.

Я пока не осилил функции над списками с побочными эффектами вроде rplacd, а нет ли функции работающей как push, но в обратном порядке? Чтобы без новой памяти трогать список с другого конца?
treep - 09.04.2010 13:01
[#]
> нет ли функции работающей как push, но в обратном порядке? 

nconc? Только, обычно это не самая хорошая идея, ведь быстродействие падает: что бы добавить что-то в конец, его надо сначала найти. Чем больше список - тем дальше до конца. Связан push и nreverse (вместо reverse) работают на самом деле очень хорошо, ибо не потребляют лишней памяти и просты в использовании.
archimag - 09.04.2010 13:08
[#]
Кстати, nconc - структуроразрушающий аналог append, меня до сих пор удивляет почему его не назвали nappend.

Запустил функцию из первого поста на пеньке втором 233 мгц, 320 мб оп :

* (time (progn (delete-negatives-a *a*) nil))

Evaluation took:
  0.160 seconds of real time
  0.150216 seconds of total run time (0.150216 user, 0.000000 system)
  93.75% CPU
  52,275,413 processor cycles
  0 bytes consed

То есть, sbcl здесь работает быстрее, чем на двухядерном пентиуме 2 ггц с 4 гигами оп :)
Ander Skirnir - 09.04.2010 14:19
[#]
Просьба полностью выложить код, которым тестировалось (код функции delete-negatives-a, используемые опции компиляции, и значение переменной *a*)
dmitry_vk - 09.04.2010 14:40
[#]
> полностью выложить код
(defun delete-negatives-a (lst)
  (loop (if (and (car lst) (< (car lst) 0))
            (setf lst (cdr lst))
            (return)
)
)

  (let ((iter-ptr lst))
    (loop (when (null (cdr iter-ptr))
            (return lst)
)

          (if (< (cadr iter-ptr) 0)
              (rplacd iter-ptr (cddr iter-ptr))
              (setf iter-ptr (cdr iter-ptr))
)
)
)
)


(defun make-random-list (n r)
  (loop for i from 1 to n
        collect (- (/ r 2) (random r))
)
)


(defvar *a* (make-random-list 1000000 100))

* (time (progn (delete-negatives-a *a*) nil))

Evaluation took:
  0.150 seconds of real time
  0.150216 seconds of total run time (0.150216 user, 0.000000 system)
  100.00% CPU
  50,981,723 processor cycles
  0 bytes consed

> используемые опции компиляции
sbcl.exe --load delete-negatives.lisp
http://smaylik.ru/templates/smaylik/images/ab.gif

> Я пока не осилил функции над списками с побочными эффектами вроде rplacd

Так это ж гораздо проще, чем большинство того, что ты пишешь на этом форуме (:

http://s50.radikal.ru/i129/1004/d6/73e2ad827342.png

rplaca меняет содержимое клеточки car списочной ячейки (cons),
rplacd - содержимое cdr

В первом томе Мира Лиспа целая глава (2.8, внутреннее представление списков) этому посвящена, где всё на пальцах, с примерами и рисуночками объяснено.
Ander Skirnir - 09.04.2010 15:13
[#]
Кстати, только что наткнулся на ошибку:

(defun test ()
  (time (progn (setf *a* (make-random-list 1000000 100)) nil))
  (time (progn (delete-negatives-a *a*) nil))
)

* (test)

Evaluation took:
  1.201 seconds of real time
  1.181699 seconds of total run time (0.881267 user, 0.300432 system)
  98.42% CPU
  398,516,315 processor cycles
  7,999,488 bytes consed

Evaluation took:
  0.151 seconds of real time
  0.140201 seconds of total run time (0.140201 user, 0.000000 system)
  92.72% CPU
  50,552,099 processor cycles
  0 bytes consed

NIL
* (test)

debugger invoked on a SIMPLE-ERROR: EXCEPTION_ACCESS_VIOLATION

Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
  0: [ABORT] Exit debugger, returning to top level.

("bogus stack frame")
0]
WARNING: Starting a select without a timeout while interrupts are disabled.


Только один раз возникла, воспроизвести при перезапусках не удалось.
Ander Skirnir - 09.04.2010 15:29
[#]
 > Я пока не осилил функции над списками с побочными эффектами вроде rplacd
Почему бы не забить и не использовать (setf ([car | cdr] ...)..)? Он раскрывается в rplacd/rplaca и выглядит лучше.
>
Чтобы без новой памяти трогать список с другого конца?
 Добавление в конец означает изменение правой части последней cons-ячейки на адрес списка, который нужно присоединить. Чтобы обратиться к этой ячейке нужно либо хранить ее(O(1)), либо пройтись по списку(O(n)).
Fallen - 09.04.2010 18:02
[#]
> Вот это меня настораживает: юзерспейсный код отработал те же 0.04 секунды. Все остальное время - system. Смотреть код надо детально.

Возможно, это - проявление особенности сборщика мусора sbcl. После цикла сборки мусора он помечает все страницы памяти как read-only, и использует segfault при попытке записи в эту страницу как указание на то, что страница теперь "грязная" (сразу после этого страница помечается как rw, и дальнейшая запись в неё к сегфолтам не приводит). Из-за сегфолта первая запись в каждую страницу памяти сразу после сборки мусора немного замедляется (на чтение и последующие записи это влияния не оказывает).

Немного про это написано тут
slav - 09.04.2010 18:54
[#]
Если дело работает на винде то ещё возможно, что всё дело в отсутствии тредов - их нет, нет SMP и распараллеливания на два ядра, в вот в CCL есть поддержка потоков на количестве ядер > 1 и на винде. Ведь если речь идёт о сортировке списков ~миллионов элементов - параллельность может дать не хилый выигрыш на нескольких ядрах.

  92.72% CPU

должно же быть > 100.
treep - 09.04.2010 19:48
[#]
Программа однопоточная, и поддержка потоков роли здесь не сыграет.
Сборщик мусора тоже вряд ли причастен - программа ничего не аллокейтит, а лишь изменяет сгенерированный ранее список, поэтому все сегфолты были до запуска непосредственного кода. Ну и к тому же в винде действительно могут быть аномалии, т.к. виндовый порт находится в немного более заброшенном состоянии. (Кстати, можно в диспетчере задач в винде смотреть количество ошибок страниц (т.е., сегфолтов) - я когда в первый раз увидел, насколько дикое количество сегфолтов генерируют ccl и sbcl, очень сильно удивился).
dmitry_vk - 09.04.2010 22:31
[#]
ВНЕЗАПНО! Я окончательно перестал что-либо понимать,

This is experimental prerelease support for the Windows platform: use
at your own risk.  "Your Kitten of Death awaits!"
Evaluation took:
  0.011 seconds of real time
  0.015600 seconds of total run time (0.015600 user, 0.000000 system)
  145.45% CPU
  21,195,050 processor cycles
  0 bytes consed

Это уже опять на мощном компе.
Ander Skirnir - 10.04.2010 05:28
[#]
 Хм, может быть дело в антивирусе - последний нортон с эвристическим сонаром. Может в sbcl используются хакерские оптимизации, однажды антивирь жаловался на скомпиленный sbcl'ем exe'шник
 http://t2.gstatic.com/images?q=tbn:MPHytK4WipfnxM:http://www.veryicon.com/icon/preview/Application/3D%2520Cartoon%2520Icons%2520Pack%2520III/Norton%2520Symantec%2520Icon.jpghttp://t2.gstatic.com/images?q=tbn:MPHytK4WipfnxM:http://www.veryicon.com/icon/preview/Application/3D%2520Cartoon%2520Icons%2520Pack%2520III/Norton%2520Symantec%2520Icon.jpghttp://t2.gstatic.com/images?q=tbn:MPHytK4WipfnxM:http://www.veryicon.com/icon/preview/Application/3D%2520Cartoon%2520Icons%2520Pack%2520III/Norton%2520Symantec%2520Icon.jpg
Ander Skirnir - 10.04.2010 06:02
[#]
Во:

  145.45% CPU

то бишь он задействовал > 1 ядра.

>> Может в sbcl используются хакерские оптимизации

Выполнение кода на стеке / в куче?
treep - 10.04.2010 20:03
[#]
>то бишь он задействовал > 1 ядра.

Я под виндой видел такие аномалии. На самом деле SBCL в винде вообще не запускает несколько нитей и не использует несколько ядер. А когда речь идет о величинах порядка сотых секунды, то профилирование может врать.
dmitry_vk - 10.04.2010 22:35
@2009-2013 lisper.ru