September 2011 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] PetitSmalltalk: now with a self-contained grammar for number literals

by Nicolas Cellier

And there is more: with second algorithm, you can use karatsuba product (or more evolved ones Toom or FFT) and get a significant speed-up, while that has no effect on naive algorithm. I plotted the timings of Integer>>readFrom: for the two algorithms versus number of decimal digits in log log scaled in attached pdf. Nicolas 2011/9/25 StÃ©phane Ducasse <stephane.ducasse(a)inria.fr>: > thanks for the analysis I ejoyed reading it. > > Stef > On Sep 25, 2011, at 4:21 PM, Nicolas Cellier wrote: > >> 2011/9/25 Frank Shearar <frank.shearar(a)gmail.com>: >>> Nicolas, you'd mentioned a log_2 n implementation for number parsing. >>> I think by that you mean the division of digits into two "packets" >>> that are processed and then added? >>> >>> I tried a straight-forward fold (using the * 10 that you said you didn't like!) >>> >>> Time millisecondsToRun: [10000 timesRepeat: >>> ['123456789012345678901234567890' inject: 0 into: [:acc :each | 10 * >>> acc + each digitValue]]] => 818 >>> >>> and what I think you meant: >>> >>> | f | >>> f := 1. "Just to shut the compiler up about the self-reference." >>> f := [:someDigits | | len | >>> Â Â Â Â len := someDigits size. >>> Â Â Â Â (len = 1) >>> Â Â Â Â Â Â Â Â ifTrue: [someDigits first digitValue] >>> Â Â Â Â Â Â Â Â ifFalse: [ | leftHalf rightHalf | >>> Â Â Â Â Â Â Â Â Â Â Â Â leftHalf := someDigits first: len // 2. >>> Â Â Â Â Â Â Â Â Â Â Â Â rightHalf := someDigits allButFirst: len // 2. >>> Â Â Â Â Â Â Â Â Â Â Â Â ((f value: (leftHalf)) * (10 raisedTo: rightHalf size)) + (f value: >>> rightHalf)]]. >>> Time millisecondsToRun: [10000 timesRepeat: [f value: >>> '123456789012345678901234567890']] => 1508 >>> >>> I went with the straight-forward fold because it was simpler and my >>> (quite possibly wrong/inefficient) attempt at a log_2 n version was a >>> lot less readable. >>> >>> I'd greatly appreciate being gently corrected! >>> >>> frank >>> >> >> Hmm, let's see. >> >> Suppose that SmallIntegers are on 3 digits, and Large begins at 4. >> And let's compose a 32 digits number 12345678901234567890123456789012 >> >> If I do the naive loop the first 3 loops (6 ops) give small ints. >> Then the next 29 loops (58 ops) are performed with large ints. >> >> Now, if I perform these ops: >> >> ((1234 * (10**4) + 5678) * (10**8) + (9012 * (10**4) + 3456)) * >> (10**16) + ((7890 * (10**16) + 1234) * (10**8) + (5678 * (10**4) + >> 9012)) >> >> This time, I have 24 loops with small int (48 ops) and 8 loops (16 >> ops) with large ints for evaluating the 4 digits ints. >> Plus 14 operations to assemble these large ints into the final result. >> Plus a number of operations required to evaluate the powers of 10: >> without cache, this is >> >> 10**4 = 10 squared squared (1 small op + 1 large) * 4 times. >> 10**8 = 10 squared squared squared (1 small op + 2 large) * 2 times. >> 10**16 = 10 squared squared squared (1 small op + 3 large) * 1 time. >> >> The total is 55 ops on small ints + 41 ops on large ints. >> So the second algorithm costs more operations on total, but cheaper ones. >> Suppose every operation on SmallInteger costs 1 and LargeInteger costs 10, >> we have a cost of 586 for the first, 465 for the second. >> >> Also, the cost of Large int operations is not constant. >> It is proportional to max(length1,length2) for + and to length1*length2 for *. >> So, we'll consider length(10**n)=n. >> In first case, length2=1 and length1 is varying linearly between 4 and >> 32, thus a mean of 18*2 digit ops per loop * 29 loops. >> >> In the second case, the cost in digit ops is: >> 1) (3*1+4) per loop * 8 loops for forming the 4 digits elementary large ints >> 2) (4*4+8) per loop * 4 loops for forming the 8 digits large ints >> 3) (8*8+16) per loop * 2 loops for forming the 16 digits large ints >> 4) (16*16+32) for the last iteration >> >> Plus the costs of evaluating powers of 10: >> 1) (100 squared) is evaluated 7 times * (2*2) digit ops >> 2) (10000 squared) is evaluated 3 times * (4*4) digit ops >> 3) (100000000 squared) is evaluated 1 times * (8*8) digit ops >> >> grand total is 18*2*29 = 1044 digit ops for the naive algorithm >> For the divide and conquer form, that is ((3*1+4)*8) + ((4*4+8)*4) + >> ((8*8+16)*2) + (16*16+32) + (2*2*7) + (4*4*3) + (8*8) Â = 740 >> >> In your 30 decimal digits example, large integers are formed of 10 >> decimal digits (SmallInteger maxVal + 1) printString size, so we would >> have to translate above count... >> But it's boring, we can lazily bench it: >> >> | stream | >> stream := '123456789012345678901234567890' readStream. >> { >> [stream reset; nextFloat] bench. >> [stream reset. Number readFrom: stream] bench. >> } >> #('15,600 per second.' '23,500 per second.') "Old 4.2 VM" >> #('56,100 per second.' '97,700 per second.') "recent COG VM" >> >> Stream>>nextFloat is a naive loop with almost every operation inlined. >> Number>>readFrom: traverses a bunch of sends before the real >> operations take place. >> >> The overhead equlibrates around 12 decimal digits in non COG VM ! >> That's why it was already faster for scanning a 15 digits Float (non >> counting the fact that nextFloat fails to answer the nearest Float). >> Now, in COG, it equilibrates around 20 digits. >> >> If we want to draw the cost versus log of number of digits: >> >> | gen counts serie cost1 cost2 | >> gen := Generator on: [:g | [g yield: '1234567890' atRandom] repeat]. >> counts := (2 to: 13) collect: [:e | 2 raisedTo: e]. >> serie := counts collect: [:count | >> Â Â Â String withAll: (gen next: count)]. >> cost1 := serie collect: [:e | >> Â Â Â [1000 timesRepeat: [e readStream nextFloat]] timeToRun]. >> cost2 := serie collect: [:e | >> Â Â Â [1000 timesRepeat: [(Number readFrom: e readStream) asFloat]] timeToRun]. >> {counts. cost1. cost2.} >> #("NON COG VM" >> #(4 8 16 32 64 128 256 512 1024 2048 4096 8192) >> #(2 2 25 65 146 304 647 1412 3288 8393 24021 77189) >> #(6 6 21 51 94 177 361 742 1550 3872 8471 22647)) >> >> #("COG VM" >> #(4 8 16 32 64 128 256 512 1024 2048 4096 8192) >> #(0 2 3 20 56 139 334 838 2323 7010 23614 85925) >> #(2 0 4 13 24 53 116 264 626 1646 4552 14191)) >> >> It's not a log_2 cost at the end, but it's already some gain. >> It's possible that above costs are dominated by garbage collection, >> but I don't know how to measure that accurately... >> >> Nicolas >> >>> On 14 September 2011 20:26, Frank Shearar <frank.shearar(a)gmail.com> wrote: >>>> On 3 September 2011 19:35, Nicolas Cellier >>>> <nicolas.cellier.aka.nice(a)gmail.com> wrote: >>>>> 2011/9/3 Frank Shearar <frank.shearar(a)gmail.com>: >>>>>> On 3 September 2011 18:50, Lukas Renggli <renggli(a)gmail.com> wrote: >>>>>>> I think it is a good idea to have the number parser separate, after >>>>>>> all it might also make sense to use it separately. >>>>>>> >>>>>>> It seems that the new Smalltalk grammar is significantly slower. The >>>>>>> benchmark PPSmalltalkClassesTests class>>#benchmark: that uses the >>>>>>> source code of the collection hierarchy and does not especially target >>>>>>> number literals runs 30% slower. >>>>>>> >>>>>>> Also I see that "Number readFrom: ..." is still used within the >>>>>>> grammar. This seems to be a bit strange, no? >>>>>> >>>>>> Yes: it's a double-parse, which is a bit lame. First, we parse the >>>>>> literal with PPSmalltalkNumberParser, which ensures that the thing >>>>>> given to Number class >> #readFrom: is a well-formed token (so, in >>>>>> particular, Squeak's Number doesn't get to see anything other than a >>>>>> well-formed token). >>>>>> >>>>>> It sounds like you're happy with the basic concept, so maybe I should >>>>>> remove the Number class >> #readFrom: stuff, see if I can't remove the >>>>>> performance issues, and resubmit the patch. >>>>>> >>>>>> frank >>>>>> >>>>> >>>>> Yes, a NumberParser is essentially parsing, and this duplication sounds useless. >>>>> The main feature of interest in NumberParser that I consider a >>>>> requirement and should find its equivalence in a PetitNumberParser is: >>>>> - round a decimal representation to nearest Float >>>>> It's simple, just convert a Fraction asFloat in a single final step to >>>>> avoid cumulating round off errors - see >>>>> #makeFloatFromMantissa:exponent:base: >>>>> >>>>> The second feature of interest in NumberParser is the ability to >>>>> parser LargeInteger efficiently by avoiding (10 * largeValue + >>>>> digitValue) loops, and replacing them with a log(n) cost. >>>>> This would be a simple thing to implement in a functional language. >>>> >>>> Hopefully this won't offend your sensibilities too much :). It does, >>>> in fact, use 10* loops - I wrote an experimental "front half * rear >>>> half" recursion, which was slower in my benchmarks. >>>> >>>> This version has the grammar and parser doing no string->number >>>> conversion at all. PPSmalltalkNumberMaker supplies a number of utility >>>> methods designed to stop one from making malformed numbers. It also >>>> supplies a builder interface that the parser uses to construct >>>> numbers. >>>> >>>> frank >>>> >>>>> Nicolas >>>>> >>>>>>> Lukas >>>>>>> >>>>>>> >>>>>>> On 3 September 2011 17:18, Frank Shearar <frank.shearar(a)gmail.com> wrote: >>>>>>>> On 3 September 2011 15:56, Lukas Renggli <renggli(a)gmail.com> wrote: >>>>>>>>> On 3 September 2011 16:51, Frank Shearar <frank.shearar(a)gmail.com> wrote: >>>>>>>>>> Hi Lukas, >>>>>>>>>> >>>>>>>>>> I haven't :) mainly because I'm unsure where to put it - is there >>>>>>>>>> perhaps a PP Inbox, or shall I just post the merged version, or what's >>>>>>>>>> your preference? (How about an mcd between my merge and PP's head?) >>>>>>>>> >>>>>>>>> Just put the .mcz at some public URL (dropbox, squeak source, ...) or >>>>>>>>> attach it to a mail. >>>>>>>> >>>>>>>> Ah, great - here it is. You'll see I've written the grammar as a >>>>>>>> separate class. That was really more to make what I'd done more >>>>>>>> obvious and to minimise the change to PPSmalltalkGrammar, but perhaps >>>>>>>> it's not a bad idea anyway: it's easy to see the number literal >>>>>>>> subgrammar. >>>>>>>> >>>>>>>> frank >>>>>>>> >>>>>>>>> Lukas >>>>>>>>> >>>>>>>>> -- >>>>>>>>> Lukas Renggli >>>>>>>>> www.lukas-renggli.ch >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> Lukas Renggli >>>>>>> www.lukas-renggli.ch >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>> >>>>> >>>> >>> >>> >> > > >

Sept. 26, 2011

Re: [Pharo-project] new Cog VMs available...

by Eliot Miranda

On Fri, Sep 23, 2011 at 10:53 PM, StÃ©phane Ducasse < stephane.ducasse(a)inria.fr> wrote: > Thanks eliot. > > Do you have tests that we could harvest to create a non regession database? > Alas not in this case. The bug manifests itself when a cog code compaction occurs soon after an MNU PIC has been created and the symptom is a fatal crash. So a) it is very difficult to reproduce and b) there would be no neat test failure, there would be a core dump. Yes this is useful for a Jenkins context, but in general I think it better to test things like this with heavy stress tests (and general community usage) rather than trying to produce a specific test. > Stef > > > > ...in http://www.mirandabanda.org/files/Cog/VM/VM.r2495/. These fix the > regression introduced in r2487 in > > introducing faster MNu processing. The bug was the leaking up of an > error code that was misinterpreted as > > a valid target machine code method. Thanks /very/ much to those of you > who tested the 2493 & 2494 VMs. > > With your help this bug was found quickly. I now have reason to hope > that these VMs will be quite stable. > > > > > > Here's the readme: > > CogVM binaries as per VMMaker.oscog-eem.127/r2495. Fix MNU PIC creation > not > > to answer an error code to the interpreter. This is the call 0x00000013 > bug. > > > > again thanks > > -- > > best, > > Eliot > > > > > -- best, Eliot

Sept. 26, 2011

Re: [Pharo-project] google issue 3236

by Norbert Hartl

Am 26.09.2011 um 18:19 schrieb StÃ©phane Ducasse: > sure it will Now I see why it wasn't integrated. The fix is not that easy as it is in the bug entry. > Now did you check the motivation? Of the issue? Of course, to get time information that contains milliseconds and not only seconds. > Was it good? I think yes. The milliSecondClock is nothing reliable. You need to fiddle with it to get a real millisecond value. > Worth to get it in? Yes, I need to be able to measure milliseconds. I could use milliSecondClock but I think it is good for pharo to integrate it into DateAndTime properly. Norbert > On Sep 26, 2011, at 5:24 PM, Norbert Hartl wrote: > >> >> Am 26.09.2011 um 16:40 schrieb Marcus Denker: >> >>> >>> On Sep 26, 2011, at 4:36 PM, Norbert Hartl wrote: >>> >>>> Does anybody know what happened to >>>> >>>> http://code.google.com/p/pharo/issues/detail?id=3236 >>>> >>>> In pharo-1.3 and pharo-1.4 they aren't in. Well, that matches the status of FixedWaitingToBePharoed. Last change by Marcus is from April 7th. >>>> >>> >>> Every issue not closed has yet to be done. >>> >>> So the anwer is: Nothing happend. >>> >> Ok, >> >> there was only a diff so I guess it was more manual work to have it integrated. I'm redoing the stuff on a fresh 1.4 image so it can be easily integrated. I hope this will help getting it in. >> >> Norbert >> >> >> > >

