Skip to content

Instantly share code, notes, and snippets.

@amalloy

amalloy/core-using-array.hs

Last active December 1, 2021 22:39
Show Gist options
  • Save amalloy/48a9141b10812cd63b31ab3b2ae3a7d8 to your computer and use it in GitHub Desktop.
Save amalloy/48a9141b10812cd63b31ab3b2ae3a7d8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
core-using-array.hs
-- seems fairly straightforward: wnumIncreasingDiffsOfSize is some loop with y_a2nf as iterator index.
-- it checks whether the loop should stop; if not, it calls get a couple times, compares the results, and updates sum
-- RHS size: {terms: 101, types: 31, coercions: 0, joins: 1/5}
$wnumIncreasingDiffsOfSize
= \ ww_s3K3 ww1_s3Ka ww2_s3Kf ww3_s3Ki ->
let { y_a2nf = -# ww2_s3Kf ww_s3K3 } in
case ># ww1_s3Ka y_a2nf of {
__DEFAULT ->
let { wild_a2n2 = I# ww2_s3Kf } in
let { wild1_a2mO = I# ww1_s3Ka } in
let {
$wget_s3JR
= \ ww4_s3JP ->
case <=# ww1_s3Ka ww4_s3JP of {
__DEFAULT -> main3 ww4_s3JP wild1_a2mO wild_a2n2;
1# ->
case <=# ww4_s3JP ww2_s3Kf of {
__DEFAULT -> main3 ww4_s3JP wild1_a2mO wild_a2n2;
1# ->
case indexArray# ww3_s3Ki (-# ww4_s3JP ww1_s3Ka) of
{ (# ipv_a2ho #) ->
ipv_a2ho
}
}
} } in
joinrec {
$wgo_s3JY w_s3JS ww4_s3JW
= case $wget_s3JR (+# w_s3JS ww_s3K3) of { I# x_a2mv ->
case $wget_s3JR w_s3JS of { I# y1_a2my ->
case ># x_a2mv y1_a2my of {
__DEFAULT ->
case ==# w_s3JS y_a2nf of {
__DEFAULT -> jump $wgo_s3JY (+# w_s3JS 1#) ww4_s3JW;
1# -> ww4_s3JW
};
1# ->
case ==# w_s3JS y_a2nf of {
__DEFAULT -> jump $wgo_s3JY (+# w_s3JS 1#) (+# ww4_s3JW 1#);
1# -> +# ww4_s3JW 1#
}
}
}
}; } in
jump $wgo_s3JY ww1_s3Ka 0#;
1# -> 0#
}
Raw
core-using-zip.hs
-- much harder to follow for me, because it seems like everything is inlined into main.
-- i've added some comments to understand what's going on
Rec {
-- RHS size: {terms: 37, types: 20, coercions: 0, joins: 0/0}
$wgo -- amalloy: inlining (length . filter (< 0) . zipWith (-)) into a zero-allocation loop
= \ w_s4l5 w1_s4l6 ww_s4la ->
case w_s4l5 of {
[] -> ww_s4la;
: ipv_a2LH ipv1_a2LI ->
case w1_s4l6 of {
[] -> ww_s4la;
: ipv2_a2LM ipv3_a2LN ->
case ipv_a2LH of { I# x_a46o ->
case ipv2_a2LM of { I# y_a46r ->
case <# (-# x_a46o y_a46r) 0# of {
__DEFAULT -> $wgo ipv1_a2LI ipv3_a2LN ww_s4la;
1# -> $wgo ipv1_a2LI ipv3_a2LN (+# ww_s4la 1#)
}
}
}
}
}
end Rec }
-- RHS size: {terms: 14, types: 8, coercions: 0, joins: 0/0}
part1 -- just calling wgo with xs and tail xs
= \ w_s4ld ->
case $wgo
w_s4ld
(case w_s4ld of {
[] -> scanl2; -- amalloy: i don't really understand what scanl2 is. maybe error/undefined?
: ds1_a2zY xs_a2zZ -> xs_a2zZ
})
0#
of ww_s4lg
{ __DEFAULT ->
I# ww_s4lg
}
-- RHS size: {terms: 17, types: 24, coercions: 0, joins: 0/0}
threeWindows
= \ @ a_a2jh xs_a1Dr ->
case xs_a1Dr of wild_XK {
[] -> [];
: ds_d2zo ys_a1Ds ->
case ys_a1Ds of wild1_Xb {
[] -> [];
: ds1_d2zp zs_a1Dt -> zipWith3 Three wild_XK wild1_Xb zs_a1Dt
}
}
-- RHS size: {terms: 19, types: 13, coercions: 3, joins: 0/0}
main2 -- amalloy: implementation of sum for Three
= \ ds_d2Ac ->
case ds_d2Ac of { Three a1_a1Xi a2_a1Xj a3_a1Xk ->
case a1_a1Xi of { I# x_a3Yj ->
case a2_a1Xj of { I# x1_X40Z ->
case a3_a1Xk of { I# y_a3Ym ->
(I# (+# x_a3Yj (+# x1_X40Z y_a3Ym))) `cast` <Co:3>
}
}
}
}
-- RHS size: {terms: 8, types: 3, coercions: 0, joins: 0/0}
main3 = case $wgo [] scanl2 0# of v_B2 { __DEFAULT -> I# v_B2 }
-- RHS size: {terms: 34, types: 31, coercions: 5, joins: 0/1}
$wpart2
= \ w_s4nC ->
case w_s4nC of wild_XK {
[] -> case main3 of { I# v1_B2 -> v1_B2 };
: ds_d2zo ys_a1Ds ->
case ys_a1Ds of wild1_Xb {
[] -> case main3 of { I# v1_B2 -> v1_B2 };
: ds1_d2zp zs_a1Dt ->
let {
w1_s4ld
= map
(main2 `cast` <Co:5>)
(zipWith3 Three wild_XK wild1_Xb zs_a1Dt) } in
$wgo
w1_s4ld
(case w1_s4ld of {
[] -> scanl2;
: ds2_a2zY xs_a2zZ -> xs_a2zZ
})
0#
}
}
Raw
performance-data.txt
$ git checkout main; stack build; seq 1000000 | time stack run -- +RTS -s
Switched to branch 'main'
Your branch is ahead of 'origin/main' by 1 commit.
(use "git push" to publish your local commits)
day01> configure (exe)
Configuring day01-0.1.0.0...
day01> build (exe)
Preprocessing executable 'day01' for day01-0.1.0.0..
Building executable 'day01' for day01-0.1.0.0..
[1 of 1] Compiling Main
Linking .stack-work/dist/x86_64-linux-tinfo6/Cabal-3.2.1.0/build/day01/day01 ...
day01> copy/register
Installing executable day01 in /usr/local/google/home/amalloy/src/haskell/aoc-2021/day01/.stack-work/install/x86_64-linux-tinfo6/cdcae495b8241f80fe0c4f87270e419efc1803cb961b4c612038254b7c562a9d/8.10.7/bin
(999999,999997) 6,295,111,096 bytes allocated in the heap
496,891,136 bytes copied during GC
35,672,576 bytes maximum residency (32 sample(s))
6,114,816 bytes maximum slop
102 MiB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 6013 colls, 0 par 0.154s 0.157s 0.0000s 0.0001s
Gen 1 32 colls, 0 par 0.142s 0.142s 0.0044s 0.0171s
INIT time 0.000s ( 0.000s elapsed)
MUT time 1.209s ( 1.206s elapsed)
GC time 0.296s ( 0.300s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 1.505s ( 1.506s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 5,207,795,851 bytes per MUT second
Productivity 80.3% of total user, 80.1% of total elapsed
1.79user 0.12system 0:01.90elapsed 100%CPU (0avgtext+0avgdata 107992maxresident)k
0inputs+256outputs (4major+46941minor)pagefaults 0swaps
$ git checkout day1-array; stack build; seq 1000000 | time stack run -- +RTS -s
Switched to branch 'day1-array'
day01> configure (exe)
Configuring day01-0.1.0.0...
day01> build (exe)
Preprocessing executable 'day01' for day01-0.1.0.0..
Building executable 'day01' for day01-0.1.0.0..
[1 of 1] Compiling Main
/usr/local/google/home/amalloy/src/haskell/aoc-2021/day01/src/Main.hs:13:9: warning: [-Wname-shadowing]
This binding for ‘indices’ shadows the existing binding
imported from ‘Data.Array’ at src/Main.hs:6:1-17
(and originally defined in ‘GHC.Arr’)
|
13 | indices = [lo..hi - delta]
| ^^^^^^^
Linking .stack-work/dist/x86_64-linux-tinfo6/Cabal-3.2.1.0/build/day01/day01 ...
day01> copy/register
Installing executable day01 in /usr/local/google/home/amalloy/src/haskell/aoc-2021/day01/.stack-work/install/x86_64-linux-tinfo6/cdcae495b8241f80fe0c4f87270e419efc1803cb961b4c612038254b7c562a9d/8.10.7/bin
(999999,999997) 6,031,119,928 bytes allocated in the heap
953,681,888 bytes copied during GC
153,073,256 bytes maximum residency (15 sample(s))
2,110,048 bytes maximum slop
397 MiB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 5768 colls, 0 par 0.351s 0.355s 0.0001s 0.0042s
Gen 1 15 colls, 0 par 0.456s 0.456s 0.0304s 0.1325s
INIT time 0.000s ( 0.000s elapsed)
MUT time 1.132s ( 1.130s elapsed)
GC time 0.807s ( 0.811s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 1.940s ( 1.941s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 5,326,976,905 bytes per MUT second
Productivity 58.4% of total user, 58.2% of total elapsed
2.19user 0.20system 0:02.38elapsed 100%CPU (0avgtext+0avgdata 410096maxresident)k
0inputs+256outputs (4major+122443minor)pagefaults 0swaps
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment