Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Data structure to keep things in memory

Reply
Thread Tools

Data structure to keep things in memory

 
 
ClassCastException
Guest
Posts: n/a
 
      11-29-2010
On Sun, 28 Nov 2010 10:12:51 -0800, Mike Schilling wrote:

> "ClassCastException" <(E-Mail Removed)> wrote in message
> news:icta6n$av9$(E-Mail Removed)-september.org...
>> On Sun, 28 Nov 2010 01:56:40 -0800, Mike Schilling wrote:
>>
>>> "ClassCastException" <(E-Mail Removed)> wrote in message
>>> news:ict651$av9$(E-Mail Removed)-september.org...
>>>> On Sun, 28 Nov 2010 00:09:40 -0800, Mike Schilling wrote:
>>>>
>>>>> Without going into all the details, I have the following situation:
>>>>>
>>>>> There are a set of objects RTS, all of the same type, that gather
>>>>> run-time statistics about the running of a program. Various related
>>>>> objects with different lifecycles pass them around and use them.
>>>>> I'm interested in when each member of RTS is no longer being
>>>>> updated, because I want to collect its final statistics , but
>>>>> there's no good way to tell when it's no longer in use except via
>>>>> its collection, so when it's created I attach a weak reference to it
>>>>> and associate the weak reference with a queue. When the reference
>>>>> is delivered, I record the statistics. [1]
>>>>>
>>>>> So far so good. The question is, what's the best way to keep the
>>>>> references in memory until they can be delivered to the queue?
>>>>> Obviously, I could put them into a synchronized HashSet, but I'd
>>>>> prefer to optimize for concurrency by minimizing locking. At the
>>>>> moment, I'm using a ConcurrentHashMap, since it seems to give the
>>>>> best concurrency for updates. (The usage pattern is a bit unusual,
>>>>> since there are effectively no lookups. There's a put() when the
>>>>> reference is created, and a remove() when it's pulled out of the
>>>>> reference queue.) This is an area where I have very little
>>>>> experience, so I'd welcome input from anyone who's worked with these
>>>>> classes.
>>>>>
>>>>> 1. Obviously, a member of RTS points to a separate statistics object
>>>>> which is also pointed to by the weak reference.
>>>>
>>>> The RTS object won't be collected, and so won't end up on the
>>>> reference queue, if it's held in a hashmap.
>>>
>>> Isn’t it clear that it's the *references* that are in the Map?

>>
>> Not from his post, it wasn't.

>
>>>>> The question is, what's the best way to keep the ***references*** in
>>>>> memory until they can be delivered to the queue? Obviously, I could
>>>>> put them into a synchronized HashSet


I see a lot of quoted text but no original text. In particular, I *don't*
see any addressing of the following point:

"He only mentioned RTSs and WeakReferences in particular. If he just had
RTSs and WeakReference<RTS>s, he had a problem either way: if the RTSs
are in the map the WeakReferences never get enqueued, and if they're not,
by the time one's enqueued the associated RTS object is gone
irretrievably. Using the proposed RTSHandle allows to detect when the
RTS's *other* references are gone before losing the RTS."
 
Reply With Quote
 
 
 
 
Mike Schilling
Guest
Posts: n/a
 
      11-29-2010


"ClassCastException" <(E-Mail Removed)> wrote in message
news:icv9de$3u0$(E-Mail Removed)-september.org...
> On Sun, 28 Nov 2010 10:12:51 -0800, Mike Schilling wrote:
>
>> "ClassCastException" <(E-Mail Removed)> wrote in message
>> news:icta6n$av9$(E-Mail Removed)-september.org...
>>> On Sun, 28 Nov 2010 01:56:40 -0800, Mike Schilling wrote:
>>>
>>>> "ClassCastException" <(E-Mail Removed)> wrote in message
>>>> news:ict651$av9$(E-Mail Removed)-september.org...
>>>>> On Sun, 28 Nov 2010 00:09:40 -0800, Mike Schilling wrote:
>>>>>
>>>>>> Without going into all the details, I have the following situation:
>>>>>>
>>>>>> There are a set of objects RTS, all of the same type, that gather
>>>>>> run-time statistics about the running of a program. Various related
>>>>>> objects with different lifecycles pass them around and use them.
>>>>>> I'm interested in when each member of RTS is no longer being
>>>>>> updated, because I want to collect its final statistics , but
>>>>>> there's no good way to tell when it's no longer in use except via
>>>>>> its collection, so when it's created I attach a weak reference to it
>>>>>> and associate the weak reference with a queue. When the reference
>>>>>> is delivered, I record the statistics. [1]
>>>>>>
>>>>>> So far so good. The question is, what's the best way to keep the
>>>>>> references in memory until they can be delivered to the queue?
>>>>>> Obviously, I could put them into a synchronized HashSet, but I'd
>>>>>> prefer to optimize for concurrency by minimizing locking. At the
>>>>>> moment, I'm using a ConcurrentHashMap, since it seems to give the
>>>>>> best concurrency for updates. (The usage pattern is a bit unusual,
>>>>>> since there are effectively no lookups. There's a put() when the
>>>>>> reference is created, and a remove() when it's pulled out of the
>>>>>> reference queue.) This is an area where I have very little
>>>>>> experience, so I'd welcome input from anyone who's worked with these
>>>>>> classes.
>>>>>>
>>>>>> 1. Obviously, a member of RTS points to a separate statistics object
>>>>>> which is also pointed to by the weak reference.
>>>>>
>>>>> The RTS object won't be collected, and so won't end up on the
>>>>> reference queue, if it's held in a hashmap.
>>>>
>>>> Isn’t it clear that it's the *references* that are in the Map?
>>>
>>> Not from his post, it wasn't.

>>
>>>>>> The question is, what's the best way to keep the ***references*** in
>>>>>> memory until they can be delivered to the queue? Obviously, I could
>>>>>> put them into a synchronized HashSet

>
> I see a lot of quoted text but no original text.


There was no need for new text, because it was all explained in the original
post.

> In particular, I *don't*
> see any addressing of the following point:
>
> "He only mentioned RTSs and WeakReferences in particular. If he just had
> RTSs and WeakReference<RTS>s, he had a problem either way: if the RTSs
> are in the map the WeakReferences never get enqueued, and if they're not,
> by the time one's enqueued the associated RTS object is gone
> irretrievably.


That is, the problem handled by

>>>1. Obviously, a member of RTS points to a separate statistics object
>>> which is also pointed to by the weak reference.



 
Reply With Quote
 
 
 
 
ClassCastException
Guest
Posts: n/a
 
      11-29-2010
On Sun, 28 Nov 2010 21:29:13 -0800, Mike Schilling wrote:

> "ClassCastException" <(E-Mail Removed)> wrote in message
> news:icv9de$3u0$(E-Mail Removed)-september.org...
>> In particular, I *don't*
>> see any addressing of the following point:
>>
>> "He only mentioned RTSs and WeakReferences in particular. If he just
>> had RTSs and WeakReference<RTS>s, he had a problem either way: if the
>> RTSs are in the map the WeakReferences never get enqueued, and if
>> they're not, by the time one's enqueued the associated RTS object is
>> gone irretrievably.

>
> That is, the problem handled by
>
>>>>1. Obviously, a member of RTS points to a separate statistics object
>>>> which is also pointed to by the weak reference.


You mean, the problem *not* handled by

>>>>1. Obviously, a member of RTS points to a separate statistics object
>>>> which is also pointed to by the weak reference.


If the WR points to the actual statistics object you want to keep, it can
never be dequeued and then the statistics object dumped to a log (or
whatever you want done with it), because the WR won't be enqueued before
that object ceases to exist.

You appeared, in other words, to propose

WR
\
\
_\|
_ stats
/|
/
/
handle

while you actually need


WR ---> handle ---> stats

so the handle can become collectable (and thus the WR get enqueued) while
the stats object is still live. Everything in your system holds the stats
object only via the handle object except the CHM, which maps from WR
directly to stats object and keeps the stats object alive without
stopping the handle from being collectable when the stats object is no
longer in use anywhere else. Your queue consumer thread periodically
wakes up, polls the reference queue, and if it finds a reference uses
remove() to yank the stats object out of the map, uses the stats object
for its final task (whatever that is -- logging it somewhere?), and then
lets its reference to it lapse so the GC can claim the stats object
itself. (And the WR.)

Clear now?
 
Reply With Quote
 
ClassCastException
Guest
Posts: n/a
 
      11-29-2010
On Mon, 29 Nov 2010 09:42:48 +0000, ClassCastException wrote:

> On Sun, 28 Nov 2010 21:29:13 -0800, Mike Schilling wrote:
>
>> "ClassCastException" <(E-Mail Removed)> wrote in message
>> news:icv9de$3u0$(E-Mail Removed)-september.org...
>>> In particular, I *don't*
>>> see any addressing of the following point:
>>>
>>> "He only mentioned RTSs and WeakReferences in particular. If he just
>>> had RTSs and WeakReference<RTS>s, he had a problem either way: if the
>>> RTSs are in the map the WeakReferences never get enqueued, and if
>>> they're not, by the time one's enqueued the associated RTS object is
>>> gone irretrievably.

