Squeak-dev April 2001

squeak-dev@lists.squeakfoundation.org

165 participants
614 discussions

Re: Comments on Smalltalk block closure designs, part 1
by Mark van Gulik 27 Apr '01

27 Apr '01

on 4/26/01 7:36 PM, Richard A. O'Keefe at ok(a)atlas.otago.ac.nz wrote: > Allen_Wirfs-Brock(a)mail.instantiations.com wrote: > A 100-to-1 performance hit on a cache miss is a rule of thumb I > have heard people use for modern processor/memory subsystems. > > The figures I saw for UltraSPARC, back in 1996, were > load from register => result available 1 cycle later > L1 cache => 2 cycles later > L2 cache => 8 cycles later > main memory => 30 cycles later > for a machine that could run 4 instructions per cycle. Since then, > CPU speeds have nearly quadrupled, but memory speeds have not. > > Then there's the point that if you try to recycle contexts in the heap, > you had better make sure that the garbage collector knows to ignore > references from slots that are not currently in use (more GC complexity) > or that they are nilled out on exit (more time overhead). I prepared a much larger post about this, then noticed something interesting and started again... There is no advantage to saving Newspace-allocated context corpses during scavenging. Thus, at scavenge-time you can simply throw away your context freelist. Alternatively, if you've allocated them in a separate LIFO-Context space, you won't be scanning the dead ones at scavenge time anyhow. Since corpses are never scanned, you don't have to worry about garbage pointers in them. Still, a debugging version of the VM might want to fill context corpses with DEADBEEF (hex) for your own sanity. Say you nil the slots at allocation time. Some architectures allow you to zero an entire cache line with one instruction (to avoid the latency and traffic of a memory read when you intend to clobber all the data anyhow). To avoid chocking the write queue, simply use this technique to get the cache to believe you have current data for the data block that's, say, 64 bytes ahead of where you're actually allocating. That's probably small enough that the writes (due to the zeroing) won't get flushed out before the memory actually gets used to house an object. Leave a 128 byte headroom at the end of Newspace that never gets written to. Don't worry about precisely zeroing every data block, just don't ever zero a data block more than 64 bytes beyond the end of allocatable Newspace. Most objects are small, so a single zero-data-block instruction per object allocation should be plenty. Redundant zeroing of the same data block (due to very small objects) probably aren't too expensive, since they only affect the innermost cache. If you nil the slots at context-exit time, you run the risk that a scavenge could happen, wasting the nilling effort (i.e., throwing away the context corpse -- it's still cheaper than *copying* it to ToSpace). Also, by the time you reuse the object the cache line might have been reused for other data, so you'd have to read it back from the next layer of cache. >From this I conclude that allocation time is when nilling should happen. Something else: Someone in this thread (I think it was Ian Piumarta) mentioned that basically there is no such thing as "locality of reference" between cache lines. This is due to the fact that this kind of cache uses associative lookup (typically with some kind of "wired-or" if MY associative memory serves me). He then stated that until a memory boundary was reached, the cache miss cost stayed pretty low, then suddenly spiked way up. As a worst case, consider swapping to a rotating disk. A disk read of 10ms is ***1,000,000 times slower*** than accessing cheap 100MHz (=10ns) memory (approximately). I've heard horror stories from the "good ol' days" in which the code was *executed* directly from drum memory. Brrr. Anyhow, I've been thinking of ways to make garbage collection of <sarcasm>involuntarily persisted</sarcasm> objects quicker. If a CPU running in User Mode is allowed to test the current permissions of a page (without triggering a page fault), a garbage collector could simply do its best to mark what's currently in memory while building up a list of what to fetch later from disk. In theory, this list could be fed to an OS for page-prefetching. The OS might even re-order the reads to minimize latency. This would greatly reduce the insane amount of thrashing that current GC's exhibit when hitting the memory/disk barrier. It would also allow the GC to continue to do useful work while the disk stays busy prefetching pages. Current GC's will block the whole thread for 10ms until a needed (random) page is completely fetched, then do the same thing a microsecond later with another page. Meanwhile, a page gets swapped *out* to make room, and a few milliseconds later it's needed again... The working set is just too large to access randomly when you know almost every page will be accessed many times per GC. Has anyone heard of any work being done in this vein? If the rate of increase of processor speeds continues to be significantly higher than the rate of increase of memory speed, this idea might soon become applicable at the cache/main-memory boundary too. Tied to a futuristic multiple-path-speculative-execution, multi-threaded processor core, this might stretch the concept of out-of-order execution to its extreme. -Mark

1 0

Re: HELP! MIDI-player demo sounds like *@#%!
by Andrew P. Black 27 Apr '01

27 Apr '01

>From: Stephane Ducasse <ducasse(a)iam.unibe.ch> >Subject: Re: HELP! MIDI-player demo sounds like *@#%! > >Pay attention to put the right display depth and the cycling processor >should not be allowed > >on 4/22/01 3:56 AM, Andrew P. Black at black(a)cse.ogi.edu wrote: > > >> I just tried out the MIDI player demo that, in 3.x, lives in the "Fun >> with Music" project. I didn't expect any problems, since I have used >> this in classes several times over the last couple of years. >> > > It sounds like *@#%! Stephane was right: processor cycling was on. I was at my wits end over this one. Once again, the Squeak list saves the day. Thanks Stephane; I'm posting this here so that other can learn from my mistake. Andrew

2 1

[ENH] OrderedCollection>>removeAllSuchThat: speedup
by Richard A. O'Keefe 27 Apr '01

27 Apr '01

Some time after 2.7 the removeAllSuchThat: methods were revised to just remove and not return the removed elements, making their names inconsistent with other methods such as removeFirst. Luckily, that doesn't break any of my code. However, the OrderedCollection>>removeAllSuchThat: method in Squeak 3.0 is an O(N**2) method. Here is an O(N) method. 'From Squeak3.0 of 4 February 2001 [latest update: #3552] on 27 April 2001 at 3:36:48 pm'! !OrderedCollection methodsFor: 'removing' stamp: 'raok 4/27/2001 15:35'! removeAllSuchThat: aBlock "Remove each element of the receiver for which aBlock evaluates to true. The method in Collection is O(N^2), this is O(N)." |n| n _ firstIndex. firstIndex to: lastIndex do: [:index| (aBlock value: (array at: index)) ifFalse: [ array at: n put: (array at: index). n _ n + 1]]. n to: lastIndex do: [:index | array at: index put: nil]. lastIndex _ n - 1! !

1 0

[ENH] Collection>>storeOn: refactoring
by Richard A. O'Keefe 27 Apr '01

27 Apr '01

I have a subclass of OrderedCollection and wanted to provide storeOn: for it. It seemed silly to copy the whole method when I only wanted to fill in a few instance variables. With this refactoring, a subclass of OrderedCollection that adds 'foo' and 'bar' instance variables with appropriate setters can do storeEmptyOn: aStream super storeEmptyOn: aStream. aStream nextPutAll: ' foo: '. foo storeOn: aStream. aStream nextPutAll: '; bar: '. bar storeOn: aStream. ^false and the "new" expression and the "add:"s will still come from Collection. 'From Squeak3.0 of 4 February 2001 [latest update: #3552] on 27 April 2001 at 3:20 pm'! !Collection methodsFor: 'printing' stamp: 'raok 4/27/2001 15:09'! storeEmptyOn: aStream "Write to Stream an expression that creates an empty collection of my class that is as like me as possible, except for my elements. storeOn: will take care of writing the elements out. Return a Boolean to say whether the expression ends with a message send so that storeOn: knows to write a semicolon. This is provided so that subclasses can override it to write out attributes of various kinds. They will typically call this method via a super call." aStream nextPut: $(; nextPutAll: self class name; nextPutAll: ' new)'. ^true! ! !Collection methodsFor: 'printing' stamp: 'raok 4/27/2001 15:08'! storeOn: aStream "Refer to the comment in Object|storeOn:." | noneYet | aStream nextPut: $(. noneYet _ self storeEmptyOn: aStream. self do: [:each | noneYet ifTrue: [noneYet _ false] ifFalse: [aStream nextPut: $;]. aStream nextPutAll: ' add: '. aStream store: each]. noneYet ifFalse: [aStream nextPutAll: '; yourself']. aStream nextPut: $)! !

1 0

[ENH] Collection>>includesSubStringAnywhere:
by Richard A. O'Keefe 27 Apr '01

27 Apr '01

Collection currently includes includesSubstringAnywhere: testString "Answer whether the receiver includes, anywhere in its nested structure, a string that has testString as a substring" self do: [:element | (element isKindOf: String) ifTrue: [(element includesSubString: testString) ifTrue: [^true]]. (element isKindOf: Collection) ifTrue: [(element includesSubstringAnywhere: testString) ifTrue: [^true]]]. ^false I find it somewhat confusing that we have substrings findSubstring:in:startingAt:matchTable: includesSubstringAnywhere: includesSubstring:caseSensitive: but includesSubString: ^ That is the ONLY method which spells "Substring" with an internal capital. Part 1 of this enhancement is to add a copy of the includesSubString message, spelled consistently. The main point is that anything which is a kind of String is thereby a kind of Collection, but there is no point in checking a bunch of Characters to see if they are Strings or Collections. It turns out that I have a use for this method. So part 2 of this enhancement is to skip the Collection check for Strings. This changeset should also work in 2.7 and 2.8. 'From Squeak3.0 of 4 February 2001 [latest update: #3552] on 27 April 2001 at 2:53:08 pm'! !Collection methodsFor: 'testing' stamp: 'raok 4/27/2001 14:49'! includesSubstringAnywhere: testString "Answer whether the receiver includes, anywhere in its nested structure, a string that has testString as a substring" self do: [:element | (element isKindOf: String) ifTrue: [(element includesSubString: testString) ifTrue: [^ true]] ifFalse: [(element isKindOf: Collection) ifTrue: [(element includesSubstringAnywhere: testString) ifTrue: [^ true]]]]. ^ false "#(first (second third) ((allSentMessages ('Elvis' includes:)))) includesSubstringAnywhere: 'lvi'"! ! !String methodsFor: 'accessing' stamp: 'raok 4/27/2001 14:43'! includesSubstring: subString ^ (self findString: subString startingAt: 1) > 0! !

1 0

Re: StarLogoAnts and missing class
by Ned Konz 27 Apr '01

27 Apr '01

On Thursday 26 April 2001 18:50, Ross Boylan wrote: > Anyone know about running this on MS Windows? I assume I'm out of luck on > Linux with the plugin. You're never out of luck with Linux! Just generate the VM sources and re-compile! in Squeak: StarSqueakPlugin translate quit Squeak. move the generated .c file (and its directory) to your source directory: mv StarSqueakPlugin Squeak-3.0pre2/src/generated/ cd into your build directory cd Squeak-3.0pre2/build and re-build make clean make make install (as root, if necessary, or just move files) This is from memory, but I think it's all I had to do. Specifically, I didn't have to add StarSqueak to src/unix/PLUGINS as I recall. If you have an x86 system and aren't up to that, you could get it from me and put it with your other plugin shared libs (my guess is that only the .so is necessary). Look at: http://nedkonz.dhs.org:8080/Ned/uploads/10/StarSqueakPlugin.so http://nedkonz.dhs.org:8080/Ned/uploads/10/StarSqueakPlugin.la -- Ned Konz currently: Stanwood, WA email: ned(a)bike-nomad.com homepage: http://bike-nomad.com

1 0

Re: Newsweek article on "Dynabook-like" computer
by David P. Harris 26 Apr '01

26 Apr '01

Hi- Yes, I meant one that mactched your ideal, not the Microsoft one. D Alan Kay wrote: > Well, as Andreas pointed out, one really needs a keyboard as part of > the idea. If you look at the earliest photograph of the cardboard > model from 1968, you will see that it has a keyboard -- harder to see > is the stylus which is embedded in the side. These considerations came > from a fair amount of use of both GRAIL at RAND (a completely penbased > system with a great realtime character recognizer), and of NLS > (Engelbart's system that used mouse, chord keyboard and regular > keyboard). One could go fairly quickly with both the character > recognizer and the chord keyboard, but not quickly enough to do large > scale compositions in text. These were great for small scale > compositions, such as typos, names, a few lines of code, etc. For this > reason Engelbart had a regular keyboard in between the mouse and the > chord keyboard, that you would switch to when you had large amounts of > text to input. We all realized that this would have been a good idea > for GRAIL, and I incorporated the idea in the original Dynabook model, > on the grounds that even a perfect instant character recognizer > couldn't do the whole job. Most of the tablet computers from > Newton onwards have had marketing people in the way who want real > differentiation in the product and don't care about actual human use. > In the MS Tablet, they really need to have something like a > flip-from-underside keyboard for real use. (I didn't put that in the > first model because I would have been very happy to have any portable > flat-screen display at that time, the squarish one shown here would > have been just fine with me. BTW, the Owens-Illinois plasma panel > (512*512) was happening at the time but it drew too much power. There > were also a few LC panels being pioneered at > Westinghouse. Cheers, Alan[Image]At 7:43 AM -0700 4/26/01, David P. > Harris wrote: > >> I imagine that getting a 'real' Dynabook will be a grand experience >> for >> you. Here's hoping it will happen in the near future! >> D >> >> >> Alan Kay wrote: >> >> > BTW Squeak runs beautifully on Chuck's* machine. Using the >> fleshed >> > out media version of Squeak on the Tablet is the closest thing to >> a >> > complete Dynabook experience I've yet had. Cheers, Alan *The >> "Tablet" >> > was done by Chuck Thacker who did the Xerox PARC computers, and by >> >> > Butler Lampson who was one of the leading lights at PARC. It's >> really >> > nice, and only 1 pound too heavy. -------- At 6:17 PM -0500 >> 4/25/01, >> > Larry Trutter wrote: >> > >> >> There is a brief article in Newsweek (April 30th, 2001 issue) >> about >> >> the "Dynabook-like" computer being >> > >> >> developed by Microsoft. It contains some quotes from Alan Kay and >> >> >> some history. >> > >> >> >> > >> >> The author of the article did not seem to grasp the meaning of >> the >> >> Dynabook as envisioned by Alan Kay. It bascially described an >> >> unltra-portable computer with character-recognition capability. >> The >> >> article discussed >> > >> >> benefits such as information and convenience but not one word >> about >> >> the potential of the real Dynabook. >> > >> >> >> > >> >> That's all I remember, I just borrowed the magazine during lunch >> >> hour at a restaurant...... >> > >> >> >> > >> >> FYI, >> > >> >> Larry Trutter >> > >> > > >

1 0

Re: looking for answers to exercises in Squeak book Ch 2.
by Bob Arning 26 Apr '01

26 Apr '01

Hi Tom, On Thu, 26 Apr 2001 15:45:15 -0400 txporter(a)mindspring.com wrote: >At the end of chapter 2, there are some exercises, specifically No. 3: >Write a piece of workspace code [...] to do the following: >(a) Replace all vowels in the string 'Squeak' with dashes. >(b) Compute the average of a set of integers in an array. > >I did this like so, but think it is more like "procedural-language speak' and not Smalltalk. Anyone have any more elegant solutions? I particularly do not like the use of the aCount variable. > >aString := 'squeak'. >aCount := 1. >aString do: [:element | element isVowel ifTrue: > [aString at: aCount put: $-]. "Could aString be self?" > aCount := aCount +1]. 'squeak' collect: [ :ch | ch isVowel ifTrue: [$-] ifFalse: [ch]] >anArray := #(12 14 16 18 20). >aSum := 0. >aCount := 0. >anArray do: [:num | aSum := aSum + num. > aCount := aCount +1]. >anAverage := aSum / aCount. Well, the simplest way would be #(12 14 16 18 20) average If you weren't aware that #average existed, you might try | anArray | anArray _ #(12 14 16 18 20). anArray sum / anArray size If #sum weren't available, you could do | anArray | anArray _ #(12 14 16 18 20). (anArray inject: 0 into: [ :sum :each | sum + each]) / anArray size >Sorry for such a trivial start, but I really want to grok the OO way to do this. No problem. Cheers, Bob

1 0

[FIX]MPEGPlayerMorph>>openMPEGFile
by Karl Ramberg 26 Apr '01

26 Apr '01

Fixes a bug when the file dialog is canceled. Karl

1 0

List policy
by Scott A Crosby 26 Apr '01

26 Apr '01

---------- Forwarded message ---------- Date: Mon, 23 Apr 2001 14:23:03 -0400 (EDT) From: Scott A Crosby <crosby(a)qwes.math.cmu.edu> To: squeak-request(a)cs.uiuc.edu Subject: Re: Bug in package browser On 23 Apr 2001 squeak-request(a)cs.uiuc.edu wrote: > Your message was not sent to the squeak(a)cs.uiuc.edu mailing list > because your e-mail address does not appear to be subscribed. You > can only send mail to the mailing list if you are subscribed. If > you are possibly subscribed under another alias, please > let me know so I can change it if necessary. I am curious why you have this policy. It can be convenient to send messages without being subscribed, especially if it is something short, like a bug report. To sign up requires somewhat more effort; both the subscription, and the mail filtering to put hte messages in a seperate filter. As such, will you change the policy and/or at least forward this message? Scott > > If you want to send to the mailing list from different addresses, > please tell me. I can set it up to accept mail from multiple > addresses. > > Once the problem is resolved, you will need to resend your message > to the mailing list. > > Your original message is included below. > > -Eric

1 0

← Newer
1
...
5
6
7
8
9
10
11
...
62
Older →

Jump to page: