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

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

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 97 bytes --]

Hi,

I would like to install the following patch to Gnu Elpa.  Does it look
ok to you, Nicolas?


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Pinpoint-semantics-of-seq-subseq-s-implementation-for-streams.patch --]
[-- Type: text/x-diff, Size: 2527 bytes --]

From 77871facc3b00b8fe6d032e38c4b229d114a97ae Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Wed, 7 Sep 2016 15:45:07 +0200
Subject: [PATCH] Pinpoint semantics of `seq-subseq's implementation for
 streams

- Make argument END optional.

- Forbid negative index arguments.

- Add tests.
---
 packages/stream/stream.el             | 15 +++++++++++++--
 packages/stream/tests/stream-tests.el | 10 ++++++++--
 2 files changed, 21 insertions(+), 4 deletions(-)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 8c156f1..9954fc8 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -229,8 +229,19 @@ This function will eagerly consume the entire stream."
       (setq stream (stream-rest stream)))
     len))
 
-(cl-defmethod seq-subseq ((stream stream) start end)
-  (seq-take (seq-drop stream start) (- end start)))
+(cl-defmethod seq-subseq ((stream stream) start &optional end)
+  "Return a stream of elements of STREAM from START to END.
+
+END is exclusive.  If END is omitted, include all elements from
+START on.  Both START and END must be non-negative.  Since
+streams are a delayed type of sequences, don't signal an error if
+START or END are larger than the number of elements (the returned
+stream will simply be accordingly shorter, or even empty)."
+  (when (or (< start 0) (and end (< end 0)))
+    (error "seq-subseq: only non-negative indexes allowed for streams"))
+  (let ((stream-from-start (seq-drop stream start)))
+    (if end (seq-take stream-from-start (- end start))
+      stream-from-start)))
 
 (cl-defmethod seq-into-sequence ((stream stream))
   "Convert STREAM into a sequence."
diff --git a/packages/stream/tests/stream-tests.el b/packages/stream/tests/stream-tests.el
index 16b5756..31c3530 100644
--- a/packages/stream/tests/stream-tests.el
+++ b/packages/stream/tests/stream-tests.el
@@ -112,8 +112,14 @@
     (should (stream-empty-p (stream-rest (stream-rest rest))))))
 
 (ert-deftest stream-seq-subseq-test ()
-  ;; TODO
-  )
+  (should (equal (seq-into (seq-subseq (stream (list 0 1 2 3 4)) 1 3) 'list)
+                           (seq-subseq         (list 0 1 2 3 4)  1 3)))
+  (should (= (stream-first (seq-subseq (stream-range 0) 5))
+             5))
+  (should (= (stream-first (seq-subseq (seq-subseq (stream-range 0) 5) 5))
+             10))
+
+  (should-error (seq-subseq (stream-range 0) -1)))
 
 (ert-deftest stream-seq-into-test ()
   (should (streamp (seq-into (stream-empty) 'stream)))
-- 
2.9.3


[-- Attachment #3: Type: text/plain, Size: 21 bytes --]



Regards,

Michael.

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

[Clément Pit--Claudel]

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

On 2016-09-13 12:23, Michael Heerdegen wrote:
> - Forbid negative index arguments.

Do you really want to forbid negative arguments? Do we have a function akin to `tail' for streams (something that would return the last n elements?


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

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

[Michael Heerdegen]

Hi Clément,

> On 2016-09-13 12:23, Michael Heerdegen wrote:
> > - Forbid negative index arguments.
>
> Do you really want to forbid negative arguments? Do we have a function
> akin to `tail' for streams (something that would return the last n
> elements?

Thanks for your feedback!

Yes, I want to forbid them, unless there are realistic use cases.  No,
we don't have something like `tail' for streams.  If you want something
like that, you are in general better done with lists (i.e. convert the
stream into a list), I think.

Streams are delayed.  In general, you don't know how many (or if any at
all) elements a stream will generate later.  All functions building
streams out of argument streams are not allowed to generate any elements
from any input stream.

Negative indexes for `seq-subseq' would still be possible without
breaking these rules - but you would probably not need the result to be
a stream anyway (instead of a list, for example).  Streams are a mean to
program in a certain way (called data flow control or something like
that).  Negative indexes for `seq-subseq' collide with this model.

That's why I thought it's better to forbid negative indexes for now.  If
I see an example where it is really useful and appropriate, or good
arguments against this decision, I'll change my mind.


