I've submitted a pull request fixing those errors and supporting running in serial mode.
One thing I notice is that it's substantially faster than `vector-sort!` even when run in serial mode on traditional Racket (but not on Racket CS), so perhaps this should be integrated (or there are improvements that we can adopt). Alex, just to clarify a couple things about futures: they block when performing operations that are either sensitive to the current continuation or need single-threaded access to the runtime. Vector operations, as you see in Dominik's code, are not in this category. Mutable hash table operations are blocking. Here's some numbers with performance on sorting a vector with random fixnums using this package on a 4 core machine with hyperthreading, "classic" is `vector-sort!`. Note that the futures-sort library creates 2^k futures. k: 0 cpu time: 3402 real time: 3399 gc time: 45 k: 1 cpu time: 3487 real time: 1834 gc time: 46 k: 2 cpu time: 3581 real time: 1097 gc time: 69 k: 4 cpu time: 5745 real time: 1014 gc time: 69 k: 8 cpu time: 5742 real time: 992 gc time: 45 k: 16 cpu time: 8111 real time: 2189 gc time: 279 'classic cpu time: 4390 real time: 4388 gc time: 98 Here are similar numbers for Racket CS: k: 0 cpu time: 2960 real time: 2960 gc time: 33 k: 1 cpu time: 3021 real time: 1594 gc time: 33 k: 2 cpu time: 3462 real time: 1154 gc time: 36 k: 4 cpu time: 4381 real time: 929 gc time: 36 k: 8 cpu time: 4406 real time: 889 gc time: 34 k: 16 cpu time: 7124 real time: 1655 gc time: 440 'classic cpu time: 2749 real time: 2749 gc time: 51 On Mon, Oct 7, 2019 at 8:17 PM Alex Harsanyi <alexharsa...@gmail.com> wrote: > > Hi Dominik, > > I tried to use your package and you are missing a dependency for the > `scribble-math` package in your info.rkt file, this has to be installed > separately otherwise your package won't install. > > However, I tried to use the `vector-futures-sort!` function and got an error: > > > (vector-futures-sort! #(3 1 7 6 4) <) > . . vector-futures-sort!: broke its own contract > promised: vector? > produced: #<void> > in: the res result of > (->i > ((unsorted vector?)) > ((compare procedure?)) > (res vector?)) > contract from: <pkgs>/futures-sort/main.rkt > blaming: <pkgs>/futures-sort/main.rkt > (assuming the contract is correct) > at: <pkgs>/futures-sort/main.rkt:40.2 > > > > I would also be interested to know what performance gains did you get by using > futures. I experimented with futures a few years ago and noticed that they > will block when accessing shared data structures. My understanding is that > all the futures will wait for each other while trying to access and set > elements in the vector and this the execution will be mostly serial with no > performance gains. I am curious if anything has changed with regards to this > in the last few years. > > Alex. > > On Monday, October 7, 2019 at 9:01:25 PM UTC+8, Dominik Pantůček wrote: >> >> Hello, >> >> over the course of past few months I have been tasked with solving a >> (real-world) problem of sorting the sums of all possible combinations of >> numbers. Some boring accounting stuff revolving around invoices. As the >> total number of combinations is 2^N where N is the number of source >> numbers, this task got "interesting" once there were more than 24 >> numbers - that is on my laptop with: >> >> model name : Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz >> >> 4 cores, 8 hyper-threads and 16GB RAM. >> >> Long story short, I had to implement a custom merge-sort for fxvectors >> and managed to leverage futures for fully parallel execution. Now in >> some spare time, I slightly polished the code and released it as >> "futures-sort" package. >> >> The source code is available on GitHub[1] and it is already in Racket >> package index[2]. >> >> The package provides four sorting functions - two for vector? and two >> for fxvector?. There are two variants of each, one with progress >> reporting and one without. For the original task I needed to show >> progress using racket/gui gauge% and it might be helpful for others >> (it's just a callback that gets current and total number of merges >> performed regularly). >> >> I would really appreciate any feedback regarding the naming conventions, >> code style and generally anything else. >> >> Yes, the tests are not there (yet). >> >> The same algorithm without futures runs on par with Racket's default >> sorting routines (tested for sets upto 2^30 - only 16G of memory here) >> and for fixnums it is even (very slightly but consistently) faster than >> vector-sort alone. With parallelism using futures it runs roughly N >> times faster where N is the number reported by (processor-count). >> >> I have already some benchmark results available and once I get more data >> I am more than happy to share it as well. >> >> The parallelism is configurable as parameter. >> >> And yes, all of this can be seen in the documentation which is included >> but I still have to look into how to build it - I was sort of assuming >> this works automatically based on what I see for example in >> scribble-math[3][4]. Any help with getting this right is also more than >> welcome. >> >> >> Lastly - thanks go out to Jens Axel Søgaard for pointing out that >> fixnums and fxvectors might help (and why) and also to other helpful >> folks on #racket at Freenode. >> >> >> Cheers, >> Dominik >> >> >> [1] https://github.com/dzoep/futures-sort >> [2] https://pkgd.racket-lang.org/pkgn/package/futures-sort >> [3] https://docs.racket-lang.org/scribble-math/index.html >> [4] https://pkgd.racket-lang.org/pkgn/package/scribble-math >> > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/racket-users/cc4e09cd-e968-4edf-8046-90e3cadb38fb%40googlegroups.com. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAK%3DHD%2BZj15veWA8gE6RdjJsBiWkQ43Yf13iiJW2md618cssWSg%40mail.gmail.com.