Sept. 26, 2011

Re: [Pharo-project] google issue 3236

by StÃ©phane Ducasse

sure it will Now did you check the motivation? Was it good? Worth to get it in? Stef On Sep 26, 2011, at 5:24 PM, Norbert Hartl wrote: > > Am 26.09.2011 um 16:40 schrieb Marcus Denker: > >> >> On Sep 26, 2011, at 4:36 PM, Norbert Hartl wrote: >> >>> Does anybody know what happened to >>> >>> http://code.google.com/p/pharo/issues/detail?id=3236 >>> >>> In pharo-1.3 and pharo-1.4 they aren't in. Well, that matches the status of FixedWaitingToBePharoed. Last change by Marcus is from April 7th. >>> >> >> Every issue not closed has yet to be done. >> >> So the anwer is: Nothing happend. >> > Ok, > > there was only a diff so I guess it was more manual work to have it integrated. I'm redoing the stuff on a fresh 1.4 image so it can be easily integrated. I hope this will help getting it in. > > Norbert > > >

Sept. 26, 2011

Re: [Pharo-project] google issue 3236

by Norbert Hartl

Am 26.09.2011 um 16:40 schrieb Marcus Denker: > > On Sep 26, 2011, at 4:36 PM, Norbert Hartl wrote: > >> Does anybody know what happened to >> >> http://code.google.com/p/pharo/issues/detail?id=3236 >> >> In pharo-1.3 and pharo-1.4 they aren't in. Well, that matches the status of FixedWaitingToBePharoed. Last change by Marcus is from April 7th. >> > > Every issue not closed has yet to be done. > > So the anwer is: Nothing happend. > Ok, there was only a diff so I guess it was more manual work to have it integrated. I'm redoing the stuff on a fresh 1.4 image so it can be easily integrated. I hope this will help getting it in. Norbert

