New interesting application of Transactional Memory for
single-threading
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/relacy/web