[racket] Using future and touch

Yes, that's the point: parallelism (for speed) and concurrency (for ease of
programming) are completely different things and a progress meter needs
only the latter, which is very well supported in Racket via events and
threads and friends.

Continuing what Carl wrote: in addition to the GC issues, there are also
serious issues with making the runtime system safe for parallelism. Our
research papers on futures and places explain this in a little more detail.

http://www.eecs.northwestern.edu/~robby/pubs/papers/oopsla2010-stdff.pdf

http://www.eecs.northwestern.edu/~robby/pubs/papers/dls2010-tsffd.pdf

Robby



On Fri, Jul 26, 2013 at 1:36 AM, Carl Eastlund <cce at ccs.neu.edu> wrote:

> Joe,
>
> There are multiple concurrency and parallelism tools in Racket.  If you
> want concurrency but aren't concerned about parallelism, there are software
> threads in Racket that will all run in the same OS thread (
> http://docs.racket-lang.org/reference/threads.html).  If you want a tool
> that supports both concurrency and parallelism, there are places, which
> each run in a separate OS thread but have limited communication with each
> other (http://docs.racket-lang.org/reference/places.html).  What you're
> using, futures, are a mechanism for parallelism without concurrency -- they
> simulate deterministic, sequential behavior by only running in parallel as
> long as known-pure operations are used, which is why so many operations
> cause them to stop running in parallel (
> http://docs.racket-lang.org/reference/futures.html).
>
> Racket does not currently have what many other languages do, which is a
> thread library that uses native OS threads with shared memory.  As I
> understand the issue, we have avoided that primarily because it complicates
> the garbage collector's job, and often requires a "stop the world" approach
> to garbage collection.  Hopefully one of the options above will suffice for
> your project.
>
> Carl Eastlund
>
> On Fri, Jul 26, 2013 at 12:43 AM, Joe Gilray <jgilray at gmail.com> wrote:
>
>> Hi Robby,
>>
>> Please pardon my ignorance, but is there an easy to use thread library
>> with Racket?  I've used threads in other environments and I don't recall so
>> many restrictions.
>>
>> For example, how would you do something like a %-done meter if you have
>> very limited ability to instrument the code you are metering?
>>
>> Thanks,
>> -Joe
>>
>>
>> On Thu, Jul 25, 2013 at 5:40 PM, Robby Findler <
>> robby at eecs.northwestern.edu> wrote:
>>
>>> hashes are definitely not future-safe, unfortunately.
>>>
>>> Robby
>>>
>>>
>>> On Thu, Jul 25, 2013 at 6:50 PM, Joe Gilray <jgilray at gmail.com> wrote:
>>>
>>>> Here is an update:
>>>>
>>>> I rewrote gcd and used a hash-table for the squares check.  The
>>>> hash-table change sped up the sequential code about 10x!  Then I tried
>>>> using future / touch and it seems to improve the performance a little, but
>>>> there is quite a bit of blocking (on >= and hash-ref) still.
>>>>
>>>> New code below.
>>>>
>>>> -Joe
>>>>
>>>> ; function that searches for progressive numbers for a given range of b
>>>> values
>>>> (define (find-progressive-num2 b-start b-end b-incr lim ht)
>>>>   (define (mgcd a b) (if (= b 0) a (mgcd b (modulo a b))))
>>>>    (for/sum ([b (in-range b-start b-end b-incr)])
>>>>     (let loopa ([a (add1 b)] [suma 0])
>>>>       (cond
>>>>         [(> (mgcd a b) 1) (loopa (add1 a) suma)]
>>>>         [(>= (* a a a b) lim) suma]
>>>>         [else
>>>>          (let loopc ([c 1] [sumc 0])
>>>>            (define n (+ (* a a a c c b) (* c b b)))
>>>>            (cond
>>>>              [(>= n lim) (loopa (add1 a) (+ suma sumc))]
>>>>              [(hash-has-key? ht n) (loopc (add1 c) (+ sumc n))]
>>>>               [else (loopc (add1 c) sumc)]))]))))
>>>>
>>>> ;(require future-visualizer)
>>>> (define (euler141b)
>>>>   (define lim 1000000000000)
>>>>   (define ht (make-hash))
>>>>   (for ([i (in-range 1 1000000)]) (hash-set! ht (sqr i) 1))
>>>>   ; (visualize-futures
>>>>   (let ([f1 (future (λ () (find-progressive-num2 1 1000 4 lim ht)))]
>>>>         [f2 (future (λ () (find-progressive-num2 2 1000 4 lim ht)))]
>>>>         [f3 (future (λ () (find-progressive-num2 3 1000 4 lim ht)))])
>>>>     (+ (find-progressive-num2 4 1000 4 lim ht) (touch f1) (touch f2)
>>>> (touch f3))))
>>>>
>>>>
>>>> On Wed, Jul 24, 2013 at 9:46 PM, Robby Findler <
>>>> robby at eecs.northwestern.edu> wrote:
>>>>
>>>>> You might try places. Writing your own gcd seems straightforward. I'm
>>>>> not sure about integer-sqrt?, tho. Maybe you could make a table or
>>>>> something if you know there are not that many numbers.
>>>>>
>>>>> Or maybe someone will adjust the runtime to make those future safe!
>>>>>
>>>>> Robby
>>>>>
>>>>>
>>>>> On Wed, Jul 24, 2013 at 11:34 PM, Joe Gilray <jgilray at gmail.com>wrote:
>>>>>
>>>>>> So I should write my own (gcd   ) and (square?   ) functions?
>>>>>>
>>>>>> I can try that, but isn't there a simple way to use threads?
>>>>>>
>>>>>> Thanks,
>>>>>> -Joe
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Wed, Jul 24, 2013 at 7:47 PM, Robby Findler <
>>>>>> robby at eecs.northwestern.edu> wrote:
>>>>>>
>>>>>>> When I run this, the future visualizer shows that gcd and
>>>>>>> square-number? block the futures. square-number? is implemented in TR and
>>>>>>> if you take it, you find that integer-sqrt also blocks the futures. I'm not
>>>>>>> sure if those functions can be made to run safely in futures or not.
>>>>>>>
>>>>>>> Robby
>>>>>>>
>>>>>>>
>>>>>>> On Wed, Jul 24, 2013 at 7:26 PM, Joe Gilray <jgilray at gmail.com>wrote:
>>>>>>>
>>>>>>>> I have a ProjectEuler problem that I wanted to speed up so I
>>>>>>>> thought I would try to speed it up with future / touch.
>>>>>>>>
>>>>>>>> I tried the following:
>>>>>>>>
>>>>>>>> ; function that searches for progressive numbers for a given range
>>>>>>>> of b values
>>>>>>>> (define (find-progressive-num b-start b-end b-incr lim)
>>>>>>>>   (for/sum ([b (in-range b-start b-end b-incr)])
>>>>>>>>     (let loopa ([a (add1 b)] [suma 0])
>>>>>>>>       (cond
>>>>>>>>         [(> (gcd a b) 1) (loopa (add1 a) suma)]
>>>>>>>>         [(>= (* a a a b) lim) suma]
>>>>>>>>         [else
>>>>>>>>          (let loopc ([c 1] [sumc 0])
>>>>>>>>            (define n (+ (* a a a c c b) (* c b b)))
>>>>>>>>            (cond
>>>>>>>>              [(>= n lim) (loopa (add1 a) (+ suma sumc))]
>>>>>>>>              [(square-number? n) (loopc (add1 c) (+ sumc n))]
>>>>>>>>              [else (loopc (add1 c) sumc)]))]))))
>>>>>>>>
>>>>>>>> ; ProjectEuler problem #141
>>>>>>>> ; n = q * d + r
>>>>>>>> ; q/d = d/r = a/b (where a and b are relatively prime)
>>>>>>>> ; so d = a*r/b and q = a^2 * r / b^2
>>>>>>>> ; since a and b are coprime r must be divisible by b^2 or r = c*b^2
>>>>>>>> ; substituting: d = a*c*b and q = a^2*c
>>>>>>>> ; n = a^3 * c^2 * b + c * b^2
>>>>>>>> (define (euler141)
>>>>>>>>   (define lim 10000000000)
>>>>>>>>   (let ([f1 (future (λ () (find-progressive-num 1 1000 2 lim)))])
>>>>>>>>     (+ (find-progressive-num 2 1000 2 lim) (touch f1))))
>>>>>>>>
>>>>>>>> Unfortunately this runs no faster than the sequential version.  I
>>>>>>>> tried using the future-visualizer but I couldn't understand what it was
>>>>>>>> telling me (I guess some operation is blocking).  I also tried finer
>>>>>>>> grained threads (one for each value of b), but that did no better.
>>>>>>>>
>>>>>>>> Can anyone give me some pointers to successfully using future /
>>>>>>>> touch?
>>>>>>>>
>>>>>>>> Thanks,
>>>>>>>> -Joe
>>>>>>>>
>>>>>>>> ____________________
>>>>>>>>   Racket Users list:
>>>>>>>>   http://lists.racket-lang.org/users
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>> ____________________
>>   Racket Users list:
>>   http://lists.racket-lang.org/users
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130726/93f340f5/attachment-0001.html>