gmane.comp.java.jsr.166-concurrency

Re: Fork/Join Examples

Dr Heinz M. Kabutz — 2012-05-25T05:36:15

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Re: Fork/Join Examples

Joe Bowbeer — 2012-05-25T04:05:06

Thanks for the examples! I will certainly check them out.

Regarding a cache for recursive subdivision, search in JCiP and www for
Memoizer and you will find some of our attempts.
On May 24, 2012 3:41 PM, "Dr Heinz M. Kabutz" <heinz< at >javaspecialists.eu>
wrote:

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Fork/Join Examples

Dr Heinz M. Kabutz — 2012-05-24T22:33:57

In my latest newsletter, I show two examples how we can solve a problem 
faster using Fork/Join.  The first is Fibonacci, but a better recursive 
algorithm than is found in the JavaDocs.  However, this sum-of-squares 
algorithm requires us to do multiplication which is particularly bad 
with BigInteger.  I thus also implemented the Karatsuba multiplication 
algorithm, including a way to do it with the Fork/Join framework.

I also implemented a FibonacciCache.  I believe that caching should 
maybe be solved in general for the recursive decomposition approach with 
RecursiveTask.  In my cache, if one thread tries to do work with which 
another thread is already busy, then he waits until the other thread has 
completed his task.  This prevents duplication of work.  I bet that this 
is a common problem with recursive decomposition algorithms.  Have any 
of you thought of writing a cache that solves this problem in general 
and then making that available in the JDK?

Also, could we *please* change the example in

Re: synchronization based on a key

Dimitris Andreou — 2012-05-24T18:22:00

Yes. Basically you choose a point in the trade-off of "how much memory
you're willing to spend on lock stripes" vs "how many accidental collisions
(different keys mapped to the same lock) you can tolerate".

The other option is whether you want to preallocate all locks (and get a
compact representation for them; viable for small sets of stripes, but not
if you want millions of them), or allocate them dynamically (needs a
ConcurrentMap and the overhead is higher)

On Thu, May 24, 2012 at 10:48 AM, bhm <bheem< at >sbcglobal.net> wrote:

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Re: synchronization based on a key

bhm — 2012-05-24T17:48:30

Thanks.

If I understand this correctly, this keeps a collection of lock
objects (Lock/Semaphore/ReadWriteLock) and smear method can map
multiple keys to same index and
so same lock and amount of concurrency is contained by the size of
collection of lock objects (eager or lazy)

On Thu, May 24, 2012 at 12:13 PM, Dimitris Andreou
<jim.andreou< at >gmail.com> wrote:

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Re: synchronization based on a key

Dimitris Andreou — 2012-05-24T16:13:16

http://code.google.com/p/guava-libraries/issues/detail?id=859#c11

The file attached to the linked comment might end up in guava, and deals
with this very problem.
On May 24, 2012 7:27 AM, "bhm" <bheem< at >sbcglobal.net> wrote:

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Re: synchronization based on a key

√iktor Ҡlang — 2012-05-24T15:56:22


Wow, I'd never do that.
How about just having a map from String to Semaphore?

Cheers,
√

Re: synchronization based on a key

R.A. Porter — 2012-05-24T15:46:53

How about a simpler approach:

void foo(String key) {
  synchronized(key.intern()) {
    // process this key
  }
}

-r


On Thu, May 24, 2012 at 7:22 AM, bhm <bheem< at >sbcglobal.net> wrote:

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

synchronization based on a key

bhm — 2012-05-24T14:22:37

I have a method that needs to be synchronized based on a key passed as
parameter, that is, for same key multiple threads shouldn't be
running. Following is what I did--


static final ConcurrentMap<String,Boolean> IN_PROGRESS =
   new ConcurrentHashMap<String,Boolean>();

void foo(String key){
    if(null == IN_PROGRESS.putIfAbsent(key, Boolean.TRUE)){
      // no other thread is processing this key
      try{
          // process this key
      } finally {
         // done with processing this key
         IN_PROGRESS.remove(key)
      }
    } else {
      // some other thread is running this key, discard it
    }
}

this works if I need to discard the request to process the key from
thread t1 when another thread, t2, is processing that key.

I need help to do following-
make thread t1 wait while t2 is processing the key and resume t1 when
t2 is finish processing same key.

I'm aware that if there are multiple threads t1,t3,t4.. etc waiting
for t2 to finish anyone of these thread can wake up and start
proce

Re: Quest for the optimal queue

√iktor Ҡlang — 2012-05-24T12:53:20

Hi Andriy,

On Thu, May 24, 2012 at 2:21 PM, Andriy Plokhotnyuk
<plokhotnyuk< at >gmail.com>wrote:



The task will not be rescheduled while it is still running.

Cheers,
√

Re: Quest for the optimal queue

Andriy Plokhotnyuk — 2012-05-24T12:21:03

Hi All,

Thank you, Michael, for sharing idea how to minimize access to volatile
variables.

Here is my attempt to use one of Dmitriy Vyukov's version of multi producer
/ single consumer node based queue in implementation of Scalaz actor instead
of ConcurrentLinkedQueue:
https://github.com/plokhotnyuk/actors/blob/master/src/main/scala/com/github/plokhotnyuk/actors/Actor2.scala

Your hints allowed to improve throughput in ~3x times and decrease latency
on ~20% comparing to Scalaz actor that uses CLQ, here are simple benchmarks
and their results:
https://github.com/plokhotnyuk/actors/blob/master/src/test/scala/com/github/plokhotnyuk/actors/ScalazActor2Test.scala
https://github.com/plokhotnyuk/actors/blob/master/out1.txt#L252

Also I found that the same approach cannot be easy applied for custom
implementations of Akka mailboxes:
https://github.com/plokhotnyuk/actors/blob/master/src/main/scala/com/github/plokhotnyuk/actors/UnboundedMailbox2.scala
https://github.com/plokhotnyuk/actors/blob/master/out1.txt#L48

Re: ForkJoinPool does not achieve expectedparallelism

Romain Colle — 2012-05-23T09:25:38

Thanks for the explanation and the quick fix!
Romain

On Wed, May 23, 2012 at 1:17 AM, Doug Lea <dl< at >cs.oswego.edu> wrote:

Re: ForkJoinPool does not achieve expected parallelism

Doug Lea — 2012-05-22T23:17:50

Thanks for the nicely conceived test case!
The problem was lack of a secondary signalling check
(present in previous versions) that isn't now needed
for submissions queues, but sometimes is otherwise.
This is now in updated CVS and jar files.


It allows some parallelization of signalling, by
letting other threads help with wakeups when
they find work.

-Doug

ForkJoinPool does not achieve expectedparallelism

Romain Colle — 2012-05-22T16:20:47

Hi Doug and all,

Using the latest version of the ForkJoinPool available on the jsr166y
website, we ran into an issue/regression with our existing code base.

In our code, we have a single task that scans a fairly large fact table
while applying some filtering conditions. Any row that passes this
condition must then be processed.
The pattern that we use is that the scanning task saves (in an array) the
rows that passed the condition and forks a processing task as soon as we
have enough rows to process (say 1024).
We expect that these processing tasks will be picked up (i.e. stolen) by
the other threads in the pool and executed while we continue scanning and
filtering.
Unrelated to the current issue, we have a completion phase at the end of
the scanning that ensures all the forked tasks have been executed.

To sum it up, we have a single task that scans some data and forks lots of
processing task.
Previously (with the version from a few months back without the worker
queues), this was working perfectly and al

Re: CallerRunsOrRejects for JDK8?

√iktor Ҡlang — 2012-05-21T17:43:12

On Mon, May 21, 2012 at 7:19 PM, Aleksey Shipilev <
aleksey.shipilev< at >gmail.com> wrote:


Problem is all the baggage of ExecutorService. :/

Cheers,
√

Re: CallerRunsOrRejects for JDK8?

Aleksey Shipilev — 2012-05-21T17:19:09

I had always had a feeling this is the difference between
Executor.execute() and ExecutorService.submit(). submit() should not
allow to do caller-runs unless explicitly told so by rejection policy.
I would anticipate lots of people are betting on that.

-Aleksey.

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Re: a volatile bug?

Kirk Pepperdine — 2012-05-21T08:19:16

Didn't mean to imply this was going to be easy nor error prone. I fully appreciate the difficulties. But we are dealing with a class of bugs that are statistical in nature.. those stats change based on a uncontrollable number of environmental conditions which implies the problem is intractable. That said, we still must test and if the problem has moved from one of a binary (worked, didn't work) to a statistical one, it seems that the testing must move in that direction also... agreed it cannot be perfect but that's no reason for not starting.

For example, I had a biased locking bench that failed occasionally. By making numerous runs I was able to detect cases where the biased locking optimization wasn't applied. All I could sort out is there was some sort of race condition that was affected by were the JVM was loaded into memory.. pure speculation but that was one variable that differed between runs. If I could speculate more, my guess is that there was an underlying time sensitive optimization that some ti

Re: What's mean TLR?

Rémi Forax — 2012-05-21T07:56:44

ThreadLocalRandom :)


cheers,
Rémi

What's mean TLR?

Min Zhou — 2012-05-21T07:43:42

Hi, all

Here is some lines of comments in ThreadLocalRandom.java

    // Padding to help avoid memory contention among seed updates in
    // different TLRs in the common case that they are located near
    // each other.

What's the above TLR short for ?

Thanks,
Min

Re: a volatile bug?

David Holmes — 2012-05-20T22:48:31

My point was that it is very difficult to write tests that trigger different compilation strategies. As it stands unless people play with the compiler strategies via -XX options then these tests will always behave the same way in that regard, so the coverage is not what you might think.

David



_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

Re: a volatile bug?

Kirk Pepperdine — 2012-05-20T17:34:55

I've been rooting around at the hardware level and the best testing idea I've been able to come up with is to treat this stuff as a "trait". Test coverage for this stuff is utterly impossible. I think the best one can do is as you suggested, write the tests, make them statistical in nature and then make it easily available so that the community can run the test them selves. I see this tactic as necessary evil in the future of testing.

Regards,
Kirk

On 2012-05-20, at 7:21 PM, Boehm, Hans wrote:



_______________________________________________
Concurrency-interest mailing list
Concurrency-interest< at >cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest