How can I make a universal construction more efficient?
- by VF1
A "universal construction" is a wrapper class for a sequential object that enables it to be linearized (a strong consistency condition for concurrent objects). For instance, here's an adapted wait-free construction, in Java, from [1], which presumes the existence of a wait-free queue that satisfies the interface WFQ (which only requires one-time consensus between threads) and assumes a Sequential interface:
public interface WFQ<T> // "FIFO" iteration
{
int enqueue(T t); // returns the sequence number of t
Iterable<T> iterateUntil(int max); // iterates until sequence max
}
public interface Sequential
{
// Apply an invocation (method + arguments)
// and get a response (return value + state)
Response apply(Invocation i);
}
public interface Factory<T> { T generate(); } // generate new default object
public interface Universal extends Sequential {}
public class SlowUniversal implements Universal
{
Factory<? extends Sequential> generator;
WFQ<Invocation> wfq = new WFQ<Invocation>();
Universal(Factory<? extends Sequential> g) { generator = g; }
public Response apply(Invocation i)
{
int max = wfq.enqueue(i);
Sequential s = generator.generate();
for(Invocation invoc : wfq.iterateUntil(max))
s.apply(invoc);
return s.apply(i);
}
}
This implementation isn't very satisfying, however, since it presumes determinism of a Sequential and is really slow. I attempted to add memory recycling:
public interface WFQD<T> extends WFQ<T>
{ T dequeue(int n); } // dequeues only when n is the tail, else assists other threads
public interface CopyableSequential extends Sequential { CopyableSequential copy(); }
public class RecyclingUniversal implements Universal
{
WFQD<CopyableSequential> wfqd = new WFQD<CopyableSequential>();
Universal(CopyableSequential init) { wfqd.enqueue(init); }
public Response apply(Invocation i)
{
int max = wfqd.enqueue(i);
CopyableSequential cs = null;
int ctr = max;
for(CopyableSequential csq : wfq.iterateUntil(max))
if(--max == 0) cs = csq.copy();
wfqd.dequeue(max);
return cs.apply(i);
}
}
Here are my specific questions regarding the extension:
Does my implementation create a linearizable multi-threaded version of a CopyableSequential?
Is it possible extend memory recycling without extending the interface (perhaps my new methods trivialize the problem)?
My implementation only reduces memory when a thread returns, so can this be strengthened?
[1] provided an implementation for WFQ<T>, not WFQD<T> - one does exist, though, correct?
[1] Herlihy and Shavit, The Art of Multiprocessor Programming.
