Skip to content

Instantly share code, notes, and snippets.

@donaldh
Last active October 1, 2018 15:19
Show Gist options
  • Save donaldh/87441392c21f1190a3d82b385d95cc36 to your computer and use it in GitHub Desktop.
Save donaldh/87441392c21f1190a3d82b385d95cc36 to your computer and use it in GitHub Desktop.

A Twist To The Rational Story

As a followup to brrt’s Curious Benchmark post, I wanted to explore some of the questions that were left unanswered.

A Reminder

This is the benchmark that we started with.

# reciprocal.pl
my $x = 0;
$x += 1/$_ for 1..50_000_000;
print "$x\n";
say "Took {now - BEGIN now} seconds";
18.304749238293297
Took 37.44224442 seconds

I ran this on a Perl 6 with all the nice MoarVM postrelease-opts performance improvements. Even still, it takes its leisurely time to complete the 50M iterations. In the samples below I am going to use a far smaller range, for reasons that will become clear.

Enforcing the Rat Type

Firstly, what happens if we require $x to be a Rat?

my Rat $x = 0.Rat;
$x += 1/$_ for 1..50_000;
say $x;
CATCH { default { .say } }
Type check failed in assignment to $x; expected Rat but got Num (4.437963841730785e0)
  in sub  at EVAL_0 line 4
  in block <unit> at EVAL_0 line 7
  in block <unit> at -e line 1

That’s a surprise! Partway through execution, the Rat must overflow and get promoted to a Num – or is that demoted?

Let’s Try FatRat

Okay, so Rat wasn’t big enough so let’s try a FatRat instead.

