WPF and data multithreading deadlocks.

WPF & Multithreading

In designing applications, it may be advantageous to run data processing methods on a separate thread from the UI. This allows greater responsiveness in the application and takes advantage of concurrent computation.

The cornerstone interface to any binding in WPF is INotifyPropertyChanged, which is implemented on a data structure's different properties. Although this can be the source of deadlocks if the data structure is being processed on a separate thread where locks are explicitly implemented by the developer.

A deadlock could occur if some UI event was being triggered on a data structure (eg. expanding a view, changing a text box entry) while the data thread was processing it with an acquired lock. Internally, the PropertyChanged event will call a Dispatcher.Invoke on the UI. Although the UI could be waiting for the lock to release on that same property that the data thread already has, creating a cyclic dependency or deadlock.

The call stack for the UI thread. Note the wait call.

The call stack for the data thread.

Deadlock Scenario

As an example, suppose you have your standard WPF application UI thread and a separate data thread. The data thread polls a time stamp from a remote database and updates a class property called DataObject.Timestamp, which raises the PropertyChanged event. The property is also bound to a text box in our WPF application window, which is made visible in the window based on the user's preference (ie. collapsing and expanding a view).

In our deadlock example, the data thread puts a lock on the DataObject.Timestamp property while it updates it and other data structures. While this is happening, the view is expanded, causing the text box to start binding to the DataObject.Timestamp property and wait for an acquire of the lock that the data thread is holding. The data thread then sets the DataObject.Timestamp property inside the critical region code and the PropertyChanged event is raised. This causes the new time stamp value to be marshaled back onto the Dispatcher with a blocking/synchronous Dispatcher.Invoke call. Although the data thread now deadlocks in the critical region, waiting for the UI Dispatcher.Invoke to return, which is waiting on the data thread to release the lock.

Solution

To prevent the data thread's deadlock critical region from blocking on the Dispatcher.Invoke, override the OnPropertyChanged method to marshal the value asynchronously to the dispatcher.

protected override void OnPropertyChanged(string propertyName)
{
 Application.Current.Dispatcher.BeginInvoke(new Action(() => { base.OnPropertyChanged(propertyName); }));
}

This will ensure that the critical region doesn't block and the property changes are still serviced by the dispatcher.

Tips for Java performance on Android.

While Java may be a higher level language that makes code writeability easier, conventions must be broken when developing on Android to reap performance gains. This is especially true for games where logic and rendering must be done on a tight loop.

The Android developer page provides helpful tips for optimizing your Java code. Below are the optimizations that I have found to improve performance.

