[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

New interesting application of Transactional Memory for single-threading

Dmitriy V'jukov

10/23/2008 7:25:00 PM

While dealing with Transactional Memory I realize new interesting
application of Transactional Memory for SINGLE threaded applications.
Atomicity guarantees provided by TM can be useful not only for multi-
threaded environment, but also for single-threaded environment. Well,
it's actually not astonishing, nevertheless I don't hear anything
similar in all that hype around TM.

Assume we have complicated operation which involves non-trivial
modifications of several objects/containers. Assume that exception can
be thrown either by memory allocator, or by copy constructor of some
object, or just by application logic. In order to provide strong
exception safety in such situation we have to manually write code for
cancellation of all those modifications. This can be non-trivial error-
prone task.

TM already has all necessary machinery for cancellation of arbitrary
operations. TM doesn't care about complexity of operations, number of
involved objects/containers, it can just instantly cancel anything
which happens inside atomic block. Why don't use it?

So the general recipe for strong exception safety with the help of TM:
wrap arbitrary operation in atomic block, if the case of error just
abort transaction. Hocus-pocus! Your operation obtains strong
exception safety at once w/o single line of code!

This can be equally applied to exceptions and errors codes/return
values, no matter.

Here is something which I was actually able to model with Intel C++
STM Compiler:

// object which "sometimes" throws exception in copy ctor
bool fail_bad_int = false;
int fail_bad_int_step = 8;

__declspec(tm_callable)
struct bad_int
{
bad_int(int v = 0)
: v(v)
{}

bad_int& operator = (bad_int r)
{
if (fail_bad_int && 0 == --fail_bad_int_step)
throw 0;
v = r.v;
return *this;
}

operator int () const
{
return v;
}

bool operator < (bad_int r) const
{
return v < r.v;
}

int v;
};

// transactional sort function
template<typename T>
__declspec(tm_callable)
void sort(T* begin, T* end)
{
T temp;
size_t n = end - begin;
if (n < 2)
return;
bool swapped = false;
do
{
swapped = false;
n -= 1;
for (size_t i = 0; i != n; ++i)
{
if (begin[i + 1] < begin[i])
{
temp = begin[i];
begin[i] = begin[i + 1];
begin[i + 1] = temp;
swapped = true;
}
}
}
while (swapped);
}

int main()
{
std::vector<bad_int> x;
std::generate_n(std::back_inserter(x), 10, rand);
std::copy(x.begin(), x.end(),
std::ostream_iterator<int>(std::cout, " \t"));
std::cout << std::endl;

fail_bad_int = true;
bad_int* begin = &*x.begin();
bad_int* end = begin + x.size();
__tm_atomic
{
try
{
sort(begin, end);
}
catch (...)
{
__tm_abort;
}
}

std::copy(x.begin(), x.end(),
std::ostream_iterator<int>(std::cout, " \t"));
std::cout << std::endl;
}



Output:

41 18467 6334 26500 19169 15724 11478 29358 26962 24464
41 18467 6334 26500 19169 15724 11478 29358 26962 24464

And if I comment __tm_abort statement out, then output is:

41 18467 6334 26500 19169 15724 11478 29358 26962 24464
41 6334 18467 19169 26500 26500 11478 29358 26962 24464

Notice that in latter case array is in some intermediate state. And in
former case array is in initial state.

Although one has to understand that this method can incur substantial
run-time (space and time) overheads even if exception is not thrown.
On the other hand it's extremely simple and not error prone (i.e. you
can not forget to cancel some things or cancel incorrectly). So this
approach can be used on cold-paths or on initial development stage.

I see that Intel C++ STM Compiler has execution mode called 'serial
atomic', which used for serialized transactions which have abort
statements. Serial atomic mode can be used to hasten such single-
threaded usage of TM. I.e. TM run-time only has to log writes, no need
for synchronization, quiescence, verification etc.

--
Regards,
Dmitriy V'jukov

Relacy Race Detector: Make your synchronization correct!
http://groups.google.ru/group/...
5 Answers

Ian Collins

10/23/2008 7:33:00 PM

0

Dmitriy V'jukov wrote:
> While dealing with Transactional Memory I realize new interesting
> application of Transactional Memory for SINGLE threaded applications.
> Atomicity guarantees provided by TM can be useful not only for multi-
> threaded environment, but also for single-threaded environment. Well,
> it's actually not astonishing, nevertheless I don't hear anything
> similar in all that hype around TM.
>
> Assume we have complicated operation which involves non-trivial
> modifications of several objects/containers. Assume that exception can
> be thrown either by memory allocator, or by copy constructor of some
> object, or just by application logic. In order to provide strong
> exception safety in such situation we have to manually write code for
> cancellation of all those modifications. This can be non-trivial error-
> prone task.
>
> TM already has all necessary machinery for cancellation of arbitrary
> operations. TM doesn't care about complexity of operations, number of
> involved objects/containers, it can just instantly cancel anything
> which happens inside atomic block. Why don't use it?
>
But what's new about this use? Database transactions have been used for
this for a long time now.

--
Ian Collins

Dmitriy V'jukov

10/23/2008 8:12:00 PM

0

On Oct 23, 11:32 pm, Ian Collins <ian-n...@hotmail.com> wrote:

> But what's new about this use?  Database transactions have been used for
> this for a long time now.

If everybody is already informed about such usage then sorry and just
ignore this post. Although for me it was new and I read tens of papers/
articles/presentations on TM...

Dmitriy V'jukov

Ian Collins

10/23/2008 8:25:00 PM

0

Dmitriy V'jukov wrote:
> On Oct 23, 11:32 pm, Ian Collins <ian-n...@hotmail.com> wrote:
>
>> But what's new about this use? Database transactions have been used for
>> this for a long time now.
>
> If everybody is already informed about such usage then sorry and just
> ignore this post. Although for me it was new and I read tens of papers/
> articles/presentations on TM...
>
TM is still in its infancy, but the use of transactions to ensure atomic
operations is well established.

I guess the most basic use in C++ is as an extension of RAII, which on
the surface performs the same function as your example.

--
Ian Collins

Jon Harrop

10/31/2008 5:58:00 PM

0

Ian Collins wrote:
> TM is still in its infancy...

In what sense? People started implementing it in dedicated hardware over two
decades ago...

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsulta...

Chris M. Thomasson

10/31/2008 6:15:00 PM

0

"Jon Harrop" <jon@ffconsultancy.com> wrote in message
news:MLmdnUEPGJ8ApZbUnZ2dnUVZ8v-dnZ2d@posted.plusnet...
> Ian Collins wrote:
>> TM is still in its infancy...
>
> In what sense?

Perhaps using it as general purpose software tool for "normal" programmers
who don't build database server infrastructures for a living.




> People started implementing it in dedicated hardware over two decades
> ago...

Indeed; IBM 801 comes to mind:

http://groups.google.com/group/comp.arch/msg/995379...