replace Stream with Sequence

[Ashish Agarwal]

Core introduced a new module called Sequence a few weeks ago, which I didn't notice until now. It is a Stream alternative, so I'm wondering if we should switch to it. That would remove our dependency on cfstream. (Presumably Sequence is better than Stream, else they would've just used Stream, but I'm unaware of any explanation of this.) Let me know if you have any opinions.

[Philippe Veber]

Funnily, I refrained these past weeks to propose a similar change, but for the sequence library by Simon Cruanes [1]. I was motivated by a benchmark made by Drup, showing a big speedup compared to streams [2], although I don't know if this speedup is obtained at the expense of memory.

At first glance, c-cube's sequence is more feature rich than janestreet's, but less core-friendly of course. Maybe a small benchmark (n-queens?) wouldn't hurt here to make a choice.


[1] https://github.com/c-cube/sequence
[2] https://lists.forge.ocamlcore.org/pipermail/batteries-devel/2014-January/001917.html

2014-07-03 18:52 GMT+02:00 Ashish Agarwal <agarw...@gmail.com>:

Core introduced a new module called Sequence a few weeks ago, which I didn't notice until now. It is a Stream alternative, so I'm wondering if we should switch to it. That would remove our dependency on cfstream. (Presumably Sequence is better than Stream, else they would've just used Stream, but I'm unaware of any explanation of this.) Let me know if you have any opinions.

--
You received this message because you are subscribed to the Google Groups "biocaml" group.
To unsubscribe from this group and stop receiving emails from it, send an email to biocaml+u...@googlegroups.com.
To post to this group, send email to bio...@googlegroups.com.
Visit this group at http://groups.google.com/group/biocaml.
To view this discussion on the web visit https://groups.google.com/d/msgid/biocaml/CAMu2m2LS4kxu-cH27QOxtbgnuqUhNhWD3SxNBTgiYsQAFHjRaw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Ashish Agarwal]

It would be great if you can run a benchmark. However, Core's Sequence would have to have substantially worse performance for me to prefer c-cube's sequence. For one thing, c-cube's library is not in Core style, so we'd have to write a cfsequence library.  :)

To view this discussion on the web visit https://groups.google.com/d/msgid/biocaml/CAOOOohT%3DiyNocSw3b5vYKPEaVyh2YONseaaz3Yj6J537FTPBfA%40mail.gmail.com.

[Philippe Veber]

I ran Drup's benchmark on stream-like datastructure, which is provided in LILiS source code [1]. Interestingly, it features cfstream and core's sequence:

 --- Lsystem Von_koch for 7 iterations ---
  Stream+: LazyList+:     Enum+:      Seq+:     Core+: CFStream+: Sequence+:             Rate       Stream+ LazyList+ CFStream+  Enum+ Core+   Seq+ Sequence+
  Stream+ 3.58+-0.00/s      --      -30%      -78%   -90%  -93%   -94%      -95%
LazyList+ 5.14+-0.00/s     44%        --      -68%   -86%  -90%   -91%      -92%
CFStream+ 15.9+- 0.0/s    344%      209%        --   -57%  -69%   -72%      -76%
    Enum+ 37.0+- 0.1/s    933%      619%      132%     --  -28%   -34%      -44%
    Core+ 51.2+- 0.0/s   1331%      896%      222%    38%    --    -8%      -23%
     Seq+ 56.0+- 0.1/s   1463%      988%      252%    51%    9%     --      -16%
Sequence+ 66.2+- 0.0/s   1751%     1188%      316%    79%   29%    18%        --


 --- Lsystem dragon for 15 iterations ---
           
            Rate       Stream+ LazyList+ CFStream+  Enum+ Core+   Seq+ Sequence+
  Stream+ 2.15+-0.00/s      --      -29%      -78%   -90%  -92%   -94%      -95%
LazyList+ 3.04+-0.00/s     41%        --      -70%   -85%  -89%   -91%      -93%
CFStream+ 9.98+-0.00/s    364%      228%        --   -52%  -64%   -71%      -77%
    Enum+ 20.7+- 0.0/s    861%      580%      107%     --  -25%   -40%      -52%
    Core+ 27.5+- 0.0/s   1180%      805%      176%    33%    --   -21%      -36%
     Seq+ 34.7+- 0.0/s   1513%     1041%      248%    68%   26%     --      -20%
