[squeak-dev] Faster fibonacci
lists at fniephaus.com
Sun Apr 28 13:40:20 UTC 2019
On Sun, 28 Apr 2019 at 3:35 pm, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> wrote:
> Le sam. 27 avr. 2019 à 22:49, Nicolas Cellier <
> nicolas.cellier.aka.nice at gmail.com> a écrit :
>> Le sam. 27 avr. 2019 à 20:26, tim Rowledge <tim at rowledge.org> a écrit :
>>> > On 2019-04-27, at 1:43 AM, Nicolas Cellier <
>>> nicolas.cellier.aka.nice at gmail.com> wrote:
>>> > Just ask, it's in the inbox now :)
>>> Good grief. That's some interesting code.
>>> BUT - it isn't in the inbox so far as I can see; the newest Kernel mcz
>>> is http://source.squeak.org/inbox/Kernel-nice.1216.mcz ... oh, wait, I
>>> see you've put an even newer version in trunk. Phew, I thought you might
>>> have been suffering from uploading problems like my NuScratch stuff.
>>> I merged (because I had my fastfib method already) your Kernel-nice.1220
>>> and tried out [4784969 fastDoublingFib asString ] timeToRun . It crashed
>>> because of no Interval>>digitShiftSum: method, which needs to go into
>>> Collections I guess.
>>> Oups! It's in Collection, I forgot to commit it!
>>> [4784969 fastDoublingFib asString ] timeToRun -> 136833mS (on my Pi3+)
>>> [4784969 fastDoublingFib asString ] timeToRun -> 21060mS
>>> Call 6.5X faster.
>>> Assuming we are all confident about the correctness I'd urge making that
>>> the default multiply for large ints. Unless somebody is going to improve
>>> the plugin to assist in making this even faster?
>> The problem is that fastMultiply: just put overhead for every moderately
>> LargeIntegers, which is the most common case, so I hesitate to do it the
>> Implementing divide and conquer in the primitives is also not a pleasant
>> path: divide and conquer often trade speed for space, so it means that we
>> must massively allocate new objects in primitives which is a difficult
>> task. Or resuse some preallocated memory, which gives a horrible taste to
>> these beautiful and simple algorithms. Also it hides those algorithms from
>> our view, make debugging not a pleasure, and make improvment a less
>> enjoyable hobby.
>> What we could do instead, is to make some primitive fail when digitLength
>> is above a certain threshold.
>> That threshold would be a parameter controlled from the image, and a
>> default value of 0 at VM startup could mean no primitive failure making the
>> VM friendly to those image not Karatsuba aware...
> Hmm, after thoughts and experiments, I retract what I said.
> The overhead cost in Squeak is very marginal at least in 64bits VM, so we
> can make #fastMultiply: the default.
> Last time I tried was in VW, where the arrangement of primitives is a bit
Java's BigInteger applies different multiplication algorithms depending on
the values to multiply:
Maybe we could do something similar?
> Seuls les imbéciles ne changent pas d'avis ;)
>>> tim Rowledge; tim at rowledge.org; http://www.rowledge.org/tim
>>> Useful random insult:- Talks to plants on their own level.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Squeak-dev