June 2018 - Pharo-dev - lists.pharo.org

Recommendation for password encryption?
by Mariano Martinez Peck Sept. 30, 2022

Sept. 30, 2022

Hi guys. Some time ago I asked about the best way to encrypt a password. Some of the recommendations I got was: 1) Generally for passwords you do not write a decrypt method for security purposes (eg you do not want people to be able to reverse engineer the encrypted password easily) 2) put a little salt 3) There is http://www.squeaksource.com/Cryptography/PasswordHashingFFI 4) I should not decrypt password but instead I should compare both encrypted versions to see if they are equal. My scenario is the following. I need to store database passwords in text files. So I don't want to let them as plain text. And while I understand 4), I think it's a different scenario than mine. I know that some database driver may allow you to directly send the encrypted password. But still...I have another similar scenario in which I have to store a password and then send it (unencrypted)...so I kind of really need a bi-directional encryption. Now..I would try to avoid having an external library + FFI. Any ideas what is the best thing I can do? And how could I solve 1) if I want bidirectional like in my case? Thanks in advance, -- Mariano http://marianopeck.wordpress.com

9 26

Re: [Pharo-project] Parsing and navigating Html
by Paul DeBruicker July 16, 2020

July 16, 2020

On 12/05/2010 06:02 AM, pharo-project-request(a)lists.gforge.inria.fr wrote: > From: St?phane Ducasse<stephane.ducasse(a)inria.fr> > Subject: [Pharo-project] Parsing and navigating Html > To:"Pharo-project(a)lists.gforge.inria.fr Development" > <Pharo-project(a)lists.gforge.inria.fr> > Message-ID:<1C53DFD8-3021-4233-BC83-CE8C1EA8D103(a)inria.fr> > Content-Type: text/plain; charset=us-ascii > > Hi > > I would like extract partial information from HTML pages. > So I started to play and fix HTMLParser. > > Now does anybody know alternatives? > > Second, does anybody develop a lib to query HTML structure as with the XMLSupport package? > > Stef The Soup package on SqueakSource.com works OK.

3 4

Re: [Pharo-dev] [Vm-dev] Image crashing on startup, apparently during GC
by Eliot Miranda June 3, 2019

June 3, 2019

Hi Damien, On Fri, Mar 23, 2018 at 12:38 PM, Damien Pollet <damien.pollet(a)gmail.com> wrote: > > Here are the files (image and various outputs). Running with --leakcheck > does mention a few object leaks (see output.txt); > Indeed the image is corrupt at start-up. See below. > I'm not sure where to get or how to build an assert VM. > When you build a phar. VM under build.macos64x64/pharo.cog.spur using the mvm script (mvm -A) you produce an assert VM in PharoAssert.app. > I also realized the VM I had was from this summer (the one that comes with > a 70 image with zeroconf). The output files I include were produced by the > VM at get.pharo.org/64/vmLatest70 > > https://www.dropbox.com/s/y8yqjuzd9nsvy1u/clap-broken.tar.gz?dl=0 > > On 20 March 2018 at 18:17, Eliot Miranda <eliot.miranda(a)gmail.com> wrote: > >> >> Hi Damien, >> >> On Tue, Mar 20, 2018 at 3:12 AM, Damien Pollet <damien.pollet(a)gmail.com> >> wrote: >> >>> >>> Hi, I have a Pharo image that crashes the VM on startup. The crash >>> report below seems to incriminate GC. Should I make it available somewhere >>> online? What's most convenient? >>> >> >> Don't care. Anywhere it can be downloaded from. Also, try running with >> -leakcheck 15, preferably in an assert VM and see if that gets you >> additional information. >> >> >>> >>> Process: Pharo [64892] >>> Path: /Users/USER/*/Pharo.app/Contents/MacOS/Pharo >>> Identifier: org.pharo.Pharo >>> Version: 5.0.201708271955 (5.0.201708271955) >>> >> Right. This VM is prior to the bug fixes in VMMaker.oscog-eem.2320: Spur: Fix a bad bug in SpurPlnningCompactor. unmarkObjectsFromFirstFreeObject, used when the compactor requires more than one pass due to insufficient savedFirstFieldsSpace, expects the corpse of a moved object to be unmarked, but copyAndUnmarkObject:to:bytes:firstField: only unmarked the target. Unmarking the corpse before the copy unmarks both. This fixes a crash with ReleaseBuilder class>>saveAsNewRelease when non-use of cacheDuring: creates lots of files, enough to push the system into the multi-pass regime. Pharo urgently needs to upgrade the VM to one more up to date than 2017 08 27 (in fact more up-to-date than opensmalltalk/vm commit 0fe1e1ea108e53501a0e728736048062c83a66ce, Fri Jan 19 13:17:57 2018 -0800). The bug that VMMaker.oscog-eem.2320 fixes can result in image corruption in large images, and can occur (as it has here) at start-up, causing one's work to be irretrievably lost. > Code Type: X86-64 (Native) >>> Parent Process: ??? [64888] >>> Responsible: Pharo [64892] >>> User ID: 501 >>> >>> Date/Time: 2018-03-19 20:27:03.906 +0100 >>> OS Version: Mac OS X 10.13.3 (17D102) >>> Report Version: 12 >>> Anonymous UUID: 6D022236-78DD-6676-117F-EADA56D5D1BE >>> >>> Sleep/Wake UUID: AC9E4E55-3CDB-4B4F-A6B4-51ACB1177154 >>> >>> Time Awake Since Boot: 28000 seconds >>> Time Since Wake: 6500 seconds >>> >>> System Integrity Protection: enabled >>> >>> Crashed Thread: 0 Dispatch queue: com.apple.main-thread >>> >>> Exception Type: EXC_BAD_ACCESS (SIGABRT) >>> Exception Codes: KERN_INVALID_ADDRESS at 0x000000012b67c0b0 >>> Exception Note: EXC_CORPSE_NOTIFY >>> >>> VM Regions Near 0x12b67c0b0: >>> VM_ALLOCATE 000000011adfc000-00000001259fc000 [172.0M] >>> rw-/rwx SM=PRV >>> --> >>> STACK GUARD 0000700005613000-0000700005614000 [ 4K] >>> ---/rwx SM=NUL stack guard for thread 1 >>> >>> Application Specific Information: >>> abort() called >>> >>> Thread 0 Crashed:: Dispatch queue: com.apple.main-thread >>> 0 libsystem_kernel.dylib 0x00007fff53fbde3e __pthread_kill + 10 >>> 1 libsystem_pthread.dylib 0x00007fff540fc150 pthread_kill + 333 >>> 2 libsystem_c.dylib 0x00007fff53f1a312 abort + 127 >>> 3 org.pharo.Pharo 0x0000000104ed8997 sigsegv + 190 >>> 4 libsystem_platform.dylib 0x00007fff540eff5a _sigtramp + 26 >>> 5 ??? 000000000000000000 0 + 0 >>> 6 org.pharo.Pharo 0x0000000104e73558 markObjects + 464 >>> 7 org.pharo.Pharo 0x0000000104e72d40 fullGC + 72 >>> 8 org.pharo.Pharo 0x0000000104e92dea primitiveFullGC + >>> 45 >>> 9 org.pharo.Pharo 0x0000000104e52425 interpret + 26715 >>> 10 org.pharo.Pharo 0x0000000104e5c7f6 >>> enterSmalltalkExecutiveImplementation + 152 >>> 11 org.pharo.Pharo 0x0000000104e4be6c interpret + 674 >>> 12 org.pharo.Pharo 0x0000000104ed9cc1 >>> -[sqSqueakMainApplication runSqueak] + 394 >>> 13 com.apple.Foundation 0x00007fff2e6d696c >>> __NSFirePerformWithOrder + 360 >>> 14 com.apple.CoreFoundation 0x00007fff2c579127 >>> __CFRUNLOOP_IS_CALLING_OUT_TO_AN_OBSERVER_CALLBACK_FUNCTION__ + 23 >>> 15 com.apple.CoreFoundation 0x00007fff2c57904f >>> __CFRunLoopDoObservers + 527 >>> 16 com.apple.CoreFoundation 0x00007fff2c55b6a8 __CFRunLoopRun + >>> 1240 >>> 17 com.apple.CoreFoundation 0x00007fff2c55af43 >>> CFRunLoopRunSpecific + 483 >>> 18 com.apple.HIToolbox 0x00007fff2b872e26 >>> RunCurrentEventLoopInMode + 286 >>> 19 com.apple.HIToolbox 0x00007fff2b872a9f >>> ReceiveNextEventCommon + 366 >>> 20 com.apple.HIToolbox 0x00007fff2b872914 >>> _BlockUntilNextEventMatchingListInModeWithFilter + 64 >>> 21 com.apple.AppKit 0x00007fff29b3df5f _DPSNextEvent + >>> 2085 >>> 22 com.apple.AppKit 0x00007fff2a2d3b4c >>> -[NSApplication(NSEvent) _nextEventMatchingEventMask:untilDate:inMode:dequeue:] >>> + 3044 >>> 23 com.apple.AppKit 0x00007fff29b32d6d -[NSApplication >>> run] + 764 >>> 24 com.apple.AppKit 0x00007fff29b01f1a NSApplicationMain >>> + 804 >>> >>> -- >>> Damien Pollet >>> type less, do more [ | ] http://people.untyped.org/damien.pollet >>> >>> >> >> >> -- >> _,,,^..^,,,_ >> best, Eliot >> >> > > > -- > Damien Pollet > type less, do more [ | ] http://people.untyped.org/damien.pollet > > -- _,,,^..^,,,_ best, Eliot

9 26

Recent Pharo 6.1 OSX shows lots of "Error: unsupported compressor 8 on command line"
by Tim Mackinnon April 19, 2019

April 19, 2019

I noticed that recent Pharo 6.1 zero conf downloads show lots of these errors when you run the image in the terminal. Previous versions didnât do this - is this something to do with the latest vm upgrade? ./pharo-ui PagerDuty.image /BuildRoot/Library/Caches/com.apple.xbs/Sources/AppleFSCompression/AppleFSCompression-96.30.2/Common/ChunkCompression.cpp:50: Error: unsupported compressor 8 /BuildRoot/Library/Caches/com.apple.xbs/Sources/AppleFSCompression/AppleFSCompression-96.30.2/Libraries/CompressData/CompressData.c:353: Error: Unknown compression scheme encountered for file '/System/Library/CoreServices/CoreTypes.bundle/Contents/Resources/Exceptions.plist' /BuildRoot/Library/Caches/com.apple.xbs/Sources/AppleFSCompression/AppleFSCompression-96.30.2/Common/ChunkCompression.cpp:50: Error: unsupported compressor 8 /BuildRoot/Library/Caches/com.apple.xbs/Sources/AppleFSCompression/AppleFSCompression-96.30.2/Libraries/CompressData/CompressData.c:353: Error: Unknown compression scheme encountered for file '/System/Library/CoreServices/CoreTypes.bundle/Contents/Library/AppExceptions.bundle/Exceptions.plist' Tim

6 6

About the infinite debugger
by Guillermo Polito Aug. 8, 2018

Aug. 8, 2018

Hi all, during today's sprint we have been working with lots of people on the infinite debugger problem (https://pharo.fogbugz.com/f/cases/22085/) We have checked the emails sent in the latest month. Then, together with Quentin, Pablo, Pavel, Yoan we have been discussing and testing hypothesis all day. We have been also comparing the debuggers code between pharo 3/4 (where the bug was is present) and pharo 7, but this was not necessarily straight forward as the code is not the same and there is no easy diff... AAAAND, we have found that the problem may come from a wrong pragma marker. Just removing that pragma gives us back the same behaviour as in Pharo 3/4. :D https://github.com/pharo-project/pharo/pull/1621 I know that the exception handling/debugging has been modified several times in the latest years (some refactorings, hiding contexts...), we unfortunately don't have tests for it, so I'd like some more pair of eyes on it. Ben, Martin could you take a look? Thanks all for the fish, Guille

14 27

[PROPOSAL] Put the WorldMenu in a Menu bar
by Cyril Ferlicot D. July 22, 2018

July 22, 2018

Hi everyone, With Guille we are trying to improve the usability of the WorldMenu. The world menu is by large un-intuitive: - Users are not used to click on a background to open a menu - For those that "get it" they try to do it with right click (Of course, it looks like a context menu!) and that does not work Since some decades now the default way to display a menu in applications is to have a bar at the top of the windows. We should change that world menu by a menu bar like any application. That will lower the entrance barrier to new users, at the cost of having to move the cursor to the top to look for the menu... You can find here a PR that add the WorldMenu as a top bar to Pharo and reorganize it: https://github.com/pharo-project/pharo/pull/1470 See screen in the PR. It still have room for improvements but we think it's stable enough for integration in Pharo. Missing features: - What do we do when Pharo is not wide enough? - What to do when a window is dragged behind? - Make it parametrizable to allow users to build a bar with their own menu builder - Add shortcuts to open the menu windows like (maybe) - Update it when we change the font size (this is a general Pharo problem) Feedback is welcome. Related issue: https://pharo.fogbugz.com/f/cases/22038/Replace-World-Menu-by-Menu-bar Guille & Cyril -- Cyril Ferlicot https://ferlicot.fr

12 26

Promote new Pharo 7 VM?
by Alistair Grant July 4, 2018

July 4, 2018

Hi Esteban, Would you consider promoting a new Pharo 7 VM? 140ff02 should finally solve an issue I've had with time zones and DST on Windows in the FileAttributesPlugin. Testing I've done on this VM: - Loaded up and used my normal dev environment. - Run the full automated test suite on: -- Linux 64 bit -- Linux 32 bit -- Win 32 bit In each case the set of failures in my environment roughly aligns with the current stable VM and the proposed one. I guess if anyone else has any objections they'll reply to this. :-) Of course, if you've got any questions or concerns, please let me know. In case it is useful for anyone, download links are: Linux 64 bit: http://files.pharo.org/vm/pharo-spur64/linux/pharo-linux-x86_64threaded-201… Linux 32 bit: http://files.pharo.org/vm/pharo-spur32/linux/pharo-linux-i386threaded-20180… Mac 64 bit: - http://files.pharo.org/vm/pharo-spur64/mac/pharo-mac-x86_64-201806171702-14… - http://files.pharo.org/vm/pharo-spur64/mac/pharo-mac-x86_64-201806171702-14… Mac 32 bit: - http://files.pharo.org/vm/pharo-spur32/mac/pharo-mac-i386-201806171702-140f… - http://files.pharo.org/vm/pharo-spur32/mac/pharo-mac-i386-201806171702-140f… Win 32 bit: http://files.pharo.org/vm/pharo-spur32/win/pharo-win-i386-201806171702-140f… Thanks! Alistair

2 6

[ann] gt documenter
by Tudor Girba July 2, 2018

July 2, 2018

Hi, We are happy to announce a new leap of GToolkit Documenter, the tool for manipulating live documents directly in the development environment: https://github.com/feenkcom/gtoolkit-documenter Documenter is part of the second generation GToolkit project, it is based on Bloc and works with the latest Pillar. It is mainly developed by Juraj Kubelka. Attached you can see a preview of how documents look like: At its core it offers a live editor for manipulating Pillar documents. The interaction happens seamlessly directly in the text editor, and it can be combined with different types of previews to serve several classes of use cases: â¢ code documentation â¢ tutorials â¢ interactive data notebook Code documentation ---- Documenter complements the GToolkit Examples engine to redefine code documentation. When practicing example-driven development, examples get written as part of the typical development. Once examples exist, they can be quickly put together in a document to form documentation. For example, the linked picture shows the comment of a class containing a visual explanation: https://twitter.com/feenkcom/status/973899862482866176 You can see a live example of documentation by inspecting the following snippet: GtDocumenter editorForText: BrToggleExamples comment. Tutorials: ---- Documenter offers a new experience of writing tutorials for Pharo by enabling the creation and embedding of Epicea change sessions directly in the document. For example, take a look at the following animation: https://twitter.com/feenkcom/status/999975333972541440 The document shows a method on top, and a change preview at the bottom showing both the code and the associated diff to the state from the image. Applying the change updates both the change view (no more diff), and method preview. This speeds up significantly the process of going through a tutorial. Furthermore, given that now the document shows the diff to the current image, the reader can safely explore alternative scenario and come back to the tutorial at any time without losing the overview. The size of the preview can also be adjusted live: https://twitter.com/feenkcom/status/1001152789874167808 https://twitter.com/feenkcom/status/1001407762285375490 You can see a live tutorial by inspecting: IceRepository repositoriesLocation / 'feenkcom'/ 'gtoolkit-examples' / 'doc' / 'tutorial' / 'examples-tutorial.pillarâ. Interactive data notebook: ---- A Documenter document can also be used as an interactive notebook. Internally it essentially acts as a playground: â¢ it supports defining variables in code snippets, and â¢ the execution of code shows an embedded inspector. For example: https://twitter.com/feenkcom/status/996310432225820672 https://twitter.com/feenkcom/status/1002851190475026432 An example, can be seen by inspecting: IceRepository repositoriesLocation / 'feenkcom'/ 'gtoolkit' / 'doc' / 'gtoolkit' / 'gtoolkit.pillar'. As always, please do let us know what you think. Enjoy, The feenk team -- www.tudorgirba.com www.feenk.com "If you can't say why something is relevant, it probably isn't."

3 3

Re: [Pharo-dev] [squeak-dev] Why do we have SmallDictionary?
by Chris Muller June 30, 2018

June 30, 2018

>> This discussion has limited its context to comparing *in-memory* >> Dictionary implementations, where open-addressing has an advantage. >> Using Magma reveals another context where chained Dictionary's can have >> some advantages: When they're large, persistent, and shared in a multi-user >> system -- e.g., when grow rehashing is not an option. > > > B-trees were designed for that use case. > If growing is not an option, then your dictionary's performance will degrade > as its size increases, won't it? Yes, but only logarithmically. But I was not making a performance-based comparison, only a possibility-based one. >> Not only do chained Dictionary's make that scenario possible, they improve >> the concurrency -- different users can add/change/remove from the Dictionary >> as long as they occur at different keys. With regular >> Dictionary's, concurrency guarantees a commit conflict. > > If you created a new, larger dictionary on grow and lazily copied the > entries from the smaller to the larger upon access, then I think you could > use open addressing hash tables. That's an interesting idea, but what if it grows beyond "the larger" again while still many entries in the smaller? Add a third which is doubled in size again? That sounds like it starts to intrude into the efficiency of open-addressing (both computation and space), but the idea still sparks some interesting design thoughts in my head.. > Also, I don't see the concurrency issue with open addressing, because as > long as different users modify different chains, the case of concurrency is > the same as what you described, isn't it? Magma has a class called "MagmaPreallocatedDictionary" which does exactly this. It's like a regular Dictionary, except for its internal 'array', it utilizes a MagmaArray, which is just like an Array except large and persistent and can grow in place (so able to maintain its identity). However, this alone was not enough to implement your proposal because of the 'tally'. Clients would each be trying to propose their specific value for that variable = conflict. Thankfully, Magma has yet another special class called MagmaCounter which fits that role beautifully. Designed for multi-user systems, a MagmaCounter provides a concurrent counter. Instances start at a #value of 0, after which any number of sessions may simultaneously increment or decrement (even by more than 1), but no one can actually hard set its value. Best, Chris

1 0

Re: [Pharo-dev] [squeak-dev] Why do we have SmallDictionary?
by Chris Muller June 30, 2018

June 30, 2018

