Julieta Shem <jshem@yaxenu.org> writes:

> I'd like to thank everyone in this thread. Valuable help. Thank you.
>
> Raymond Wiker <rwiker@gmail.com> writes:
>
>> Julieta Shem <jshem@yaxenu.org> writes:
>>
>>> First I define x to be a list of bytes of an NNTP article.
>>>
>>> (defvar x (fetch-article "local.test" "28"))
>>>
>>> Now x is a list of integers, the bytes of the article 28, which is a
>>> MIME message containing a PDF of 610 KiB.
>>>
>>> Now I want to split it line by line. I am able to do it, but it's very
>>> slow.
>>>
>>> * (time (length (split-sequence (list 13 10) x nil)))
>>> Evaluation took:
>>> 65.710 seconds of real time
>>> 65.671875 seconds of total run time (47.093750 user, 18.578125 system)
>>> [ Run times consist of 23.968 seconds GC time, and 41.704 seconds non-GC time. ]
>>> 99.94% CPU
>>> 170,322,749,168 processor cycles
>>> 79,439,358,864 bytes consed
>>>
>>> 11585
>>> *
>>>
>>> Less than 12k lines. The number 79,439,358,864 of bytes is way more
>>> than I would have expected for anything regarding this invocation above,
>>> but I have no idea what this number really measures here. I appreciate
>>> any help. Thank you.
>>>
>>> Here's the procedure:
>>>
>>> (defun split-sequence (delim ls acc &key limit (so-far 1))
>>> (let* ((len (length ls))
>>> (delim delim)
>>> (pos (search delim ls))
>>> (n-take (or pos len))
>>> (n-drop (if pos
>>> (+ n-take (length delim))
>>> n-take)))
>>> (cond ((zerop len) acc)
>>> ((and limit (= so-far limit)) (list ls))
>>> (t (split-sequence
>>> delim (drop n-drop ls)
>>> (cons (take n-take ls) acc)
>>> :limit limit
>>> :so-far (1+ so-far))))))
>>>
>>> (defun take (n seq) (subseq seq 0 n))
>>> (defun drop (n seq) (subseq seq n))
>>
>> It is slow because
>>
>> * You're repeatedly calling #'length on whatever is left of the
>> list. Computing the length of a list is an O(n) operation; repeatedly
>> calling #'length on the remainder of the list is then O(n^2).
>>
>> * You are generating new lists for both the initial segments and the
>> rest of the list. In order to generate 12k lines you have to generate
>> lists containing the lines, but also 12 lists containing the remainder
>> (at various points) of the input.
>
> That's the take and drop, I think.

Yup.

>
>> * Each character of the input requires a cons cell, which is probably 16
>> bytes (assuming a 64-bit Lisp implementation). So, your input now
>> requires 610000*16, so about 9.76MB.
>
> So that's one of the advantages of using a vector, I think.

Right. The other is that accessing any element in an array by position
(index) is O(1); for a list, it's O(n).

>> * The remainder lists will consume about 0.5*610000*16*12000, so about
>> 55GB. This is not too far from the 74GB that time reports. (My
>> calculations are probably off, but clearly not _too_ far off.)
>
> Impressive.

Maybe... but it also appears to be wrong :-)

>> * I'm going to assume that 74GB is going to be a significant chunk of
>> the available memory in your computer. That means that there will be
>> significant garbage-collection activity, and you may also end up
>> swapping to disk.
>
> What do you mean by ``available memory;'''? I have 24 GiB of RAM---23.9
> GiB usable, says Windows. I don't know how to show this right now, but
> I think I don't have any swap space (on Windows). I tried to turn it
> off some time ago I think I succeeded.

What implementation of Common Lisp are you using? Is it a 32-bit or
64-bit version?

>> If you used strings (or byte arrays instead), you would
>>
>> * Require much less memory.
>>
>> * Computing #'length for a string or array is O(1), so the overall complexity
>> becomes O(n).
>
> Because strings and arrays store their size somewhere in their data
> structure, I suppose, and lists do not.

Right. Lists are literally composed of objects that contain two values
(cons cells), where the second value is a pointer to the next cons cell.

>> * You don't have to create new arrays containing the successive
>> remainders; instead, you can use the :start keyword to #'search.
>
> I tried this. Here's how I rewrote it. First some user interface that
> gets the length just once, even though now it's probably okay to call
> length multiple times. (The /acc/umulator should be probably be
> optional here, but I was afraid of mixing &optional with &key. This is
> my first Common Lisp program.)
>
> (defun split-vector (delim v acc &key limit (so-far 1))
> (let ((len (length v)))
> (split-vector-helper delim v len acc limit so-far 0)))
>
> Now, find the position of /delim/ between /start/ and /len/. If you
> can't find it, we're done. If we've reached the limit of lines the
> caller requested, we're done. Now we found /delim/: copy the slice of
> the vector that goes from /start/ to the /pos/ition we found /delim/;
> save it in the accumulator. Update /start/ we along over the vector.
> Now repeat everything.
>
> (defun split-vector-helper (delim v len acc limit so-far start)
> (if (zerop len)
> acc
> (let ((pos (search delim v :start2 start :end2 len)))
> (cond ((or (not pos) (and limit (= so-far limit)))
> (nreverse (cons (subseq v start len) acc)))
> (t (split-vector-helper delim
> v
> len
> (cons (subseq v start (or pos len)) acc)
> limit
> (1+ so-far)
> (+ pos (length delim))))))))
>
> The result is better:
>
> * (time (length (split-vector (vector 13 10) x nil)))
> Evaluation took:
> 0.011 seconds of real time
> 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
> 0.00% CPU
> 30,857,378 processor cycles
> 7,000,064 bytes consed
>
> 11576
>
> (Difficult to understand 0.011 real time atgainst ``total run time''.)

That's a good second implementation, and a very nice improvement in run
time and memory use!

Note that you do not actually need the "len" parameter: if you don't
specify :end2 for #'search or the end position for #'subseq, they will
assume the value nil, which means the end of the sequence.

"real time" is the actual time taken for the operation, while "total
time" is the time that the Lisp runtime will admit to. So, basically,
the time taken to execute your new implementation is so small that it
cannot be measured by the Lisp runtime.

> (I call /length/ so I won't get the output of split-vector, which is
> long.)

The canonical way of doing this in Common Lisp would be to store the
value in a variable, instead, and return either nil or or no values at
all.

Something like

(time (defparameter *lines* (split-vector (vector 13 10) x nil)))

or

(time
(progn
(setf *lines* (split-vector (vector 13 10) x nil))
(values)))

> Question. When split-vector-helper is repeated, will the arguments be
> copied over to the new invokation, or will SBCL somehow pass on
> pointers?

Common Lisp in general does not copy complex structures unless
explicitly asked to. So, a list is passed around as a pointer to the
first cons cell, and an array is passed as a pointer to a structure that
defines the shape and size of the array. The pointers may also include
information in the least significant bits that describe what the
pointers point to.

Certain types of values (e.g, characters and a subset of integers) are
passed directly; the least significant bits of the value then indicate
that there is an integer or a character encoded in the rest of the
value.

>
> I haven't studied about the /loop/ macro yet.

Some people abhor loop, while others find it strangely attractive (or
even addictive).

>> * Also, if you used strings, you could just create a string stream from
>> the input string and repeatedly call #'read-line to collect the
>> lines. The entire program would be something like this (untested):
>>
>> (defun split-article (article-as-string)
>> (with-input-from-string (str article-as-string)
>> (loop for line = (read-line str nil)
>> while line
>> collect line)))
>
> As Spiros Bousbouras remarked in the thread, I'd prefer not to try to
> understand article content because the user has the right to use
> whatever encoding they please in NNTP articles. So I've been trying
> handle them as byte sequences.

At some point you will probably have to encode the article as
characters. In order to do so, you will have to parse the article
headers to find what encoding is used. I'm not convinced that this is
possible, but if you have a 16-bit character encoding, you may have an
octet 13 from one character, and an octet 10 from the following
character.