Sept. 26, 2011

[Pharo-project] [update 1.4] #14167

by Marcus Denker

14167 ----- Issue 4861: Enhance TickDialog http://code.google.com/p/pharo/issues/detail?id=4861 -- Marcus Denker -- http://marcusdenker.de

Sept. 26, 2011

Re: [Pharo-project] google issue 3236

by Marcus Denker

On Sep 26, 2011, at 4:36 PM, Norbert Hartl wrote: > Does anybody know what happened to > > http://code.google.com/p/pharo/issues/detail?id=3236 > > In pharo-1.3 and pharo-1.4 they aren't in. Well, that matches the status of FixedWaitingToBePharoed. Last change by Marcus is from April 7th. > Every issue not closed has yet to be done. So the anwer is: Nothing happend. Marcus -- Marcus Denker -- http://marcusdenker.de

Sept. 26, 2011

[Pharo-project] google issue 3236

by Norbert Hartl

Does anybody know what happened to http://code.google.com/p/pharo/issues/detail?id=3236 In pharo-1.3 and pharo-1.4 they aren't in. Well, that matches the status of FixedWaitingToBePharoed. Last change by Marcus is from April 7th. Norbert

Sept. 26, 2011

[Pharo-project] www.squeakdbx.org temporally moved

by Mariano Martinez Peck

Hi guys. www.squeakdbx.org was temporally moved to http://dbxtalk.smallworks.com.ar/ (thanks SmallWorks for always host our image) We didn't yet update the website to match DBXTalk project, but soon we will do it and when that happens we will register www.dbxtalk.org and shut down http://dbxtalk.smallworks.com.ar/ Cheers DBXTalk team

Sept. 26, 2011

[Pharo-project] [update 1.4] #14165

by Marcus Denker

14165 ----- Issue 4858: Fix some undeclareds in Scriptloader http://code.google.com/p/pharo/issues/detail?id=4858 Issue 4857: Move Finder to Tools package http://code.google.com/p/pharo/issues/detail?id=4857 Issue 4859: Ballon package contains tests http://code.google.com/p/pharo/issues/detail?id=4859 -- Marcus Denker -- http://marcusdenker.de

Sept. 26, 2011