1. Front load memory allocation at startup instead of dynamically.

   We saw the largest performance gain here. The GC can kill performance in a CPU intensive application or game. If you pool your instances in an array instead of dynamically allocating it, you can save the GC calls from happening. This will result in a slightly larger memory footprint if you tweak it right.

   Below is code that provides a fixed-size generic list implementation; the internal array never grows/shrinks. The executePendingRemoves routine is needed since object removal must sometimes be put into a critical region with a synchronized block. You may want to queue up removals but still make them available to other threads up until the moment they are removed in bulk.

   public class List<T> {
   
    private int mCount;
    private T mItems[];
    private int mRemoveCount;
    private int[] mRemoveIndices; 
    
    @SuppressWarnings("unchecked")
    public List(int capacity) {
     mItems = (T[]) new Object[capacity];
     mRemoveIndices = new int[capacity];
     mCount = 0;
    }
    
    public void add(T item){
     mItems[mCount] = item;
     mCount++;
    }
    
    public void clear(){
     for(int index=0; index < mCount; index++)
     {
      mItems[index] = null;
     }
     mCount = 0;
    }
    
    public void executePendingRemoves() {
     for (int i=0;i < mRemoveCount; i++) {
      mItems[mRemoveIndices[i]] = null;
     }
     int newCount=0;
     for (int i=0;i < mCount; i++) {
      if (mItems[i] != null) {
       mItems[newCount] = mItems[i];
       newCount++;
      }
     }
     mCount = newCount;
     mRemoveCount = 0;
    }
    
    public T get(int index) { return mItems[index];}
    public int getCount() { return mCount;}
    public int getIndex(T item) {
     for (int i=0; i < mCount; i++) {
      if (mItems[i] == item) return i;
     }
     return -1;
    }
    public int getPendingRemoveCount() { return mRemoveCount; }
    public int[] getPendingRemoves() { return mRemoveIndices; }
    public Object[] getItems() { return mItems;}
    
    public void pendingRemoveAt(int index) {
     for (int i=0; i< mRemoveCount; i++) {
      if (index == mRemoveIndices[i])
       return;
      else if  (index < mRemoveIndices[i]) {
       int swapIndex = mRemoveIndices[i];
       mRemoveIndices[i] = index;
       index = swapIndex;
      }
     }
     mRemoveIndices[mRemoveCount] = index;
     mRemoveCount++;
    }
    
    public void removeAt(int index) {
     if (index < mCount) {
               for (int i = index; i < mCount; i++) {
                   if (i + 1 < mItems.length && i + 1 < mCount) {
                    mItems[i] = mItems[i + 1];
                   } else {
                    mItems[i]  = null;
                   }
               }
               mCount--;
           }
    }
    
    public T removeLast() {
     mCount--;
     
     final T item = mItems[mCount];
     mItems[mCount] = null;
     return item;
    }
    
   }
   

   Lastly is the pooling object that can be inherited by any application level instance (eg. FlyingWizardsPool extends ObjectPool). When you want to instantiate a flying wizard object, just type in FlyingWizard wizard = wizardPool.checkOut();.

   public abstract class ObjectPool<T> {
   
    private int mCapacity;
    private List<T> mPool;
    
    @SuppressWarnings({ "unchecked", "rawtypes" })
    public ObjectPool(int capacity) {
     mPool = new List(capacity);
     mCapacity = capacity;
     this.fill();
    }
    
    public void checkIn(T poolItem) {
     mPool.add(poolItem);
    }
    
    public T checkOut() {
     return mPool.removeLast();
    }
    
    public abstract void fill();
    
    public int getCount() {
     return mPool.getCount();
    }
    
    public int getCapacity() {
     return mCapacity;
    }
   
   }
   

   Below is an example implementation of the ObjectPool abstract class. Note how the fill routine is implemented. Also, front loading memory like this means that you will need an initialize on your instances so that the class fields can be put back to a "just instantiated" state. Normally we would use a constructor but to keep the allocation static, an initialize call is necessary.

   public static class FlyingWizardPool extends ObjectPool {
    public FlyingWizardPool(int capacity) {
     super(capacity);
    }
   
    public FlyingWizard checkOut(float x, float y, float destinationX, float destinationY) {
     FlyingWizard wizard = this.checkOut();
     wizard.initialize(x, y);
     return wizard;
    }
     
    @Override
    public void fill() {
     for (int i=0; i < this.getCapacity(); i++) {
      this.checkIn(new FlyingWizard());
     }
    }
   }
   

2. Choose larger block routines instead of calling out to helper subroutines.

   Since the Dalvik is a register based architecture, every time a routine is called from another, the register values must be stored to memory before the call and loaded back in after the routine has returned. Avoiding helper routine inside commonly called routines will reduce this load/store overhead.

3. Remove accessors and allow direct access to class fields.

   Accessors are usually good form and observe the ADT. Although, to avoid the overhead involved in a routine call and additional allocation of memory for the copied out value, it is best to allow direct access to the class field. This makes it more difficult to protect the conditions for the field but is a worthy sacrifice if it is called often.

4. Make routines static if they don't access class fields.

   The Android team recommends using this for an approximate 15-20% performance gain. This means less work for the Dalvik during run-time optimization and the routine can be inlined for faster execution.

5. Use constants instead of enums.

   This is more of a negligible optimization; it was delisted from Android's performance page. Instead of having an enum, you can keep the enumeration as an integer constant.

It is important to follow the ADT for good code writeability/readability and bug minimization. Use these optimizations only on code that really needs it. This means it should apply to routines and fields that are called frequently by your application.

POCO not transforming into a POCO proxy.

A POCO (Plain Old CLR Object) must be transformed into a POCO proxy
MyNamespace.MyClass ->{System.Data.Entity.DynamicProxies.MyClass_0A943C2FC37D33304CEB497A9210C754E3F553B50315F8E6F0F7A6FAF43777F2})
in order for features like lazy loading and change tracking to work.