my FatRat $x = 0.FatRat;
$x += 1/$_ for 1..50_000;
say $x;
say "Took {now - BEGIN now} seconds";
11.39700394927848263794723724204579293271830505742186834750693578144465183531290496913748510727570775070058686438785753373472816524003689477778418417449218342586002887149134757360258497418431668625047881023241923443605684025701592626446377998766294011642454781091728212201574721432415046263777496948540914639958507450091241565616210098690370499110808738567858930441605773678975300621854275794569259805492076847896257824136227606259608083311775632944471689981909846078048753336947544753235041376792210867534316336359608587161871857798597055555519583606612618969324454220094510617208906186054144002433098900027526628875443569926253281889469311244526731099881809629716366488870204296571934907364565903448441703210061775623159445180430546074238003671788828939795588581849420278384803427057743552336323978179752533086538267918726735101334213611544536109504560343938607417727597869643305220479063875777090858806933853320874828221870304360786296651556740286778637508577406915634652698237985188152827668086907259693198257769563699368257325100905228699895267214996084361795519563787845603768495022019192493939116749921323325065261318310776357786493115895046275736693430031331278351091701698414765858371880629889559569877555499739898083149192356947926517021772251418947236808568105154087725571392196529318733728638123288386793295308180583027233855446520603238343984421733536374255149003435809099540819109947751893497364132734081056718362776207394531439607391418243164533991436116747797931485021349632885309531609895887801693074174469791283964664881778551024712372504778476625207432884862077599040828975864600356477807590194007479989663099556596846181287130594238331732748024212515581435219988069678563942060556523698559844461660883628222086790352656961983096480796268587048236025708130749103679025760105337667432874024152301375646400264599439353058130789490186159699713450038230732807381990836146317184342542464515615797537928044431704513697142312490054429012581368967225154099591941153570622805559133774313386540902168223221384740595168428666045552985758070056248838506028320321298918969440135708239757484479017219955415360425183740787901723167988687444602433649913644519211816423944275673657207918193049120335301526482954680161022766264453348674076769854973383447403661090017722977169915469707714296175098986883552558356212713658530130214515446231323039476924084367464869959747859744904954583569234123637016083103603211402615320916183022334244349275203764693871690743892300829913475421847049443587069954503966956288924852441268806129632250765264140255186286402807483536245991372492976343595172116534101447617908201199277654558640040905299496333861103019970143388090079572632448317771481944602644573464763559125843619522933451163921750677075000204832323237690185492945906556357560482781574625426701770627246033246108863282371096031642354524330671750186519245099938369784790978864446263141189902485687535931950571063083733163313085852312112175815172028103292793871467684956446205828328818709544952000456562191915522353683009980555451352322990207643332661306477139104850363616220208299461238837582125838650534135295786152817364839142852203887972141114465379520808171357977982021917413580239474674391308622740461106272504013210228445088743765311752245080145294035645680616868883049619884594718629675836376792044910855295027129328032653699008651799440701461166934292259325838576414180464170285282741585320913031737214365307592226129680335738267521186056376121931712130816268802890479370802581847440657588952701299985538841054638820598846594644521413707675283997278317462421922650156006794594876879462297625488000168773023215281317727597329901562669268954501990933068761341719485582315864405509406356152534063764698287347268732627511094493371621209775884235788916800899363132042029294750959831318237752963894312372159896249138837226157093354800498686854694875692465037184386256304812124087768155086337119555735388714665990532625553972308110792543436107946959891122994705631830446103604823422997310888461319243112385692393055332277420581486796081519472377123093942437471687125619157650577676808703042376369567567994491810889517763459862953187712052796686627509800755740412220060569808811694235598746254990342473448283762262837550092952047100867726394278452124067102105854212445061473521239268116585804916830975612048314714918017119482432062639800566437337791979082506317410266375722026482902153131100240433362934924561788354328509378711757835779086667519989060894790630039997644788410032666026185542946719919393742191769550322155038187228150583043519130967649547742472715498660584345037616705586696448972855290107113055268501991880233369641312556839034994486234121014120530745474335735467471930914270337338922492941868006244772177589360315359417757428130667659853284801731653635600273622322459353692885215398077819055234769547403456816608950374852567155759331288709067407762394287492268773694850894936304455553236760029174614418930038846531093007830280521444946224936426750872819728742029619056706576019398899663478884959762435429656019089332244111269697829285822753109081449831877592362167024920600005451729898640865389565452135857154038083256040234937583901585749983037632331246285239896400641200856216031502891498650845783089831059977306685386259894222143888925953884622921384885828217294685105368836108379804390472055510441999142780779171743825474315018832100239339671769588659055435792011380935799317509813544570871202699709977079358546111698304804120132272844815433878612051156753733036897476035954292969560405934625911179759272213859652894908546983123396745432989042150338347370230334864425458251960824871822499903224858922695709426328844413465837976005947616034416533044696045359556817954212311259562249867373394261241123438248288595467478413376868957525422381591368648346620151661404624519718731755342440719228425180055133975147235037465893892013114179745112208793761179743165677057746205932526518157850611343244251404845161069369549902322841859359807007661449120546405840828272559602348914318530985507829867204680035040795402492939346448285159212465762987164755289315258236713053690297998556585008657584108044586459247365507459413037838742547715678976850958978465634188923097931934922315811138999540367509192322933254127159964717241368036800576672763356322048209811500198175143302929712178702997634278846463261305105794606003672032873041973443675965974969813473823905078554729061002342949876379278834851940871252447003783816164063167955638824090828667186835133580836681192559376693108672426890889857372140145629125577809563320890376015893658306014138689151872673962941348782914099957808529632234251281233242257467411551883018527632773866891538078256116988316573092725993253950732432376152038206793931040913287360001065901568459745250860324091088639756759023413909020227803146304429507889635024493826483662146487185561803980992254733475784472376518813126938556340778537880464280555045942183964100092236114867026061621665876693080482338318903860549184484579295080291788271339121530200803581965605138787620220467309408508498465549437714396935675754253972131881032253204431207450560196674378373702563627999019879657565066471175999389387734044666157216911915172226261949089417649211551843539649475474005518038126450956624430019233595628106048576012794415305792441460080643598534397842570358674480726745934140492148045061018487905030273299747486593723889535713604247897432853210532576850495672048513306297002351268394572946506052879305121927867382522749191914884734632963984823079288057988824723606305712490219346373741015894853371482314479371001115003226717996359242543272337582570448617745480895689402752936075915518561261416195317418357297896277952066729678803070485373550971308029728696321417415944701287898941230409129630589216927457520031117726363871061782184361874765411244564796001078854060732377557198997391289962030144586792824406645531162648352744528118203716227954604736407223893788772966852247258874028986549172135814379510784482040098535290614212538922203724364919583211719024834654995140174090233553469416450791301429776809804014895238836276182421012143163995883264036952008295344191149147816181708300645766895832810017485252793270113022921063044301320695561366321667523526880148898865612859915758167932947700987056094198562032785768609677316897056131446882421343892357641812682942209570320016551838018189399170797807781229947901138261819708412925127731438146156314270912238735011742876128824535384783129781195975212394901454086023546540478864185696276170734632855819515611665553698785248472389155946710197317086452106978853361054976086882908661157946774066095528831659000190497414827219724971583809170853615595033405589785744775865613524456842978090270859425001920215575409704211135148774336683208256523167082406563909755831697211783497906697104335809374645779497573342635862876182304453697603122889357954281933027312267158651093393153308464397653592774767132458954101355662721672374116691072283642268488321259065809538282437903925644125904300683883310614541716471724826392361216841005404462303384453287962837086802454072901499320431169289272852303878919375327433609584377050726136937588964712072287819796682860072692828449255161688401203535222607495782984685159810559309309212253173631951175507986235266965480172184512407788436076800420841216609450835376142146981134392745352922684987457782717135637017547192019243821223873685070557193724574775868974620973526671435393827670048466371031308823506473605922748695639393635291074562203655411686833086365044825027230788193279893979559959096731882020113778192025473595398197995443603207989203351378084431023894779342793717463259845555265411611178800733867290178512595351841308626448616174445449480604175029059681209897052754035009791474957198626998686502055571033733316725207218702848848714834028275238884032018587664740247569256961374503982622455728545780391695491073572498808564189003215613365386204469507516614637366820703384202355643476291242811666753340913035027823632694921744631239998897375082927154230370031202486588348386683122502163905031080084734497424678553527214955787717141220698473349911754286757100504510727862319563195870616390661471338720000755526395889857052750720053756490247571883465185886160012368848262373205901799649634496657116336545799122395438596438700173850952277247276707496025254611392578979767988734463473596611650823926649134666664740731465888578527003555623993976617494088363748522170558094539148513957057465291359160779447683295807674777213114833996792835078417928879220652895517830606456370022021755574034298416190273889505525847804284909935450824110674789766820615963815649722679706100269780614067798546438096995020175776609788981278036128556942957710664451174711002202463978740431449181279671801127308833583804110377512770594506453322907882823371607643163729286308538854392483523355743670480084953534587114140848736945550621727815997323869020066650984410732819686931704588670680094700819179677228193463608197702295306748850035182264443764259650417135283508905743361762913040973591885371137010076931412173734934570483143622874651718601076006802544657682809954888186102234461639171011700786619508663327395970672251712232363346634402777831593191018229869120355193449916329012298926557795907167374097042131056832664788782329778303517393605654291230776617939074624186238135765583917264263153537105510251807171590142953815442805515931796347159537597491026911480412568203862361617907220425505110545116411514048519194715083625022062894234317528318913264465290246417449856151534210222439887374942326798846393362428367862502684528825580778694863912001922461242813277788790109276857431783670866353841495073062892207528946378367395992267794504948259760653545180617301147926620565020801202534955265553351781123474808345681394466038643313566256980912358745939513790527626751533397420877356414779546621123128680251453637510257803735627042866582000330991694814377851005544300604060914783983372835385000176839424869529109125560760903374405790431962415582569995688300375676704353313169102512458682923971946504718103515524863156774227493067017924778995193036612699306924975099637112779128320515106469391848831363714651936692817190651136428764748289550304524413901513546881517331961623880156342624938933635525348890755594292253188306104677963403052859983365244541275616967205100253388280787616338373677788711833904297275613956224234591921303250752275358709166858802468611073995008362237529774264982020302922050524938642308056156537158592345468013433735567111147506154730273921892871743820276080963075928098073190891028526161113718801513409753311063922385410909917842459093526427761381966609003880447342229236023538841861590307965221440788828321918500255864252987637633238140167162862571546374684725239206996114852885402173486350752715168502363948930648322961956883050858033610965655178526278821387318539758107659293234401780672834683670735957548948762737887125653147702272250788192599849271883837410318819425136148969871759772078242895614566296610807078425254897364942620114575830014732786879234381406310667442978511493065990505382406757352448928550744534514914038890087771131249051698209231636042814282436989104813019136811506315678619612000423456360679110554742593610906285035670354911455199266515397278304196573468338373752793248691997243361808710140646890441390026869634534885539093008067364324089165437119927688262118726194616385784164388471667194133783097240104685517292393582693602682988186751449313927309499765726959883636530124979327559475833534984072344776111465110776328513968327012119437120193220340160284828472785003706347532678953879756123203070153547788593399954445060413920916093876403444854033076276751999198395528746442478198050223599602953236156120662570459716657501865108796169939970378631802999953747930184625088899500218236313179241628066609378316539967036070075887260348024633162257816628546262736643199077818623879713558995227375406513900784180459799551488500693780025116437566242961322475469230962156513352314774068487278897908340411560823231316584678953667817304188597584711045065280538906970439024415484730128715567481093616988754669739342356046167192176271920594014187901204340681302565100296295965850782679614602900791561620044769211372779838294244897181001357000045174849961019953681804195855091758953243059781846898807555708691954457641104433460455196864004317858224277788256097368592868548639971565280944821791565049822800619461555603965571571351770347764779741265171443550673622064499083347278912193770027232205044181518635931922908420564959484515916493912310575577263024832062933150097310654456940475048538219683938984265197399311139870758582960209229572984214859824308907965699590163492014159842850858917020547428596761112803858253167300567932189072689550471998044651355085875235894375291179304024323428894291213419178823958991473474753594555255031843264117771694500432147674782964546762409853746651544187348218674273927761240619502778366575673716049051196918337049090453384497606457486823071288859726696070948047490832895941477925218059545919483653059409910449397504803667680699222070212199112233603744875407585144094242876446821443427564367174239672087539089397863377115792485634814056464638678044911477330769524451570075905510766866371443751452436778708137070784564837832384837494464963480478126593630971539931766019911441106205809359349208583955867659688770217362709349583061072637753704767956788860206565567338767307341847595654420732504113354855918463520981571208723518848389538998445392884511792160451789406463581994608172839019438201318131257236468862053857731229600601331203968474387139126487941949078134819146075878224655306686179488645962109077649294345270388236688801925459034393269639918462720468743768012465251500194007423227820799864403209739621257597168045229082906682689017597922987193442003678851374891809450419898425574321624643291120381558546815922509304145859134567389488436918749128662372509637077597428697507118275770103553886771427542777280464080265811852772865552748971705142196224084520965765443499060883972599967067208873785057616254768245045175768511840838057656479578610669014685076693385594863998065230925225897273427030437245863792745238426103693277322024709492805286250680186233571985411394239003091825964070309579967292408771952817954487513595563656666799882820860269961441396544089329751023082656908917638107285659089721542200931253708573000833173167061045812300817170616200732269819222431128460969602717482201395231845427963999625643901287576483957384534636163423749427448042601302897768908651487565782316946721772126129173284014848611283136708909335972775474731624823738025090698002042424547301231242691267079768448853207449414813381017164719376659871713560166005215721249227070307666223535876913647233402442348272144184441061029546715633282293378342607688746640219693633723077006528876557406888633233142222262060768865085751018390714876080025270097171610409803508457083811798262732004988904694345513297626788404119659149770460396270190906052570391613386017017049024766736084425737876565335042972709314978850104113978779976336409549487239886260180557522375657422470617686569967251443709903649163601434278660189797469566860292147659019273626132402411828710166873532475722745430858559686654351775467864897906238936240229339487376679083265798578264497198395322676610671776499389151467888166233354407827709301946273279580513081992296425752982312669446694309327022667388032748400304056803812578353600103933126102332245905535494964219084415520808270988075832912970955069217796634600894736740353481595498679037491225141810170219189952977900057830104388762356166317033851340478413816507333708728574768645471850056524130881758143532933446843444313821665189328746661954104470773688694394376975148121498028304549805105764082804381743944902569076620495434835541279699627815641133769953452519073353688168438725146919401607933983099910590829944421973722436987174323512982560278472882576280075082263395686260697929287176587449231596052547099780652671600934752304764409340205500288418902243792890237998457353615455707803060704863652998032987255717533596925209863772742258673068169613781637864031179787497993101171222461672161524585125616209867578178771152386281571394776643272088412543322925781708071681795612113844051457285765494378375515097122255142507232109828285106553688266048308523156171254918147301103424145951908451384365828590565993314036683791401130389015692369700972413830474975980321694492767229270882327121637096367885989074006607737339786598406586184755993097426084552424262728083752865927297183551616571612651013437521189443617125479226001759378576820244433994853224733964412696832879312537549987263722256459826496540841943111414565573060042616725611101895021686121866534267849174131576001733481506152140292569221126919125942558900126032481693638677065805099406807377921111785818132689907063914165919593467286175393293515872454668337249707672111964506073374256609328550791942470839191650345987382972973237274407923838607557408799845865424006798459524709410885954617194345889298694194426771746430320032373015036539611088730375142997420687999414790908020824554696801506921222312742303173751051506808504539661845479646002355864657839514241051733686034223855288407988663066085936812316373159077274043342632048607850832486942643500868088580081051018691876588864866136380649433109197913402070937943407871545899674174731222739746980484448732152552326651359332354087463357439012864019868086306598852203213964911543261345195926371694766494275935950964768273637832016466547567178722021664014325605483456324683107297513209835844913552683538041520144074935164772443277103431832930987245680197033734255832523492347494630669313322568386150567238239964816884545996679635704083842214058100823283900869189527409150917695178750261058168771449360404619134935228376000786166821884410673881716943362934317621342858870379717260189094369853277124631490534519937253016592737434295429284847378119145771145798352751476187871803519099322498857967222728663266766014453193455872832121268605622446362308508102079756022214210152017696428452294625585858786932889906112310799243780637921567040442080170531267093169017447194208311534181229609067901402484767307157487664383525426851334835249111325031724540548958580758861500426431647457835251401217734886647375384581114583920867272033796293415635766301403286123659176683203905775372186601951762168183703715892827249379297192984205333636722917253146890207737527893935263547790757406704443961932642778168178277278245718464587933850248421925604646861101963059707188831735741793034169250031037820729656029073854702411046981289125998796083001313565977866831740367077158247241215437229471933235528764351816040797770376829813377326212179908862818418137588072104785033252745593399413360299716654920022660972684891295174237582661300067511256239587592390729077495886818005094787672006561217668947856605919487216441346041749895223596428734195786098851413232477133020319881286637705830012132826010997810702183410574988682291813634874821978536424825831533522361302790031344161183819183449518361492719459133491447017368212705386587515600336416676372792801360028609862543825235384681408347985719579543952665022460615866282332725281523619541593271884051200000317442208903985804217668508563799176999968151775538825593688606747816732352823609149574904765128046209615202081236740186950730684271167206341192106319015025496794755766170223606281954261185114069080910993094893417788373970042475343130398110656868534783392806497366567408855309139927571437349284365375039397207728221882605691056888401754794113534209793831576017601109573482739349883615746023457152419167015926398742499239329813505806838224832608650992726421551596229067346240000846149173244205168114204426365846776797436941341177419627623937005217620919351017425725474521296220333349118088652193888387411292685958
Took 767.158196 seconds

