[squeak-dev] Faster fibonacci

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Sat Apr 27 20:49:43 UTC 2019

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+)
> Now
> [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?
> tim

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...

> 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...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20190427/850da70a/attachment.html>

More information about the Squeak-dev mailing list