>>
>> That is, the problem handled by
>>
>>>>>1. Obviously, a member of RTS points to a separate statistics object
>>>>> which is also pointed to by the weak reference.

>
> You mean, the problem *not* handled by
>
>>>>>1. Obviously, a member of RTS points to a separate statistics object
>>>>> which is also pointed to by the weak reference.

>
> If the WR points to the actual statistics object you want to keep, it
> can never be dequeued and then the statistics object dumped to a log (or
> whatever you want done with it), because the WR won't be enqueued before
> that object ceases to exist.
>
> You appeared, in other words, to propose
>
> WR
> \
> \
> _\|
> _ stats
> /|
> /
> /
> handle
>
> while you actually need
>
>
> WR ---> handle ---> stats
>
> so the handle can become collectable (and thus the WR get enqueued)
> while the stats object is still live. Everything in your system holds
> the stats object only via the handle object except the CHM, which maps
> from WR directly to stats object and keeps the stats object alive
> without stopping the handle from being collectable when the stats object
> is no longer in use anywhere else. Your queue consumer thread
> periodically wakes up, polls the reference queue, and if it finds a
> reference uses remove() to yank the stats object out of the map, uses
> the stats object for its final task (whatever that is -- logging it
> somewhere?), and then lets its reference to it lapse so the GC can claim
> the stats object itself. (And the WR.)
>
> Clear now?


Oh, I should probably add -- there's no guarantee a particular object
will ever get GC'd before VM shutdown. If you want every stats object to
eventually be processed, you'll also want an orderly shutdown process
that stops everything else (including, as its penultimate step, the queue
consumer thread) and then goes over the CHM's .values() Collection
calling the stats-processing-thingie on each one still in there before
actually returning/System.exit()ing.
 
Reply With Quote
 
Steven Simpson
Guest
Posts: n/a
 
      11-29-2010
On 28/11/10 20:43, Mike Schilling wrote:
> "Steven Simpson" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)2s.com...
>> Maybe you can get away with a ConcurrentMap<Key, RTSUser>, if you want
>> to avoid synchronization:

>
> ConcurrentMap is what I'm using. The consensus seems to be that it's
> the best choice.


I understand your OP better now. Basically, it seems you already had
the structures we were talking about:

> 1. Obviously, a member of RTS points to a separate statistics object
> which is also pointed to by the weak reference.


Your RTS is the RTSHandle. Your 'separate statistics object' is RTSImpl.

>> So you need a container of RTSUsers. That was served by the
>> Map<Reference<RTSHandle>, RTSImpl> in ClassCastException's original
>> suggestion, and a Collection<RTSUser> will suffice here.


Your weak reference is my RTSUser. You're using a ConcurrentMap (of
<Reference<RTS>, Boolean>, I presume) as a kind of set, which
corresponds to the Collection<RTSUser> above, used to hang on to references.

Actually, you must have extended WeakReference in order to point it
(strongly) at the separate statistics object...? Or you're already
using a ConcurrentMap<Reference<RTS>, SeparateStatisticsObject> as CCE
suggested.

> (The usage pattern is a bit unusual, since there are effectively no
> lookups. There's a put() when the reference is created, and a
> remove() when it's pulled out of the reference queue.)


To make it a little less unusual, can you afford to use
Collections.newSetFromMap here, since you're only using normal puts and
removes?

 
Reply With Quote
 
Tom Anderson
Guest
Posts: n/a
 
      11-29-2010
On Sun, 28 Nov 2010, Mike Schilling wrote:

> Without going into all the details, I have the following situation:
>
> There are a set of objects RTS, all of the same type, that gather run-time
> statistics about the running of a program. Various related objects with
> different lifecycles pass them around and use them. I'm interested in when
> each member of RTS is no longer being updated, because I want to collect its
> final statistics , but there's no good way to tell when it's no longer in use
> except via its collection, so when it's created I attach a weak reference to
> it and associate the weak reference with a queue. When the reference is
> delivered, I record the statistics. [1]
>
> So far so good. The question is, what's the best way to keep the references
> in memory until they can be delivered to the queue?


Extend the references to make them nodes in a doubly-linked list - give
them forward and back pointers to others of their kind. Put a pointer to a
reference somewhere in the rootset, perhaps right next to the reference
queue. When you create a reference, add it to the list. When you pull a
dead reference off the queue, remove it from the list - because the
reference itself is the link, this can be done directly, without needing
to do a lookup.

You can make the removal code slightly neater with the old trick of
hanging the list off a fake head/tail link which never gets removed, to
avoid having to special-case removing the true head or tail. I'm sure you
know that, but i mention it for completeness.

Both addition and removal need to be protected by locks. Adding something
to the list involves reading one pointer and storing three, with
essentially no computation, so although there may be contention for the
lock, it's unlikely to be a bottleneck. If it is, do what the concurrent
collections do, and stripe the work over multiple parallel lists. Removing
from the list shouldn't involve any contention, as removals will be well
spread out, and you may not even be removing in multiple threads.

I had a bit of a think about whether you could do this lock-free with
atomics, but i don't think it's a winning strategy; multiple threads
adding nodes to the same head will always compete, and if that doesn't
manifest as contention for a lock, it will manifest as retries in a
lock-free algorithm. Unless you can find a wait-free algorithm to do this;
i'll buy you a pint if you can.

tom

--
eggflip, brandy, bits of Tia Maria, Beecham's powder, aspirin,
Benedictine, Alka-Seltzer, black currant juice, a touch of mustard and
"other things"
 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      11-29-2010


"Steven Simpson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)2s.com...
> On 28/11/10 20:43, Mike Schilling wrote:
>> "Steven Simpson" <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed)2s.com...
>>> Maybe you can get away with a ConcurrentMap<Key, RTSUser>, if you want
>>> to avoid synchronization:

>>
>> ConcurrentMap is what I'm using. The consensus seems to be that it's
>> the best choice.

>
> I understand your OP better now. Basically, it seems you already had
> the structures we were talking about:
>
>> 1. Obviously, a member of RTS points to a separate statistics object
>> which is also pointed to by the weak reference.

>
> Your RTS is the RTSHandle. Your 'separate statistics object' is RTSImpl.
>
>>> So you need a container of RTSUsers. That was served by the
>>> Map<Reference<RTSHandle>, RTSImpl> in ClassCastException's original
>>> suggestion, and a Collection<RTSUser> will suffice here.

>
> Your weak reference is my RTSUser. You're using a ConcurrentMap (of
> <Reference<RTS>, Boolean>, I presume) as a kind of set, which
> corresponds to the Collection<RTSUser> above, used to hang on to
> references.
>
> Actually, you must have extended WeakReference in order to point it
> (strongly) at the separate statistics object...?


Yes.

> Or you're already using a ConcurrentMap<Reference<RTS>,
> SeparateStatisticsObject> as CCE
> suggested.
>
>> (The usage pattern is a bit unusual, since there are effectively no
>> lookups. There's a put() when the reference is created, and a
>> remove() when it's pulled out of the reference queue.)

>
> To make it a little less unusual, can you afford to use
> Collections.newSetFromMap here, since you're only using normal puts and
> removes?


That was introduced in 1.6, and I need it to compile with 1.5
>

 
Reply With Quote
 
Mike Schilling
Guest
Posts: n/a
 
      11-29-2010


"ClassCastException" <(E-Mail Removed)> wrote in message
news:icvsio$amg$(E-Mail Removed)-september.org...
> You appeared, in other words, to propose
>
> WR
> \
> \
> _\|
> _ stats
> /|
> /
> /
> handle
>
> while you actually need
>
>
> WR ---> handle ---> stats


It's not a question of proposing: It's all working. It looks like:

WR --> RTS --> statistics
--> statistics

When the RTS is collected, the WR is delivered and the statistics processed.




 
Reply With Quote
 
ClassCastException
Guest
Posts: n/a
 
      11-30-2010
On Mon, 29 Nov 2010 08:32:32 -0800, Mike Schilling wrote:

> "ClassCastException" <(E-Mail Removed)> wrote in message
> news:icvsio$amg$(E-Mail Removed)-september.org...
>> You appeared, in other words, to propose
>>
>> WR
>> \
>> \
>> _\|
>> _ stats
>> /|
>> /
>> /
>> handle
>>
>> while you actually need
>>
>>
>> WR ---> handle ---> stats

>
> It's not a question of proposing: It's all working. It looks like:
>
> WR --> RTS --> statistics
> --> statistics
>
> When the RTS is collected, the WR is delivered and the statistics
> processed.


That should work, then. Your original post didn't make the structure
clear, and indeed hinted at a different structure, one that wouldn't have
worked.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
keep things in place mcnewsxp HTML 16 07-29-2012 08:37 PM
Simple structure and copying data to pointer of the same structure A C++ 27 04-16-2011 11:07 PM
What are important things to keep very valuable data secure? 32andtwentyseven Computer Support 3 10-19-2007 06:49 PM
vs2005 publish website doing bad things, bad things =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?= ASP .Net 1 10-25-2006 06:18 PM
Memory allocation in Structure to Structure pra_ramli@rediffmail.com C++ 2 03-09-2006 05:51 AM



Advertisments