Sequence+ 43.3+- 0.1/s   1912%     1323%      334%   109%   57%    25%        --


 --- Lsystem fern for 9 iterations ---
             Rate        Stream+ LazyList+ CFStream+ Enum+ Core+  Seq+ Sequence+
  Stream+ 0.437+-0.001/s      --      -34%      -78%  -90%  -93%  -93%      -95%
LazyList+ 0.659+-0.001/s     51%        --      -68%  -86%  -90%  -90%      -92%
CFStream+  2.03+- 0.00/s    365%      208%        --  -56%  -68%  -69%      -75%
    Enum+  4.57+- 0.00/s    946%      593%      125%    --  -29%  -29%      -44%
    Core+  6.42+- 0.00/s   1369%      874%      216%   40%    --   -1%      -21%
     Seq+  6.46+- 0.00/s   1377%      880%      218%   41%    1%    --      -21%
Sequence+  8.14+- 0.00/s   1762%     1135%      301%   78%   27%   26%        --


 --- Lsystem Tetradragon for 12 iterations ---
             Rate        Stream+ LazyList+ CFStream+ Enum+ Core+  Seq+ Sequence+
  Stream+ 0.307+-0.000/s      --      -30%      -78%  -90%  -93%  -94%      -95%
LazyList+ 0.435+-0.002/s     42%        --      -68%  -86%  -90%  -91%      -92%
CFStream+  1.37+- 0.00/s    348%      215%        --  -56%  -68%  -72%      -76%
    Enum+  3.10+- 0.00/s    910%      612%      126%    --  -27%  -36%      -46%
    Core+  4.26+- 0.00/s   1291%      880%      211%   38%    --  -12%      -26%
     Seq+  4.86+- 0.00/s   1485%     1016%      254%   57%   14%    --      -16%
Sequence+  5.78+- 0.00/s   1784%     1227%      321%   86%   35%   19%        --

On this benchmark, core's sequence is clearly less efficient than c-cube's, but already much better than cfstream (BTW, I'm not sure why cfstream performs any better than stream, this looks strange to me at first sight). I noticed there will be a talk at OUD'14 about core's sequence library. How about deciding whether to switch to it when we know a little more? Hopefully, the change should be easy (thanks to cfstream!)

[1] https://github.com/Drup/LILiS

To view this discussion on the web visit https://groups.google.com/d/msgid/biocaml/CAMu2m2Jh_hNqXv4%3DZFZp1ZOUH%3DWHvLozf-Uqga_NOoD_K-t49g%40mail.gmail.com.

[Ashish Agarwal]

On Wed, Jul 9, 2014 at 5:31 PM, Philippe Veber <philipp...@gmail.com> wrote:

How about deciding whether to switch to it when we know a little more? Hopefully, the change should be easy (thanks to cfstream!)

It's a few lines of code in Future, and none in Biocaml because the Future.S signature doesn't change. So no problem switching again. I'll look more closely at your benchmarks next week since BOSC is keeping me busy right now.

[Ashish Agarwal]

BTW, a few days ago switched back to Stream. The Sequence interface isn't very compatible with Lwt_stream and Async.Pipe. The Sequence interface assumes they are pure, so it is more awkward to provide an implementation against the Future signature.

[Philippe Veber]

I think we had two benefits for switching to core's sequence:
- remove one dependence and maybe one maintenance burden (if we could have dropped cfstream)
- performance gain (core's sequence appears about 2 times faster than cfstreams)

First point is out of question if core's sequence is not suited for future. Second point is maybe not such a big deal for our use of streams. I'd be okay to stick with CFStream for now.

--
You received this message because you are subscribed to the Google Groups "biocaml" group.
To unsubscribe from this group and stop receiving emails from it, send an email to biocaml+u...@googlegroups.com.
To post to this group, send email to bio...@googlegroups.com.
Visit this group at http://groups.google.com/group/biocaml.

To view this discussion on the web visit https://groups.google.com/d/msgid/biocaml/CAMu2m2JW00%3DiRH8JX22Z__ota9z7iHLvqXNt1yCC061COUHtpg%40mail.gmail.com.