MSDN has a great article that explains how to prepare a POCO to be transformed into a proxy. If you find that an object retrieved or attached to the context does not show itself in the DynamicProxies namespace (eg. MyNamespace.MyClass instead of ...DynamicProxies.MyClass), then you probably don't have a compliant class. You may have noticed this already when hovering your mouse cursor over an instance and seeing the runtime information on it.

The distilled points are that your POCO must:

• be public, not abstract and not sealed;
• have a public or protected parameterless constructor;
• have public overridable properties that are read/write if they are navigation properties;
• and implement ICollection if they are a one-to-many navigation property.

Detecting cycles in decimal digits and lists.

I was recently working on solving problem 64 for project Euler and one of the needed algorithms was a detection of cycles in a list. This routine works for detecting cycles in lists of cardinality greater than 2.

def get_cycle_len(N):
  i = k = 0
  for j in range(2, len(N)):
    if N[i] == N[j]:
      if k == 0:
        k = j
        i = 1
      else:
        if i == k:
          return k
        i += 1
    else:
      i = 0
      k = 0
  return -1

Entity Framework June 2011 CTP Bug

I recently installed the Entity Framework June 2011 CTP to preview the enum support but ran into a bug along the way that reported an error while processing the template.

I encountered this error while trying to run an Entity based project using the "Database & Model First" paradigm. Uninstalling the preview removed the problem. Not sure why this error occured since the preview doesn't modify the assembly it is complaining about not finding an entry point in.

EF 4.1 Code First: Many one-to-one properties for same class type on an object.

I just started using the Entity Framework recently to employ persistence for an already established code base. Initially I was using the "Model & Database First" paradigm where a designer is used to layout the data model. Although, this ended up being tedious since my POCO instance had to exactly match the POCO proxy instance in my model designer view. After upgrading to EF 4.1, I realized the "Code First" paradigm was the way to go since I had to adapt the persistence model to my already existing code.

One of the earliest problems that I ran into was having more than one property on a class that referenced the same class type. This example was taken from a great site that explored the different EF properties.

public class Customer
{
 public int Id { get; set; }
 public int Age { get; set; }
 public Address BillingAddress { get; set; }
 public Address DeliveryAddress { get; set; }
}

Notice how both the BillingAddress and DeliveryAddress properties references the same class type. I kept trying to establish two 1-to-1 relationships on the class but this caused a problem with cascading deletes and foreign key constraints. I found a solution but it still required exceptional behavior on the part of my context and the database schema.

The most elegant solution was to just treat both of the properties as complex types. The only thing I had to do was remove the Id property from the properties' class and the context took care of the rest. So instead of two tables in the database (one for Customer and the other for Address), there would be only one. Below is a layout of what the table would look like.

Customer
{
 Id
 Age
 BillingAddress_City
 BillingAddress_Street
 BillingAddress_Zipcode
 DeliveryAddress_City
 DeliveryAddress_Street
 DeliveryAddress_Zipcode
}

Pseudo random proportional scheduling in games.

I have been working on a game where enemy characters must select a target seemingly at random but such that the distribution of selected targets is balanced. Initially I had come up with a randomization algorithm with weighted values for each target but this became cumbersome and much too complex.

Then I remembered the scheduling algorithms from my Operating Systems class. In particular, the lottery scheduling algorithm.

// assume a queue of targets
int total = 0;

for (Target t : targets) {
   t.tickets = 5;
   total += t.tickets;
}

// generate a random number from 0 to total
for (Target t : targets) {
   randNum -= t.tickets;
   if (randNum <= 0) {
      targets.reenqueue(t);
      return t;
   }
}

The queue structure is critical to ensuring proportionality in target selection. Also, targets can be given a higher amount of tickets if bias is needed.

Writing a TEDS (IEEE 1451.4) parser.

I was tasked recently with writing a parser for TEDS bit stream data. There is an IEEE published paper with an overview of the standard but it doesn't give any examples for implementation. I was finally able to find a paper that gave examples but still had trouble parsing the data. I finally realized there is not only 2 selector bits after the basic TEDS block but selector bits inside the standard template (2 in the case of template 25). Here are my main findings:

• It depends on the software interface to get the bit-stream, but bits usually start their indexing from left to right. If you are using a language that assumes right to left bit encoding, the stream indices will need to be reversed (eg. 010110002 translates to 000110102 = 2610).
• If you are using an little-endian architecture (eg. x86), then the byte order will need to be converted from big-endian (reverse the byte indices). It is big-endian since the standard is defined for networks and thus has a network byte order.
• To calculate ConRelRes values, use the formula...
  <start_value> * [1 + 2 * <tolerance>] ^ <teds_value>
  In the published paper, you will see an entry like ConRelRes(5E-7 to 172, +- 0.15%) in the "Data Type (and Range)" field. 5E-7 is the start value, 0.15 is the tolerance and the TEDS value is whatever value gets parsed from the bit stream.

Here are some helper functions to parse TEDS correctly on the .NET platform (x86 systems).

int _streamOffset = 0;

private System.Collections.BitArray _GetBits(System.Collections.BitArray bits, int length)
{
 System.Collections.BitArray result = new System.Collections.BitArray(length);
 for (int index = 0; index <= length - 1; index++) {
  result[index] = bits[_streamOffset + index];
 }
 return result;
}
private byte[] _GetBytes(System.Collections.BitArray bits)
{
 int byteCount = Convert.ToInt32(Math.Ceiling(bits.Count / 8));
 int padCount = (byteCount * 8) - bits.Count;
 byte[] bytes = new byte[byteCount];
 int byteIndex = 0;
 int bitIndex = 0;
 System.Collections.BitArray reverseBits = new System.Collections.BitArray(bits.Count + padCount);

 //byte align new bit array
 for (int index = 0; index <= padCount - 1; index++) {
  reverseBits[index] = false;
 }
 //reverse bits to read from right to left
 for (int index = 0; index <= bits.Length - 1; index++) {
  reverseBits[padCount + index] = bits[bits.Length - 1 - index];
 }

 //create byte array from byte aligned right to left bits
 for (int index = 0; index <= reverseBits.Count - 1; index++) {
  if ((reverseBits[index])) {
   bytes[byteIndex] = bytes[byteIndex] | Convert.ToByte(1 << (7 - bitIndex));
  }

  bitIndex += 1;
  if ((bitIndex == 8)) {
   bitIndex = 0;
   byteIndex += 1;
  }
 }

 return bytes;
}

private bool _GetBoolean(System.Collections.BitArray bits)
{
 bool result = bits[_streamOffset];
 _streamOffset += 1;
 return result;
}
private char _GetChar(System.Collections.BitArray bits, int length)
{
 char result = BitConverter.ToChar(new byte[] {
  0,
  _GetBytes(_GetBits(bits, length))[0]
 }, 0);
 _streamOffset += length;
 return result;
}
private int _GetInteger(System.Collections.BitArray bits, int length)
{
 byte[] intBytes = new byte[] {
  0,
  0,
  0,
  0
 };
 byte[] bytes = _GetBytes(_GetBits(bits, length));
 int result = 0;
 //pad out rest of bytes so it is int32 aligned and convert endianess
 for (int index = 0; index <= bytes.Length - 1; index++) {
  intBytes[index] = bytes[bytes.Length - 1 - index];
 }
 result = Convert.ToInt32(BitConverter.ToUInt32(intBytes, 0));
 _streamOffset += length;
 return result;
}

Reentrant lock acquires in CLR.

I always like when a post gets to the point (especially after searching in Google). In short, if you perform an operation that waits to acquire a lock, the thread doesn't actually stop.

In concrete terms of .NET coding, if you call the WaitOne method on a thread, it may still process events that the CLR deems "high priority". This can be a big problem if the event handlers go into the critical region you are trying to protect.

int criticalRegion = 0;

private void criticalRegionWait() 
{
   AutoResetEvent are = new AutoResetEvent(false);
   Thread thread = new Thread(() => 
      { 
         criticalRegion = -1
         Debug.WriteLine(criticalRegion);
         are.Set();
      });
   thread.SetApartmentState(ApartmentState.STA);
   thread.IsBackground = true;
   thread.Start();
}

private void criticalRegionUpdateEvent(object sender, EventArgs e) 
{
   criticalRegion = 1;
}

In the above example, if there is a high priority event that has criticalRegionUpdateEvent in its call path a race condition is possible. While criticalRegionWait waits for the thread to finish, the criticalRegionUpdateEvent has a chance of setting criticalRegion = 1 so that WriteLine ends up printing 1 instead of -1.

Namespaces for classes.

