Hi, I had replaced list_vt with qlist and now it is the most efficient version I could get now: ``` patscc -O2 -DATS_MEMALLOC_LIBC -I"../libs/" -o test7 TEST/test7.dats /run/current-system/sw/bin/time ./test7 1077871 0.84user 0.01system 0:00.85elapsed 100%CPU (0avgtext+0avgdata 35108maxresident)k 0inputs+0outputs (0major+8486minor)pagefaults 0swaps ``` in comparison to haskell's: ``` 1.16user 0.02system 0:01.18elapsed 99%CPU (0avgtext+0avgdata 74492maxresident)k 0inputs+0outputs (0major+17827minor)pagefaults 0swaps ``` I have to note, that test4 is more correct than test3: it is the same, except that it is using GC to collect stream() ``` patscc -O2 -DATS_MEMALLOC_GCBDW -lgc -o test4 TEST/test4.dats /run/current-system/sw/bin/time ./test4 1077871 2.13user 0.03system 0:02.13elapsed 101%CPU (0avgtext+0avgdata 97344maxresident)k ``` which is expected to use less memory, but increases time to GC (as expected as well), but, technically, this version is the closest to haskell's one.
for 2^30 constraint: ``` patscc -O2 -DATS_MEMALLOC_LIBC -I"../libs/" -o test7 TEST/test7.dats /run/current-system/sw/bin/time ./test7 54400028 227.79user 0.63system 3:48.43elapsed 99%CPU (0avgtext+0avgdata 1701428maxresident)k 0inputs+0outputs (0major+425064minor)pagefaults 0swaps ``` haskell version with GHC8.10: ``` 54400028 278.48user 0.62system 4:38.75elapsed 100%CPU (0avgtext+0avgdata 3016564maxresident)k 0inputs+0outputs (0major+753319minor)pagefaults 0swaps ``` and test4 ``` patscc -O2 -DATS_MEMALLOC_GCBDW -lgc -o test4 TEST/test4.dats /run/current-system/sw/bin/time ./test4 54400028 704.39user 1.81system 11:46.22elapsed 99%CPU (0avgtext+0avgdata 4966216maxresident)k 0inputs+0outputs (0major+1241156minor)pagefaults 0swaps ``` I am wondering why test4 performs quite poor(I guess, Boehm GC is just too general/unoptimized), because, I had expected, that GC should free stream_con() instances as soon as they will be converted into stream_vt_con() by stream_t2vt... That is what haskell's GC is doing with intermediate data. I wish I was able to free stream_con() instance forcibly in stream_t2vt(). In this case, I expect it will be on par with haskell (I assume, that qlist is implemented as a flat array (I haven't actually checked, hehe)) Meanwhile: 1. I had started this topic, because Haskell's source code is a good example of composability of lazy evaluation: it is short, but quite powerful as I had spent quite some time to produce an outperforming version which is more difficult as well. Basically, I had to implement memoization using qlist() which is built-in into Haskell's runtime; 2. now I have an example of stateful lazy stream processing in ATS2 and it was very interesting as I had the impression that it is hard in ATS to keep an implicit state (as resource usage is harder without GC); 3. I have a food for thoughts, because, even if Haskell's version is short but powerful, lazy-by-default evaluation has a side-effect of having to dig and decide what is worse in particular case: code being too lazy or code being too strict. Just a simple example is a `foldr` implementation ( https://downloads.haskell.org/~ghc/latest/docs/html/libraries/base-4.16.1.0/src/Data.Foldable.html#foldr): which requires some time to understand how it is being done. Also it is hard to not to meet https://downloads.haskell.org/~ghc/latest/docs/html/libraries/deepseq-1.4.6.1/Control-DeepSeq.html for forcing evaluation. So Haskell hides laziness but requires understanding how to force evaluation and marshall data to fit GC's expectations. ATS on its turn, exposes laziness primitives and requires understanding how to use laziness. For me, it seems that it is a more fair approach: if you don't use laziness, then you don't pay for it, unlike with haskell: if you write a strict code, you will still need to be aware of laziness/GC/marshalling and etc...; 4. I was missing `qlist_free` function; 5. it is still interesting if there a way how to improve test4: I understand, that having stream_free() will be impossible, as stream() is a datatype and type checker will not be able to protect from double free, as well as having possibility to have a recursive linear stream like this: ``` val rec ones: stream_vt(int) = $ldelay( stream_vt_cons( 1, ones)) ``` will probably won't help as well, as it will require a possibility to forcibly walk through a stream without consuming it, which is hard due to requirement of usage of $ldelay.... So it looks like some Boehm GC optimization is the correct answer... Or, maybe it means that linear streams and qlist is the "only" correct version for such task... Especially, as we already know that older GHC version produces worse results I hope that the topic of lazy streams in ATS is interesting for others :) пн, 11 июл. 2022 г. в 23:02, gmhwxi <[email protected]>: > > I put my ATS2 code here: > > https://github.com/githwxi/ATS-Postiats/tree/master/libats/TEST > > I will put some code similar to what you did in test5 later. I think that > test5-style > is going to be faster for a relative small input (e.g., 2^24) but it may > not be able to > beat test02 for larger input (e.g., 2^30). > > > On Monday, July 11, 2022 at 8:46:02 AM UTC-4 gmhwxi wrote: > >> There is 'qlist' in libats that does what you want. >> >> By using the two-stream approach I mentioned earlier, you can readily get >> to 2^30: >> >> 54400028 >> real 18m47.053s >> user 18m46.372s >> sys 0m0.424s >> >> (* >> This info is for the number of primes up to 2^28: >> >> ATS2: >> 14630843 >> real 2m35.548s >> user 2m35.532s >> sys 0m0.000s >> >> Haskell (GHC-7.10.3) >> 14630843 >> real 7m41.733s >> user 7m36.208s >> sys 0m1.688s >> *) >> >> I could not get the haskell implementation to finish for 2^30. I had to >> stop its running once >> its memory usage reached 25% after about 10 minutes (I was monitoring >> using 'top'). >> >> >> On Mon, Jul 11, 2022 at 7:20 AM Dambaev Alexander <[email protected]> >> wrote: >> >>> I had checked some more and was able to make a stateful numbers >>> generator using list_vt for accumulating of evaluated results here >>> https://github.com/dambaev/mobt2/blob/master/ats2/src/TEST/test5.dats >>> but for some reason, it takes forever to complete with default constraint >>> <= g0int_npow( 2, 24) using linear streams >>> >>> I guess is due to list_vt_extent, which is O(n) >>> >>> I was trying to pass pointer to a tail of the list_vt data to pass >>> through auxmain/auxmain_con to make extend to be O(1), but I was not able >>> to satisfy type checker :) So I decided to ask if it is possible to use >>> such pointer/hole to the tail in the environment of $ldelay? >>> >>> вс, 10 июл. 2022 г. в 03:12, gmhwxi <[email protected]>: >>> >>>> >>>> I see. >>>> >>>> By the way, when I tried test1 and test3 on my machine, the latter is >>>> only about 10% faster than the former. >>>> >>>> It should be easy to have a version in ATS that beats Haskell: >>>> >>>> You first produce a non-linear thePrimes. Then you produce a linear >>>> thePrimes2 (where isPrime uses thePrimes). >>>> In this way, the memory foot print should be very small. And I bet the >>>> running time is much faster. Try 2^28 or 2^30 :) >>>> >>>> On Saturday, July 9, 2022 at 10:37:03 PM UTC-4 [email protected] >>>> wrote: >>>> >>>>> I will check ATS3 version, meanwhile GHC 8.10 produces much more >>>>> optimised code: >>>>> >>>>> ``` >>>>> [nix-shell:/data/devel/mobt2/haskell]$ ghc --version >>>>> The Glorious Glasgow Haskell Compilation System, version 8.10.7 >>>>> [nix-shell:/data/devel/mobt2/haskell]$ ghc -O2 --make app/Main.hs -o >>>>> haskell >>>>> [1 of 1] Compiling Main ( app/Main.hs, app/Main.o ) >>>>> Linking haskell ... >>>>> [nix-shell:/data/devel/mobt2/haskell]$ $(which time) ./haskell >>>>> 1077871 >>>>> 1.04user 0.00system 0:01.05elapsed 100%CPU (0avgtext+0avgdata >>>>> 72140maxresident)k >>>>> 0inputs+0outputs (0major+17298minor)pagefaults 0swaps >>>>> ``` >>>>> in comparison to ATS2 versions from repo above: >>>>> >>>>> ``` >>>>> [nix-shell:/data/devel/mobt2/ats2/src]$ make >>>>> patscc -O2 -DATS_MEMALLOC_LIBC -I"../libs/" -o test3 TEST/test3.dats >>>>> /run/current-system/sw/bin/time ./test3 >>>>> 1077871 >>>>> 1.11user 0.01system 0:01.12elapsed 100%CPU (0avgtext+0avgdata >>>>> 102456maxresident)k >>>>> 0inputs+0outputs (0major+25327minor)pagefaults 0swaps >>>>> patscc -O2 -DATS_MEMALLOC_LIBC -I"../libs/" -o test1 TEST/test1.dats >>>>> /run/current-system/sw/bin/time ./test1 >>>>> 1077871 >>>>> 2.11user 0.03system 0:02.14elapsed 99%CPU (0avgtext+0avgdata >>>>> 203448maxresident)k >>>>> 0inputs+0outputs (0major+50589minor)pagefaults 0swaps >>>>> ``` >>>>> ie, non-linear version (test1) is twice slower and using 2x memory of >>>>> test3 (which converts stream into stream_vt). But still, haskell version >>>>> is >>>>> faster and using less memory :) >>>>> >>>>> вс, 10 июл. 2022 г. в 02:21, gmhwxi <[email protected]>: >>>>> >>>>>> Here is a version I wrote in ATS3: >>>>>> >>>>>> >>>>>> https://github.com/githwxi/ATS-Xanadu/blob/master/xatslib/libcats/TEST/test02_isPrime.dats >>>>>> >>>>>> Currently, I can only compile the ATS3 code to JS. The generated JS >>>>>> code runs about 10 times slower >>>>>> than the C code generated from compiling a comparable ATS2 >>>>>> implementation: >>>>>> >>>>>> |thePrimes2| = 1077871 >>>>>> >>>>>> real 0m23.060s >>>>>> user 0m23.380s >>>>>> sys 0m0.188s >>>>>> On Saturday, July 9, 2022 at 5:33:43 PM UTC-4 gmhwxi wrote: >>>>>> >>>>>>> I took a look. Your ATS code looks very fine to me. >>>>>>> >>>>>>> I did some profiling on my own. In my trials, your ATS code is >>>>>>> actually a lot faster than >>>>>>> the Haskell code you posted. Note that my ghc version is very old: >>>>>>> GHC 7.10.3 >>>>>>> >>>>>>> ###### ATS ###### >>>>>>> >>>>>>> (* Your code using non-linear stream *) >>>>>>> hwxi@hongwei-t440p:/tmp$ patscc -O2 -o primes -DATS_MEMALLOC_LIBC >>>>>>> primes.dats >>>>>>> hwxi@hongwei-t440p:/tmp$ time ./primes >>>>>>> 1077871 >>>>>>> >>>>>>> real 0m3.118s >>>>>>> user 0m3.064s >>>>>>> sys 0m0.048s >>>>>>> >>>>>>> ###### Haskell ###### >>>>>>> (* Your haskell version *) >>>>>>> (* >>>>>>> Glasgow Haskell Compiler, Version 7.10.3, stage 2 booted by GHC >>>>>>> version 7.10.3 >>>>>>> *) >>>>>>> >>>>>>> hwxi@hongwei-t440p:/tmp$ ghc -O2 primes.hs >>>>>>> Linking primes ... >>>>>>> hwxi@hongwei-t440p:/tmp$ time ./primes >>>>>>> 1077871 >>>>>>> >>>>>>> real 0m8.195s >>>>>>> user 0m8.152s >>>>>>> sys 0m0.040s >>>>>>> >>>>>>> ################ >>>>>>> >>>>>>> ###### ATS ###### >>>>>>> (*My version using linear stream that is based on yours*) >>>>>>> >>>>>>> hwxi@hongwei-t440p:/tmp$ patscc -O2 -o primes2 -DATS_MEMALLOC_LIBC >>>>>>> primes2.dats >>>>>>> hwxi@hongwei-t440p:/tmp$ time ./primes2 >>>>>>> 1077871 >>>>>>> >>>>>>> real 0m2.120s >>>>>>> user 0m2.092s >>>>>>> sys 0m0.000s >>>>>>> >>>>>>> On Saturday, July 9, 2022 at 12:50:11 PM UTC-4 [email protected] >>>>>>> wrote: >>>>>>> >>>>>>>> My initial motivation was this Haskell source code: >>>>>>>> https://github.com/dambaev/mobt2/blob/master/haskell/app/Main.hs >>>>>>>> which is using lazy list (of course) and recursive binding and I >>>>>>>> decided to >>>>>>>> check if it will be possible to get something similar >>>>>>>> >>>>>>>> ATS version using non-linear stream is here: >>>>>>>> https://github.com/dambaev/mobt2/blob/master/ats2/src/TEST/test1.dats >>>>>>>> , but it takes to much memory as `stream_take_while` duplicates data, >>>>>>>> as I >>>>>>>> have got, that datatype constructor can't be unfolded with >>>>>>>> `@stream_cons` >>>>>>>> pattern match >>>>>>>> >>>>>>>> There is another version, that generates primes with non-linear >>>>>>>> stream and then, converting it to linear stream >>>>>>>> https://github.com/dambaev/mobt2/blob/master/ats2/src/TEST/test3.dats >>>>>>>> . This is the closest version to haskell's one. but still is using more >>>>>>>> space and as twice as slow as Haskell, so I had started to think of >>>>>>>> how to >>>>>>>> eliminate intermediate data structure. >>>>>>>> >>>>>>>> So, not a production issue, hehe, just found an interesting topic >>>>>>>> to dig in :) >>>>>>>> >>>>>>>> сб, 9 июл. 2022 г. в 11:11, Hongwei Xi <[email protected]>: >>>>>>>> >>>>>>>>> By looking at your first version, my simple answer is that a >>>>>>>>> linear stream cannot be used >>>>>>>>> in this way. The second version is possible but I am not sure what >>>>>>>>> you wanted to do exactly. >>>>>>>>> If you show me how to use a non-linear stream to do it, then I >>>>>>>>> could probably say more. >>>>>>>>> >>>>>>>>> On Sat, Jul 9, 2022 at 5:26 AM Dambaev Alexander < >>>>>>>>> [email protected]> wrote: >>>>>>>>> >>>>>>>>>> Hi, >>>>>>>>>> >>>>>>>>>> I had tried to implement function of type: >>>>>>>>>> >>>>>>>>>> ``` >>>>>>>>>> fun >>>>>>>>>> {a:t0p} >>>>>>>>>> isPrime >>>>>>>>>> ( xs: !stream_vt( int) >>>>>>>>>> , x: int >>>>>>>>>> ):<cloptr1> >>>>>>>>>> bool >>>>>>>>>> ``` >>>>>>>>>> >>>>>>>>>> Ie, I want to force evaluation of some portion of a stream, but I >>>>>>>>>> need to preserve it for a later use. >>>>>>>>>> >>>>>>>>>> I had tried to make a similar version: >>>>>>>>>> ``` >>>>>>>>>> fun >>>>>>>>>> {a:t0p} >>>>>>>>>> isPrime >>>>>>>>>> ( xs: stream_vt( int) >>>>>>>>>> , x: int >>>>>>>>>> ):<cloptr1> >>>>>>>>>> ( stream_vt( int), bool) >>>>>>>>>> ``` >>>>>>>>>> >>>>>>>>>> but failed as well, so I decided to ask for a direction if >>>>>>>>>> someone had tried to do similar stuff >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> You received this message because you are subscribed to the >>>>>>>>>> Google Groups "ats-lang-users" group. >>>>>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>>>>> send an email to [email protected]. >>>>>>>>>> To view this discussion on the web visit >>>>>>>>>> https://groups.google.com/d/msgid/ats-lang-users/CAHjn2KwFq7JH%2BiZE7bWCJ_L7oZ38K-kmGBFii7DZsdxWLDsGmg%40mail.gmail.com >>>>>>>>>> <https://groups.google.com/d/msgid/ats-lang-users/CAHjn2KwFq7JH%2BiZE7bWCJ_L7oZ38K-kmGBFii7DZsdxWLDsGmg%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>>>>>>>> . >>>>>>>>>> >>>>>>>>> -- >>>>>>>>> You received this message because you are subscribed to the Google >>>>>>>>> Groups "ats-lang-users" group. >>>>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>>>> send an email to [email protected]. >>>>>>>>> >>>>>>>> To view this discussion on the web visit >>>>>>>>> https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqp62MaoG8hugJ8h2mUt%2BsSAJ2eu6uRuJ%3D5nMOc4EbcfQ%40mail.gmail.com >>>>>>>>> <https://groups.google.com/d/msgid/ats-lang-users/CAPPSPLqp62MaoG8hugJ8h2mUt%2BsSAJ2eu6uRuJ%3D5nMOc4EbcfQ%40mail.gmail.com?utm_medium=email&utm_source=footer> >>>>>>>>> . >>>>>>>>> >>>>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "ats-lang-users" group. >>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>> send an email to [email protected]. >>>>>> >>>>> To view this discussion on the web visit >>>>>> https://groups.google.com/d/msgid/ats-lang-users/d87d273b-c937-40b8-ae6a-8846a9fbb801n%40googlegroups.com >>>>>> <https://groups.google.com/d/msgid/ats-lang-users/d87d273b-c937-40b8-ae6a-8846a9fbb801n%40googlegroups.com?utm_medium=email&utm_source=footer> >>>>>> . >>>>>> >>>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "ats-lang-users" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to [email protected]. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msgid/ats-lang-users/69a5b6f5-69e9-48dd-9b1d-aa164f9b0566n%40googlegroups.com >>>> <https://groups.google.com/d/msgid/ats-lang-users/69a5b6f5-69e9-48dd-9b1d-aa164f9b0566n%40googlegroups.com?utm_medium=email&utm_source=footer> >>>> . >>>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "ats-lang-users" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> >> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/ats-lang-users/CAHjn2Ky0URPmxCYFYQeT64KqcTxcLnRw7e4W0LKS8CAkqcdsjw%40mail.gmail.com >>> <https://groups.google.com/d/msgid/ats-lang-users/CAHjn2Ky0URPmxCYFYQeT64KqcTxcLnRw7e4W0LKS8CAkqcdsjw%40mail.gmail.com?utm_medium=email&utm_source=footer> >>> . >>> >> -- > You received this message because you are subscribed to the Google Groups > "ats-lang-users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/ats-lang-users/14f3697b-b90c-4c7a-9b14-c70e7205ed75n%40googlegroups.com > <https://groups.google.com/d/msgid/ats-lang-users/14f3697b-b90c-4c7a-9b14-c70e7205ed75n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "ats-lang-users" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/ats-lang-users/CAHjn2Ky1v9%3DNsO1fCAkmTJQ4%3DZ%2BEpwWS1gg0D9HUO5KQh%2B0DoA%40mail.gmail.com.
