river-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From MICHAEL MCGRADY <mmcgr...@topiatechnology.com>
Subject Re: datastructure classes
Date Wed, 15 Dec 2010 01:47:16 GMT

Here is an update from one of the authors of the PDF you cited.

Mr. McGrady,
In a paper on lock-free memory management (http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf)
I describe a variant of the lock-free algorithm in the PODC 1996, such that the memory used
by the nodes of the queue can be freed and reused arbitrarily.
My published work on concurrent algorithms since then is listed here (http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Michael:Maged_M=.html).

Examples include:
- Idempotent work stealing. PPOPP 2009: 45-54
- Practical Lock-Free and Wait-Free LL/SC/VL Implementations Using 64-Bit CAS. DISC 2004:
- Scalable lock-free dynamic memory allocation. PLDI 2004: 35-46
- Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Trans. Parallel Distrib.
Syst. 15(6): 491-504 (2004)
- High performance dynamic lock-free hash tables and list-based sets. SPAA 2002: 73-82
Please let me know if you have any questions.
Best regards,

On Dec 14, 2010, at 1:40 PM, Patricia Shanahan wrote:

> On 12/14/2010 8:37 AM, Gregg Wonderly wrote:
>> On 12/14/2010 1:36 AM, MICHAEL MCGRADY wrote:
>>> I would say that in addition to just be a fast data structure the data
>>> structure
>> > must be fast and accommodate synchronous and asynchronous backups,
>> partitions,
>> > and transactions.
>> This is an important issue from the perspective that there are two
>> scenarios that used to be supported by outrigger. A persistent and an
>> non-persistent version used to exist. The persistent version used PSE
>> for serialization to disk. That was a simple yet powerful mechanism. Due
>> to licensing (Sun paid for a distribution license), it was in a sense,
>> deprecated at the point of River being started.
>> For those that don't know about PSE, it used a post compilation bytecode
>> manipulator that looked for calls to a "start transaction" method, and
>> then found modification assignments to associated data structures, and
>> modified the byte code to set a "modified bit" on the associated data.
>> When "end transaction" was encountered, it stopped.
>> I think it would be a good idea to focus on the performance of the in
>> memory (messaging only type of application) version. The persistent
>> version is a completely different animal and requires some fairly
>> advanced features for managing all of the appropriate control points.
>> Making one code path do both can be somewhat challenging from an all out
>> performance perspective.
> Thanks for the useful background information.
> There is one slim hope I can see for a common code path, but it is a
> very long way off.
> My prejudice, subject to being convinced that another approach would be
> better, would be to try to map a persistent version to a relational
> database through SQL. Relational databases deal with transactions, ACID,
> distribution, and performance issues. There are a lot of options for
> users, more than for OO databases, at all price points starting at free.
> The way outrigger uses its FastList looks rather like a sort of
> simplified relational database, with each FastList instance representing
> a table and selects being done by linear scan of the table.
> If we made a persistent version use a relational database to represent
> the space, we could then experiment with performance run-offs between
> our best shot at an ad-hoc in-memory implementation, and what we get
> from the persistent version if we drop in an in-memory database
> implementation. If they come close, we could drop the ad-hoc
> implementation and focus all effort on the relational database version.
> It is a slim hope. Often, a custom tuned data structure will out-perform
> a specialization of a general data structure. In any case, I agree with
> working first on the in-memory version.
> Patricia

Michael McGrady
Chief Architect
Topia Technology, Inc.
Cel 1.253.720.3365
Work 1.253.572.9712 extension 2037

  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message