When designing classes for outside use (eg. API) or as a library component for multiple applications, readability and easy element (field/function) selection is important. No developer likes hunting around for fields or functions; a legible and hierarchical organization of elements aids quicker turnaround time in code delivery.

In some cases, a large class is needed that can possibly contain dozens or hundreds of elements. Naming convention can aid in this organization (ie. using common prefixes in field/function names) but are not inherent to the grammar of languages. Therefore, no semantic advantage can be taken from using these conventions.


class Store
   ItemList clothingMensShirts
   ItemList clothingMensShoes
   ...
   ItemList clothingWomensShirts
   ItemList clothingWomensShoes
   ...
   ItemList hardwareToolsWrenches
   ...
   ItemList hardwareMaterialsWood
   ...
   ItemList electronicsGamesPCFallout3Copies
   ...
   ItemList electronicsAudioHeadphones
   ...


The current solution to the management of large classes is by using publicly exposed nested classes.


class Clothing inherits Department
   ClothingSection mens
   ...

class Mens inherits ClothingSection
   ItemList shirt
   ItemList shoes
   ...

abstract class Store
   ...
   Department clothing
   ...

class IKEA inherits Store
   ...

IKEA newYorkStore = new IKEA();
newYorkStore.buy(newYorkStore.clothing.mens.shirts[0]);


This is a possible solution but also comes with it's own problems. Encapsulation of the nested class will not only hide information from the public user but also from the parent class as well. This can be problematic when designing an abstract class where the functions, that must be implemented, must also access non-public elements inside the nested. For example, in the store example, any data the top level class (Store) may want to access from the lower level ones (ClothingSection, ItemList) will be unavailable if that data must also be hidden from the public user.

Also, the nested classes cannot be abstracted to require implementation from any inheriting class. Revisting the store example, this means that abstracting the ClothingSection class would require two new classes for one implementation. Creating not only a child Store but also a child ClothingSection class.

Nested classes are helpful for creating logical hierarchies within a class or providing abstract functionality privately inside the class. Although, I would propose the use of namespacing inside a class instead. It would provide the logical hierarchy needed in a very simple way and allow for information sharing across the entire domain of the class. It would need a separate keyword though to prevent use outside of classes.


class Store

classnamespace clothing
   classnamespace mens
      ItemList shirts
      ItemList shoes
      ...
   ...
   classnamespace womens
      ItemList shirts
      ItemList shoes
      ...
   ...
   classnamespace hardware
      classnamespace tools
         ItemList wrenches
         ...
      ...
      classnamespace materials
         ItenList Wood
         ...
      ...
   ...


Delete long file path names.

I made the stupid mistake of importing an Eclipse project into my workspace when the import location was from the workspace itself. I went to delete the recursive folder when I encountered an error that the file path name was too long to delete.

The best manual solution that I found was to go as deep as possible in the recursive folder and then map it to a virtual drive.


subst x: c:\recursiveFolder\recursiveFolder\recursiveFolder\...


This can be quite an arduous process; I found myself creating up to 9 virtual drives. It eventually worked though and I was able to delete the recursive folder.


I also found a site with a Perl script that deletes long file paths but haven't tested it myself.

Representing scientific units in code.

I have been working on implementing a stream reader for IEEE 1451.4 TEDS and came across this interesting paper regarding representation of scientific units in code. It provides solutions to determining unit equivalency (eg. V/(m•kg/s²) = m/(s•A)). Also discovered some indivisible base units that can represent any unit (amp, candela, kelvin, gram, meter, mole, radian, second). With a bit to represent the placement (high for numerator, low for denominator) and a bit for presence, a unit storage type can be derived that only occupies 2 bytes.

Using Ubuntu 10.04 with SVN+HTTP.

I setup a server recently using Ubuntu 10.04. LAMP was easy to configure, as was Subversion. Although making Subversion and Apache2 play nice together with DAV SVN was a nightmare. I followed the guide provided but the website location just kept reprompting for my login.

After hours of running in circles, I was able to find the solution. The Require valid-user directive in /etc/apache2/mods-available/dav_svn.conf required the Limit directive to be around it.

<Limit GET POST PUT DELETE CONNECT OPTIONS PATCH PROPFIND PROPPATCH MKCOL COPY MOVE LOCK UNLOCK>
   Require valid-user
</Limit>

The LimitExcept directive can also be used as long as the limitations are specified.