search

haskell / containers

Assorted concrete container types
https://hackage.haskell.org/package/containers
314 stars 177 forks source link

Improve Map minViewSure/maxViewSure #1001

Open meooow25 opened 2 months ago

meooow25 commented 2 months ago

minViewSure/maxViewSure allocates one MinView/MaxView. This is avoidable, by not having the local go function.

Before

https://github.com/haskell/containers/blob/c651094ec026b90c4e9d4ed81bc15eb337d3fc2e/containers/src/Data/Map/Internal.hs#L4017-L4024

Core with GHC 9.6 ``` Rec { -- RHS size: {terms: 38, types: 63, coercions: 0, joins: 0/0} $wgo6_rpA5 :: forall {k} {a}. k -> a -> Map k a -> Map k a -> (# k, a, Map k a #) [GblId[StrictWorker([!, ~, !, !])], Arity=4, Str=<1L><1L><1L>, Unf=OtherCon []] $wgo6_rpA5 = \ (@k_sowX) (@a_sowY) (k1_sowZ :: k_sowX) (x_sox0 :: a_sowY) (ds_sox1 :: Map k_sowX a_sowY) (r_sox2 :: Map k_sowX a_sowY) -> case ds_sox1 of { Bin bx_dmPX kl_a6HQ xl_a6HR ll_a6HS lr_a6HT -> case $wgo6_rpA5 @k_sowX @a_sowY kl_a6HQ xl_a6HR ll_a6HS lr_a6HT of { (# ww_soQH, ww1_soQI, ww2_soQJ #) -> case balanceR @k_sowX @a_sowY k1_sowZ x_sox0 ww2_soQJ r_sox2 of conrep_a7Kp { __DEFAULT -> (# ww_soQH, ww1_soQI, conrep_a7Kp #) } }; Tip -> case k1_sowZ of conrep_a7Kn { __DEFAULT -> case r_sox2 of conrep1_a7Kp { __DEFAULT -> (# conrep_a7Kn, x_sox0, conrep1_a7Kp #) } } } end Rec } -- RHS size: {terms: 17, types: 28, coercions: 0, joins: 0/0} go10_rpA6 :: forall {k} {a}. k -> a -> Map k a -> Map k a -> MinView k a [GblId, Arity=4, Str=<1L><1L><1L>, Cpr=1, Unf=OtherCon []] go10_rpA6 = \ (@k_sowX) (@a_sowY) (k1_sowZ :: k_sowX) (x_sox0 :: a_sowY) (ds_sox1 :: Map k_sowX a_sowY) (r_sox2 :: Map k_sowX a_sowY) -> case $wgo6_rpA5 @k_sowX @a_sowY k1_sowZ x_sox0 ds_sox1 r_sox2 of { (# ww_soQH, ww1_soQI, ww2_soQJ #) -> Data.Map.Internal.MinView @k_sowX @a_sowY ww_soQH ww1_soQI ww2_soQJ } -- RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0} minViewSure [InlPrag=NOINLINE] :: forall k a. k -> a -> Map k a -> Map k a -> MinView k a [GblId, Arity=4, Str=<1L><1L><1L>, Cpr=1, Unf=OtherCon []] minViewSure = go10_rpA6 ``` As an example of a use site, `glue` looks like: ``` -- RHS size: {terms: 44, types: 57, coercions: 0, joins: 0/0} glue :: forall k a. Map k a -> Map k a -> Map k a [GblId, Arity=2, Str=<1L><1L>, Unf=Unf{Src=, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [30 30] 281 0}] glue = \ (@k_aao1) (@a_aao2) (ds_di14 :: Map k_aao1 a_aao2) (r_a6Hq :: Map k_aao1 a_aao2) -> case ds_di14 of wild_X1 { Bin ipv_snjA ipv1_snjB ipv2_snjC ipv3_snjD ipv4_snjE -> case r_a6Hq of wild1_X2 { Bin ipv5_snjG ipv6_snjH ipv7_snjI ipv8_snjJ ipv9_snjK -> case GHCExts.># ipv_snjA ipv5_snjG of { __DEFAULT -> case minViewSure @k_aao1 @a_aao2 ipv6_snjH ipv7_snjI ipv8_snjJ ipv9_snjK of { MinView ipv10_snjM ipv11_snjN ipv12_snjO -> balanceL @k_aao1 @a_aao2 ipv10_snjM ipv11_snjN wild_X1 ipv12_snjO }; 1# -> case maxViewSure @k_aao1 @a_aao2 ipv1_snjB ipv2_snjC ipv3_snjD ipv4_snjE of { MaxView ipv10_snjQ ipv11_snjR ipv12_snjS -> balanceR @k_aao1 @a_aao2 ipv10_snjQ ipv11_snjR ipv12_snjS wild1_X2 } }; Tip -> wild_X1 }; Tip -> r_a6Hq } ```

After

Core, again ``` Rec { -- RHS size: {terms: 38, types: 63, coercions: 0, joins: 0/0} Data.Map.Internal.$wminViewSure [InlPrag=[2], Occ=LoopBreaker] :: forall {k} {a}. k -> a -> Map k a -> Map k a -> (# k, a, Map k a #) [GblId[StrictWorker([!, ~, !, !])], Arity=4, Str=<1L><1L><1L>, Unf=OtherCon []] Data.Map.Internal.$wminViewSure = \ (@k_sowH) (@a_sowI) (k1_sowJ :: k_sowH) (x_sowK :: a_sowI) (l_sowL :: Map k_sowH a_sowI) (r_sowM :: Map k_sowH a_sowI) -> case k1_sowJ of k2_X0 { __DEFAULT -> case r_sowM of r1_X1 { __DEFAULT -> case l_sowL of { Bin bx_dmPJ lk_a6HO lx_a6HP ll_a6HQ lr_a6HR -> case Data.Map.Internal.$wminViewSure @k_sowH @a_sowI lk_a6HO lx_a6HP ll_a6HQ lr_a6HR of { (# ww_soQr, ww1_soQs, ww2_soQt #) -> case balanceR @k_sowH @a_sowI k2_X0 x_sowK ww2_soQt r1_X1 of conrep_a7Kj { __DEFAULT -> (# ww_soQr, ww1_soQs, conrep_a7Kj #) } }; Tip -> (# k2_X0, x_sowK, r1_X1 #) } } } end Rec } -- RHS size: {terms: 17, types: 28, coercions: 0, joins: 0/0} minViewSure [InlPrag=[2]] :: forall k a. k -> a -> Map k a -> Map k a -> MinView k a [GblId, Arity=4, Str=<1L><1L><1L>, Cpr=1, Unf=Unf{Src=StableSystem, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=ALWAYS_IF(arity=4,unsat_ok=True,boring_ok=False) Tmpl= \ (@k_sowH) (@a_sowI) (k1_sowJ [Occ=Once1] :: k_sowH) (x_sowK [Occ=Once1] :: a_sowI) (l_sowL [Occ=Once1] :: Map k_sowH a_sowI) (r_sowM [Occ=Once1] :: Map k_sowH a_sowI) -> case Data.Map.Internal.$wminViewSure @k_sowH @a_sowI k1_sowJ x_sowK l_sowL r_sowM of { (# ww_soQr [Occ=Once1], ww1_soQs [Occ=Once1], ww2_soQt [Occ=Once1] #) -> Data.Map.Internal.MinView @k_sowH @a_sowI ww_soQr ww1_soQs ww2_soQt }}] minViewSure = \ (@k_sowH) (@a_sowI) (k1_sowJ :: k_sowH) (x_sowK :: a_sowI) (l_sowL :: Map k_sowH a_sowI) (r_sowM :: Map k_sowH a_sowI) -> case Data.Map.Internal.$wminViewSure @k_sowH @a_sowI k1_sowJ x_sowK l_sowL r_sowM of { (# ww_soQr, ww1_soQs, ww2_soQt #) -> Data.Map.Internal.MinView @k_sowH @a_sowI ww_soQr ww1_soQs ww2_soQt } ``` `glue` now does not create `MinView`/`MaxView`s. ``` -- RHS size: {terms: 44, types: 69, coercions: 0, joins: 0/0} glue :: forall k a. Map k a -> Map k a -> Map k a [GblId, Arity=2, Str=<1L><1L>, Unf=Unf{Src=, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [30 30] 281 0}] glue = \ (@k_aam7) (@a_aam8) (ds_dhZa :: Map k_aam7 a_aam8) (r_a6Hm :: Map k_aam7 a_aam8) -> case ds_dhZa of wild_X1 { Bin ipv_snhE ipv1_snhF ipv2_snhG ipv3_snhH ipv4_snhI -> case r_a6Hm of wild1_X2 { Bin ipv5_snhK ipv6_snhL ipv7_snhM ipv8_snhN ipv9_snhO -> case GHCExts.># ipv_snhE ipv5_snhK of { __DEFAULT -> case Data.Map.Internal.$wminViewSure @k_aam7 @a_aam8 ipv6_snhL ipv7_snhM ipv8_snhN ipv9_snhO of { (# ww_soOL, ww1_soOM, ww2_soON #) -> balanceL @k_aam7 @a_aam8 ww_soOL ww1_soOM wild_X1 ww2_soON }; 1# -> case Data.Map.Internal.$wmaxViewSure @k_aam7 @a_aam8 ipv1_snhF ipv2_snhG ipv3_snhH ipv4_snhI of { (# ww_soOB, ww1_soOC, ww2_soOD #) -> balanceR @k_aam7 @a_aam8 ww_soOB ww1_soOC ww2_soOD wild1_X2 } }; Tip -> wild_X1 }; Tip -> r_a6Hm } ```

Benchmarks

Running map-benchmarks on minView (which uses minViewSure) and difference (which uses glue which uses minViewSure and maxViewSure):

Name          Time - - - - - - - -    Allocated - - - - -
                   A       B     %         A       B     %
difference     90 μs   78 μs  -13%    351 KB  287 KB  -18%
minView        28 ns   22 ns  -22%    167 B   135 B   -19%