This discussion has limited its context to comparing *in-memory* Dictionary implementations, where open-addressing has an advantage. Using Magma reveals another context where chained Dictionary's can have some advantages: When they're large, persistent, and shared in a multi-user system -- e.g., when grow rehashing is not an option. Not only do chained Dictionary's make that scenario possible, they improve the concurrency -- different users can add/change/remove from the Dictionary as long as they occur at different keys. With regular Dictionary's, concurrency guarantees a commit conflict. - Chris On Fri, Jun 29, 2018 at 2:56 PM, Peter Crowther <peter(a)ozzard.org> wrote: > In an environment with garbage collection, it's worth considering the > overhead of one's representation on the memory allocator and the garbage > collector. Open addressing adds objects - the exact number of these varies > - and hence adds GC overhead (= paying extra cycles for the life of the > dictionary even if it never changes). Each object also has some bytes of > overhead for headers, so chaining becomes less efficient as collisions > occur due to extra object allocations. > > Also, modern processors and memory systems are very good at reading > forward in memory, as there's often a wide memory bus (and sometimes other > optimisations). This means it's often quick to read the next entry as it's > already been pulled in due to adjacency. By contrast, chaining puts > collisions all over memory, reducing adjacency and increasing the bandwidth > required to memory. > > I'm unconvinced that chaining dictionaries are sensible in modern > languages with garbage collection on modern architectures where bandwidth > to memory, and cache space, are both scarce resources. The days of memory > being truly random-access are long gone, and too few programmers realise > the impact that can have. > > Cheers, > > - Peter > > > On 29 June 2018 at 08:27, ClÃ©ment Bera <bera.clement(a)gmail.com> wrote: > >> Hum, about dictionary implementations, I've just found this [1]: >> Open addressing vs. chaining >> *Chaining* *Open addressing* >> *Collision resolution* Using external data structure Using hash table >> itself >> *Memory waste* Pointer size overhead per entry (storing list heads in >> the table) No overhead 1 >> *Performance dependence on table's load factor* Directly proportional Proportional >> to (loadFactor) / (1 - loadFactor) >> *Allow to store more items, than hash table size* Yes No. Moreover, it's >> recommended to keep table's load factor below 0.7 >> *Hash function requirements* Uniform distribution Uniform distribution, >> should avoid clustering >> *Handle removals* Removals are ok Removals clog the hash table with >> "DELETED" entries >> *Implementation* Simple Correct implementation of open addressing based >> hash table is quite tricky1 Hash tables with chaining can work >> efficiently even with load factor more than 1. At the same time, tables >> based on open addressing scheme require load factor not to exceed 0.7 to be >> efficient. Hence, 30% of slots remain empty, which leads to obvious memory >> waste. >> >> Do you guys agree with this? >> >> Their open addressing implementation is slightly different from the >> Smalltalk one (they have deleted entries upon removal while we fix >> collisions, at least in Pharo 6). >> Their chaining implementation does not use balanced binary tree when a >> bucket becomes large like Java's implementation. >> >> I don't really understand why an open addressing implementation is >> trickier to implement, in high level languages such as Smalltalk I may >> agree that it might be easier to implement chaining, but in low level >> language such as in the VM, IMO open addressing is easier since you've got >> only one large chunk of memory to manage. Maybe it's because of hash >> collisions, having good hash and good hash collection size >> (See HashTableSizes) is not that easy. >> >> I'm curious because I do more and more bare metal programming and I end >> up having to implement this kind of things myself, I've always implemented >> naive open addressing up until now without really understanding details. >> >> [1] http://www.algolist.net/Data_structures/Hash_table/Open_addressing >> >> On Sat, Jun 16, 2018 at 8:49 PM, Max Leske <maxleske(a)gmail.com> wrote: >> >>> >>> >>> On 8 Jun 2018, at 09:48, StÃ©phane Rollandin wrote: >>> >>> FWIW it seems there is no SmallDictionary in Squeak. >>>> >>> >>> Oh... Thanks StÃ©f, I wasn't aware of that. >>> >>> >>> >>> On 8 June 2018, at 15:13, John Brant wrote: >>> >>> Is anyone aware of a reason for hanging on to SmallDictionary? I'm also >>>>>> curious to know how SmallDictionary came to be. There must have been some >>>>>> advantage over Dictionary at some point in the past. >>>>>> >>>>> >>>>> It came from RBâ¦ the idea was that there are (in the Refactoring >>>>> engine) a lot of very small dictionaries with <10 elements. >>>>> The idea is that for such dictionaries, the overhead of hashing was >>>>> higher than just linear search. >>>>> >>>> >>>> I created its ancestor in VW some 20+ years ago (as RBSmallDictionary). >>>> It was used when doing pattern matching. When it performs a pattern >>>> match against an AST, it puts the potential value of the pattern >>>> variable in the dictionary. If the value is used later in the pattern, >>>> then we can get the previous value and make sure that we have an >>>> equivalent AST. This allows you to write patterns like: >>>> >>>> `@a = `@a >>>> >>>> to find where someone has the same expression on both sides of the #= >>>> message. Since most patterns have very few pattern variables, these >>>> dictionaries won't hold many entries. Furthermore, we are likely to >>>> abort the match when we have 0 entries. >>>> >>>> The original RBSmallDictionary had an #empty method that "emptied" the >>>> dictionary without actually removing any elements -- it just set the >>>> size to 0. In a general dictionary this would lead to memory leaks since >>>> the previous values are still held by the dictionary. However, these >>>> dictionaries were only used during the matching process and went away >>>> after the process completed. >>>> >>>> Anyway, at the time when we converted our pattern matching code from >>>> using the VW parser with our pattern matching extensions to use the new >>>> RB parser with pattern matching, the time to run Smalllint on the image >>>> was cut in half even though our parser was quite a bit slower than the >>>> VW parser. I don't remember everything that was done, but I think that >>>> most of the speedup came from having special pattern AST nodes and the >>>> small dictionary. >>>> >>>> >>>> John Brant >>>> >>> >>> >>> Very interesting! Thanks John! >>> >>> As Marcus has mentioned before in this thread, it would make a lot of >>> sense to run benchmarks again. Actually, I think it would be nice to have a >>> benchmark suite for these cases, that would let us monitor the performance >>> and ensure that changes to the codebase don't have a deteriorative effect. >>> I'm not saying that it would be easy to make this happen, writing proper >>> benchmarks is hard (for me especially, as it seems, given my utter failure >>> to think of the edge cases before starting this thread). Such a suite might >>> also prevent these sorts of questions on the mailing list in the future, or >>> at least might make it easier to answer them. >>> >>> >>> >>> >>> On 8 June 2018, at 13:01, Andres Valloud wrote: >>> >>> In addition, open addressing with linear probing has superior cache line >>>> read behavior (no indirection / random traversal, and if the first probe >>>> misses the second one was likely cached by the first one). >>>> >>> >>> >>> Ah, nice catch! Although that would require frequent access to the >>> dictionary / repeated access to the same items to have an effect, wouldn't >>> it? >>> >>> >>> >>> On 8 Jun 2018, at 10:01, ClÃ©ment Bera wrote: >>> >>> Hi Max, >>>> >>>> Theoretically, for a small number of elements, usually somewhere >>>> between 3 >>>> and 30 depending on implementations, a linear search is faster than a >>>> hash >>>> search, especially in the Pharo dictionary hash search implementation. >>>> >>>> Efficient dictionary implementations are usually bucket-based. The >>>> dictionary holds a certain number of buckets, and based on the key hash, >>>> the bucket where the key value is present is determined. Small buckets >>>> are >>>> linear (arrays or linked list). Large buckets are typically balanced >>>> binary >>>> trees (red-black trees typically). Under a certain number of elements >>>> there >>>> is a single bucket, which means a linear search is performed, as for the >>>> SmallDictionary. When it grows the dictionary search becomes a >>>> combination >>>> between a hash search and a linear or tree search. >>>> >>>> Pharo dictionary search is first hash-based, then all the buckets are >>>> represented next to each other in the same arrays and a linear search is >>>> performed there, leading to many collisions and slower search time >>>> (especially when the element is not found), sometimes the code searches >>>> over multiple buckets because the dictionary is too full or there are >>>> too >>>> many near-collisions. The memory consumption is competitive with the >>>> advanced implementations though (precise measurements would need to be >>>> made). >>>> >>>> Method dictionaries are represented differently to optimize the look-up >>>> logic. >>>> >>>> If you want to improve things and have one dictionary implementation >>>> instead of two, implement or look for a bucket based dictionary and put >>>> it >>>> in the base image instead of Dictionary. This is quite some work since >>>> there are many APIs to port. You can look at the Pinnochio >>>> implementation, >>>> it's quite good but they've not implemented large buckets. >>>> >>> >>> Thanks for the detailed explanations ClÃ©ment and Levente. I'll probably >>> not add a new dictionary implementation ;) >>> >>> >>> >>>> >>>> >>>> On Fri, Jun 8, 2018 at 8:46 AM, Max Leske <maxleske(a)gmail.com> wrote: >>>> >>>> Hi, >>>>> >>>>> I was messing around with SmallDictionary when I suddenly realised >>>>> that I >>>>> can't find a single reason to use it over a normal Dictionary. While >>>>> its >>>>> name and class comment imply that it is somehow an optimised >>>>> Dictionary, I >>>>> don't see any measurement where that actually holds up. The following >>>>> was >>>>> run in a Pharo 7 image on a recent VM (see below): >>>>> >>>>> | d | >>>>> d := SmallDictionary new. >>>>> d sizeInMemory. "24" >>>>> [100000 timesRepeat: [ >>>>> 1 to: 100 do: [ :i | d at:i put: i] ] ] timeToRun. >>>>> "0:00:00:05.226" >>>>> >>>>> [100000 timesRepeat: [ >>>>> d at: 48 ifAbsent: [] ] ] timeToRun. "0:00:00:00.041" >>>>> >>>>> >>>>> >>>>> | d | >>>>> d := Dictionary new. >>>>> d sizeInMemory. "16" >>>>> [100000 timesRepeat: [ >>>>> 1 to: 100 do: [ :i | d at:i put: i] ] ] timeToRun. >>>>> "0:00:00:00.385" >>>>> [100000 timesRepeat: [ >>>>> d at: 48 ifAbsent: [] ] ] timeToRun. "0:00:00:00.006" >>>>> >>>>> >>>>> As you can see, SmallDictionary is 8 bytes larger per instance and >>>>> significantly faster while reading and writing (I know that this isn't >>>>> a >>>>> good benchmark but it suffices to make my point). >>>>> >>>>> >>>>> Is anyone aware of a reason for hanging on to SmallDictionary? I'm also >>>>> curious to know how SmallDictionary came to be. There must have been >>>>> some >>>>> advantage over Dictionary at some point in the past. >>>>> >>>>> >>>>> Cheers, >>>>> Max >>>>> >>>>> >>>>> >>>>> >>>>> >>>>> Image version: Pharo 7.0 >>>>> Build information: Pharo-7.0+alpha.build.961.sha. >>>>> a69e72a97136bc3f93831584b6efa2b1703deb84 (32 Bit) >>>>> >>>>> VM version: CoInterpreter VMMaker.oscog- nice.2281 uuid: >>>>> 4beeaee7-567e-1a4b-b0fb-bd95ce302516 Nov 27 2017 >>>>> StackToRegisterMappingCogit VMMaker.oscog-nice.2283 uuid: >>>>> 2d20324d-a2ab-48d6-b0f6-9fc3d66899da Nov 27 2017 >>>>> VM: 201711262336 https://github.com/OpenSmalltalk/opensmalltalk-vm.git >>>>> $ >>>>> Date: Mon Nov 27 00:36:29 2017 +0100 $ Plugins: 201711262336 >>>>> https://github.com/OpenSmalltalk/opensmalltalk-vm.git $ >>>>> >>>>> OS: macOS 10.13.5 >>>>> Machine: MacBook Pro (13-inch, 2016, Four Thunderbolt 3 Ports) >>>>> >>>>> >>>>> >>>> >>>> -- >>>> ClÃ©ment BÃ©ra >>>> https://clementbera.github.io/ >>>> https://clementbera.wordpress.com/ >>>> >>> >>> >>> >>> >> >> >> -- >> ClÃ©ment BÃ©ra >> https://clementbera.github.io/ >> https://clementbera.wordpress.com/ >> >> >> >> > > > >

1 0