Regards,

Michael.

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 270 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Hi,

Hi Michael,

> I would like to install the following patch to Gnu Elpa.  Does it look
> ok to you, Nicolas?

It looks good thank!
Could you bump the version number of stream.el to 2.2.2 as well?

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

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

[Michael Heerdegen]

Nicolas Petton <nicolas@petton.fr> writes:

> Could you bump the version number of stream.el to 2.2.2 as well?

I'll wait with committing until we have finished discussing here.  I
could bump the version number now, but we can also wait until I have
committed some other pending patches in the next days.  I already
changed the version number in my local copy so that I can't forget.
Maybe can go to 2.3 then anyway.

Michael.

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

[Clément Pit--Claudel]

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

Hi Michael,

On 2016-09-13 17:17, Michael Heerdegen wrote:
> Yes, I want to forbid them, unless there are realistic use cases.
> No, we don't have something like `tail' for streams.  If you want
> something like that, you are in general better done with lists (i.e.
> convert the stream into a list), I think.

I don't think converting to list would be a good idea.  When operating on text files, for example, it's often convenient to get the last n lines of a file.  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.

> Streams are a mean to program in a certain way (called data flow
> control or something like that).  Negative indexes for `seq-subseq'
> collide with this model.

I don't see why; isn't it common to implement slyding-window-style algorithms on data streams? 'tail' is just one such example.  

I do agree, however, that the return value of these silding-window algorithms is not commonly a stream (rather a list, or a function of that list).  But I'm not sure that this is enough to make subseq with negative arguments irrelevant. Otherwise, what's a point of subseq vs. e.g. drop + take?

Let me know what you think of the 'last n lines of a file' example.  Maybe I'm missing something :)

Cheers,
Clément.


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

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

[John Wiegley]

>>>>> "MH" == Michael Heerdegen <michael_heerdegen@web.de> writes:

HM> Yes, I want to forbid them, unless there are realistic use cases. No, we
HM> don't have something like `tail' for streams. If you want something like
MH> that, you are in general better done with lists (i.e. convert the stream
HM> into a list), I think.

You could implement tail as a stream adapter that basically implements a
sliding window:

  Whenever an element is requested from the tail stream, it keeps requesting
  elements from the parent stream, filling up its window buffer and cycling
  out old elements, until it reaches the end of the parent stream.  At that
  point, it knows enough to start draining the window buffer to the caller.

It "forces" the parent stream, but provides the requested behavior for those
who might prefer a streams interface.  Also, the forcing of the parent stream
can be delayed until at least one element is requested.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 442 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I'll wait with committing until we have finished discussing here.  I
> could bump the version number now, but we can also wait until I have
> committed some other pending patches in the next days.  I already
> changed the version number in my local copy so that I can't forget.
> Maybe can go to 2.3 then anyway.

I guess it depends what you have in your other patches :)

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

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

[Michael Heerdegen]

Clément Pit--Claudel <clement.pit@gmail.com> writes:

> I don't think converting to list would be a good idea.  When operating
> on text files, for example, it's often convenient to get the last n
> lines of a file.  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.

> 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).

> 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?  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).  If you are interested in the last n lines, this is
potentially unlimited inefficient.

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

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.

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?


Regards,

Michael.

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

[Michael Heerdegen]

John Wiegley <jwiegley@gmail.com> writes:

> You could implement tail as a stream adapter that basically implements a
> sliding window:
>
> Whenever an element is requested from the tail stream, it keeps
> requesting elements from the parent stream, filling up its window
> buffer and cycling out old elements, until it reaches the end of the
> parent stream.  At that point, it knows enough to start draining the
> window buffer to the caller.

Yeah, implementing it that way would be cool: if we use `stream-pop', we
would not even need to create a new stream, we would just return the
original stream `stream-pop'ped accordingly until we have found its end
- and everything wrapped inside `stream-delay' so that this is done not
before elements are requested from the returned stream.


Thanks,

Michael.

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

[Clément Pit--Claudel]

[-- 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 --]

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

[John Mastro]

Clément Pit--Claudel <clement.pit@gmail.com> wrote:
>> 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.

(Asking for my own edification)

Wouldn't finding the last N elements require forcing every thunk in the
stream (to find its end), thus using more memory than a linked list with
the same contents? As long as you don't "hang on to the head" of the
stream, earlier elements could be reclaimed by GC, but the same applies
to a list.

In short, I find this conversation interesting, but don't quite
understand where the memory savings come in :)

        John

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

[Michael Heerdegen]

Clément Pit--Claudel <clement.pit@gmail.com> writes:

> 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.

Ok.  But how do you refer to the file's contents from elisp, then?
As a string?


> > 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.

Sure, but with what I mean, the error (inefficiency) would already be in
the "I have..." part.


> 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).

As a string, right?  Or in which way do you refer to the process output
via streams?  Can you please explain in short how you are using streams
in your use case?  (Sorry, I'm more a mathematician than a programmer,
so it's not your fault if I miss the point).  And should we add `stream'
method implementations for building streams from files and/or processes
to stream.el if such stuff is useful?

But I guess I'm beginning to understand: if you have a string (or
something "similar") consisting of multiple lines (or records or
whatever), and you are interested in the last n lines, in contrast to a
buffer, the "go to the end and then n times backwards" approach might
not even be possible, so there is no alternative to dissect the complete
string into entities from the start until you hit the end (and throw
away most of the stuff without accumulation) -- i.e. to the sliding
window approach implemented by seq-subseq with negative indexes.  If
there are such use cases in Emacs Lisp (with no more efficient
alternative), you have convinced me that negative indexes would indeed
be useful.



Thanks,

Michael.

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

[Clément Pit--Claudel]

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

On 2016-09-14 20:51, John Mastro wrote:
> Clément Pit--Claudel <clement.pit@gmail.com> wrote:
>>> 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.
> 
> (Asking for my own edification)

:) Keep in mind that I could be making a mistake, too :)

> Wouldn't finding the last N elements require forcing every thunk in the
> stream (to find its end), thus using more memory than a linked list with
> the same contents?

That's correct, if by more memory you mean "more memory allocated over the lifetime of the process".  The key is that we don't need to allocate it all at once. In the simple case where we want, for example, just the last element, we only need to hold on to one value at a time.

> As long as you don't "hang on to the head" of the
> stream, earlier elements could be reclaimed by GC,

Exactly :)

> but the same applies to a list.

Not exactly: the list needs to be fully built before you iterate over it.  That's when the memory problems occur.
So yes, during iteration you can discard the cons cells that you've already seen in both cases, but in the list case these cells need to all be constructed and kept in memory beforehand.

> In short, I find this conversation interesting, but don't quite
> understand where the memory savings come in :)

Let me try to summarize it in a different way.  In the stream case, you build one cons cell at a time, and every time you build a new cons cell the previous one is available for garbage collection.  With a good GC, there's only a few cells physically present in memory at any time (plus the memory it takes to keep the last "n" elements, if you're desired output is the n-elements tail of the stream).

In the list case, on the other hand, the full list exists in memory before you iterate on it.  Sure, after you iterate on it, the list can be garbage collected; but before you iterate on it, all the cons cells need to exist at the same time.

Here's a concrete bit of code to demo this (I tried to write this in Emacs Lisp, but Emacs kept segfaulting on me, so I gave up and wrote it in Python):

    import sys

    def mkstream(n):
        for k in range(n):
            yield "a" * (k % 25) * 10

    def mklist(n):
        return ["a" * (k % 25) * 10 for k in range(n)]

    def last(seq):
        lastx = None
        for x in seq:
            lastx = x
        return lastx

    def test_list(n):
        last(mklist(n))

    def test_stream(n):
        last(mkstream(n))

    tests = {"stream": test_stream, "list": test_list}

    tests[sys.argv[1]](100*1000*1000)

When I run this on my machine as “python stream.py stream”, the total memory usage doesn't noticeably change.  When I run it as “python stream.py list”, python allocates about 25GB of RAM.  This obviously not exactly the same as what would happen on the Emacs Lisp side, but hopefully it's close enough :)

Clément.


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

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

[Clément Pit--Claudel]

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

On 2016-09-14 20:58, Michael Heerdegen wrote:
> Clément Pit--Claudel <clement.pit@gmail.com> writes:
> 
>> 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.
> 
> Ok.  But how do you refer to the file's contents from elisp, then?
> As a string?

I didn't have a string in mind.  More something like running `cat` in a subprocess maybe?

>>> 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.
> 
> Sure, but with what I mean, the error (inefficiency) would already be in
> the "I have..." part.

