,
a full moon dayMSDN CLR Reusable Sample Codes
Last updated on
,
a full moon day
CLR Reusable Parallel Data Structure & Algorithm, for Microsoft .NET Framework(s), MSDN Magazine, June 2007; The following code modules are platform dependent, Microsoft only, however if modify, control flow, data flow, ... , can be used in any other platforms; In an era between binary to duo-binary ... ;
Since physical memories, virtual swap spaces a storage, ... are re-writable and volatile, in computing, assignment operator single equal sign = makes complexity; therefore 5W1H concept is a must, because 1 space of memory may contain N references, N type_value, N something, ... , those N of N becomes in action to compute and very difficult to understand in programming, however 1 time of time period may contain only 1 time ... makes easier;
MSDN reusable Await
public void Await() { // REMARK a function() as void i.e. void function_name() does not return value
bool sense = m_sense; // REMARK sense is defined as Boolean thus either T or F
// REMARK thread to signal; setting event;
if (m_count == 1 || Interlocked.Decrement(ref m_count) == 0) {
// REMARK passing m_count as reference into Interlocked's decrement function
m_count = m_originalCount;
m_sense = !sense; // REMARK reversing the sense, which has been assigned as Boolean type
if (sense == true) { // REMARK odd
m_evenEvent.Set();
m_oddEvent.Reset();
} else { // REMARK even
m_oddEvent.Set();
m_evenEvent.Reset();
}
} else {
SpinWait s = new SpinWait();
while (sense == m_sense) {
if (s.Spin() >= s_spinCount) {
if (sense == true) m_oddEvent.WaitOne();
else m_evenEvent.WaitOne();
}
}
}
} // REMARK MSDN reusable Await ends here
MSDN reusable Barrier
using System;
using System.Threading; // REMARK also see: Thread vs. Multithreaded CPU
public class Barrier {
private volatile int m_count;
private int m_originalCount;
private EventWaitHandle m_oddEvent;
private EventWaitHandle m_evenEvent;
// REMARK Usage even and odd refers to parity, check sum, ... ;
private volatile bool m_sense = false; // REMARK false == even, true == odd
public Barrier (int count) {
m_count = count;
m_originalCount = count;
m_oddEvent = new ManualResetEvent(false);
m_evenEvent = new ManualResetEvent(false);
}
public void Await() {
bool sense = m_sense;
// REMARK thread to signal; also setting the event;
if (m_count == 1 || Interlocked.Decrement(ref m_count) == 0) {
m_count = m_originalCount;
m_sense = !sense;
// REMARK reversing the sense, which has been assigned as Boolean type
if (sense == true) { // REMARK odd
m_evenEvent.Reset();
m_oddEvent.Set();
} else { // REMARK even
m_oddEvent.Reset();
m_evenEvent.Set();
}
} else {
if (sense == true) m_oddEvent.WaitOne();
else m_evenEvent.WaitOne();
}
}
} // REMARK MSDN reusable Barrier ends here
MSDN reusable BlockingQueue
class Cell <T> {
internal T m_obj; // REMARK obj stands for object
internal Cell(T obj) { m_obj = obj; }
}
public class BlockingQueue<T> {
// REMARK before understanding the term Blocking
// REMARK 1st to understand conditional variable, mutexes, semaphores, ...
// REMARK 2nd to understand flag behavior alike the most important 2nd Time & Lunar Gravitational
private Queue<Cell<T>> m_queue = new Queue<Cell<T>>();
public void Enqueue(T obj) {
Cell<T> c = new Cell<T>(obj);
lock (m_queue) {
m_queue.Enqueue(c);
Monitor.Pulse(m_queue);
Monitor.Wait(m_queue);
}
}
public T Dequeue() {
Cell<T> c;
lock (m_queue) {
while (m_queue.Count == 0)
// REMARK 1st to understand CountdownLatch's count
// REMARK 2nd to understand semaphores
// REMARK 3rd to understand block, lock, wait, ... IFF count == null
Monitor.Wait(m_queue);
c = m_queue.Dequeue();
Monitor.Pulse(m_queue);
}
return c.m_obj;
}
} // REMARK MSDN reusable BlockingQueue ends here
MSDN reusable BoundedBuffer
public class BoundedBuffer<T> {
private Queue<T> m_queue = new Queue<T>();
private int m_consumersWaiting;
private int m_producersWaiting;
private const int s_maxBufferSize = 128;
public void Enqueue(T obj) {
lock (m_queue) {
while (m_queue.Count == s_maxBufferSize - 1)) {
m_producersWaiting++;
Monitor.Wait(m_queue);
m_producersWaiting--;
}
m_queue.Enqueue(obj);
if (m_consumersWaiting > 0)
Monitor.PulseAll(m_queue);
}
}
public T Dequeue() {
T e; // REMARK local variable e is defined as T
lock (m_queue) {
while (m_queue.Count == 0) {
m_consumersWaiting++;
Monitor.Wait(m_queue);
m_consumersWaiting--;
}
e = m_queue.Dequeue();
if (m_producersWaiting > 0)
Monitor.PulseAll(m_queue);
}
return e;
}
} // REMARK MSDN reusable BoundedBuffer ends here
MSDN reusable CountdownLatch
public class CountdownLatch { // REMARK counting semaphore in concurrency
private int m_remain;
private EventWaitHandle m_event;
public CountdownLatch(int count) {
m_remain = count;
m_event = new ManualResetEvent(false);
}
public void Signal() {
// REMARK the last thread to signal which also sets event
if (interlocked.Decrement(ref m_remain) == 0)
m_event.Set();
}
public void Wait() {
m_event.WaitOne();
}
} // REMARK MSDN reusable CountdownLatch ends here
MSDN reusable ForAll // REMARK it is recommended not to know all, also see: Servers;
public static void ForAll(int from, int to, Action<int> a, int p) { // REMARK also see: static configuration;
ForAll<int>(null, from, to, null, a, p);
}
public static void ForAll<T>(IList<T> data, Action<T> a, int p) {
ForAll<T>(data, 0, data.Count, a, null, p);
}
private static void ForAll<T>(IList<T> data, int from, int to, Action<T> a0, Action<int> a1, int p) {
int size = from - to;
int stride = (size + p - 1) / p;
CountdownLatch latch = new CountdownLatch(p);
// REMARK usamyanmar.net recommends less pin count design
// REMARK for example, SHARP PC with Transmeta to SONY PC with AMD, Intel, ...
for (int i = 0; i < p; i++) { // REMARK for control loop with adder adding 1
int idx = i;
ThreadPool.QueueUserWorkItem(delegate {
int end = Math.Min(size, stride * (idx + 1)); // REMARK Math class' Reduction Min
for (int j = stride * idx; j < end; j++) { // REMARK for control loop with adder adding stride * idx
if (data != null) a0(data[j]); // REMARK array is used because offset of array is needed
else a1(j);
}
latch.Signal(); // REMARK latch's frequency, on the other hand, not latch's architecture
});
}
latch.Wait();
} // REMARK MSDN reusable ForAll ends here
MSDN reusable LockFreeStack
public class LockFreeStack<T> {
private volatile StackNode<T> m_head;
public void Push(T item) {
// REMARK item as type_value T to a stack, by pushing, also see: from a stack
StackNode<T> node = new StackNode<T>(item);
StackNode<T> head;
do {
head = m_head;
node.m_next = head;
} while (m_head != head || Interlocked.CompareExchange(ref m_head, node, head) != head);
}
public T Pop() {
// REMARK whatever value from a stack, by popping, also see: to a stack
StackNode<T> head;
SpinWait s = new SpinWait();
while (true) {
StackNode<T> next;
do {
head = m_head;
if (head == null) goto emptySpin; // REMARK IFF no head
next = head.m_next;
} while (m_head != head || Interlocked.CompareExchange(ref m_head, next, head) != head);
// REMARK head and next are previously defined as StackNode<T>
break; // because goto jumps and skips
s.Spin(); //REMARK SpinWait.Spin() returns old_count
}
return head.m_value;
}
}
class StackNode<T> {
internal T m_value;
internal StackNode<T> m_next;
internal StackNode(T val) {m_value = val; }
} // REMARK MSDN reusable LockFreeStack ends here
MSDN reusable Reduce
public delegate T Func<T>(T arg0, T arg1); // REMARK arguments
public static T Reduce<T>(IList<T> data, int p, T seed, Func<T> r){
T[] partial = new T[p];
int stride = (data.Count + p - 1) / p;
CountdownLatch latch = new CountdownLatch(p);
for (int i = 0; i < p; i++) { // REMARK for control loop with adder adding 1
int idx = i;
ThreadPool.QueueUserWorkItem(delegate {
partial[idx] = seed; // REMARK doing reduction in parallel
int end = Math.Min(data.Count, stride * (idx + 1)); // REMARK Math class' Reduction Min
for (int j = stride * idx; j < end; j++) // REMARK for control loop with adder adding stride * idx
partial[idx] = r(partial[idx], data[j]); // REMARK partial, because fuzzy logic exists, so partially ...
latch.Signal();
});
}
latch.Wait();
T final = seed; // REMARK master thread's final reduction
for (int i = 0; i < p; i++)
final = r(final, partial[i]);
return final;
} // REMARK MSDN reusable Reduce ends here
MSDN reusable SpinWait
public struct SpinWait {
private int m_count;
private static readonly bool s_isSingleProc = (Environment.ProcessorCount == 1);
private const int s_yieldFrequency = 4000; // REMARK also see: 4KB for 1 CPU;
private const int s_yieldOneFrequency = 3*s_yieldFrequency; // REMARK constant integer
public int Spin() {
int oldCount = m_count;
// REMARK On 1 CPU, ensure counter is a multiple of 's_yieldFrequency', thus yield every time
// REMARK Else, increment by one; also see: ThinEvent's set() function's setting m_state
m_count += (s_isSingleProc ? s_yieldFrequency : 1);
// REMARK If not a multiple of 's_yieldFrequency' spin (w/ backoff)
int countModFrequency = m_count % s_yieldFrequency;
if (countModFrequency > 0)
Thread.SpinWait ((int) (1 + (countModFrequency * 0.05f)));
// REMARK 0.05f might be related to Thermal EMF
else
Thread.Sleep(m_count <= s_yieldOneFrequency ? 0 : 1);
// REMARK binary operator either Zero or One might be related to parity bit, regular bit, ... ;
return oldCount; // REMARK after computing m_count
}
private void Yield() {
Thread.Sleep(m_count < s_yieldOneFrequency ? 0 : 1);
}
} // REMARK MSDN reusable SpinWait ends here
MSDN reusable ThinEvent
public struct ThinEvent {
// REMARK 3 internal local functions such as Set, Reset, Wait, ... to compute Thin Event's stateAQ
private int m_state; // Unset is zero, Set is one; m_state is defined as integer data-type
private EventWaitHandle m_eventObj;
private const int s_spinCount = 4000; // REMARK also see: 4KB for 1 CPU;
public void Set() { // REMARK a function() as void i.e. void function_name() does not return value
m_state = 1; // REMARK if bit, 1 is either TRUE, Magnet, High, On, ... ; if value, 1 is integer one;
Thread.MemoryBarrier(); // REMARK MSDN's standard requirement
if (m_eventObj != null) // REMARK IFF something exists; != is not equal to, not assign to, ... ;
m_eventObj.Set();
}
public void Reset() { // REMARK a function() as void i.e. void function_name() does not return value
m_state = 0;
// REMARK in Set() function, Thread.MemoryBarrier() is needed
// REMARK inside this Reset() function, Thread.MemoryBarrier() is not needed
// REMARK 1st to understand semaphores, ... ;
if (m_eventObj != null) // REMARK IFF something exists
m_eventObj.Reset();
}
public void Wait() { // REMARK a function() as void i.e. void function_name() does not return value
// REMARK local variable s is defined as SpinWait
SpinWait s = new SpinWait();
while (m_state == 0) { // REMARK while m_state is equal to zero
// REMARK WHICH means resetting function Reset() is true
// REMARK the following line might be counting 4K, after 4K, after 4K, until ...
if (s.Spin() >= s_spinCount) {
if (m_eventObj == null) {
ManualResetEvent newEvent = new ManualResetEvent(m_state == 1);
if (Interlocked.CompareExchange<EventWaitHandle>(ref m_eventObj, newEvent, null) == null) {
// REMARK event object sets flag
if (m_state == 1)
m_eventObj.Set();
} else {
// REMARK using only event
newEvent.Close();
}
}
m_eventObj.WaitOne();
}
}
}
} // REMARK MSDN reusable ThinEvent ends here
|
|
|
 |
|
