Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #11127 > unrolled thread

Atomic integer array class question

Back to article view | Back to comp.lang.java.programmer

Contents

  Atomic integer array class question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-09 07:10 -0800
    Re: Atomic integer array class question Knute Johnson <nospam@knutejohnson.com> - 2012-01-09 07:45 -0800
      Re: Atomic integer array class question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-09 08:17 -0800
        Re: Atomic integer array class question Patricia Shanahan <pats@acm.org> - 2012-01-09 10:56 -0800
          Re: Atomic integer array class question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-10 06:22 -0800
            Re: Atomic integer array class question Roedy Green <see_website@mindprod.com.invalid> - 2012-01-10 06:52 -0800
            Re: Atomic integer array class question Lew <noone@lewscanon.com> - 2012-01-10 07:17 -0800
            Re: Atomic integer array class question Patricia Shanahan <pats@acm.org> - 2012-01-10 07:43 -0800
            Re: Atomic integer array class question markspace <-@.> - 2012-01-10 08:37 -0800

#11127 — Atomic integer array class question

Does the atomic integer array class treat each individual element in
the array separately?

Would an array of size 10 have the same performance as an array of
AtomicIntegers of size 10, in terms of accesses to one element
affecting accesses to another element?

[toc] | [next] | [standalone]

#11128

On 1/9/2012 7:10 AM, raphfrk@gmail.com wrote:
> Does the atomic integer array class treat each individual element in
> the array separately?
>
> Would an array of size 10 have the same performance as an array of
> AtomicIntegers of size 10, in terms of accesses to one element
> affecting accesses to another element?

Read the package description for java.util.concurrent.atomic to get a 
good idea of what the Atomic variables are.  But no the performance will 
not be as good as a regular array.

Why don't you post something about what you are really going to do with 
the array and maybe somebody can give you a better idea of what way to go.

-- 

Knute Johnson

[toc] | [prev] | [next] | [standalone]

#11129

On Jan 9, 3:45 pm, Knute Johnson <nos...@knutejohnson.com> wrote:
> Read the package description for java.util.concurrent.atomic to get a
> good idea of what the Atomic variables are.  But no the performance will
> not be as good as a regular array.

Sorry, I wasn't clear, I didn't mean compared to a regular array.

AtomicIntegerArray intArray = new AtomicIntegerArray(10);

compared to

AtomicInteger[] intArray = new AtomicInteger[10];

If 2 writes happen to an AtomicIntegerArray, but at different
locations, do they interfere?

> Why don't you post something about what you are really going to do with
> the array and maybe somebody can give you a better idea of what way to go.

I was wondering if having writes to an array happen one at a time
would be slower than an AtomicIntegerArray.

Something like (though not actually for int arrays, as then I would
just use AtomicIntegerArray)

private final int UNSTABLE = 0;
int[] array = new int[1000];
AtomicInteger sequence = new AtomicInteger(1);

public void set(int index, int value) {
    while (true) {
        int oldSequence = sequence.getAndSet(UNSTABLE);
        if (oldSequence == UNSTABLE) {
            continue;
        }
        array[index] = value;
        sequence.set(oldSequence + 2);
        return;
    }
}

public void get(int index) {
    while (true) {
        int initialSequence = sequence.get();
        if (localSequence == UNSTABLE) {
            continue;
        }
        int value = array[index];
        int finalSequence = sequence.get();
        if (initialSequence != finalSequence) {
            continue;
        }
        return value;
    }
}

So, the effect is that writes happen one at a time.  If a thread sets
the sequence number to UNSTABLE, then all other writers will
spinlock.  Also, if any element is changed, then all readers will
detect it and have to retry (even though their data was actually not
changed).

[toc] | [prev] | [next] | [standalone]

#11136