There are two things to note here. Firstly, the precision of the result is far greater. Secondly, it runs like treacle. It’s taken nearly 13 min for just 50K iterations. You’re welcome to try a 500K or more, but the run time deteriorates non-linearly.

Reducing Hyper Fun

Okay, that was interesting. And we’ve uncovered just how slow Rat and FatRat are just now. But questions. What would be a more idiomatic way to write this in Perl 6?

say [+] [1..50_000] »**» -1;
say "Took {now - BEGIN now} seconds";
11.397003949278504
Took 0.32804122 seconds

That was pretty slick. Why not run it for more iterations, I hear you ask.

say [+] [1..500_000] »**» -1;
CATCH { default { .say } }
Too many arguments in flattening array.
  in sub  at EVAL_0 line 3
  in block <unit> at EVAL_0 line 5
  in block <unit> at -e line 1

Sadface. I’m not sure why this flattens before the reduce operator.

It’s a Race

Could we speed things up a bit with a .race? Yes we can!

say [+] [1..50_000].race.map(1 / *);
say "Took {now - BEGIN now} seconds";
11.397003949278504
Took 0.2375065 seconds
@dmaestro
Copy link

The sequence of FatRat's can be generated fairly quickly, but the reduce operation is quite slow when the denominators get large. Trying to race the map portion isn't that effective at speedup. I tried partitioning the FatRat lists (pretty much classic map/reduce) to get about a 6-fold speedup.
FatRat's may be relatively slow, but this benchmark compounds it by doing most of the additions on large-denominator rationals. The precision is pretty incredible, though. :-)

