Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Scaling issues in STM

3 views
Skip to first unread message

Joe Seigh

unread,
Mar 11, 2008, 9:10:36 PM3/11/08
to
A quick write up on scaling problems in STM.

The basic problem is most operations on data are read-modify-write. That is the
value or values stored back into the data are dependent on the read values. And
the problem with the read values is that there can be a lot of them. This is a
problem since the likelihood of interference increases with the number of reads.
Most STM implementations appear to have modifying reads, the reads actually
modify storage usually with an atomic operation. This makes them expensive as
well.

Let's take a worse case example. A singly linked list with O(n) insert and delete
costs. In order to access a node in the list, you will have to read on average n/2
predecessor nodes to access a given node. For any two concurrent transactions
on this list, the predecessor nodes of one will be a subset of the other and cause
transaction interference. So you won't make forward progress unless your
transactions do not overlap (at least for obstruction-free implementations).

One thing that would help is if you were using PDR to manage the nodes, is to
not track the reads and for deletes just update the forward pointer in the predecessor
node and store null into the forward pointer pointer of the deleted node. You only
have 2 rather localized stores in this case and a lower likelihood of interference.
This should work since no predecessor node could be removed from the list without
nulling its forward pointer first. If you have DCAS instead of STM, that would work
as well. The problem with this is it's not the STM implementation that knows about
this trick so it can't know which reads to ignore and which ones not to.

If you're thinking if just making this a rule for all node type operations in arbitrary
data structures, implement a class that splits out sublists from linked lists. That
node trick won't work. So no silver bullet there.

So given that most large applications will have a lot of reads to access data unless
most of your data are single objects pointed to by static global pointers, it's not
at all clear yet that STM will scale very well. Or you will have an STM implementation
that is only usable by expert programmers who know what they are doing.


--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

Dmitriy V'jukov

unread,
Mar 17, 2008, 5:55:10 AM3/17/08
to
On Mar 12, 4:10 am, Joe Seigh <jseigh...@xemaps.com> wrote:
> A quick write up on scaling problems in STM.
>
> The basic problem is most operations on data are read-modify-write. That is the
> value or values stored back into the data are dependent on the read values. And
> the problem with the read values is that there can be a lot of them. This is a
> problem since the likelihood of interference increases with the number of reads.
> Most STM implementations appear to have modifying reads, the reads actually
> modify storage usually with an atomic operation. This makes them expensive as
> well.

What do you think about obstruction-free STM which uses something like
sequence lock to track reads? Sequence number can be global, or per
memory location, or global hashed array. This way reads are not
modifying.

Dmitriy V'jukov

Dmitriy V'jukov

unread,
Mar 17, 2008, 5:59:24 AM3/17/08
to
On Mar 12, 4:10 am, Joe Seigh <jseigh...@xemaps.com> wrote:

> One thing that would help is if you were using PDR to manage the nodes, is to
> not track the reads and for deletes just update the forward pointer in the predecessor
> node and store null into the forward pointer pointer of the deleted node. You only
> have 2 rather localized stores in this case and a lower likelihood of interference.
> This should work since no predecessor node could be removed from the list without
> nulling its forward pointer first. If you have DCAS instead of STM, that would work
> as well. The problem with this is it's not the STM implementation that knows about
> this trick so it can't know which reads to ignore and which ones not to.

What do you think about approach when I will use STM/HTM only to
implement DCAS, and then use only DCAS to implement lists/queues etc?
Is it promising?
This obviously falls into 'expert programmers' case, because it's the
same 'lock-free' programming.

Dmitriy V'jukov

Dmitriy V'jukov

unread,
Mar 17, 2008, 6:31:22 AM3/17/08
to
On Mar 12, 4:10 am, Joe Seigh <jseigh...@xemaps.com> wrote:

Is all this applicable only to STM? Or to HTM too?
It seems that HTM already in the pipeline:
http://blogs.sun.com/dave/resource/transact08-dice.pdf

Dmitriy V'jukov

0 new messages