Не могу понять, это в 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?

> (0.046801 user, 0.156001 system)
Вот это меня настораживает: юзерспейсный код отработал те же 0.04 секунды. Все остальное время - system. Смотреть код надо детально.

Код кривоват правда, можно было лучше сделать:
(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.

Нет, этот вызов не хвостовой. В некоторых схемах добавлен специальный случай для cons - компилятор умеет преобразовывать их в хвостовой рекурсивный вызов. В sbcl такого нет. Надо в delete-negatives-b добавить cons-ячейку в качестве параметра.

Про хвостовую рекурсию:
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.

Хотя постоянный setf - это плохо. Но что-то ничего в голову не приходит.

Антипод 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

Красиво очень пишете, отличный вариант иммутабельной функции. Хотелось бы еще увидеть что-нибудь красивое структуроразрушающее - с максимальной экономией памяти (не создавать новые списочные ячейки) и процессора.
> постоянный setf - это плохо
А почему? Он же один раз раскроется в (setq negative ...). Вот append же каждый раз будет список проходить от самого начала до конца - это точно не очень хорошо. По идее, порядок чисел в списках нас здесь не должен особо интересовать (ведь он теряется при разделении), поэтому можно вместо collect просто заюзать push.

Я =   

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

Да мне можно на "ты" :)
>> Кстати, если Вас всё-же интересует по какой-то причине порядок, можете делать, как макрос loop при использовании collect - хранить указатель на последнюю списочную ячейку и через неё добавлять новые, затем смещая её - это будет быстрее push + reverse.
Я пока не осилил функции над списками с побочными эффектами вроде rplacd, а нет ли функции работающей как push, но в обратном порядке? Чтобы без новой памяти трогать список с другого конца?

> нет ли функции работающей как push, но в обратном порядке? 
nconc? Только, обычно это не самая хорошая идея, ведь быстродействие падает: что бы добавить что-то в конец, его надо сначала найти. Чем больше список - тем дальше до конца. Связан push и nreverse (вместо reverse) работают на самом деле очень хорошо, ибо не потребляют лишней памяти и просты в использовании.

Кстати, 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 гигами оп :)

Просьба полностью выложить код, которым тестировалось (код функции delete-negatives-a, используемые опции компиляции, и значение переменной *a*)

> полностью выложить код
(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

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

rplaca меняет содержимое клеточки car списочной ячейки (cons),
rplacd - содержимое cdr
В первом томе Мира Лиспа целая глава (2.8, внутреннее представление списков) этому посвящена, где всё на пальцах, с примерами и рисуночками объяснено.

Кстати, только что наткнулся на ошибку:
(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.
Только один раз возникла, воспроизвести при перезапусках не удалось.

 > Я пока не осилил функции над списками с побочными эффектами вроде rplacd
Почему бы не забить и не использовать (setf ([car | cdr] ...)..)? Он раскрывается в rplacd/rplaca и выглядит лучше.
>Чтобы без новой памяти трогать список с другого конца?
 Добавление в конец означает изменение правой части последней cons-ячейки на адрес списка, который нужно присоединить. Чтобы обратиться к этой ячейке нужно либо хранить ее(O(1)), либо пройтись по списку(O(n)).

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

Если дело работает на винде то ещё возможно, что всё дело в отсутствии тредов - их нет, нет SMP и распараллеливания на два ядра, в вот в CCL есть поддержка потоков на количестве ядер > 1 и на винде. Ведь если речь идёт о сортировке списков ~миллионов элементов - параллельность может дать не хилый выигрыш на нескольких ядрах.
  92.72% CPU
должно же быть > 100.

Программа однопоточная, и поддержка потоков роли здесь не сыграет.
Сборщик мусора тоже вряд ли причастен - программа ничего не аллокейтит, а лишь изменяет сгенерированный ранее список, поэтому все сегфолты были до запуска непосредственного кода. Ну и к тому же в винде действительно могут быть аномалии, т.к. виндовый порт находится в немного более заброшенном состоянии. (Кстати, можно в диспетчере задач в винде смотреть количество ошибок страниц (т.е., сегфолтов) - я когда в первый раз увидел, насколько дикое количество сегфолтов генерируют ccl и sbcl, очень сильно удивился).

ВНЕЗАПНО! Я окончательно перестал что-либо понимать,
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
Это уже опять на мощном компе.

 Хм, может быть дело в антивирусе - последний нортон с эвристическим сонаром. Может в sbcl используются хакерские оптимизации, однажды антивирь жаловался на скомпиленный sbcl'ем exe'шник
 

Во:
  145.45% CPU
то бишь он задействовал > 1 ядра.
>> Может в sbcl используются хакерские оптимизации
Выполнение кода на стеке / в куче?

>то бишь он задействовал > 1 ядра.
Я под виндой видел такие аномалии. На самом деле SBCL в винде вообще не запускает несколько нитей и не использует несколько ядер. А когда речь идет о величинах порядка сотых секунды, то профилирование может врать.