{
    my $p = (1...50_000).classify( * % 8 ).values.map: { .map({ FatRat.new(1, $_) }) };
    say "Map Took ", (now - ENTER now), " seconds";
    {
        my FatRat $x = [+] $p.map( { [+] $_ } );
        say "Reduce Took ", (now - ENTER now), " seconds";
        {
            say $x;
            say "Print Took ", (now - ENTER now), " seconds";
        }
    }
}
# Map Took 0.8337299 seconds
# Reduce Took 250.31103172 seconds
# 11.3970039492784826379472372420457929327183050574218683475069357814446518353129049691374851072757077507...
# Print Took 1.89496162 seconds

Time on the original script with my slow machine (but running 2018.08) was 1585 seconds.

@b2gills
Copy link

b2gills commented Sep 11, 2018

{
    # create the FatRats
    my $a = (1..50_000).race.map: -> $_ --> FatRat:D {FatRat.new: 1, $_};

    # sum them up 1,000 at a time
    my $b = $a.rotor(1_000, :partial).race(:batch(1)).map: *.sum;

    my FatRat $x = $b.sum;

    say "Took ", (now - ENTER now), " seconds";
    {
        say $x;
        say "Took ", (now - ENTER now), " seconds";
    }
}
Took 11.438193 seconds
11.397003949278482637947237242045792932718305057421868347506935781444651835312904969137485107275707750700…
Took 1.7931441 seconds

Note that $a and $b run concurrently, starting when $b.sum is called.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment