Planet Smalltalk

Michael writes about some interesting performance results that came out of experimental usage of the xtreams code.

Technorati Tags: xtreams

I began to write up a blog post about how to do things in Xtreams compared to Streams. I was also benchmarking as I went. Things were going smoothly until I got to an example where I would read a file line by line and test if it starts with an angle bracket. In this case, Xtreams was well over 60x slower. Scanning over a large file took a long time.

I began to investigate and I discovered that there were plenty of places to improve performance, but the biggest killer of time was the testing-for and raising-of exceptions. In my particular file, 70,000 exceptions were being raised over the 22mb file. The time to test-for and raise these 70,000 exceptions was more than half the execution time of the example.

I made a branch of Xtreams that didn't use exceptions. Instead, the API methods would return the number of elements they read and you would have to check that result each time. This was not an ideal API and Martin hated it. Still, the example was capable of running only 2x slower than the regular Streams version, while doing it in a much "fancier" fashion (ie: I had more options and more power at my finger tips).

We still want the exceptions, we're not going to live without them, but we came to the conclusion that raising exceptions when you read the end of a substream (as opposed to when you read the end of a stream) was a bad thing. 70,000 substreams do not need to raise an exception internally just to move you to the next substream. If you send a method like #rest or -= 0 to a substream, you shouldn't ever have to raise an exception. It's only if you attempt to read -past- the end that you should see the exception.

Substreams are useless if you don't give them a reasonable end condition. In our current implementation you provide the end condition separate to the substream itself. Here's an example that will give you a substream that will read only 100 elements at a time:

stream slicing: [:substream | substream limiting: 100]

Because we have a separation of the slicing implementation and the ending implementation, the two must communicate between themselves and they do so by raising and listening for exceptions. This is where the expensiveness comes in.

Since you're unlikely use a substream without requiring it to end in some fashion ahead of the main stream and since you can always use a substream to do the ending even if you only ever want one substream, we've decided to merge the slicing and ending code together. This will allow us to implement substream slicing without the need for thousands of internal exception checks and raises.

We've not begun implementing this, but I suspect the implementing will probably remain fairly similar to the end user, sans the #slicing: terminology, in otherwords this would be the same example as above:

stream limiting: 100

Hopefully this new approach will mean we can have comparable speeds to Smalltalk-80 streams while still giving us all the new power of Xtreams.

Didn't get a chance to see us at any of our recent Smalltalk technology events? Well, you can still see what we presented - we have video of everything. You can subscribe to our video feed to have them downloaded directly with your favorite podcatching software, or head on over to the video page for the events.

Technorati Tags: video, cincom

Travis explains:

we've separated what to diff with how to diff completely. This means that I can have a method on RBScanner which scans source tokens. But it can go further. Since said scanner knows where comments are, we can produce strings for the comments. In fact we can go further, we can break the comments up into words easily. We can even note when the token is a string literal token and break it up into words as well. And we can insert elements for white space. So that when we difference Smalltalk methods, we get everything broken down to the granularity we'd like.

One of the things I've never liked about the VisualWorks differencing tools, is that I have to choose between source and text differencing. Usually I want source. Source compares the source code tokens. But sometimes, it shows nothing. Why? Because the only change is a word in the method comment. Unfortunately, it only shows me the whole comment is changed, not the actual localized changes. Changes only in whitespace are equally distracting. The current solution embodied by DiffList, and a UI tool called Differator, doesn't really get where I want to.

What I really want one is ONE difference mode, that shows all of this at the same time. Pursuing this goal, lend me on an interesting journey. The results are in the mar10.2 7.8 build that will come out tomorrow.

To begin with, we have to separate two distinct parts. One is comparing texts. The other is what to do with the differences we find. Let's leave the second behind for a minute. If we solve the first problem generally enough, we'll have a myriad of choices open to us for the second.

A good starting place, is to go to the classic Unix diff command line utility. After digging around for a while with this, we'll discover two things: 1) It's not really about text at all 2) the algorithm found at the heart of the diff program is a nicely tuned piece of work.

The basic diff algorithm starts out on the basis, that for any two sequences (whether they're sequences of characters, words, textlines, bytecodes, or even DNA markers), there is a sequence that is a "longest common sequence". There may be multiple resolutions to this, but none of them is longer than the other. You can find lots of interesting stuff about this around the net. A simple example is the sequences h-u-m-a-n and c-h-i-m-p-a-n-z-e-e. The longest common sequence (LCS) between the two is h-m-a-n. Once we have that, we can determine the steps it takes to turn the first sequence into the second. This is sometimes called the shortest edit script. In this case, we end up with the following edit script: Insert c, copy h, delete u, copy m, insert p, copy a and n, insert z and e and e. This gives a directional evolution from one to the other. Want to go the other direction though? Just transpose inserts with deletes and keep matches in place.

With this kind of information, we can envision a number of different ways of highlighting differences between texts, or DNA sequences, etc. We can do them in a unified view. We can do them in side by side views. We can even discern replacements from true insertions or deletions, because it's a paired delete/insert sequence.

The mar10.2 build adds a new differences: API to SequenceableCollection. You can take any two sequences and determine how to evolve one from the other. You can feed it DNA symbols, strings, numbers, whatever you can think of to put in a SequenceableCollection. The result is an array of SubsequenceDifference subclasses, one for each of the different kind of edits.

At the heart of the algorithm is a modified/ported version of a generalized version of the Meyer's Diff algorithm. This too, you can find lots of stuff on the net about. You'll even find a couple of visualizations. What the Myers adaptation of the LCS exploits is that usually, the algorithm is applied in cases where differences are few compared to matches. It also integrates the process of finding the LCS with the process of determining steps, it ends up being a linear space algorithm. To say it's a hairy nasty work of indirection and head scratching, is an understatement. It makes sorting algorithms look like kindergarten reading.

I ported it 3 times. Each implementation I found had a test suite, so I gathered those into one big test suite and added a couple edge cases. The first port was of a C# implementation. This seemed easy, but I ended up with out of bounds errors (the algorithm relies heavily on 0 based array addressing). So I tried a Ruby version. It was ironically harder to port (this is the language that's supposed to be a lot like Smalltalk). And it too had issues. Then I ported a generalized C version (generalized in the sense it was parameter-izable), and it worked! All the tests passed. There's irony for you.

How much faster is it? Given the degenerate case of determining how to get from Object comment to Object comment reverse, the VisualWorks DiffList which is a hybrid LCS searcher and produces only "unmatching range" information, takes 12.5 seconds to run. The differences: method does it in under half a second. Implementing a naive recursive LCS method, has to be killed after grinding for 3 hours.

At least two good things have come out of this. One is that there is now a general purpose method to quickly and efficiently produce complete shortest edit scripts between any two sequences. Application programmers don't have to be tied to the IDE's method of highlighting differences between two strings, they can do whatever they want. Application Programmers can use it in contexts beyond source comparison (e.g. comparing load lists, or determining undo differences, or DNA sequencing, or schedule comparison, etc).

Secondly, we've separated what to diff with how to diff completely. This means that I can have a method on RBScanner which scans source tokens. But it can go further. Since said scanner knows where comments are, we can produce strings for the comments. In fact we can go further, we can break the comments up into words easily. We can even note when the token is a string literal token and break it up into words as well. And we can insert elements for white space. So that when we difference Smalltalk methods, we get everything broken down to the granularity we'd like. Which was what I wanted in the first place.

Travis shares some ideas he's got on evolving the UI in VisualWorks - complete with a screencast.

Technorati Tags: visualworks, UI

A couple of months ago, I was daunted by the prospect of having to do yet another Look and Feel set of subclasses for the VisualWorks widget set. The technique of subclassing is hopelessly over-leveraged in what is there.

The debate about whether to do native widgets or not, and in what form factor has gone round and round for years now. It will continue to do so. Somewhere in there, I pondered "what would happen if I could draw standard widgets faithfully (or pretty darn close), but still emulate them? Is there a half way point there?"

I found that for OSX and Windows, there actually was to some degree. I discovered that all of the graphic resources that OSX uses are actually in a database and can be pried out and reused. You have to make the right decisions about how to use them, but if you use them correctly, you're doing the same thing OSX is. On Windows the story was even better. uxTheme.dll is the theming engine that Windows uses to evolve it's look and feel, as well as customize widgets for other platforms (such as mobile devices) -- much thanks to Michael Lucas-Smith for pointing me towards this.

So I began experimenting with that, and some other ideas that we've already been hinting at, in a package that I dubbed Skinny. It's so dubbed, because I'm interesting in getting to a point, where changing the skin of a VW app (whether the IDE itself, or something else), is relatively easy.

Here's a screencast that shows me playing with version 93 which is in the Open Repository.

Here's a list of questions/answers one might ask about such an experiment:

Q: Which versions of VisualWorks do I have to have for this?

A: You need a pretty recent 7.8 dev build. There are small things from this project, that we've been rolling into VisualWorks proper.

Q: Do you plan on integrating this in the product someday?

A: I don't know yet. It could be that we end up doing yet another subclass tree and just harvest the uxTheme.dll drawing know how. Or maybe more of a hybrid. I don't know yet.

Q: Does the Windows look and feel work on other platforms?

A: No. It doesn't.

Q: What other skins have you played with?

A: There's an OSX one. It uses Cairo to render the various graphics excavated out the OSX graphics database. Ironically, it actually works better at the moment on either Windows of X11, since Cairo doesn't interleave efficiently with Quartz drawing. It works there, but it's pretty jerky. Great benchmark for really improving Cairo on OSX.

Q: Which widgets have you built for?

A: Push Buttons, Radio Buttons, Check Boxes, Scroll Bars, Tab Controls, Splitters (the splitters don't build thru UIBuilders tho)

Q: What if I'm more interested in not using UIBuilder technology and just simply snapping widgets together?

A: Look at the various class side example methods on Skinny objects.

Q: What known issues are there already?

A: Haven't made any of them keyboard navigable (waiting to integrate some changes to the core to simplify KeyboardProcessor first). The Scrollbars don't get their thumbs sized initially right, they require a click to do so. Lots of others, I'm sure.

Q: What IDE tools seem to work?

A: In the screencast, I show workspace, inspector, and settings tool. There's actually one page in settings tool that has issues still (a store one with a dataset). The browser kind of works. Some of the widgets don't pick up the skinny skin. The FileBrowser tanked last time I tried it. I have used the debugger on it successfully before, but currently have it turned off.

Q: Why are you blogging about it?

A: Always a good idea to give people a peek at what kind of things are going on. I'd also be interested in people trying to use it with their own apps. I'm curious how long it would stay alive and if there's an obvious "implement this next" vector.

Very nice Cairo and Pango work in Cincom Smalltalk from Chris Thorgrimmsen.

Technorati Tags: cairo, pango, graphics