Squeak-dev September 2010

squeak-dev@lists.squeakfoundation.org

110 participants
401 discussions

The Trunk: Collections-nice.385.mcz
by commits＠source.squeak.org 30 Sep '10

30 Sep '10

Nicolas Cellier uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-nice.385.mcz ==================== Summary ==================== Name: Collections-nice.385 Author: nice Time: 30 September 2010, 11:46:29.277 pm UUID: 4d54da08-721a-4a4d-8387-914046189879 Ancestors: Collections-ul.384 Improve comment of Heap. Please feel free to improve me. As the class comment did start with a bit misleading comparison against SortedCollection, provides an optional #fullySort operation to fully sort the Heap and restore comparison ground - hope I didn't spoil announced O(n log n) efficiency. Of course, #fullySort has no interest for priority queues, but a Heap could be of more general use. =============== Diff against Collections-ul.384 =============== Item was changed: SequenceableCollection subclass: #Heap instanceVariableNames: 'array tally sortBlock indexUpdateBlock' classVariableNames: '' poolDictionaries: '' category: 'Collections-Sequenceable'! + !Heap commentStamp: 'nice 9/30/2010 23:22' prior: 0! + Class Heap implements a special data structure commonly referred to as 'heap' [ http://en.wikipedia.org/wiki/Heap_%28data_structure%29 ] + A Heap is a kind of binary tree stored in a linear array - see details after the instance variables description. - !Heap commentStamp: '<historical>' prior: 0! - Class Heap implements a special data structure commonly referred to as 'heap'. Heaps are more efficient than SortedCollections if: - a) Elements are only removed at the beginning - b) Elements are added with arbitrary sort order. - The sort time for a heap is O(n log n) in all cases. + Heaps are good at handling priority queues because: + 1) greatest priority element according to the sort block will be stored in first position and thus accessed in O(1) operations + 2) worse time for inserting or removing an element is in O(log n) operations, where n is the size of the Heap + Insertion/Removal times are more efficient than above upper bound, provided that: + a) Elements are only removed at the beginning + b) Elements are added with arbitrary sort order. + 3) there is no need to fully sort the Heap, which makes it more efficient than a SortedCollection + + The heap can be fully sorted by sending the message #fullySort. + Worse time for fully sorting the Heap is in O(n log n) operations, but this is rarely used a feature. + Remind that the Heap does not fully sort the collection if you don't ask. + Thus don't expect #do: and other iterators to enumerate elements according to the sortBlock order. + Instance variables: array <Array> The data repository tally <Integer> The number of elements in the heap sortBlock <Block|nil> A two-argument block defining the sort order, or nil in which case the default sort order is [:element1 :element2| element1 <= element2] indexUpdateBlock <Block|nil> A two-argument block of the form [:data :index | ... ] which allows an application object to keep track of its index within the heap. Useful for quick heap update when object's sort value changes (for example, when an object in a priority queue has its priority increased by an external event, you don't want to have to search through the whole heap to find the index before fixing + the heap). No update occurs if nil. + + The Heap can be viewed as a binary tree (every node in the tree has at most two children). + The root is stored in first slot of internal array. + The children are stored in next two slots. + The children of children in next four slots. + etc... + For a node A of index i (1 based), the two children B1 and B2 are thus stored in indices (2*i) and (2*i+1). + Of course, the children indices must be less than the tally otherwise they are considered inexistent. + + The Heap does arrange to preserve the following invariant: + For any children B of a node A, A is sorted before B, in other words, (self sort: A before: B) = true + This implies that the root is always the first element according to sort order. + + ! - the heap). No update occurs if nil.! Item was added: + ----- Method: Heap>>fullySort (in category 'accessing') ----- + fullySort + "Fully sort the heap. + This method preserves the heap invariants and can thus be sent safely" + self privateReverseSort. + 1 to: tally // 2 do: [:i | array swap: i with: 1 + tally - i]! Item was added: + ----- Method: Heap>>privateReverseSort (in category 'private') ----- + privateReverseSort + "Arrange to have the array sorted in reverse order. + WARNING: this method breaks the heap invariants. It's up to the sender to restore them afterwards." + | oldTally | + oldTally := tally. + [tally > 1] whileTrue: + [array swap: 1 with: tally. + tally := tally - 1. + self downHeapSingle: 1]. + tally := oldTally!

1 0

Why do Heap re-sort when it removes elements ?
by Nicolas Cellier 30 Sep '10

30 Sep '10

Hi, I just saw this: Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. array at: index put: (array at: tally). array at: tally put: nil. tally := tally - 1. index > tally ifFalse:[ "Use #downHeapSingle: since only one element has been removed" self downHeapSingle: index]. ^removed This means that an element removal triggers a new sort phase... (even a simplified one costs) I think this could be more efficient: Heap>>privateRemoveAt: index "Remove the element at the given index and make sure the sorting order is okay" | removed | removed := array at: index. tally := tally - 1. array replaceFrom: index to: tally with: array startingAt: index + 1. array at: tally + 1 put: nil. indexUpdateBlock ifNotNil: [ index to: tally do: [:i | self updateObjectIndex: i]]. ^removed Did I miss a good reason justifying to re-sort ? Nicolas

2 2

WideString hash is way slower than ByteString hash.
by christophe.jalady＠free.fr 30 Sep '10

30 Sep '10

Just print this two scripts: |s| s := WideString with: (Character value: 16r55E4). [100000 timesRepeat: [s hash]] timeToRun. |s| s := ByteString with: (Character value: 16rE4) with: (Character value: 16rE4) with: (Character value: 16rE4) with: (Character value: 16rE4). [100000 timesRepeat: [s hash]] timeToRun. I've seen that "ByteString>>stringHash:initialHash" use a primitive. Could we have such optimisation for WideString ? Christophe.

5 25

[ANNOUNCE] Squeak Etoys 4.1
by Bert Freudenberg 30 Sep '10

30 Sep '10

Hi everyone, I am proud to announce the new Etoys 4.1, which you can now download from the Squeakland website: http://squeakland.org/download We provide installers for Windows and Macintosh machines. There is also a "to-go" version that you can put on a USB thumb drive to take with you. Linux packages should be available shortly by the distribution of your choice. You can find release notes at http://squeakland.org/download/releaseNotes.jsp This has been a world-wide volunteer effort. Kudos to all contributors! - Bert, for the whole team -

1 0

NativeBoost and Cog. A working protype.
by Igor Stasenko 30 Sep '10

30 Sep '10

Hello, just wanna tell you that i adopted NativeBoost under Cog and have a first running prototype. It still lacks callbacks support, but its already can be used for callouts and to run native code. NativeBoost-CogPlugin does not requires patched for platform-specific code. Just load it into Cog VMMaker image, generate & build vm and you done! Thanks Eliot for providing necessary bits for controlling memory execution protection. The NativeBoost-CogPlugin will have some additional functionality, comparing to its Squeak VM cousin. - it using a primitive failure codes, so when primitive fails , you can determine why and where your native call fails. The primitive error codes still not handled/used by language side, so its a work to do: - a marchalling code can use error codes to report that primitive fails due to coercion error, and it even will tell which exactly argument failed to coerce. - of course, you will be able to add own custom error codes, and handle them as you like to. By default, a plugin could report following problems: "execution of native code is not enabled by plugin" ErrNotEnabled "failed to find a native code for primitive method" ErrNoNativeCodeInMethod "native code generated for different platform" ErrInvalidPlatformId I wanna say thanks to Eliot for providing primitive fail codes in VM. A proper error handling is an important part of infrastructure-level project (such as NativeBoost), since then people who using it, can quickly determine what's wrong with their code. -- Best regards, Igor Stasenko AKA sig.

1 0

Re: [Pharo-project] How to subclass Process and have it used by spawned blocks?
by Eliot Miranda 29 Sep '10

29 Sep '10

Hi Stefan, this sounds a lot like an issue that bit someone in squeak 4.x recently and was due to a bytecode compiler bug that I fixed. I can't find or remember the email associated with this, so if anyone does remember please speak up. Stefan, you might try running this in an updated squeak 4.1 image and compare the bytecodes. If you get different bytecodes then we need to port the compiler fixes from 4.1 trunk to Pharo. HTH Eliot On Wed, Sep 29, 2010 at 10:22 AM, Stefan Marr <pharo(a)stefan-marr.de> wrote: > Further testing reveals a strange behavior in the debugger. > So, I am not sure where the problem is actually caused. > > I added a new local variable block to the method. > block gets assigned aBlock (the parameter). > > If I executed Erlang spawn: [Transcript show: 'foo'], the '1 halt.' is > executed as I mentioned before. > However, the debugger does not allow me to access aBlock, there is a > subscript out of bound exception. > Interestingly, 'block' is accessible without error. > > > If I now actually use 'block' instead of 'aBlock' in the executed block, > then phenomena is reversed. > Thus, the variable which is actually referenced in the code is not > accessible anymore but gets somehow lost. They also get lost if I use both. > > > I would still like to understand what is going on here. > So any remarks are welcome. > > Thanks > Stefan > > > > > spawn: aBlock > "Answer an ErlProcess running the code given in the parameter. The > process isscheduled." > | proc block | > <primitive: 19> "Simulation guard" > block := aBlock. > proc := Process > forContext: > [1 halt. aBlock value. > Processor terminateActive] asContext > priority: Processor activePriority. > proc resume. > ^ proc > > > > On 29 Sep 2010, at 11:21, Stefan Marr wrote: > > > > > On 29 Sep 2010, at 11:01, Igor Stasenko wrote: > > > >> On 29 September 2010 11:11, Stéphane Ducasse <stephane.ducasse(a)inria.fr> > wrote: > >>> no idea but I want to know that too so keep us posted. > >>> > >> Smalltalk specialObjectsArray at: 28. > >> Thats it, Process is a special object, recognized by VM. > >> No other Process (sub)classes can be accepted by it. > > Could you elaborate on that? No other process can be accepted for what? > > Being scheduled, or being executed? > > > > There is also a comment in the comment of Process which suggests that it > should be possible: > > "(If anyone ever makes a subclass of Process, be sure to use > allSubInstances in anyProcessesAbove:.)" > > But even after making the change, that does not seem to be the actual > problem. > > > > > > The process gets execute fine. With a '1 halt.' as the first statement of > the aBlock block I even get a debugger. It only fails on accessing variables > referenced by the closure with an index out of bound error or something > similar. > > > >>> Erlang>>spawn: aBlock > >>> "Answer an ErlProcess running the code given in the parameter. > >>> The process is scheduled." > >>> | proc | > >>> proc := ErlProcess > >>> forContext: > >>> [1 halt. aBlock value. > >>> Processor terminateActive] asContext > >>> priority: Processor activePriority. > >>> proc resume. > >>> ^ proc > > > > > > Thanks and best regards > > Stefan > > > > > > -- > > Stefan Marr > > Software Languages Lab > > Vrije Universiteit Brussel > > Pleinlaan 2 / B-1050 Brussels / Belgium > > http://soft.vub.ac.be/~smarr > > Phone: +32 2 629 2974 > > Fax: +32 2 629 3525 > > > > > > _______________________________________________ > > Pharo-project mailing list > > Pharo-project(a)lists.gforge.inria.fr > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > -- > Stefan Marr > Software Languages Lab > Vrije Universiteit Brussel > Pleinlaan 2 / B-1050 Brussels / Belgium > http://soft.vub.ac.be/~smarr > Phone: +32 2 629 2974 > Fax: +32 2 629 3525 > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

2 1

New Trunk Image: Squeak4.2-10382-alpha
by Casey Ransberger 29 Sep '10

29 Sep '10

Get it here: http://ftp.squeak.org/trunk/Squeak4.2-10382-alpha.zip Also note that I've left the previous build, Squeak4.2-10160-alpha.zip, in place, just in case anyone finds anything terribly wrong with the new one. -- Casey Ransberger

7 18

how to install (cyrillic) fonts on OSX?
by Michal 29 Sep '10

29 Sep '10