On 1/9/2012 8:17 AM, raphfrk@gmail.com wrote:
> On Jan 9, 3:45 pm, Knute Johnson<nos...@knutejohnson.com>  wrote:
>> Read the package description for java.util.concurrent.atomic to get a
>> good idea of what the Atomic variables are.  But no the performance will
>> not be as good as a regular array.
>
> Sorry, I wasn't clear, I didn't mean compared to a regular array.
>
> AtomicIntegerArray intArray = new AtomicIntegerArray(10);
>
> compared to
>
> AtomicInteger[] intArray = new AtomicInteger[10];
>
> If 2 writes happen to an AtomicIntegerArray, but at different
> locations, do they interfere?
>
>> Why don't you post something about what you are really going to do with
>> the array and maybe somebody can give you a better idea of what way to go.
>
> I was wondering if having writes to an array happen one at a time
> would be slower than an AtomicIntegerArray.

I don't understand this comment. Each AtomicIntegerArray operation
refers to a specific element, so writes must happen one at a time anyway.

>
> Something like (though not actually for int arrays, as then I would
> just use AtomicIntegerArray)
>
> private final int UNSTABLE = 0;
> int[] array = new int[1000];
> AtomicInteger sequence = new AtomicInteger(1);
>
> public void set(int index, int value) {
>      while (true) {
>          int oldSequence = sequence.getAndSet(UNSTABLE);
>          if (oldSequence == UNSTABLE) {
>              continue;
>          }

Spin waiting, especially spin waiting that has no delay and includes
access to a volatile variable, can be very expensive in terms of load on
the processor-memory interconnect.

I would do some benchmarking, but are you sure this is better than
synchronization?

>          array[index] = value;
>          sequence.set(oldSequence + 2);
>          return;
>      }
> }
>
> public void get(int index) {
>      while (true) {
>          int initialSequence = sequence.get();
>          if (localSequence == UNSTABLE) {
>              continue;
>          }
>          int value = array[index];
>          int finalSequence = sequence.get();
>          if (initialSequence != finalSequence) {
>              continue;
>          }
>          return value;
>      }
> }
>
> So, the effect is that writes happen one at a time.  If a thread sets
> the sequence number to UNSTABLE, then all other writers will
> spinlock.  Also, if any element is changed, then all readers will
> detect it and have to retry (even though their data was actually not
> changed).

I'm still unclear what is intent, and what is infrastructure to do with
how you are trying to implement the intent. Could you provide a
description of what you want to have happen?

Patricia

[toc] | [prev] | [next] | [standalone]

#11169

On Jan 9, 6:56 pm, Patricia Shanahan <p...@acm.org> wrote:
> Spin waiting, especially spin waiting that has no delay and includes
> access to a volatile variable, can be very expensive in terms of load on
> the processor-memory interconnect.

So, add a Thread.sleep(1); or something ?

> I'm still unclear what is intent, and what is infrastructure to do with
> how you are trying to implement the intent. Could you provide a
> description of what you want to have happen?

It's basically a store that has 3 parts per element

id (short)
data (short)
auxData (Object)

However, for most places (say 95%+), it is (0, 0, null), so it really
only needs only a short.

I am planning to have a short array for the main store.  That will be
based on AtomicInteger and storing two shorts per index (it uses
compareAndSet to allow one short out of the int to be updated
atomically).

I also plan to reserve some of the short values as indexes into a
second array.

This array will store AtomicInteger (sequence number), int (both
shorts), Object.  (The AtomicInteger is one from an
AtomicIntegerArray)

Then the set and gets will be something like

set(int index, short id) {
  if (isReserved(index)) {
      set(index, id, 0, null);
  } else {
      setRaw(index, id);
  }
}

setRaw(int index, short id) {
  short oldId = shortArray.getAndSet(index, id);
  if (isReserved(oldId)) {
    // oldId is actually an index into the aux store
    auxStore.remove(oldId);
  }
}

set(int index, short id, short data, Object o) {
  int newId = auxStore.add(id, data, o);
  setRaw(index, newId);
}

Gets, which pull a non-reserved short, don't have/need the sequence
numbers.

