free-ish representation of Eff in JS

[safareli]

If representation of Eff in JS runtime, was free monad-ish way, like this:

Eff a 
 = { tag: "effect", val0 :: Void,  val1 :: Unit -> a } 
 | { tag: "pure",   val0 :: Void,  val1 :: a } 
 | { tag: "map",    val0 :: Eff b, val1 :: b -> a } 
 | { tag: "apply",  val0 :: Eff a, val1 :: Eff (b -> a) } 
 | { tag: "bind",   val0 :: Eff b, val1 :: b -> Eff a } 

then:

exports.pureE = function (a) {
  return { tag: "pure", val0: null, val1: a }
};

exports.bindE = function (a) {
  return function (f) {
    return { tag: "bind", val0: a, val1: f }
  };
};

exports.applyE = function (f) {
  return function (a) {
    return { tag: "apply", val0: a, val1: f }
  };
};

exports.unsafeRun = function (eff) {
  // TODO: fold eff in a stack safe way.
};
exports.runPure = function (eff) {
  return unsafeRun(eff)
};

This will make bind stack safe by default (no need for MonadRec)

Disadvantages:

• now, one could just grab any Eff value from JS and call it, as it's represented as a function. After proposed change, one would need to require Control/Monad/Eff.js first to get reference to unsafeRun and then use it to run the Eff.
• significantly complex than what we have now (not as complex as Aff's implementation as Eff is sync)
• braking change
• as there will be less functions, might be harder to debug

Advantages:

• instead of allocate new functions on common operations like map, ap, bind, pure, now you just create small objects whith same shape (so JS runtime can optimize property access).
• it could be stack safe by default.
• as Eff is a tree now might be easier to debug (like you can print it).

[paf31]

I think it would be good if you could demonstrate this approach in a repo, although I don't think it's a good default for purescript-eff necessarily, which is supposed to be as lightweight and low-level as possible.

[safareli]

Here it is, it's stacksafe, and should be fast, (haven't done benchmarks, yet)
https://gist.github.com/safareli/ca3c3b066d4fe0ed5917bcdd0dcebf56

I could have made port of ps-catlist to js, but uncons might still have O(n) performance (if i understand it correctly), which would not be useful, tho having cat list with 0(1) uncons would be pretty useful (will take a look at okasaki) and will avoid need to go down to the leaf nodes in unsafeRun.

[paf31]

Looks interesting, but I'll need to study it more. Perhaps you could make a repo and package it up as a PureScript library on top of eff. It might be very useful for certain tasks.

[safareli]

Currently this is what results look like:

tes-t	n	structure	mean	stddev	min	max
bind assocR	100	eff	91.59 μs	97.58 μs	57.45 μs	1.32 ms
bind assocR	100	new	89.37 μs	41.21 μs	76.01 μs	1.05 ms
bind assocR	500	eff	418.75 μs	292.12 μs	298.48 μs	2.18 ms
bind assocR	500	new	425.61 μs	68.97 μs	371.10 μs	1.01 ms
bind assocR	1000	eff	852.64 μs	491.60 μs	595.40 μs	3.02 ms
bind assocR	1000	new	831.16 μs	88.92 μs	741.44 μs	1.38 ms
bind assocR	10000	eff	75.05 ms	18.19 ms	44.50 ms	156.94 ms
bind assocR	10000	new	23.47 ms	1.70 ms	19.33 ms	35.93 ms
bind assocL	100	eff	64.05 μs	712.07 μs	16.68 μs	13.61 ms
bind assocL	100	new	20.57 μs	5.63 μs	18.63 μs	118.48 μs
bind assocL	500	eff	188.67 μs	957.96 μs	81.20 μs	11.93 ms
bind assocL	500	new	120.69 μs	446.51 μs	97.86 μs	14.21 ms
bind assocL	1000	eff	527.82 μs	1.89 ms	158.87 μs	16.15 ms
bind assocL	1000	new	262.16 μs	500.66 μs	218.21 μs	12.84 ms
bind assocL	4000	eff	2.55 ms	4.35 ms	681.78 μs	24.37 ms
bind assocL	4000	new	1.68 ms	991.33 μs	1.48 ms	15.51 ms
bind assocL	8000	eff	5.20 ms	6.01 ms	1.54 ms	32.68 ms
bind assocL	8000	new	8.26 ms	1.71 ms	7.47 ms	23.24 ms
map	100	eff	69.65 μs	887.91 μs	16.04 μs	20.04 ms
map	100	new	19.70 μs	3.43 μs	18.64 μs	76.19 μs
map	500	eff	237.35 μs	1.37 ms	80.63 μs	18.24 ms
map	500	new	110.24 μs	31.76 μs	98.00 μs	987.71 μs
map	1000	eff	633.66 μs	2.36 ms	165.66 μs	16.99 ms
map	1000	new	264.55 μs	625.85 μs	217.95 μs	14.54 ms
map	2000	eff	1.13 ms	2.92 ms	324.94 μs	18.66 ms
map	2000	new	636.19 μs	972.30 μs	527.99 μs	15.26 ms
map	4000	eff	2.49 ms	4.41 ms	665.96 μs	25.41 ms
map	4000	new	1.78 ms	1.35 ms	1.49 ms	21.16 ms
map	5000	eff	3.77 ms	5.81 ms	920.34 μs	33.17 ms
map	5000	new	2.90 ms	1.58 ms	2.43 ms	20.11 ms
apply	100	eff	576.78 μs	2.47 ms	126.48 μs	18.35 ms
apply	100	new	302.72 μs	1.51 ms	136.85 μs	18.08 ms
apply	500	eff	3.01 ms	5.30 ms	662.40 μs	22.20 ms
apply	500	new	1.56 ms	3.19 ms	744.04 μs	18.84 ms
apply	1000	eff	6.46 ms	7.39 ms	1.37 ms	34.00 ms
apply	1000	new	3.41 ms	4.61 ms	1.68 ms	31.30 ms
apply	2000	eff	15.04 ms	8.27 ms	3.35 ms	37.13 ms
apply	2000	new	8.55 ms	7.02 ms	4.36 ms	40.37 ms
apply	4000	eff	24.50 ms	5.95 ms	17.62 ms	64.13 ms
apply	4000	new	19.83 ms	1.02 ms	17.93 ms	29.60 ms
apply	5000	eff	79.78 ms	30.97 ms	35.19 ms	228.12 ms
apply	5000	new	40.61 ms	11.03 ms	27.99 ms	81.66 ms

This is how test structures are generated:

applyLoop :: Monad m => (Int -> m Unit) -> Int -> m Unit
applyLoop eff max = go (pure unit) 0
  where 
  go acc n | n == max = acc
  go acc n = go (acc <* eff n) (n + 1)

bindRightLoop :: Monad m => (Int -> m Unit)  -> Int -> m Unit
bindRightLoop eff max = go (pure unit) 0
  where 
  go acc n | n == max = acc
  go acc n = go (eff (max - n - 1) >>= const acc) (n + 1)

bindLeftLoop :: Monad m => (Int -> m Unit)  -> Int -> m Unit
bindLeftLoop eff max = go (pure unit) 0
  where 
  go acc n | n == max = acc
  go acc n = go (acc >>= const (eff n)) (n + 1)

mapLoop :: Monad m => Int -> m Int -> m Int
mapLoop max i = 
  if max == 0 
    then i 
    else mapLoop (max - 1) (map (_ + 1) i)

Note that generations must be tail call optimized so stack is not overflowed during generation.

Max numbers for particular test type is restricted because of Eff, proposed implementation could handle:

• 10000000 right associated binds in around 10 sec (on 100000000 heap out of memory)
• 40000 left associated binds in around 2 sec
• 80000 left associated binds in around 20 sec
• 40000 map in around 200 msec
• 80000 map in around 20 sec
• 40000 apply in around 27 sec
• 80000 apply in around 2 min

So now there is heap memory and time constraints only.

Right associated binds perform extremely well, my guess is that operations array is smaller in that case. I used bind based implementations of map and apply but they performed badly than normal implementation.

Need to do a bit more testing & benchmarking. but here is the code safareli/purescript-ef#1
Would love to if you can take a look.

[paf31]

I think it looks great! It would be interesting to compare it to Coyoneda or Codensity over Eff too.

[natefaubion]

This is really cool, but just an FYI wrt minibench. You have to be sure to initiate a manual GC between each test. GC from previous runs will most definitely affect subsequent runs. I hit this problem when benching purescript-run.

[safareli]

initiate a manual GC between each test

have you done similar thing somewhere, can you link that?

[natefaubion]

For v8 you just call global.gc().

[natefaubion]

And call node with --expose-gc.

[paf31]

GC already gets run once inside minibench. Maybe this would make a good PR there.

[natefaubion]

@paf31 Maybe I was using an old version?

[safareli]

Thanks! I created an initial PR if you wanna review
safareli/purescript-ef#1

[safareli]

This is too fast :D