Continuing from Streams library 2.0 development - BIG improvement: real-time applications (#247) - #248 by qw23
@qw23 Umm yeah. Sounds good. Honestly I've never thought about two threads using the same stream, apart from the exercise about joint bank accounts. But I'm pleased that you thought about it! And I'll take your word for the solution. Are you proposing to implement all that other mechanism, looking for dead threads and restarting their computation? (If so, don't forget the possibility that the first thread stalled out for a reason, and its replacement will also stall out for the same reason.)
I still think that reporters don't need to use WARP because they're warped automatically, but I think that only because I've been told, not from firsthand observation.
I suppose it must have been at the back of your mind when you wrote the Streams library, v.1. If not, why has the definition of tail of stream (and some other blocks) been warp-ed at all?
I’m actually baffled no one (including myself) ever noticed the effect of using streams on parallel processes - or at least no one raised an issue in the forum. I guess it only goes to show that, over the (five?) years the Streams library has been available, it hasn’t been used much. Well, never mind, with some practical application code added that might change.
You shouldn’t. I’m as fallible as anyone. I haven’t even tried yet if it works with two (or more) processes trying to access the same stream, like the bank account case. Hadn’t even thought of that when I wrote my post. Now that I’m aware of it, I will, of course. Still, please keep challenging my ideas and results. 
Yeah, I had thought of that in the meantime (probably while I was sleeping): the evaluating process may be waiting for user input, for example. So on second thought I’m probably not going to implement the time-out mechanism for now; better wait until a generally suitable solution will have come to mind, if ever. A message-based replacement for the active wait block may be easier to build, though it may not be necessary to do it anytime soon (depending on test results), plus it could be done without fundamentally changing the data structure, in a future minor release.
IIRC only Snap! primitive blocks are atomic. So change (balance) by (-100) is guaranteed to work correctly even in a multi-process environment. But set (available) to ((balance) ≧ (100)); if (available) (change (balance) by (-100)) is not. I’m not sure about if (my function (arguments)) (change (balance) by (-100)). In all cases: warp-protection (and, by the same token, the atomic nature of primitives) will last up to 0.5 seconds. So it’s both safer and more efficient to protect a resource using a kind of semaphore, unless the processing time is very short, and warp is the easy (and uncomplicated) solution.
Better check that with jens, and add a big “caveat” to warp’s online help (I mean, hardly anyone is aware it should only be used for a very short time, to protect a critical section),
Because there was a time when (custom) reporters weren't automatically warped, so I did it for speed. Mostly when I write a project there's just one sprite, and it just runs one script at a time. There are occasional exceptions, but that's my usual thing.
Not for the sort of modeling of state change over time that you're now focused on. I use them for the sort of situation in which it's easier to express a computation by doing more than it really needs to do, e.g., before we had FIND FIRST so I used KEEP instead.
Ah, but I'm even more fallible than anyone. Just ask Jens. But I'm happy to remind you of the things I learned in operating systems class. :~)
Even when part of a custom reporter? Although maybe it's just functional reporters (no state) that are implicitly warped? Or maybe ones that don't include loops, but are instead recursive?
But again, I'm thinking about the run-fast aspect of WARP. As for critical sections, all I know for sure is that IF and IFELSE guarantee that nothing else runs between the test part (the predicate expression) and the beginning of the action part (the Then or Else part).
No, you can use it as long as you want, if what you're trying to do is get a long computation done as fast as possible. If you're trying to do multiprocessing, then yeah, you want to keep critical sections short, as in any language.
My plane leaves in nine hours... I gotta go pack. :~(
… like with games, simulations and all that. Stuff that Snap! is especially suited for, at least for building prototypes of. So any policy should keep that in mind, IMAO.
Have a safe flight!
I know, I'm an atypical user. Still, the typical game project isn't exactly data-heavy. If users have race conditions it's more about which sprite speaks first, and they solve it by throwing in WAIT blocks.
But yes, I agree, this is one of the things we should be good at.
T - five hours...
@bh: Your flight must have been to a face transplant clinic … (I would love to have 1 2, but in my part of the world they’re so busy nowadays, I’m still Q-ing).
Another issue
While leafing through SICP I stumbled upon exercise 3.69: using streams to find Pythagorean triples.
I coded a solution in Snap!, and while obtaining the first and second triples was easy, my system crashed when I tried to have the third triple calculated.
I ran some tests to analyze the issue.
- I installed two counters, maintained by
tail of streamandin front of stream: (a) number of current promises; (b) number of evaluated items. At the time of a crash (on my system, an iPad Pro-2, 256 GB), the promises were counted at 427, with about 90k evaluated items. - I also ran a simpler script:
Judging from my observations of the evaluated-items counter, the execution of this script slowed down from the moment when the counter was about 80k, and it crashed at 110k or so, on my iPad. By contrast: the Snap! IDE will support lists containing up to about 70 million integers on the same system.
- I repeated the script on a different system (iMac), the script crashed because of insufficient memory, after about 330k evaluations.
- I converted (an earlier version of) the script to work with Streams library v1 (on iPad); similar result as with v2.
- I made a script with repeated smaller queries, assigned to different variables, and run serially. It crashed, too.
- I made a script with repeated smaller queries, serially run after having been assigned to the same variable. It did NOT crash.
Preliminary conclusions (incl. some speculations ad to the inner workings of Snap!)
- On a typical user platform, up to a few hundred thousand stream items can be supported simultaneously - mostly dependent on available memory, I guess.
- In this respect there’s hardly any difference between v1 and v2 of the Streams library - this surprised me as in v2 data structure the memory-guzzling “promise” is kept only at the current tail of the stream (it is overwritten by a pointer to the next element every time it’s evaluated). It looks like the memory that was originally needed for the promise is not freed after the promise has been superseded by the (usually) much nimbler next item.
- Only after all references to a stream have disappeared, the memory is apparently freed.
I tried to fix it, and failed
The data structure of a stream (in v2) is:
- before evaluation:
(head promise) - during evaluation:
(head nil) - after evaluation:
(head (next_head next_promise)), or eventually:(head (next_head (next_next_head ( … )))
My hypothesis was that the memory used by promise would not be freed if the thing that used to contain a reference to it was still used (even if for something else). So I experimentally modified the structure by replacing promise with (promise), and changing both in front of stream and tail of stream accordingly.
To my disappointment, this proved ineffective: large streams still cause the IDE to crash.
Self-critical note: I’ve been thinking, the “promise”’s memory use might be a red herring. I tested how large a list I could make from a typical promise such as:
It turned out memory trouble is only with a list larger than 224 (or 4 million) items.
OTOH, my observation of script (5) crashing, and not script (6), suggests it must have at least some influence; though it may not be the only influence.
And so … ?
As it is now, “range anxiety” might impede serious use of the Streams library v2. I wouldn’t know how to solve the issue, as it will probably require knowledge of Snap! (or underlying Javascript) memory use and garbage collection. I could use some help advice from the dev team. 
So, the triple (5,12,13) is at index 12,272 of the stream of triples. That's a pretty huge number, but not that huge. I agree that it shouldn't crash.
Best practice is not to keep a pointer to the head of a stream in a variable. If a variable points to a stream, it should point to the not-yet-processed part. I know that's not what we do in demos, where we have variables INTS and RATIONALS and PRIMES and so on. Paradoxically, that's not such a problem for infinite streams that you're never really going to read very far into. The problem is with huge data structures that don't fit in memory, but you want to pretend they do. If you do composition of functions, the recursive calls will automatically drop the head of the stream(s) each time.
So I tried this:
I could get up to 3 items but it still crashed on 4. So, yes, looks like it's leaking memory somehow. I agree that this is problematic, especially with respect to using streams for logic programming. I'll see if I can figure something out.
Thank you in advance! I’ll be looking forward to it.
BTW I’ve been trying - as yet: unsuccessfully -to implement a very different data structure for streams:
- A (global) variable containing a single incarnation of the “mother” stream. Item 1: current promise; item 2: list of all yet discovered items.
- Any number of “stream” entities referring to the mother stream. Item 1: reference to the variable containing the mother stream; item 2: relevant item number.
The idea is to severely reduce memory usage (and perhaps increase execution speed).
Does this make sense at all? If so, do you think it’s feasible? Or perhaps you know of an existing example?
I must be missing something; I don't see how that would help at all. It means you're stuck holding on to the beginning of the stream, just what you don't want to do, so the stuff you've processed can be recycled. And the thing you're calling a stream seems more like an item of a stream?
I'm confused.
Thx4 your opinion! I’m just moving through the dark by touch (trial & error), sometimes making no sense at all - this may be such occasion. I’ll consider this a dead end, and will await your possible diagnosis of (and solution for) the apparent memory leak.
-
I installed some debugging code in
tail of streamandin front if stream; annotated, and to be removed before release. -
I more or less finalized the simple semaphore mechanism for
tail of stream, usingwait for (condition). It’s actually more efficient than I thought (perhaps recently improved?). An alternative mechanism (suggested by @dardoro), involving continuations, is not really much faster, and more complicated - still interesting as a future basis for e.g. queues and buffers, but not for now. -
I’m considering to replace
stream of numbers fromwithstream with numbers from (start) to (end), withInfinityas default value forend.
Why?
In some cases (e.g. SICP’s Pythagorean triples exercise, or Rationals) finite streams work better, enabling faster results.
As an alternative the version featuring the ‘to”-option could be a bonus version (i.e, hidden from the palette, while accessible via the main version’s edit window).
What do you think? -
I found a different way to express the
incrementally combine-streamsdefinition - it’s much shorter and more elegant (usingmap-streamsand self-reference) than the one I had. BTW I renamed itaccumulate (combiner) over stream (stream).
I’m inclined to keep the more elegant version, even if it’s sonewhat slower (about 3:4) than the earlier version. Would you agree? -
For Logic Programming, I’m not happy with the 2-stream version (2nd input unevaluated) combined recursively of
interleave(at your suggestion, I dropped a variadic input version for it). My reason for the disliking is that the recursive 2-stream approach doesn’t treat input streams equally. E.g. with 5 streams (OR-clauses), one of the streams (clauses) is evaluated 8 times faster than two of the others, for no reason at all; if the number of OR-clauses is larger, this effect becomes even worse. Though inconsequential from a math (computability) perspective, this does matter if you’re looking to build a usable system.
On the other hand,flatten(andflatmap) requires the second stream to be unevaluated. And I prefer not to have 2 versions ofinterleavewithin the Streams library.
So I developed a new version ofinterleave, with variadic input, all unevaluated. It works fine for all cases I could think of, just a trifle slower than each of its parents. -
I modified
list-streamin two respects: (a) added an upvar calleddownstream, referring to the remainder of the stream immediately after the reported items; (b) changed the definition’s style from recursive to iterative:
The first change was triggered by my writing a generalizedmoving average-streamblock (as an application example, it’s in the “RT Monitoring” category); I needed a helper block to find an initial list of past items (precursors), and what I came up with was likelist-stream, with an extra output: the remainder of the stream, for the main iterator to continue with. And I wondered: why not always provide that as an upvar when reporting a list of the first so-many items?
The second change was ws triggered by a test where I wantedlist-streamto report 10k items: it crashed, due to stack overflow. Stream handling blocks, though defined recursively, actually operate iteratively (like you wouldn’t know
) and therefore do not use large stacks, but list-stream(or in v1 of the library:show stream) does work recursively! To my surprise, when asked for not-too-large lists, the iterative version is a little slower than the recursive one (about 3:5 on my system), but when given the choice between speed and stability, I’ll take stability, any day of the week. Do you agree? (or we could use both algorithms: one for lists of, say, < 2k items, and the other for larger lists)
BTW This may be an interesting future forum topic, I think - not for typical Snap! users but for anyone wanting to develop library-grade blocks: how to deal with dilemmas (or worse, 3+lemmas) between speed, stability, elegance, versatility, simplicity, and what not? (brevity, readability, easy input block insertion; online help, comments, naming …)
Just hearing that word in a stream library topic wants to put me in a dilemma.
I sat down with Jens looking over the Pythagorean triples example. He thinks the problem is that the JS garbage collector never gets to run if we're always in a WARP. So I took out all the warps, which shouldn't be necessary anyway if you don't have a looping block with a ⬏ at the bottom. And I rewrote the example not to use a variable pointing to the head of the stream:
I also radically simplified TAIL:
My theory is that nobody is writing multi-script programs for the same stream, and that we should optimize for the simple, common case.
With these changes I can get to item 3, but still not item 4. Jens notess that your instrumentation shows a bazillion promises, and those are costly, especially if not GCed. So my next effort will be to see if we can't eliminate the delayedness of INTERPOLATE. And also see if the two-input version is faster than the variadic version.
So all this is the opposite of the direction in which your design has been moving. In principle I like your version, but I want this example to work. Easily. I'm really afraid we won't have something actually usable this summer, let alone logic programming.
Maybe you should take your Prolog blocks and figure out how to change them minimally so that they produce a list of however many solutions they can compute in 10 minutes, or something. :~(
Why should finite streams be better for triples? And, if you write a program for finite streams, why not just use lists?
NUMBERS FROM TO: I can imagine how that might be useful, but I'm having trouble imagining a situation in which just plain lists wouldn't be better still. I mean, I don't mind having it also, but not with "to infinity"; infinite streams are the expected use, not a screwy special case of something that's ordinarily just like lists.
ACCUMULATE: Yeah, your implementation is cute; go for it. I'm more concerned about the renaming. If you recall, we had a long discussion of this; to me ACCUMULATE (or COMBINE) suggests that the block reports a single atomic value that accumulates all the items of a stream. You could actually imagine such a block, provided that the input stream converges, although I'm not sure of the exact semantics. But the block you actually have doesn't do that, so it's not an exact parallel to a list HOF, and so a slightly clunky name sort of points that out.
INTERLEAVE: I talked about this above. The worry is that it makes a bazillion anonymous procedures, each called once, and that's costly. So it's a candidate for what's making Snap*!* crash, but who knows.
LIST n ITEMS: I feel like we're having a battle in which you try to make blocks more complicated (to the user) and I try to make them simpler. I'd rather have more blocks than a few blocks with a zillion options. Also, I'm very reluctant to put pointers to streams in upvars, where they might hang around forever.
Oh! Whoa! Upvars! and Promises! When you make a promise (e.g., with IN FRONT OF STREAM, but also with your version of TAIL) in an environment that includes pointers to streams, the environment captured by the promise holds on to the stream's storage. I wonder if this is where the excess memory is going. I'll research this next time there's a dull moment here.
Implementing it iteratively is okay, I guess.
Thank you, and jens, for taking it seriously!
I don’t believe warp causes the issue though, as my latest version contains only 1 warp - around tail of stream’s critical section, which is very short both in code and execution time:
… and the crashing doesn’t stop.
Strangely, Snap!, on my system, can actually store millions of unevaluated streams:
Is there a way to force garbage collection?
I presume we’re discussing interleave. If we’re using flatmap-stream (which is kinda hard to avoid if one wants to generate “all” rationals using streams) we must use a delayed version of interleave (SICP §4.4.4.6), otherwise the flatten-stream part of the script will get stuck in an infinite loop.
And yes, the two-input version is slightly faster than the variadic one, but less versatile. I could modify the variadic version such that it redirects to the two-stream version, whenever applicable.
I don’t think we’re working in different directions. I do think the library will be more usable if stability issues can be solved. As for the exact contents of the library - once we know the release date, I can prepare a final version within a few days.
Yeah, I’ll look into that.
I’m not sure, hope to find that out along the way.
OK, let’s keep the infinite version as standard, and the bounded as an easter egg.
The name accumulate is deliberately different from combine. I don’t see why accumulation should be a one-time event, e.g. “accumulating wealth” is something one may continue to do over many years.
I truly don’t think so. A script such as:
… will crash just as easily.
From my perspective we’re mutually challenging assumptions, making for a better end result. I’m the writer, you’re the editor.
And I don’t agree with your point on upvars. By the way list-stream is an ordinary block, without any delayed evaluations, and an upvar here is not especially vulnerable (as with blocks defining streams).
I’ll try to look into that hypothesis, too.
I ran some more “Crash tests”
I even moved a stream constructor and integrated the code of both in front of stream and tail of stream into the main script, added wait time so as to facilitate garbage collection, used zero warps … it keeps crashing:
I tried many more variations, see inside, sprite = “Crash testing”.
Yeah, INTERLEAVE. Losing my mind.
That's not millions of streams; it's millions of pointers to one stream. Try taking TAIL of the first one, and then look at one of the others.
It's really quite rare that you need INTERLEAVE-DELAYED.
No you can't, not if we can't solve this problem of crashing the browser window.
It's not different enough, especially for those of us who've read SICP! Yes, you can accumulate over time, but what you want to know is the balance of the account right now, right? Metaphors aren't detailed recipes.
Let me look into that...
My problem with upvars has nothing to do with critical sections. It's that any variable that points to a stream keeps it from being garbage collected.
EDIT: You know, anything that calls IN FRONT OF STREAM, e.g. KEEP, creates an environment that remembers its variables, such as the one pointing to its input stream. So maybe the real question is why Scheme doesn't crash when doing stream programming.
Time for more research...
Did you actually try it?
Still, I guess it’s only the “recipe” that’s been stored, not the “environment”.
Perhaps. SICP calls it from flatmap-stream, which is a recursive function they use for logic programming! Besides, having unevaluated streams for input isn’t very “expensive” AFAIK, i.e. there is no real argument against it.
I trust we’ll find a solution, even more so if jens is in it with us.
Unlike recipes, metaphors are an excellent source of names. But no problem, I’ll reverse it.
I’ve come to believe that’s true.
I’m still searching for two cases with a small but significant difference, one crashing and the other functioning flawlessly, and such that the latter is usable for fixing the Streams library.
Oh. I don't understand at all what your example was supposed to prove, with that ring around the KEEP, which I didn't notice. But what I meant is this:
vs.
Taking the TAIL of item 1 of that list of streams also TAILed item 8 bazillion, because they're all the same stream.
Ugh, okay, I'll reread that section tonight if I can.
Yes, that must be the case. If not, blocks like sieve wouldn 't work. So the whole idea of a memory leak is probably a red herring after all.
That's a very good question - something for the Snap*!* dev team to look into, I guess. Scheme uses tail call optimization, reducing the issue for many cases. AFAIK Snap! doesn’t have tail call optimization (yet). Even if it had, I doubt if 
(from 
) even qualifies, or can be reformulated, as a tail call. SICP apparently solves this by not remembering if a promise was already fulfilled, instead using the simplest possible tail call as definition of cdr-stream, namely: force (cdr stream), or translated into Snap*!*: 
. I implemented this within the Streams v2 library as a test, but it did not make any difference (as of course it wouldn’t, as long as tail call optimization is not supported).
In the meantime - I presume Snap*!* has a memory area for the environments stack - perhaps it could be resized if the hardware platform allows? This would not fundamentally solve the issue, but might mitigate it.
I wondered if the issue could also be mitigated somewhat on the Streams library level by using iteration instead of recursion, whenever possible. As it turns out, there's only so much that can be done on this level. Two categories:
- Filters (such as
keep-streamoruniques-stream; - What I call "harvesters" (i.e. blocks that take a stream as input and produce a list or a single value as output).
In the end there will always be size limits. It's just that in Snap*!* those of streams are so much stricter than for lists, that it may seriously impede use for some applications; a warning for users would be appropriate, IMO.