[racket] Using future and touch

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/389836cc/attachment-0001.html>