I don't think so :) These sound like reasonable streams to me ^^
The second one in particular is one that I used recently: I wanted to enumerate all spans with constant text properties, and I didn't need to keep the whole list of spans in memory.  On the other hand, I didn't want to put the buffer segmentation in each function that iterated over the spans. Using a stream for that was quite convenient.

>> 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).
> 
> As a string, right?  Or in which way do you refer to the process output
> via streams?  Can you please explain in short how you are using streams
> in your use case?  (Sorry, I'm more a mathematician than a programmer,
> so it's not your fault if I miss the point).

I don't have a concrete use case :) This thread was born just from my looking at the original patch.  I use streams a lot more in other languages than I do in Emacs Lisp, at least for now.  And I agree that there's no hurry in implementing this feature, either (we could add it later).

> And should we add `stream'
> method implementations for building streams from files and/or processes
> to stream.el if such stuff is useful?

I think this would be great.  The comment at the top of stream.el mentions it:

;; streams could be created from any sequential input data:
;; - sequences, making operation on them lazy
;; - a set of 2 forms (first and rest), making it easy to represent infinite sequences
;; - buffers (by character)
;; - buffers (by line)
;; - buffers (by page)
;; - IO streams
;; - orgmode table cells
;; - ...

> But I guess I'm beginning to understand: if you have a string (or
> something "similar") consisting of multiple lines (or records or
> whatever), and you are interested in the last n lines, in contrast to a
> buffer, the "go to the end and then n times backwards" approach might
> not even be possible, so there is no alternative to dissect the complete
> string into entities from the start until you hit the end (and throw
> away most of the stuff without accumulation) -- i.e. to the sliding
> window approach implemented by seq-subseq with negative indexes.

Yes, essentially.  In the string case, though, you could copy the string into a buffer and apply the trick that you mentioned.  But more generally streams are good at producing their contents lazily, so an implementation that requires forcing the entire stream and then searching from the end of the resulting list is non-optimal. Of course in some cases you can just skip the production of a stream entirely; but not in all cases.

In any case, I don't think this should hold the previous patch; we can always extend the functionality of seq-subseq later.

Clément.


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

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 279 bytes --]

Clément Pit--Claudel <clement.pit@gmail.com> writes:

> In any case, I don't think this should hold the previous patch; we can
> always extend the functionality of seq-subseq later.

I agree, the patch is good as it is now, I'd like to have it installed.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]

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

[John Mastro]

Clément Pit--Claudel <clement.pit@gmail.com> wrote:
> Let me try to summarize it in a different way. In the stream case, you
> build one cons cell at a time, and every time you build a new cons
> cell the previous one is available for garbage collection. With a good
> GC, there's only a few cells physically present in memory at any time
> (plus the memory it takes to keep the last "n" elements, if you're
> desired output is the n-elements tail of the stream).
>
> In the list case, on the other hand, the full list exists in memory
> before you iterate on it. Sure, after you iterate on it, the list can
> be garbage collected; but before you iterate on it, all the cons cells
> need to exist at the same time.

Ah, it indeed makes sense now - thanks!

        John

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

[Michael Heerdegen]

Clément Pit--Claudel <clement.pit@gmail.com> writes:

> > but the same applies to a list.
>
> Not exactly: the list needs to be fully built before you iterate over
> it.  That's when the memory problems occur.  So yes, during iteration
> you can discard the cons cells that you've already seen in both cases,
> but in the list case these cells need to all be constructed and kept
> in memory beforehand.

But I think what John said is still a valid argument: If you construct a
stream of lines of a process's output (just for example), of, say, 10000
lines, you create 10000 new objects (strings), and you discard 10000 - n
of them.  They all need to be garbage collected.  This will not only
take a large amount of time - garbage collection happens not all the
time, so memory will be filled to a certain amount as well.  But I think
the impact of garbage collection of that many objects is a more serious
problem than memory usage anyway.

Instead, a simple loop incrementing a position variable or something
like that might be more appropriate (efficient).


Michael.

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

[Michael Heerdegen]

Clément Pit--Claudel <clement.pit@gmail.com> writes:

> Ok.  But how do you refer to the file's contents from elisp, then?
> As a string?

I didn't have a string in mind.  More something like running `cat` in
a subprocess maybe?

I have a question: AFAIK there is no mean to delay Emacs from accepting
output from a process (or is there? sorry if i missed it then).  But
when we must collect the complete process output when it arrives...and
we don't have asynchronity in Emacs etc...of what use is the usage of a
delayed structure (stream) in this case at all, and how would it be
different from the string case?

>> Sure, but with what I mean, the error (inefficiency) would already
>> be inthe "I have..." part.

> I don't think so :) These sound like reasonable streams to me ^^The
> second one in particular is one that I used recently: I wanted to
> enumerate all spans with constant text properties, and I didn't need
> to keep the whole list of spans in memory.  On the other hand, I
> didn't want to put the buffer segmentation in each function that
> iterated over the spans. Using a stream for that was quite convenient.

Here I again would chime in: it's convenient, but not efficient.  Search
backwards from the end of the buffer, don't enumerate from the beginning
if you are only interested in the last n, and start building a stream if
you have found the right place to start.

> > And should we add `stream'method implementations for building
> > streams from files and/or processes to stream.el if such stuff is
> > useful?
>
> I think this would be great.

Maybe you want to give it a try?  Then we will at least know how useful
that would be ;-)

> > But I guess I'm beginning to understand: if you have a string (or
> > something "similar") consisting of multiple lines (or records or
> > whatever), and you are interested in the last n lines, in contrast to a
> > buffer, the "go to the end and then n times backwards" approach might
> > not even be possible, so there is no alternative to dissect the complete
> > string into entities from the start until you hit the end (and throw
> > away most of the stuff without accumulation) -- i.e. to the sliding
> > window approach implemented by seq-subseq with negative indexes.
>
> Yes, essentially.  In the string case, though, you could copy the
> string into a buffer and apply the trick that you mentioned.

Well, I learned some time ago that because a buffer is more complicated
than a string, most operations are slower for a buffer than for an
equivalent string.

> But more generally streams are good at producing their contents
> lazily, so an implementation that requires forcing the entire stream
> and then searching from the end of the resulting list is non-optimal.

Yes, but that's was not my argument: I wanted to avoid this stream
entirely in such cases.  For your use case (of the negative indexes),
forcing the entire stream is unavoidable.  That's the point I criticize.

> In any case, I don't think this should hold the previous patch; we can
> always extend the functionality of seq-subseq later.

Ok, so I think I'll just install the patch for now.


Michael.

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

[Clément Pit--Claudel]

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

On 2016-09-15 17:07, Michael Heerdegen wrote:
> Clément Pit--Claudel <clement.pit@gmail.com> writes:
> 
>>> but the same applies to a list.
>> 
>> Not exactly: the list needs to be fully built before you iterate
>> over it.  That's when the memory problems occur.  So yes, during
>> iteration you can discard the cons cells that you've already seen
>> in both cases, but in the list case these cells need to all be
>> constructed and kept in memory beforehand.
> 
> But I think what John said is still a valid argument: If you
> construct a stream of lines of a process's output (just for example),
> of, say, 10000 lines, you create 10000 new objects (strings), and you
> discard 10000 - n of them. They all need to be garbage collected.

This is orthogonal to the list-vs-stream debate, isn't it?

> This will not only take a large amount of time - garbage collection
> happens not all the time, so memory will be filled to a certain
> amount as well.  But I think the impact of garbage collection of that
> many objects is a more serious problem than memory usage anyway.

[citation needed] :) Garbage collection costs time; memory costs, well, memory.  It's just a trade-off.

> Instead, a simple loop incrementing a position variable or something 
> like that might be more appropriate (efficient).

Sure, but again: how is this related to lists vs strings? Lists need to be garbage collected just the same.

> Instead, a simple loop incrementing a position variable or something
> like that might be more appropriate (efficient).

I'm not sure what you mean :\ Are you saying that sometime streams are not the right solution for a given problem? I agree fully :)

Cheers,
Clément.


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

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

[Michael Heerdegen]

Clément Pit--Claudel <clement.pit@gmail.com> writes:

> > Instead, a simple loop incrementing a position variable or something 
> > like that might be more appropriate (efficient).
>
> Sure, but again: how is this related to lists vs strings? Lists need
> to be garbage collected just the same.

Yes, lists and streams (I guess you meant "streams"?) both potentially
leave behind an unnecessary bulk of garbage.  When a stream is bad, a
list is worse.

> > Instead, a simple loop incrementing a position variable or something
> > like that might be more appropriate (efficient).
>
> I'm not sure what you mean :\ Are you saying that sometime streams are
> not the right solution for a given problem? I agree fully :)

Yes, more or less.  And I want to get an idea of how often "sometimes"
is in the use cases where you want the negative indexes.

Michael.

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

[Michael Heerdegen]

[-- Attachment #1: Type: text/plain, Size: 357 bytes --]

Nicolas Petton <nicolas@petton.fr> writes:

> I agree, the patch is good as it is now, I'd like to have it
> installed.

Done.

FWIW, if you would like me to push this: I have implemented the sliding
window algorithm as suggested by John, but commented it out, and added a
(hopefully not too wordy) note why we raise an error for now for
negative indexes:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: stream-add-a-comment.patch --]
[-- Type: text/x-diff, Size: 2234 bytes --]

From df5652f68fc0ca6730b3f830e805cf7e30e5615d Mon Sep 17 00:00:00 2001
From: Michael Heerdegen <michael_heerdegen@web.de>
Date: Fri, 16 Sep 2016 00:14:28 +0200
Subject: [PATCH] Add a comment to last change in stream.el and bump version

---
 packages/stream/stream.el | 25 +++++++++++++++++++------
 1 file changed, 19 insertions(+), 6 deletions(-)

diff --git a/packages/stream/stream.el b/packages/stream/stream.el
index 9954fc8..db00b0d 100644
--- a/packages/stream/stream.el
+++ b/packages/stream/stream.el
@@ -4,7 +4,7 @@
 
 ;; Author: Nicolas Petton <nicolas@petton.fr>
 ;; Keywords: stream, laziness, sequences
-;; Version: 2.2.1
+;; Version: 2.2.2
 ;; Package-Requires: ((emacs "25"))
 ;; Package: stream
 
@@ -237,11 +237,24 @@ START on.  Both START and END must be non-negative.  Since
 streams are a delayed type of sequences, don't signal an error if
 START or END are larger than the number of elements (the returned
 stream will simply be accordingly shorter, or even empty)."
-  (when (or (< start 0) (and end (< end 0)))
-    (error "seq-subseq: only non-negative indexes allowed for streams"))
-  (let ((stream-from-start (seq-drop stream start)))
-    (if end (seq-take stream-from-start (- end start))
-      stream-from-start)))
+  (if (or (< start 0) (and end (< end 0)))
+      ;; We could return something like this (for START and END < 0):
+      ;;
+      ;; (let ((cropped stream))
+      ;;   (cl-dotimes (_ (- start)) (stream-pop cropped))
+      ;;   (while (not (stream-empty-p cropped))
+      ;;     (stream-pop stream)
+      ;;     (stream-pop cropped))
+      ;;   (seq-take stream (- end start)))
+      ;;
+      ;; but we are not sure whether advertising negative indexes is a good
+      ;; idea: this would potentially create a bunch of thrown away objects,
+      ;; and "searching from the end" might be better in most use cases.  So
+      ;; we raise an error instead:
+      (error "seq-subseq: only non-negative indexes allowed for streams")
+    (let ((stream-from-start (seq-drop stream start)))
+      (if end (seq-take stream-from-start (- end start))
+        stream-from-start))))
 
 (cl-defmethod seq-into-sequence ((stream stream))
   "Convert STREAM into a sequence."
-- 
2.9.3


[-- Attachment #3: Type: text/plain, Size: 11 bytes --]



Michael.

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

[Clément Pit--Claudel]

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

On 2016-09-15 18:28, Michael Heerdegen wrote:
> Yes, more or less.  And I want to get an idea of how often "sometimes"
> is in the use cases where you want the negative indexes.

Emacs currently doesn't stream-based process filters, but they could be very nice; right now I'm not aware of a way to delay invocations of filter functions, so if you want to page through the output of a filter little by little you must still consume all of it and put it in a buffer.

Clément.


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

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

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 450 bytes --]

Michael Heerdegen <michael_heerdegen@web.de> writes:

>> I agree, the patch is good as it is now, I'd like to have it
>> installed.
>
> Done.

Thanks!

> FWIW, if you would like me to push this: I have implemented the sliding
> window algorithm as suggested by John, but commented it out, and added a
> (hopefully not too wordy) note why we raise an error for now for
> negative indexes:

I'd rather keep it as it is, at least for now.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 512 bytes --]