However, for complex read operations on the object, the process would
read the sequence number before and after the read to make sure it is
stable.  Also, the sequence number has a reserved "UNSTABLE" value
when updates are actually happening.  As long as the sequence number
is not UNSTABLE before or after the read and the two numbers are
equal, then it was a safe read.

The main reason for the question was that I was wondering if having
writes to the store using a write lock would slow things down.
However, using a sequence number system works just as well and means
that I can use AtomicIntegerArray directly anyway.

[toc] | [prev] | [next] | [standalone]

#11172

On Tue, 10 Jan 2012 06:22:31 -0800 (PST), "raphfrk@gmail.com"
<raphfrk@gmail.com> wrote, quoted or indirectly quoted someone who
said :

>
>So, add a Thread.sleep(1); or something ?

In general any such code you write will either have horrible
performance or will fail under some pathological set of conditions.
You are much better to use the well tested concurrency classes written
by genetic mutants.

See http://mindprod.com/jgloss/thread.html
and get a copy of the concurrency book with the three trains on the
cover.
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
If you can't remember the name of some method, 
consider changing it to something you can remember.
 

[toc] | [prev] | [next] | [standalone]

#11176

raphfrk@gmail.com wrote:
> Patricia Shanahan wrote:
>> Spin waiting, especially spin waiting that has no delay and includes
>> access to a volatile variable, can be very expensive in terms of load on
>> the processor-memory interconnect.
>
> So, add a Thread.sleep(1); or something ?

No, don't poll.  You put lipstick on a pig, it's still a pig.

-- 
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg

[toc] | [prev] | [next] | [standalone]

#11177

On 1/10/2012 6:22 AM, raphfrk@gmail.com wrote:
> On Jan 9, 6:56 pm, Patricia Shanahan<p...@acm.org>  wrote:
>> Spin waiting, especially spin waiting that has no delay and includes
>> access to a volatile variable, can be very expensive in terms of load on
>> the processor-memory interconnect.
>
> So, add a Thread.sleep(1); or something ?

I'm not at all sure you basic approach makes sense.

>
>> I'm still unclear what is intent, and what is infrastructure to do with
>> how you are trying to implement the intent. Could you provide a
>> description of what you want to have happen?
>
> It's basically a store that has 3 parts per element
>
> id (short)
> data (short)
> auxData (Object)
>
> However, for most places (say 95%+), it is (0, 0, null), so it really
> only needs only a short.
>
> I am planning to have a short array for the main store.  That will be
> based on AtomicInteger and storing two shorts per index (it uses
> compareAndSet to allow one short out of the int to be updated
> atomically).
...

My premature optimization detector is clicking rapidly. You are still
talking about a particular implementation, not what you want the
implementation to achieve.

Patricia

[toc] | [prev] | [next] | [standalone]

#11179

On 1/10/2012 6:22 AM, raphfrk@gmail.com wrote:

> I am planning to have a short array for the main store.  That will be
> based on AtomicInteger and storing two shorts per index (it uses
> compareAndSet to allow one short out of the int to be updated
> atomically).
>
> I also plan to reserve some of the short values as indexes into a
> second array.


I want to echo Patricia's comments and say that you still haven't 
explained what it is you are trying to do, what problem you are trying 
to solve.  This clearly describes an implementation, not the design goal 
at hand.

What do these ints ultimately represent?  Items for sale?  Customer 
purchases?  Factory assemblies?

Also, similar to Patricia, my bullshit meter is beeping loudly.  In 
fact, I see the extra large manure shovel has automatically deployed, 
and the rubber hip boots have dropped from the ceiling.  You're design 
is so obfuscated that even knowing your design goal it's likely to be an 
unmaintainable mess.  Expect to be chastised by any other programmer who 
sees this disaster.

You might want to back up and just do the obvious, like store a bunch of 
simple data objects in a synchronized collection.  I'd think that would 
be faster than what you have, as well as infinitely more maintainable.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web