2011/9/25 Frank Shearar <frank.shearar@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@gmail.com> wrote:
On 3 September 2011 19:35, Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com> wrote:
2011/9/3 Frank Shearar <frank.shearar@gmail.com>:
On 3 September 2011 18:50, Lukas Renggli <renggli@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@gmail.com> wrote:
On 3 September 2011 15:56, Lukas Renggli <renggli@gmail.com> wrote:
On 3 September 2011 16:51, Frank Shearar <frank.shearar@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