Re: [PATCH] Elpa: Pinpoint semantics of `seq-subseq' for streams

["Clément Pit--Claudel" <clement.pit@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 4196 bytes --]

On 2016-09-14 11:05, Michael Heerdegen wrote:
> Clément Pit--Claudel <clement.pit@gmail.com> writes:
>> … If the file is represented as a stream of lines, then tail makes
>> sense.  Doesn't it?  Converting the file to a list of lines
>> beforehand sounds like a bad idea, memory wise.
> 
> Indeed, in this case, it would be nonsense to convert into a list.

Ok, so we agree on this part :) Note that it may be nonsense to load the file into a buffer, too; holding the full file in a list is more or less as bad as holding the full file in a buffer.  If the file is large, that's very inefficient.

>> I don't see why; isn't it common to implement slyding-window-style 
>> algorithms on data streams? 'tail' is just one such example.
> 
> Do you have an example where this would be useful for streams in
> Emacs, different from the "last n lines" one (see my comment about
> that below).

Sure: if I have a stream of numbers, I may want to calculate the average of the last n numbers.  Or if I have a stream of non-overlapping buffer spans, I may want to remove just the last one.  To continue on the `last n lines' example, I may be interested in only the last n lines of output of a running process (think dmesg | tail).

>> Let me know what you think of the 'last n lines of a file'
>> example.
> 
> I think this is actually a very good example why it is good to
> forbid negative indexes.  If you are interested in the last n lines
> of a file, why would you dissect the complete file (or buffer) into
> lines and throw away nearly all of the result?

Because it's much more memory-efficient, as long as the file's lines are short :)  Note that I was careful to say file, not buffer: I don't need to load a full file in memory before I start processing its lines.  Same for the output of a running process: if I just want the last n lines, then accumulating all of the output before going to the end and looking backwards is extremely inefficient, memory-wise.  Dissecting the output (splitting it on newlines) and using a ring buffer to keep only the last `n` ones is much better.

> In Emacs, if you dissect a buffer into its lines, this can take
> seconds if the buffer is a bit larger (no matter if you collect the
> lines in a data structure or just throw the result away).

I agree; this approach would not be optimal for a buffer.  But I'm not talking about buffers :)

> If you are interested in the last n lines, this is potentially
> unlimited inefficient.

Loading the contents of a file into a buffer costs time linear in the size of the file and memory linear in that size too.  If I have a large file on disk, loading all of it into a buffer just to get the last few lines would be horribly inefficient.  On the other hand, the stream-based approach using subseq with negative indices would take time linear in the size of the buffer, but memory linear in just the number of lines that I want to keep.

> Instead, go to the end of buffer, go back N lines, and start building
> a stream from there.

I don't know of any implementation of the `tail` utility that works this way (loading the entire file, then looking backwards for newlines).  The approach you outline is the obvious one if the file is already loaded in a buffer, but that's not my use case (sorry for not making that clear!).

> So, in this case, in my opinion forbidding negative indexes would
> have saved you from the error of writing bad code.  Negative indexes
> would be an invitation to write bad code.

Could it be that I didn't explain the problem well, and you concluded it was bad code based on that?  The stream-based tail implementation has significant advantages in terms of memory usage.  Forbidding negative indexes would have forced me to either write memory-inefficient code, or more likely to just reimplement the required subseq functionality myself using a circular (ring) buffer.

> Maybe it would be better to provide that semantics in a separate 
> function, so that the programmer is forced to think about what he is 
> doing.  WDYT?

I don't know :)  By default, I'd assume programmers already think about what they are doing.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]