Low and behold, support for smart device dev is gone!
MSDN is quite clear about it: “Visual Studio 2010 does not support mobile application development for versions of Windows Phone prior to Windows Phone OS 7.0.”

That’s quite a bummer. Hard to believe… why would I have to license a legacy IDE to develop software for state of the art mobile operating systems? Perhaps even license two IDEs?

With this in mind, it doesn’t surprise Android is gaining market shares…

This can be accomplished via the universal OutputDebugString() API. The only shortcoming is, that it does not support variable arguments in a sprintf(…) form.

Here is a workaround:

#include <strsafe.h>
// ...
void MyOutputDebugString( LPCTSTR sFormat, ... )
{
    va_list argptr;      
    va_start( argptr, sFormat ); 
    TCHAR buffer[ 2000 ];
    HRESULT hr = StringCbVPrintf( buffer, sizeof( buffer ), sFormat, argptr );
    if ( STRSAFE_E_INSUFFICIENT_BUFFER == hr || S_OK == hr )
        OutputDebugString( buffer );
    else
        OutputDebugString( _T("StringCbVPrintf error.") );
}

I am using strsafe.h in this case to offer protection against buffer overruns. In case the internal buffer is not big enough to handle the output string, it will be safely truncated with an ending \0. In case you cannot make use of strsafe.h, here is an old style solution:

void MyOutputDebugString( LPCTSTR sFormat, ... )
{
    va_list argptr;      
    va_start( argptr, sFormat ); 
    TCHAR buffer[ 2000 ];
    wvsprintf( buffer, sizeof( buffer ), sFormat, argptr );
    buffer[ ( sizeof( buffer ) / sizeof( *buffer ) ) - 1 ] = '\0';
    OutputDebugString( buffer );
}

This was a bit of a common misbelief, since stored T-SQL procedures and functions are also optimized/compiled prior to execution. Performance gains by using .NET code instead of T-SQL are usually limited to highly iterative/procedural code, and not for optimizing anything which can be easily done within native SQL.

Let us have a look at a simple user defined function written in C#. This function takes a clear text string and a 2 character salt parameter and calculates a Unix crypt hash based on both.

public partial class UserDefinedFunctions
{
    [Microsoft.SqlServer.Server.SqlFunction( IsDeterministic=true )]
    public static SqlString Crypt( SqlString sPlainText, SqlChars cSalt )
    {
        if ( sPlainText.IsNull || cSalt.IsNull || cSalt.Length < 2 )
            return SqlString.Null;
        string sSalt = new string( cSalt.Value );
        sSalt = sSalt.Substring( 0, 2 );
        return new SqlString( UnixCrypt.Crypt( sSalt, sPlainText.Value ) );
    }
}

We just declare a class with a static function qualified as a SqlFunction that accepts and returns classes/structs of the System.Data.SqlTypes namespace. The UnixCrypt.Crypt method contains the actual code which I am excluding here. If you are interested in building this example, you can find a working implementation of the crypt class in C# at The Code Project.

After compiling the above code into a dll, you may load it into SQL Server and run it with the following commands:

-- CLR support is disabled by default
EXEC sp_configure 'clr enabled' , '1'
GO
reconfigure;
GO
-- load dll and create assembly
CREATE ASSEMBLY asmYourAssembly FROM 'D:\Your\Path\to\CryptUDF.dll' WITH PERMISSION_SET = SAFE
GO
-- add a function that references the CLR UDF
CREATE FUNCTION dbo.Crypt( @plain AS NVARCHAR(200), @salt AS NCHAR(2) )
    RETURNS NVARCHAR(200) AS EXTERNAL NAME asmYourAssembly.UserDefinedFunctions.Crypt
GO
SELECT dbo.Crypt( 'password', 'xy' );

Note PERMISSION_SET = SAFE, which reflects the external dependencies on framework libraries. Since we are doing all our calculations within the library, there is nothing additional we need to reference, which permits us to be running within the safest permission set. You can learn more about the CLR integration permission sets on MSDN.

When doing authentication, you could use the UDF as follows:

SELECT @UserID=[UserID] FROM dbo.tblAccounts 
    WHERE [UserName]=@Username COLLATE Latin1_General_CI_AS
    AND dbo.Crypt( @Password, [Password] )=[Password] COLLATE Latin1_General_CS_AS

Note that we are doing a case insensitive compare on the UserName column and a case sensitive compare on the crypt hash of the crypt hash column.

Why does it make sense to do authentication like this inside the database instead of calculating the password hash outside of the database and then just pass it to a WHERE Username=@Username AND Password=@Password query?

The reason lies in the nature of the crypt function: the hash it creates is based on a two character prefix or salt, which has to be used for hashing the candidate password prior to comparing it with the original password hash. Since the above approach can be completely encapsulated within a stored procedure, no hashes or salts need to be returned to the calling application for verifying the correctness of the password.

Where is this used today? While Unix and Linux user authentication is the classic usage of the crypt function, also some internet services are relying on it. E.g. the PayPal IPN feature for selling subscription accounts is transmitting passwords as crypt hashes only.

In my last post, I have already been talking about a safe way of handling Unicode file/path names, which was rather slow unfortunately. In this post I would like to elaborate on how to combine this with a fast reading approach using .NET.

I have chosen to give examples using C# code in these series, since it allows me to demonstrate my ideas in a very compact way. However the general approach is compatible with many programming languages and therefore not a .NET only solution.

Basically we are combining a batch read using ExifTool with a single file read operation for incompatible file names. In optimal circumstances, i.e. when all file names are convertible, this method performs as fast as ExifTool can be. Worst case would be reading all files one by one, which has a bigger performance penalty.

Prior to processing any files, we have to divide all file names into compatible and incompatible ones. After splitting them up, we start the actual reading.

public ExifFileJson[] GetOriginalDateExifToolUnicode( string[] files )
{
    // first, single out all files with incompatible file names, since they cannot be handled in a batch
    var tmp = ( from x in files select new { OriginalName = x, ConvertedName = Encoding.ASCII.GetString( Encoding.UTF8.GetBytes( x ) ) } ).ToArray();
    string[] batch = tmp.Where( x => x.OriginalName.Equals( x.ConvertedName ) ).Select( x => x.OriginalName ).ToArray();
    string[] nobatch = tmp.Where( x => !x.OriginalName.Equals( x.ConvertedName ) ).Select( x => x.OriginalName ).ToArray();
 
    List<ExifFileJson> exiffiles = new List<ExifFileJson>();
    exiffiles.AddRange( GetOriginalDateExifToolBatch( batch ) );
    foreach ( string s in nobatch )
        exiffiles.Add( GetExifImageExifTool( s ) );
    if ( files.Length != exiffiles.Count() )
        throw new Exception( "Could not open all files. Missing: " + String.Join( ", ", files.Except( exiffiles.Select( x => x.SourceFile ) ).ToArray() ) );
    return exiffiles.ToArray();
}

The next method basically runs ExifTool and parses the output in Json format.

private static ExifFileJson[] GetOriginalDateExifToolBatch( string[] files )
{
    Process oP = new Process();
    oP.EnableRaisingEvents = false;
    oP.StartInfo.CreateNoWindow = true;
    oP.StartInfo.LoadUserProfile = false;
    oP.StartInfo.RedirectStandardError = false;
    oP.StartInfo.RedirectStandardOutput = true;
    oP.StartInfo.RedirectStandardInput = true;
    oP.StartInfo.StandardErrorEncoding = null;
    oP.StartInfo.StandardOutputEncoding = Encoding.UTF8;
    oP.StartInfo.UseShellExecute = false;
    oP.StartInfo.WindowStyle = ProcessWindowStyle.Hidden;
    oP.StartInfo.FileName = @"exiftool.exe";
    oP.StartInfo.Arguments = "-EXIF:ModifyDate -EXIF:DateTimeOriginal -EXIF:CreateDate -j -d \"%Y-%m-%d %H:%M:%S\" -@ -";
    oP.Start();
 
    /// Pass all file names in an arg file which is piped to the process (no temporary file)
    byte[] data = Encoding.UTF8.GetBytes( String.Join( "\r\n", files ) );
    oP.StandardInput.BaseStream.Write( data, 0, data.Length );
    oP.StandardInput.BaseStream.Close();
 
    DataContractJsonSerializer deserializer = new DataContractJsonSerializer( typeof( ExifFileJson[] ) );
    ExifFileJson[] exif = deserializer.ReadObject( oP.StandardOutput.BaseStream ) as ExifFileJson[];
 
    oP.WaitForExit();
    return exif;
}