hi - I must be missing something obvious: how do I import OSX fonts into squeak (so that I can display eg. cyrillic text)? I am running the latest trunk image, and have tried with and without the "modified bitblt plugin" (at ftp://ftp.smalltalkconsulting.com/experimental/BitBltPlugin.v1.0.0b1.FreeTy…) but the system fonts never show up in worldMenu > appearances > system fonts, and I cannot find a way to import them so that they appear there. Any hints?

2 1

C5-2011 | Submission of papers EXTENDED until October 20, 2010
by Robert Hirschfeld 29 Sep '10

29 Sep '10

*** Submission of papers EXTENDED until October 20, 2010 *** Call for Papers Ninth International Conference on Creating, Connecting and Collaborating through Computing (C5 2011) 18-20 January 2011 Kyoto University, Kyoto, Japan http://www.cm.is.ritsumei.ac.jp/c5-11/ Computers, networks, and other forms of technology are pervasive in our information-based society. Unfortunately, most users of this technology use it for passive consumption of information and entertainment. To evolve into a true knowledge society it is critical that we transform computer-based human activities to engage users in the active process of creating, connecting, and collaborating together. The C5 conference is for anyone interested in the use of computers as tools to develop and enable user-oriented creation, connection, and collaboration processes. Researchers, developers, educators and users come together at C5 to present new and ongoing work and to discuss future directions for creative computing and multimedia environments. We welcome the submission of theoretical and technical papers, practitioner/experience reports, and papers that bridge the gap between theory and practice or that encourage inter- and cross-disciplinary study. === Submissions === C5 invites submissions of full papers in (but not limited to) the following areas: * Technology-enhanced human-computer and human-human interaction * Multimedia authoring environments * New technologies for literature, music and the visual arts * Virtual worlds and immersive environments * Gaming/entertainment platforms and infrastructure * Social networks and social networking * Novel programming paradigms and languages for implementors * Scripting or visual paradigms and languages for end-users * Creating and maintaining online communities * Tools for creating/managing online services/environments * Distributed and collaborative working * Educational environments for classroom, field work and online/distance learning * Technologies for collaborative and self-empowered learning * Social and cultural implications of new technologies Papers should be submitted electronically in PDF format via EasyChair at: http://www.easychair.org/conferences/?conf=c511 Submissions must be written in English (the official language of the conference) and must not exceed eight (8) pages. They should use the IEEE 10-point two-column format, templates for which are available at: http://www.computer.org/portal/web/cscps/home === Proceedings === A preliminary version of the proceedings will be distributed during the conference. The formal version of the proceedings will be published by the Conference Publishing Services (CPS) and sent to authors after the conference. For each accepted paper, at least one of the authors needs to attend the conference and deliver the presentation; otherwise the paper will not be included in the formal proceedings. === Dates === Submission of papers: October 20, 2010 Author notification: November 19, 2010 Camera-ready copy: December 19, 2010 Conference: January 18-20, 2011 === Organization === Honorary Co-Chairs - Alan Kay, Viewpoints Research Institute, USA - Makoto Nagao, National Diet Library, Japan Conference Co-Chairs - Hajime Kita, Kyoto University, Japan - Ian Piumarta, Viewpoints Research Institute, USA/Kyoto University, Japan Program Co-Chairs - Robert Hirschfeld, Hasso Plattner Institute Potsdam, Germany - Serge Stinckwich, Institut de Recherche pour le Développement, Vietnam Publicity and Publication Chair - Hideyuki Takada, Ritsumeikan University, Japan - Conference Secretariat/Local Arrangements - Hitomi Takada, Kyoto University, Japan Program Committee - Sheldon Brown, UC San Diego, USA - Amy Bruckman, Georgia Tech, USA - Alec Dara-Abrams, Kinnexxus, Inc, USA - Benoit Gaudou, University of Toulouse, France - Chigeru Chiba, Tokyo Institute of Technology, Japan - Michael Haupt, Hasso-Plattner-Institut, Germany - Andy Kellens, VUB Brussels, Belgium - Hidehiko Masuhara, The University of Tokyo, Japan - Kim Mens, University, Catholique de Louvain, Belgium - Oscar Nierstrasz, University of Berne, Switzerland - Yoshiki Ohshima, Viewpoints Research Institute, USA - Andreas Schmeil, Palo Alto Research Center, USA - Larry Smarr, UC San Diego, USA - Lance A. Strate, Fordham University, USA - Naoko Tosa, Kyoto University, Japan Advisory Chairs - Benay Dara Abrams, Kinnexxus, Inc., USA - Kim Rose, Viewpoints Research Institute, USA - Katsumi Tanaka, Kyoto University, Japan

1 0

Daily Commit Log
by commits＠source.squeak.org 29 Sep '10

29 Sep '10

Changes to Trunk (http://source.squeak.org/trunk.html) in the last 24 hours: http://lists.squeakfoundation.org/pipermail/packages/2010-September/003792.… Name: Morphic-laza.468 Ancestors: Morphic-nice.467 - changed 41 to 42 - see if this triggers a hudson build =============================================

1 0

← Newer
1
2
3
4
5
6
7
...
41
Older →

Jump to page: