Watchers with Nested Lists Cause Serious Performance Issues

[cycomachead]

I've noticed that watchers for 2D and 3D lists can basically cause Snap! to hang once you try to interact with them.

If you run this project and click on the set block, you get a 96_96_4 list (which isn't terribly big!) and once you try to resize the watcher Safari and Chrome just beach-ball.

http://snap.berkeley.edu/snapsource/michael/index.html#present:Username=cycomachead&ProjectName=graphics%20test%20alonzo

I've noticed this with big-ish 2D lists as well.

Processing these lists seems ok, but the second you try to use a watcher the whole UI seems to just stall,

[jmoenig]

Ah, okay. Well, that's easy to fix. As long as you don't want any changes to be immediately visible :-) I did boost list performance in Snap (as compared to BYOB) in favor of watcher performance. This way you can have several watchers on the same list (e.g. one on the stage and another one in a speech/result bubble) and both keep in synch, you can even edit either directly - try doing any of this in Scratch, btw.) The problem isn't the size of the list but the number of visible cells (which could alse be scolled into view). I've put a maximum of 100 in the list watcher, which works fine even for most nested lists. For example this one, which is way bigger than yours (300 k elements), works fine:

Problem is, the more cells you show, the longer takes for the watcher's to check each cell's value at each checkpoint (every couple of display cycles). So we'll have to be more careful to determine the number of cells which are actually visible, and maybe reduce that some way. Another idea would be to switch of the auto-update feature for largish list watchers altogether and to let the user manually press an "update" button. In your example what makes it slow is that the lists second dimension is also nearing the limit of 100 visible cells, so all in all we've got almost 30.000 cells constantly polling for updates. That can't work.

My design intention for list watchers was to enable the kind of synchronicity and "liveliness" that lets you manipulate them in place anywhere, not to enable their use as spreedsheets. Obviously this is size-dependent. So see, maybe this whole pixel data idea isn't so great after all. We ought to have an in depth discussion about the intended - well, no, about the meaningful - scope of Snap.

We keep running into this same conflict here. On one hand the most important Snap feature for me is its "liveliness". The fact that you can edit a running script, a "live" project and watch arbitrary values is something you cannot do in other languages (like Python). But I have the feeling that this isn't what many people want. They're more interested - like you - in spread sheet applications. So, I think we should have a spreadsheet widget that doesn't keep in synch with a data source, but that is the data source itself. That way we could let users edit zillions of values, no problem, as in Scratch, but then you cannot have watchable first-class lists, unless computers become way more powerful. But then again, you can already do exactly that in a real spreadsheet app, and you can totally export any Snap list as CSV, so why should we do it all inside Snap?

Anyway, I'll try to find a solution that lets you at least handle such list watchers. But I'm having doubts about this whole undertaking of handling pixel data as lists.

[cycomachead]

Anyway, I'll try to find a solution that lets you at least handle such list watchers. But I'm having doubts about this whole undertaking of handling pixel data as lists.

Well, don't worry about the pixel data as lists thing, at least not for a while! :) This is merely a project for an image manipulation class. I'm not at all certain I'm doing things in a way that makes sense right now. However, I do think some level of pixel / image manipulation in Snap! would be really amazing, because some of the techniques are amazingly simple and things like Matlab want to make me cry.

I've noticed the issue with a list that was also about 600x700.

I don't know if I'd say that it's just about spreadsheet stuff though, but students really do want to be able to data manipulation in Snap! on decently sized data sets.

In my experience, few students (or the ones I see) actually use watchers to manipulate the data. They're mostly used for debugging purposes.

[jmoenig]

Well, debugging is certainly a good usecase for list watchers and I'd like to support it in Snap even for bigger lists. The problem isn't so much whether list watchers are editable (even though I'd argue that for kids just starting out it's a great way to directly add things like names or shopping items to a list that's shown onstage), the problem is keeping potentially multiple list representations in synch with a changing data source. That's the big idea behind "first-class" lists in my view, but that's also costly performance-wise (which is why Scratch doesn't do it). So there are several paths we can explore to fix this. The obvious one would be to embrace Scratch's limitation of not having first-class lists, because then we don't even have to step (use morphic observation on) them, which will make them really fast. Other solutions could be to make them update slower, or let them take longer to complete an update, possibly over several display cycles. But mind you, this is going to slow down other things, it is going to make the IDE less responsive and slow down running scripts, and I can just see people complaining about that.

Right now Snap's first-class lists are quite usable unless you watch several ones or big nested ones (big meaning many cells). For debugging it would maybe be enough to simply open a non-auto-updating inspection widget on them.

[brianharvey]

Two things: First, can't each watcher update only the cells that are actually visible right now? That would make it super fast and would also let us get rid of that selector for which hundred items to show, which I've always disliked.

Second, as for pixel data, i.e., costumes, my idea is that their visible representation is the picture itself (and you should be able to right click on it and open the paint editor on it), and internally it's just the actual bitmap, even though it responds to list blocks.

[jmoenig]

Yep, that's a good strategy, only to step those cells which are in sight (and only even to create ones that get scrolled into sight, and maybe - or certainly - delete those again that get scrolled out of sight). I definitely want to explore this direction. But - as we Germans say - "the devil is in the details", Since we have many things in Snap that can be first class we don't know the dimensions of a cell in advance (before we query the data it holds), so we have to approximate and later iterate over the scroll bars etc. I'm not saying it can't be done, but it's something we have to add to the Morphic framework first, and it's tedious to do (but worth it!).

And yes, I also agree on the second thought. Problem is, what if you create another set of variables on some sub-lists (e.g. a row, a column, a pixel) and open a watcher on that. Wouldn't you want that to automatically update whenever it's (sub-) source somehow changes? But maybe all of this won't matter anymore once we implement 1)

[cycomachead]

Second, as for pixel data, i.e., costumes, my idea is that their visible representation is the picture itself (and you should be able to right click on it and open the paint editor on it), and internally it's just the actual bitmap, even though it responds to list blocks.

We do have visible representations of Costumes in a morph. That actually works right now, though you need to use the wardrobe reporter to be able to get to the data. My original plan was to focus more on the visual aspect, but it was easier to just use the dropdown menu. I've also been thinking that it would be nice to have 2D lists, rather than 3D lists. Each color should just be represented as the color swatch of the 4 values, and if you need a list, well there's a block. Currently, watchers can't display colors, but I think that's an easy fix.

Anyway, most of that was besides the point of this issue -- I'm going to send an email to you both and a couple others soon about the graphics project. Some of this is definitely outside the scope of 'normal' Snap! but I hope we can also figure out the extensions thing because I think this would enable a fun lab or two in BJC.

---

As far as the original issue on watchers. Yeah, my thought is similar to Brian's. It's true that we don't know the dimensions of the internal cell data, but I think the default list watcher is only 4 items, so that seems like the type of thing we could get a reasonable lower bound for, though there are lots of details to consider.

[brianharvey]

I think that bitmap, row, and pixel will all be special data types that display as the pictures they represent. If someone watches a column of a bitmap, we have to think about whether the right thing is to represent it internally as if it were a row of another bitmap or to turn it into a real list. For sure if someone prepends "hello" to a row we have to display that as a list.

Actually if you're debugging a program, sometimes you'll want to see the picture and sometimes you'll want to see numbers, so we might end up with a radio button menu like the big/small/slider one.

There is a minimum size of a list cell, and if you start by assuming all cells are that size, you'll still just examine 20-odd values before figuring out what the actual visual window will be, so I agree that it's complicated but I'm optimistic that once done it'll run fast.

[bb010g]

Since we have many things in Snap that can be first class we don't know the dimensions of a cell in advance (before we query the data it holds), so we have to approximate and later iterate over the scroll bars etc.

How are lists implemented? If they're linked lists, I get that they can't be optimized, but if they're using an array-like construct, size could be stored along with the actual array and updated when needed.

[cycomachead]

How are lists implemented? If they're linked lists, I get that they can't be optimized, but if they're using an array-like construct, size could be stored along with the actual array and updated when needed.

See lists.js. But they can be either linked lists or arrays, so some lists have a property (native [].length) and some don't.

[brianharvey]

The hard part isn't about the length of the list, but about the screen size of the elements. For example, if a script is in the list, you basically have to render it to compute its height and width.