The following Unicode-safe way does not rely on the Perl file API, but instead pipes the image to stdin. To avoid out of memory conditions, it might be advisable to read the image file in small chunks using a stream. Do not forget to set the file name in the ExifFileJson object before returning it (ExifTool does not know about the file name).

private static ExifFileJson GetExifImageExifTool( string sFile )
{
    Process oP = new Process();
    oP.EnableRaisingEvents = false;
    oP.StartInfo.CreateNoWindow = true;
    oP.StartInfo.LoadUserProfile = false;
    oP.StartInfo.RedirectStandardError = false;
    oP.StartInfo.RedirectStandardOutput = true;
    oP.StartInfo.RedirectStandardInput = true;
    oP.StartInfo.StandardErrorEncoding = null;
    oP.StartInfo.StandardOutputEncoding = Encoding.UTF8;
    oP.StartInfo.UseShellExecute = false;
    oP.StartInfo.WindowStyle = ProcessWindowStyle.Hidden;
    oP.StartInfo.FileName = @"exiftool.exe";
    oP.StartInfo.Arguments = "-j -EXIF:ModifyDate -EXIF:DateTimeOriginal -EXIF:CreateDate -d \"%Y-%m-%d %H:%M:%S\" -";;
    oP.Start();
 
    byte[] image = File.ReadAllBytes( sFile );
    oP.StandardInput.BaseStream.Write( image, 0, image.Length );
    oP.StandardInput.BaseStream.Close();
 
    DataContractJsonSerializer deserializer = new DataContractJsonSerializer( typeof( ExifFileJson[] ) );
    ExifFileJson[] exif = deserializer.ReadObject( oP.StandardOutput.BaseStream ) as ExifFileJson[];
 
    oP.WaitForExit();
    if ( exif.Length > 0 )
        exif[ 0 ].SourceFile = sFile;
    return exif.FirstOrDefault();
}

In case you wonder about the Json class we use for deserializing output:

[DataContract]
public class ExifFileJson
{
    [DataMember( IsRequired = true, Name = "SourceFile" )]
    public string SourceFile;
    [OnDeserializedAttribute()]
    internal void ReplaceBackSlashes( StreamingContext context ) { this.SourceFile = this.SourceFile.Replace( '/', '\\' ); }
 
    [DataMember( IsRequired = false )]
    public string DateTimeOriginal;
    [DataMember( IsRequired = false )]
    public string CreateDate;
    [DataMember( IsRequired = false )]
    public string ModifyDate;
}

Basically we declare required and optional attributes and a name mapping if necessary. Remember to replace forward slashes to backslashes for the file names, since these are returned in Unix style. It is probably not a good idea to parse dates as DateTime? nullables, since there could be some images with unparsable dates, which will result in a parsing exception. If you would still want to do it, remember to decorate the dates in Json format in ExifTool: -d “/Date(%Y-%m-%d %H:%M:%S)/”.

Other Options

Certainly we could reach a better performance and less coding overhead if we had a way of batch processing files independent of their name and path. If you have a perl environment on your machine with the Win32::API module, you could rewrite the above code within a Perl script and therefore get much better performance even when reading Unicode files.

There is also another option: It is possible to add Unicode file name support into the Perl interpreter for Windows. I recently did a a proof-of-concept which shows that ExifTool (or any UTF-8 supporting Perl app) could be using Unicode file names in Windows without changing a line of code, as long as it is executed with a Unicode supporting interpreter. The source code of Perl is pretty big however, and I am afraid I won’t be able to invest enough time to do a bullet-proof implementation.

Test Environment
Tests have been conducted on a Core i7 720QM system with 4 GB RAM and a 7200 rpm HD, running Windows 7 64 bit. The testing application was written in C# using .NET Framework 3.5 and Linq.

Preparation

We are benchmarking different approaches reading a total of 1000 jpg files and measuring the total time taken to read 3 EXIF dates from each file (if present). In order to minimize misleading results when reading files which have previously been cached, we are reading all files once before performing the test.

Reading files without processing

We read every file into memory after it has been cached in the file system cache, so this is more or less an in-memory operation. This gives us a clue regarding the file access overhead.

Duration for 1000 files: 226 ms.

Reading meta data with GDI+

Using the .NET builtin Image class, reading and parsing of 3 attributes is rather fast, taking less than 2 seconds.

Duration for 1000 files: 1632 ms.

Reading meta data using ExifTool

We call ExifTool for every file and parse the return values as DateTime. In order to support all filenames (also names which can only be represented in Unicode), we read the file into memory first and then pipe it to stdin of ExifTool. This is the slowest of all reading modes, taking about 200 times as long as GDI+. As we will see soon, the actual preformance hit ist the startup time of the Perl interpreter, and not ExifTool itself.

Duration for 1000 files: 337000 ms.

Reading meta data using ExifTool (-fast)

Same as above, but using the -fast option in ExifTool, which will prematurely cancel reading from stdin, once a sufficient amount of data has been found. This should increase performance especially when reading files directly over a slow network, but as we can see, it does not make a big difference in our case. Throughput increases by less than 10 percent.

Duration for 1000 files: 317000 ms.
Reading meta data using ExifTool (-fast2)
In addition to the -fast option, using -fast2 should allow for faster processing by ommitting maker notes. The effect is small in our case, which might also be because not all images in the test set contain maker notes. As we will see later, the actual work performed by ExifTool is only very small compared to the Perl startup time. Using the evidence gathered in this test, Perl consumes as much as 98.4% of the total execution time, whereas reading and parsing of the jpeg file only takes 1.6%.

Duration for 1000 files: 311000 ms.

Reading meta data using ExifTool (without extraction)

Since exiftool.exe unpacks a payload of 967 files in 60 folders (8.67 MB), one approach was to skip the extraction process and call ExifTool directly in the temporary folder with all the PAR environment variables set. Unfortunately this could not deliver any improvement worth the effort. Therefore we can say that the amount of time used for extraction is hardly relevant.

Duration for 1000 files: 314000 ms.

Reading meta data using ExifTool (multiple threads)

Since the entire operation is clearly CPU bound, the obvious optimization on a multi core / hyper threading system would be to execute ExifTool in parallel. For our test case, we are executing 8 instances of ExifTool at the same time, using 8 threads (the test system has 8 virtual cores). This results in a signifficant speed up, more than 3 times as fast as a serialized execution:

Duration for 1000 files: 99000 ms.

Reading meta data using ExifTool (batch mode)

The end of the road? With the multi threaded approach we have reached the maximum optimization possible when calling ExifTool seperately for each file. This technique gave us the advantage of being able to handle file names with arbitrary character sets and detailed progress and error reporting.

The only way of getting more (much more) throughput is to use ExifTool in batch mode, thus minimizing the actual impact of the Perl startup time.

As before, ExifTool has been set to read three Date tags from each file and format the text output. This time we are using Json as the output format, since it allows us to easily parse the result of each file. In order to avoid getting a command line which is too long, we are writing all files into an ‘argfile’, which is then written to stdin of Exiftool using -@ -.

This approach is F A S T! We are suddenly doing the same job within 1.6% of the previous time!

Duration for 1000 files: 5669 ms.

Reading meta data using ExifTool (batch mode, -fast2)

No big improvements here, we are ending up with almost the same amount of time. This might be due to the fact that only part of the tested files contain maker notes, so results may vary.

Duration for 1000 files: 5422 ms.

Conclusion

In the above test we have learned that iterating file by file is extremely slow when processing large amounts of files using ExifTool. The performance impact is caused by the overhead of calling the Perl interpreter, and is therefore difficult to minimize when calling ExifTool once for each file. Depending on the kind of data needed, it is therefore worthwhile to look into other solutions such as batch processing or using a different API.

When using ExifTool in batch mode, it is strongly recommended to check whether or not a file name and path can be represented using the current system’s code page. Otherwise such files will not be read. It is not safe to call ExifTool with MS-DOS ’8dot3′ filenames, since these are not converted to ANSI in case of eastern asian characters. Also, these names are not guaranteed to be present for each file on the NTFS file system.

For an ExifTool-only solution reading meta data, the following approach is recommended when reading larger amounts of files:

1. Create a list of image files to be processed.
2. Convert each file name into a UTF-8 byte sequence and decode using the current system ANSI code page. Then compare the resulting string to the original path of the file. If both are not equal, you must not use this file in batch processing (ExifTool cannot open it) and instead read it in a separate call. Why should you convert to UTF-8 and then to ANSI? This might be confusing at first, but it mimics exactly what happens behind the scenes. You need to pass the file names as UTF-8 to ExifTool, since they appear again in the output (which should be UTF-8).
3. Write a list of UTF-8 encoded file names to stdin of ExifTool, do not pass them on the command line, since you might hit the maximum length of the command line and truncate it unknowingly.
4. Call ExifTool, preferably using -J option for generating output in Json format. Json allows for more efficient parsing (compared to XML) of the result.
5. Parse the result and ensure you are getting a result for each file. There are many libraries to handle Json parsing, in .NET it is done in a few lines of code. If you had entered file names in ANSI encoding in the previous step, you would run into errors here because your output would contain a mix of encodings.
6. All files which did not pass the UTF-8 to ANSI encoding roundtrip need to be processed one by one.

Source Code

The source code of the test app is available for download here.

First, for the sake of speed and simplicity, we chose the GDI+ builtin capabilities of the Image class:

/// <summary>Much faster than using Exiftool. In case GDI+ cannot decode the date string we use Exiftool.</summary>
private DateTime? GetOriginalDate( string sFileName )
{
    using ( FileStream stream = new FileStream( sFileName, FileMode.Open, FileAccess.Read ) )
    {
        using ( Image img = Image.FromStream( stream, false, false ) )
        {
            int[] date_tags = new int[] { 36867, 36868, 306 }; // tag numbers with dates
            string[] s1 = ( from x in date_tags where img.PropertyIdList.Contains( x ) select Encoding.ASCII.GetString( img.GetPropertyItem( x ).Value ).Replace( "\0", "" )).ToArray(); // get date as string without training \0
            DateTime d;
            DateTime?[] dd = ( from x in s1 where x.Trim().Length > 0
                select DateTime.TryParseExact( x, new string[] { "yyyy:MM:dd HH:mm:ss", "yyyy-MM-dd HH:mm:ss", "MM/dd/yyyy HH:mm:ss", "yyyy-MM-dd'T'HH:mm:sszzz" }, CultureInfo.InvariantCulture, DateTimeStyles.AllowWhiteSpaces | DateTimeStyles.AssumeLocal, out d ) ? d as DateTime? : 
                null ).ToArray(); // we see if we can parse all the date attributes found
            if ( dd.Where( x => !x.HasValue ).Count() > 0 )
                return GetOldestExifDateExifTool( sFileName ); // if there is something in the date attribute we cannot parse we ask exiftool.
            else
                return ( from x in dd where x.Value > new DateTime( 1990, 01, 01 ) && x.Value < DateTime.UtcNow select x ).Min(); // make sure we use a valid date range
        }
    }
}

Since the EXIF standard defines date values to be stored as text data, sometimes we find non-standard date formats. This includes dates being stored with milliseconds added, using different separator characters or including an additional UTC offset. Exiftool does a pretty decent job interpreting all those values as a date, plus it might be capable of reading certain off-standard or broken meta-data which GDI+ doesn’t.

Here is the second approach:

/// <summary>Extracts the oldest possible EXIF date. Can process 3 files per second, very slow, will need 8 hours for 90.000 files.</summary>
private static DateTime? GetOldestExifDateExifTool( string sFile )
{
    Process oP = new Process();
    oP.EnableRaisingEvents = false;
    oP.StartInfo.CreateNoWindow = true;
    oP.StartInfo.LoadUserProfile = false;
    oP.StartInfo.RedirectStandardError = false;
    oP.StartInfo.RedirectStandardOutput = true;
    oP.StartInfo.RedirectStandardInput = true;
    oP.StartInfo.StandardErrorEncoding = null;
    oP.StartInfo.StandardOutputEncoding = Encoding.UTF8;
    oP.StartInfo.UseShellExecute = false;
    oP.StartInfo.WindowStyle = ProcessWindowStyle.Hidden;
    oP.StartInfo.FileName = @"exiftool.exe";
    oP.StartInfo.Arguments = "-s -s -EXIF:ModifyDate -EXIF:DateTimeOriginal -EXIF:CreateDate -d \"%Y-%m-%d %H:%M:%S\" -";
    oP.Start();
 
    byte[] image = File.ReadAllBytes( sFile );
    oP.StandardInput.BaseStream.Write( image, 0, image.Length );
    oP.StandardInput.BaseStream.Flush();
    oP.StandardInput.BaseStream.Close();
    string sStdOut = oP.StandardOutput.ReadToEnd();
    oP.WaitForExit();
 
    string[] datetags = new string[] { "DateTimeOriginal", "CreateDate", "ModifyDate" };
    string[] res1 = sStdOut.Split( new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries ); // split lines
    string[][] res2 = ( from x in res1 select x.Split( new char[] { ':' }, 2 ) ).ToArray(); // split after colon to separate attributes and values
    string[] res3 = ( from x in res2 where x.Length == 2 && datetags.Contains( x[ 0 ], StringComparer.InvariantCultureIgnoreCase ) select x[ 1 ] ).ToArray(); // only chose lines of date attributes
    DateTime d;
    DateTime?[] dd = ( from x in res3 select DateTime.TryParseExact( x, "yyyy-MM-dd HH:mm:ss", CultureInfo.InvariantCulture, DateTimeStyles.AllowWhiteSpaces | DateTimeStyles.AssumeLocal, out d ) ? d as DateTime? : null ).ToArray();
    DateTime? oDate = ( from x in dd where x.HasValue && x > new DateTime( 1990, 01, 01 ) && x < DateTime.UtcNow select x ).Min();
    return oDate;
}

Basically Exiftool has three shortcomings when used within another program:

1. It is not available as a library. Therefore we need to make use of the Process API.
2. It has a long startup time. This is because it has been written in Perl which is packed in a single self-expanding exe wrapper. As a result, we can only process about 3 files per second on a fast computer. GDI+ might be a hundred times faster. We might be able to work around this somehow by processing several files in a batch, which would require a bigger change in our program logic.
3. It does not support the unicode filesystem API, so filenames which are not compatible with the current ANSI encoding cannot be opened. To work around this limitation, we read the file into memory first and then pipe it into ExifTool.

Note: when using the Process API, you are given the option to redirect both stdout and stderr at the same time, which could allow for more detailed error handling/messages. However you *must* always read stdout and stderr in different threads to avoid a deadlock situation. For the sake of simplicity, I have ommitted error handling in this case.

Let me illustrate this by example: In this case we are looking at a string transformation algorithm that allows for sorting a Url string according to the top level domain, domain name and host name. E.g. http://www.wikipedia.de/favicon.ico should be sorted according to http://de.wikipedia.www/favicon.ico.

Using PL/SQL with its limited string processing functions, this can result in a lot of coding. Using .NET, it’s easy to write and surprisingly fast.

[SQLiteFunction( Name = "ReverseDomain", Arguments = 1, FuncType = FunctionType.Scalar )]
public class ReverseDomain: SQLiteFunction
{
    public override object Invoke( object[] args )
    {
        if ( args == null || args.Length < 1 || args[ 0 ] == null )
            return null;
        string[] ss = args[ 0 ].ToString().Split( new string[] { "://", "/" }, 3 );
        if ( ss.Length > 1 )
        {
            string[] sss = ss[ 1 ].Split( new char[] { '.' } );
            Array.Reverse( sss );
            return ss[ 0 ] + "://" + String.Join( ".", sss ) + "/" + ( ss.Length == 3 ? ss[ 2 ] : String.Empty );
        }
        return args[ 0 ];
    }
}

Alternatively, we could use the UriBuilder class:

[SQLiteFunction( Name = "ReverseDomain", Arguments = 1, FuncType = FunctionType.Scalar )]
public class ReverseDomain: SQLiteFunction
{
    public override object Invoke( object[] args )
    {
        if ( args == null || args.Length < 1 || args[ 0 ] == null )
            return null;
        UriBuilder u = new UriBuilder( args[ 0 ] as string );
        string[] ss = u.Host.Split( new char[] { '.' } );
        Array.Reverse( ss );
        u.Host = String.Join( ".", ss );
        return u.ToString();
    }
}

Where is the catch with UriBuilder? Compared to the custom string splitting solution it is about 5 times slower. It can transform only about 65000 urls per second on my machine, while the prior method can convert 350000 urls in the same time.

How is this new UDF called from SQL?

SELECT * FROM UrlTable ORDER BY ReverseDomain( Url )

Today there was a similar requirement, using Linq Except() for determining all elements of an IEnumerable which do not intersect with the elements of another IEnumerable. Again, there is a one line solution to it, which is slow on large input data:

byte[][] hashes_old = /* an array of byte arrays containing a hash value */;
byte[][] hashes_new = /* another array of byte arrays containing a hash value */;
byte[][] hashes_obsolete = ( from x in hashes_old where hashes_new.Any( y => y.SequenceEqual( x ) ) == false select x ).ToArray();

We are using two arrays of 16 byte long hashes and determine which elements do not intersect. It is a more or less elegant one liner that does not require any other comparison code. Yet when we test this with larger amounts of data, it runs slow since SequenceEqual() has to be called for every single comparison:

hashes_old: 18830 hashes_new: 8210 hashes_obsolete: 12228 time: 19564 ms

Since the Except() method is extensively using the GetHashCode() override, a lot of time can be saved by properly implementing a hash function within an IEqualityComparer derivate.

byte[][] hashes_old = /* an array of byte arrays containing a hash value */;
byte[][] hashes_new = /* another array of byte arrays containing a hash value */;
byte[][] hashes_obsolete = hashes_old.Except( hashes_new, new ByteArrayComparer() ).ToArray();
 
/* .... */
public class ByteArrayComparer : IEqualityComparer<byte[]>
{
    public bool Equals( byte[] a, byte[] b )
    {
        if ( a == null || b == null )
            return a == b;
        return a.SequenceEqual( b );
    }
    public int GetHashCode( byte[] x )
    {
        if ( x == null )
            throw new ArgumentNullException();
        int iHash = 0;
        for ( int i = 0; i < x.Length; ++i )
            iHash ^= ( x[ i ] << ( ( 0x03 & i ) << 3 ) );
        return iHash;
    }
}

hashes_old: 18830 hashes_new: 8210 hashes_obsolete: 12228 time: 14 ms

Same result, but instead of 19 seconds we only need 16 milliseconds, that is 1400 times faster!

What happens is that the result of GetHashCode() is used for each comparison. When two arrays have the same hash code, Linq calls the Equals function to ensure both are really equal (there has been no hash collision). So the main speedup is realized by writing a low-collision hashing function.

1. The most basic and least flexible would be to truncate any text exceeding a set limit of characters by applying SUBSTRING in the database query.
2. The other option would be using a TemplateField, which results in a lot of coding overhead, especially if you have to incorporate markup for the insert and update events as well.
3. Depending on your needs, using the CSS text-overflow:ellipsis could be a compact solution, yet it is only supported by Internet Explorer (some kind of workaround for FireFox exists).
4. Perhaps the most elegant approach would be the subclassing of the existing BoundField, which already has all the features ready for inserting and updating. Although we only print the first few characters of the column text, we would give the user an additional feature at hand that allows him to view the whole text by hovering the cursor over the short text.

The class EllipsisTextField extends BoundField by one property that reflects the maximum abount of characters to be displayed. If left empty, the control behaves identical with the BoundField class, so it is backwards compatible.

public class EllipsisTextField : BoundField
{
    public int? MaxChars
    {
        get { return this.ViewState[ "MaxChars" ] as int?; }
        set { this.ViewState[ "MaxChars" ] = value; }
    }
 
    protected override string FormatDataValue( object dataValue, bool encode )
    {
        string sLong = dataValue as string;
        if ( this.MaxChars.HasValue && !String.IsNullOrEmpty( sLong ))
        {
            string sShort = sLong;
            if ( sLong.Length > this.MaxChars.Value )
            {
                sShort = sLong.Substring( 0, this.MaxChars.Value ) + "...";
                sLong = HttpUtility.HtmlEncode( sLong );
                sShort = HttpUtility.HtmlEncode( sShort );
 
                dataValue = "<div title=\"" + sLong + "\" style=\"white-space: nowrap;\">" + sShort + "</div>";
                return base.FormatDataValue( dataValue, false );
            }
        }
        return base.FormatDataValue( dataValue, encode );
    }
}

We override the FormatDataValue method in order to execute our own rendering code. Inside, we truncate the original string if necessary, add ellipses and then add short and long versions to a DIV. When set as the title, any mouse over action will render the full code as a tooltip.

Note: In case you are developing software that exclusively operates on Solid State Disks (SSD) you may stop reading now…

The following idea has been developed for an image indexing engine, which is supposed to scan a large amount of images and extract information within the least possible amount of time. The entire indexing operation was disk-bound. For the main test case, a hard disk with roughly 100,000 image files was chosen.

In order to minimize the time spent waiting for each file being read, it would be worthwhile to read all files in the same physical order in which they are residing on the hard disk. So the key information we need is the physical location of each file on the hard disk.

For this purpose, the FSCTL_GET_RETRIEVAL_POINTERS operation can be used:

struct MyFile { PTSTR sFilename; DWORD64 Lcn; DWORD dwFragments; };
 
void GetStartCluster( PCTSTR sFilename, MyFile& f )
{
    f.sFilename = sFilename;
    f.dwFragments = f.Lcn = 0;
 
    HANDLE hFile = CreateFile( sFilename, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL );
    if ( INVALID_HANDLE_VALUE != hFile )
    {
        const DWORD MAX_CLUSTERS = 100; // actually we only care about the first cluster number
        const DWORD RETRIEVAL_POINTERS_BUFFER_SIZE = sizeof( RETRIEVAL_POINTERS_BUFFER ) + ( 2 * ( MAX_CLUSTERS - 1 ) * sizeof( LARGE_INTEGER ) );
        BYTE output[ RETRIEVAL_POINTERS_BUFFER_SIZE ];
 
        STARTING_VCN_INPUT_BUFFER input;
        input.StartingVcn.QuadPart = 0;
 
        DWORD dwBytesReturned;
        if ( DeviceIoControl( hFile, FSCTL_GET_RETRIEVAL_POINTERS, &input, sizeof( input ), &output, sizeof( output ), &dwBytesReturned, NULL ) )
        {
            RETRIEVAL_POINTERS_BUFFER* p = (RETRIEVAL_POINTERS_BUFFER*)&output;
            if ( p->ExtentCount > 0 && p->StartingVcn.QuadPart == 0 )
            {
                f.dwFragments = p->ExtentCount;
                f.Lcn = p->Extents[ 0 ].Lcn.QuadPart;
            }
            else
                _tprintf( _T("Error: ExtentCount = %d StartingVcn = %I64d\r\n"), p->ExtentCount, p->StartingVcn.QuadPart );
        }
        else
            _tprintf( _T("Error: DeviceIoControl = 0x%08X\r\n"), GetLastError() );
        CloseHandle( hFile ); 
    }
}

Initially, the cluster number and the number of extents (fragments) is retrieved for every file. In a second step, all files are sorted according to the number of fragments and their cluster number. Then they are processed in exactly this new order which leads to a minimized amount of disk ‘thrashing’.
The actual retrieval of file locations using DeviceIoControl is relatively fast, since it only queries information from the file system and not from the file’s data location. Typically this operation is CPU bound and consumes less than 5% of all indexing time.

Taken into account the time needed to retrieve position data and sort files, this approach can save between 20 and 50% of read time, depending on average file size, fragmentation and spacial data distribution. There is no benefit from this method if the majority of files is fragmented. However, fragmentation is more likey to happen with larger files, and the average file size in this case was only 149 KiB. Generally speaking, the performance gain this method can provide increases with decreasing file sizes.

Benchmarking

• Hard disk: 1 TB 7200 rpm SATA II, avg. access time: 17 ms
• Windows XP Professional 32 bit booted in protected mode
• Number of files scanned: 87,418
• Total file size: 12.46 GiB
• Average file size: 149 KiB
• Time for reading files in filesystem order: 506 seconds
• Average throughput reading files in filesystem order: 25.24 MiB/s
• Time for reading file position data: 12 seconds
• Time for sorting files according to their position: 54 ms
• Time for reading files in sorted order: 347 seconds
• Total time using new approach: 359 seconds
• Total throughput using new approach: 35.58 MiB/s
• Performance increase: 147 seconds or 29 %
• Reading files in filesystem order takes 1.42 times as long as a pre-sorted read