LINUX.ORG.RU

Эксперименты с обработкой текста

 ,


1

2
PERCHAR-VS-BUFFERING> (format t "~A-~A~%"
                              (lisp-implementation-type)
                              (lisp-implementation-version))
SBCL-1.3.20
NIL

Код здесь: https://pastebin.com/f6RtgQPE

Заранее извиняюсь за на коленке налабанный говнокод.

Для экспериментов нашёл свою старую курсовую в LaTeX и, редактируя и копипастя, раздул файл до 200M.

Вот результаты экспериментов у меня:

PERCHAR-VS-BUFFERING> (let ((*buffer-size* (* 4 (expt 2 10))))
                        (time
                         (with-open-file (*standard-input* #P"text3.tex")
                           (let ((lv (multiple-value-list (run-perchar))))
                             (setf *x* lv)
                             (first lv)))))
Evaluation took:
  4.092 seconds of real time
  4.092759 seconds of total run time (4.042829 user, 0.049930 system)
  100.02% CPU
  9,427,500,968 processor cycles
  7,733,248 bytes consed
  
114337080
PERCHAR-VS-BUFFERING> (defparameter *x2* *x*)
*X2*
PERCHAR-VS-BUFFERING> (let ((*buffer-size* (* 4 (expt 2 10))))
                        (time
                         (with-open-file (*standard-input* #P"text3.tex")
                           (let ((lv (multiple-value-list (run-with-buffering))))
                             (setf *x* lv)
                             (first lv)))))
Evaluation took:
  3.162 seconds of real time
  3.162505 seconds of total run time (3.117984 user, 0.044521 system)
  100.03% CPU
  7,284,480,890 processor cycles
  7,765,280 bytes consed
  
114337080
PERCHAR-VS-BUFFERING> (equal *x* *x2*)
T
PERCHAR-VS-BUFFERING> 

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

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

PS для некоторых проверок запускал wc -m. Хотя задача у него гораздо проще чем у реализаций на CL, но что примечательно - он проигрывал в скорости от самой медленной реализации на CL более чем на 800 мс.

PS2 Жирный и тупой троллинг от хомячков т.н. мейнстрима и других д**ов здесь не нужен

★★★★★

Интересуют способы оптимизации от упоминавших, что скорость и keyargs несовместимы. Речь идёт о использовании функции position в самой быстрой реализации.

ados ★★★★★ ()
Последнее исправление: ados (всего исправлений: 2)

Ну, я не настолько доктор, но я бы:

1. Глянул сюда http://benchmarksgame.alioth.debian.org/u64q/program.php?test=regexredux&...

2. Все параметры, какие можно, превратил бы в константы, а для переменных сойдёт sb-ext:defglobal (внимательно прочитать мануал).

3. Наверное, ты не забыл поставить optimize, но на всякий случай.

4. Возможно, что замена консов на вектор помогла бы.

5. Насчёт скорость и keyargs, есть deftransform (см. определения position - среди них найдётся он). Можешь попробовтаь поставить внутрь этого deftransform-а какой-нибудь print и посмотреть, что выйдет.

6. Убедись, что у тебя simple-array, а не просто vector, vector может быть богатым и с гораздо более медленным доступом .

den73 ★★★★★ ()
Последнее исправление: den73 (всего исправлений: 1)

... делающими одно и то же программами, но немного разными путями ...

1. В «gather-indexes» есть подозрительное место, так что не факт, что программы дадут одинаковый результат. Ты сравниваешь только размер текста, а списки бекслешей и процентов могут различаться.

2. Чтение из файла - крайне медленная операция.

2.а Зубок писал, что СБЦЛ читает вчетверо медленнее Си (см. посты про аудиоплеер на СБЦЛ)

2.б Год назад делалось сравнение разных ЯП на скорость ввода, могу завтра вечером найти ссылку. Правда там тесты для бинарного файла и дял СБЦЛ не доделали оптимизации.

Поэтому считай свой файл в переменную *text* и оберни вызов (run-perchar) в:

(with-input-from-string (*standard-input* *text*)
  (run-perchar))
т так же для (run-with-buffering)

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

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

2. Чтение из файла - крайне медленная операция.

, на фоне которой время обработки незначительно.

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

п.3. Собрать позиции с символами отдельно \ и %. Однако символ % открывает зону комментирования которая идёт до конца строки или файла - в ней все символы игнорируются.

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

По поводу

Поэтому считай свой файл в переменную *text* и оберни...:

Вот взял файл поменьше:

PERCHAR-VS-BUFFERING> (let ((*buffer-size* (* 4 (expt 2 10))))
                        (with-open-file (*standard-input* #P"text2.tex")
                          (let ((lv (time (multiple-value-list (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  0.298 seconds of real time
  0.298328 seconds of total run time (0.296035 user, 0.002293 system)
  100.00% CPU
  687,217,900 processor cycles
  720,896 bytes consed
  
10394280
PERCHAR-VS-BUFFERING> (let ((*buffer-size* (* 4 (expt 2 10))))
                        (with-open-file (*standard-input* #P"text2.tex")
                          (let ((lv (time (multiple-value-list (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  0.327 seconds of real time
  0.327232 seconds of total run time (0.317765 user, 0.009467 system)
  100.00% CPU
  753,808,200 processor cycles
  720,896 bytes consed
  
10394280
PERCHAR-VS-BUFFERING> (let ((*buffer-size* (* 4 (expt 2 10))))
                        (with-open-file (*standard-input* #P"text2.tex")
                          (let ((lv (time (multiple-value-list (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  0.288 seconds of real time
  0.288515 seconds of total run time (0.288515 user, 0.000000 system)
  100.35% CPU
  664,661,260 processor cycles
  719,584 bytes consed
  
10394280
PERCHAR-VS-BUFFERING> (equal *x* *x2*)
T
PERCHAR-VS-BUFFERING> (defparameter *x2* *x*)
*X2*
PERCHAR-VS-BUFFERING> (let ((*buffer-size* 10394280))
                        (with-open-file (*standard-input* #P"text2.tex")
                          (let ((lv (time (multiple-value-list (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  0.322 seconds of real time
  0.321346 seconds of total run time (0.312047 user, 0.009299 system)
  99.69% CPU
  740,291,944 processor cycles
  42,298,048 bytes consed
  
10394280
PERCHAR-VS-BUFFERING> (let ((*buffer-size* 10394280))
                        (with-open-file (*standard-input* #P"text2.tex")
                          (let ((lv (time (multiple-value-list (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  0.328 seconds of real time
  0.328358 seconds of total run time (0.315051 user, 0.013307 system)
  [ Run times consist of 0.007 seconds GC time, and 0.322 seconds non-GC time. ]
  100.00% CPU
  756,239,518 processor cycles
  42,298,048 bytes consed
  
10394280
PERCHAR-VS-BUFFERING> (let ((*buffer-size* 10394280))
                        (with-open-file (*standard-input* #P"text2.tex")
                          (let ((lv (time (multiple-value-list (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  0.324 seconds of real time
  0.323289 seconds of total run time (0.317003 user, 0.006286 system)
  99.69% CPU
  744,745,240 processor cycles
  42,265,280 bytes consed
  
10394280
PERCHAR-VS-BUFFERING> (let ((*buffer-size* 10394280))
                        (with-open-file (*standard-input* #P"text2.tex")
                          (let ((lv (time (multiple-value-list (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  0.329 seconds of real time
  0.329859 seconds of total run time (0.323318 user, 0.006541 system)
  [ Run times consist of 0.006 seconds GC time, and 0.324 seconds non-GC time. ]
  100.30% CPU
  759,465,954 processor cycles
  42,298,048 bytes consed
  
10394280
PERCHAR-VS-BUFFERING> (equal *x* *x2*)
T
PERCHAR-VS-BUFFERING> 
ados ★★★★★ ()
Ответ на: комментарий от den73

посмотрел по ссылке в п.1 и впервые заметил, что задачу можно попробовать распараллелить. Будет время можно и с этим поэкспериментировать чисто для разминки, а пока перспектив для таких улучшений нет.

п.6

PERCHAR-VS-BUFFERING> (typep (make-string 4096)
                             'simple-array)
T
   
речь я так понимаю об этом?

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

п.4. это про сбор индексов в списках? Этот механизм в обеих программах одинаков и вроде должен быть даже быстрее массивов. Вот если мне нужно было извлекать элементы по индексам - тогда да массивы были бы полезны. Но даже при таком использовании в случае с sbcl последовательности должны быть достаточно длинными чтобы массивы стали давать такую же производительность что и списки.

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

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

Файл можно в tmpfs поместить. Хотя здесь практически это оно и есть.

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

Я тоже не умею, но обычно в таких скоростемерках ставлю в начале файла такое:

(proclaim '(optimize (safety 0) (debug 0) (speed 3) (compilation-speed 0) (space 0))) (declaim (optimize (safety 0) (debug 0) (speed 3) (compilation-speed 0) (space 0)))

Что из них действительно работает - я не знаю, там всё как-то странно, поэтому я не парюсь и ставлю оба. Самая отстающая программа не станет самой быстрой, но может стать в разы быстрее, чем была. И если тебя интересует конкурентоспособность с Си, то без этого вряд ли о ней может идти речь на таких простых тестах. Как на больших программах - я не знаю.

Так ты можешь оценить скорость и прочитать много интересного про недостающие декларации типов. Также вспомнил: есть SB-INT:FAST-READ-CHAR в SBCL, к-рый читает намного быстрее обычного чтения, хотя не знаю, как по сравнению с read-sequence.

последовательности должны быть достаточно длинными чтобы
массивы стали давать такую же производительность что и списки

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

den73 ★★★★★ ()
Ответ на: комментарий от anonymous
PERCHAR-VS-BUFFERING> (sb-profile:reset)
NIL
PERCHAR-VS-BUFFERING> (let ((*buffer-size* (* 4 (expt 2 10))))
                        (time
                         (with-open-file (*standard-input* #P"text3.tex")
                           (let ((lv (multiple-value-list (run-with-buffering))))
                             (setf *x* lv)
                             (first lv)))))
Evaluation took:
  4.322 seconds of real time
  4.323310 seconds of total run time (3.568209 user, 0.755101 system)
  100.02% CPU
  9,958,165,524 processor cycles
  7,750,880 bytes consed
  
114337080
PERCHAR-VS-BUFFERING> (sb-profile:report)
  seconds  |     gc     | consed |  calls  |  sec/call  |  name  
------------------------------------------------------
     2.017 |      0.000 |      0 | 772,490 |   0.000003 | POSITION
------------------------------------------------------
     2.017 |      0.000 |      0 | 772,490 |            | Total

estimated total profiling overhead: 0.91 seconds
overhead estimation parameters:
  8.000001e-9s/call, 1.1799999e-6s total profiling, 5.02e-7s internal profiling
; No value
ados ★★★★★ ()
Ответ на: комментарий от ados

п1. Мой косяк. Ты прав. Уже засыпал - не заметил.

п3. Понял из run-perchar. Дай файл для экспериментов.

п2. Вечером напишу уточнение.

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

Я не говорю что чтение из файла вообще роли не играет. sb-sprof говорит, что оно почти больше половины времени отжирает. Но как выясняется с этим ничего не сделаешь. А главное то что доля времени даже такой элементарной обработки довольно значительна.

ados ★★★★★ ()

Попробовал без вызовов с keyargs с помощью этого:

(defun mycharpos (char buffer start end)
  (declare (type integer start end)
           (type character char)
           (type string buffer)
           (optimize (speed 3) (debug 0) (safety 0)))
  (block loop
    (loop :for i :from start :to (- end 1)
          :for c = (aref buffer i)
          :do (when (char-equal char c)
                (return-from loop i)))
    nil))

... и проиграл полсекунды. ЧЯДНТ?

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

Читаю в комментах к дизассемблеру всяких GENERIC--, GENERIC->.

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

В общем понятно что cl:position в стальной банке как стандартная функция скорее всего хорошо оптимизирована и такую всякими keyarg-ми сильно не затормозишь (борьба с тормозами на уровне компиляции). Создание её аналога смысла большого не несёт.

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

Присобачил ради интереса start и end как keyargs к mycharpos и проиграл целую секунду.

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

ЧЯДНТ?

Херню какую-то написал вместо оптимизации. Попробуй так (не проверял - негде):

(defun mycharpos (char buffer start end)
  (declare (type fixnum start end)
           (type simple-string buffer)
           (optimize (speed 3) (debug 0) (safety 0)))
  (block loop
    (loop :for i fixnum :from start :to (- end 1)
          :for c = (aref buffer i)
          :do (when (char= char c)
                (return-from loop i)))
    nil))

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

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

Ну круто. Поставил на эти рельсы run-with-buffering, пропатчил таким же образом run-perchar, добавил:

  (eval-when (:execute :compile-toplevel :load-toplevel)
    (proclaim '(optimize (safety 0) (debug 0) (speed 3)
                (compilation-speed 0) (space 0))))
  (declaim (optimize (safety 0) (debug 0) (speed 3)
                     (compilation-speed 0) (space 0)))

В начале файла. Наблюдаю значительное улучшение на том же самом файле:

PERCHAR-VS-BUFFERING> (with-open-file (*standard-input* #P"text3.tex")
                        (let ((lv (multiple-value-list (time (run-perchar)))))
                          (setf *x* lv)
                          (first lv)))
Evaluation took:
  2.664 seconds of real time
  2.664710 seconds of total run time (2.587150 user, 0.077560 system)
  100.04% CPU
  6,138,271,234 processor cycles
  7,799,248 bytes consed
  
114337080
PERCHAR-VS-BUFFERING> (defparameter *x2* *x*)
*X2*
PERCHAR-VS-BUFFERING> (let ((*buffer-size* (* 4 (expt 2 10))))
                        (with-open-file (*standard-input* #P"text3.tex")
                          (let ((lv (multiple-value-list (time (run-with-buffering)))))
                            (setf *x* lv)
                            (first lv))))
Evaluation took:
  1.961 seconds of real time
  1.962280 seconds of total run time (1.909503 user, 0.052777 system)
  100.05% CPU
  4,520,204,580 processor cycles
  7,766,016 bytes consed
  
114337080
PERCHAR-VS-BUFFERING> (equal *x* *x2*)
T
PERCHAR-VS-BUFFERING> 

Да получается, что про cl:position выше я чепухи нагородил.

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

1. заменить строку

:for c = (aref buffer i)

на

:for c = (schar buffer i)

изменение скорости будет микроскопическим, но стилистически более правильно (ночью просмотрел, а исправить пост анонимусу невозможно)

.

2. одинаковые proclaim и declaim на соседних строчках употребляют только идиоты. почитай гиперспеку и больше так не делай

(eval-when (:execute :compile-toplevel :load-toplevel)
  (proclaim '(optimize (safety 0) (debug 0) (speed 3)(compilation-speed 0) (space 0))))
  (declaim   (optimize (safety 0) (debug 0) (speed 3)(compilation-speed 0) (space 0)))

.

3. в данном тесте proclaim и declaim вообще не нужны, достаточно использовать (declare (optimize (speed 3) (debug 0) (safety 0))) внутри функций, в которых производится 99.9(9)% вычислений этого теста.

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

добрался до компа с ЦЛ

Присобачил ради интереса start и end как keyargs к mycharpos и проиграл целую секунду.

присобачил start и end как keyargs (заодно причесал код):

(defun mycharpos-2 (char buffer &key (start 0) (end (length buffer)))
  (declare (optimize (speed 3) (debug 0) (safety 0))
           (type fixnum start end)
           (type simple-string buffer))
  (loop :for i fixnum :from start :below end
        :when (char= char (schar buffer i))
          :return i))

.

Читаю в комментах к дизассемблеру всяких GENERIC--, GENERIC->.

и не вижу ни одного дженирика:

PERCHAR-VS-BUFFERING> (disassemble 'mycharpos-2)
; disassembly for MYCHARPOS-2
; Size: 133 bytes. Origin: #x1002ECE8E0
; 8E0:       84042500000F20   TEST AL, [#x200F0000]           ; safepoint
                                                              ; no-arg-parsing entry point
; 8E7:       4885F6           TEST RSI, RSI
; 8EA:       7574             JNE L9
; 8EC:       488B4FF9         MOV RCX, [RDI-7]
; 8F0: L0:   EB51             JMP L6
; 8F2:       660F1F840000000000 NOP
; 8FB:       0F1F440000       NOP
; 900: L1:   498BD0           MOV RDX, R8
; 903:       8D47F1           LEA EAX, [RDI-15]
; 906:       A80F             TEST AL, 15
; 908:       7506             JNE L2
; 90A:       807FF1E5         CMP BYTE PTR [RDI-15], -27
; 90E:       744A             JEQ L8
; 910: L2:   8D47F1           LEA EAX, [RDI-15]
; 913:       A80F             TEST AL, 15
; 915:       753F             JNE L7
; 917:       807FF1E1         CMP BYTE PTR [RDI-15], -31
; 91B:       7539             JNE L7
; 91D:       48D1FA           SAR RDX, 1
; 920:       0FB6541701       MOVZX EDX, BYTE PTR [RDI+RDX+1]
; 925: L3:   498BF2           MOV RSI, R10
; 928:       C1EE08           SHR ESI, 8
; 92B:       4839D6           CMP RSI, RDX
; 92E:       7509             JNE L5
; 930:       498BD0           MOV RDX, R8
; 933: L4:   488BE5           MOV RSP, RBP
; 936:       F8               CLC
; 937:       5D               POP RBP
; 938:       C3               RET
; 939: L5:   498BD8           MOV RBX, R8
; 93C:       4883C302         ADD RBX, 2
; 940:       4C8BC3           MOV R8, RBX
; 943: L6:   84042500000F20   TEST AL, [#x200F0000]           ; safepoint
; 94A:       4939C8           CMP R8, RCX
; 94D:       7CB1             JL L1
; 94F:       BA17001020       MOV EDX, 537919511
; 954:       EBDD             JMP L4
; 956: L7:   CC0A             BREAK 10                        ; error trap
; 958:       0F               BYTE #X0F                       ; NIL-ARRAY-ACCESSED-ERROR
; 959:       38               BYTE #X38                       ; RDI
; 95A: L8:   8B545701         MOV EDX, [RDI+RDX*2+1]
; 95E:       EBC5             JMP L3
; 960: L9:   498BC9           MOV RCX, R9
; 963:       EB8B             JMP L0

.

ну, и чтобы в гиперспеку не лазить

PERCHAR-VS-BUFFERING> (macroexpand-1 '(declaim (optimize (speed 3) (debug 0) (safety 0))))
(EVAL-WHEN (:COMPILE-TOPLEVEL :LOAD-TOPLEVEL :EXECUTE)
  (SB-C::%PROCLAIM '(OPTIMIZE (SPEED 3) (DEBUG 0) (SAFETY 0))
                   (SB-C:SOURCE-LOCATION)))

anonymous ()

special variables меньше используй, и не в циклах - они тормозят

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