@ Head : VSM

Memory mapped files and pointers… or not ???

bill — Thu, 10 Mar 2011 01:29:04 GMT

Last week I was in Seattle for the MVP summit. Whilst there I saw a brief presentation from Joe Kunk on Memory Mapped files in .NET 4. I suggested to Joe that perhaps pointers might give a performance boost. Then someone from Microsoft (not to mention names) suggested if that were the case, it might be a good argument for the inclusion of pointers in a future version. I chatted to Joe afterwards and he suggested I download the code and give it a try, so I did. The following are my findings, and the journey along the way. The end result is a dramatic performance improvement:

First steps : code review

I downloaded Joe’s code and created a 5GB sample data file. I figured 5 GB is big enough to push it into the 64 bit realm. I ran the code and it took about 25 minutes to create the index file. I had a quick look at the code and identified some areas to immediately tweak. Inside the main code block loop there were a number of conversions going on, some implied; all of which tend to slow code down. The original code was as follows:

   For i = 1 To accessor.Capacity
      Dim CurrentByte = accessor.ReadByte(ViewPosition) : ViewPosition += 1
      Dim CurrentChar = Chr(CurrentByte)

      If (Char.IsLetterOrDigit(CurrentChar)) Then
         InWord = True
         Wordlength += 1
         If ((Char.IsUpper(CurrentChar) AndAlso CurrentChar = "R") OrElse
             (Char.IsLower(CurrentChar) AndAlso CurrentChar = "r")) Then
            HasR = True
         End If

There’s a number of issues to be aware of here. The code that compares a Char with a String causes overhead, causing the char to be converted to a string and then calling VB’s string comparison routines. Rather than write AndAlso CurrentChar = "R" , it’s better to write AndAlso CurrentChar = "R"c) . This makes it a simple comparison of Char’s.

The calls to IsUpper and IsLower are completely redundant and are more expensive than the Char comparison calls. In fact, it’s questionable if Char is even needed here. Given this code is purely designed for ASCII, not Unicode, I rewrote the code to use Byte instead of Char for this initial part of the loop. Modifying the code only took a few minutes, the only bump being the need to create a replacement for the IsLetterOrDigit call. I’d argue IsLetterOrDigit might not be what is wanted in the first place, as it means words with hyphens, @ signs or apostrophes are excluded. Given St Pat’s day is next week, I certainly wouldn’t want to be excluding any of the O’Reily’s ;)

Never the less, I kept the code pure to it’s original implementation. For IsLetterOrDigit, I made a simple True/False array. This was easy to make by writing out the values into the debug window, e.g:

      For i = 0 To 255
         Debug.Write(Char.IsLetterOrDigit(Chr(i)) & ", ")
      Next

From the output in debug window the output from that, I created a lookup array via cut and paste:

Private IsLetterOrDigit() As Boolean = {False, False, False, False, False, ……………

With those quick changes in place the test time dropped to around 18 to 19 minutes: a significant improvement, and well worth the time it took to make them, but nothing earth shattering.

Look for bottlenecks

On my desktop machine I have standard mechanical hard drives and newer Solid State Drives (SSD’s). The SSD’s are blistering fast, and make a huge gain in read times (and windows boot times). Putting the data file on a SSD gave a performance improvement of about another 5 minutes. (test was now 14.4 minutes). Although again a significant improvement, it wasn’t the order of magnitude I would expect in what is basically a file IO bound operation. This alluded to the bottleneck being the code, not the hardware. So it was time to revisit the entire Memory Mapped file hypothesis. The first step was to write a standard benchmark using a standard FileStream.

My first runs came in at about 36 seconds !!

I set the FileStream to read the data in blocks of &H10000 bytes at a time. It’s an arbitrary figure, but later testing shows it’s around the sweet spot for this particular machine. My first runs came in at about 36 seconds !! I was astounded. Some minor tweaks and the time was down to 32 seconds. I checked and verified the output. The locations were correct and I had the same number of matches as Joe did plus one. I’m guessing the extra one is a boundary case condition that my code picked up on. (It’d probably be easy enough to test by looking at the last entries)

Out of curiosity I put the data file back on the old mechanical drive. The time jumped massively from 30 seconds to about 90 seconds. This told me the bottle neck was now the hardware. Investment spent on the hardware rather than the software, such as SSD’s and even RAID SSD’s etc, are worth investigating at this point.

As to pointers?

Well I never bothered writing the code to test the pointers and memory mapped file. The code I wrote was already 40 to 50 times faster than the memory mapped file implementation. With the file stream approach I estimate pointers to save about 10%, or 3 seconds on the fastest case scenario. If you look under the covers of the file stream you’ll see the buffer used internally uses pointers with win API call to ReadFile. With a bit of work you could write your own wrapper, call ReadFile yourself and skip the copying from the internal buffer to the buffer used in the search loop. Rather than go to that length, I simply tested what that extra copying was causing by copying into yet another buffer from inside the search loop: that added about 3 seconds to the code. It hardly seems worth the effort. Rather than spend time porting the code to use pointers it would be probably more worth the time to investigate making the code run async (I’ll leave that one for another day ;) )

But that doesn’t mean there isn’t a case for pointers with memory mapped files. I used them many years ago (even from VB6). All I have shown is that for this case scenario, Memory Mapped files are not a good match. A compelling case scenario for pointers and memory mapped files remains to be shown.

Conclusion

Memory mapped files are useful in many scenarios, such as shared data manipulation, and inter process communication. For raw data reads however, they are overhead with no realizable benefit.

Create benchmarks using similar techniques. And look under the covers to try to understand the differences and their significance.
Write well typed code and use Strict On semantics where ever possible. For example the quick code clean-up I did on the original code shaved off 5 minutes. Although that was only 20% improvement for the initial code, it was quick and easy to implement. On the final code, that 5 minutes is a massive overhead on top of 30 seconds (10 fold) !! So little bits of detail in your code can go a long long way to writing high performance code.

#Region "modifications by Bill McCarthy"
 
 
   Private Function CreateIndexEntryList(ByVal TextFilePath As String) As List(Of IndexEntry)
 
      Dim index As New List(Of IndexEntry)(&HF0000)
      Dim bufferSize As Int32 = &H10000
      Dim offset As Int32 = 0
      Dim buffer(0 To bufferSize - 1) As Byte
      Dim filePosition As Long = 0
 
      Dim inWord = False
      Dim wordlength As Int32 = 0
      Dim hasR = False
 
 
      Dim sb As New System.Text.StringBuilder(6)
 
      Try
 
         Using stream = New IO.FileStream(TextFilePath, FileMode.Open, FileAccess.Read, FileShare.Read, bufferSize)
 
            Dim countRead = stream.Read(buffer, offset, bufferSize - offset)
 
            While countRead > 0
 
               Dim upper = countRead + offset
               For i = offset To upper - 1
                  Dim currentByte = buffer(i)
 
                  If (IsLetterOrDigit(currentByte)) Then
                     inWord = True
                     wordlength += 1
                     If (currentByte = byteUpper_R) OrElse (currentByte = byteLower_r) Then
                        hasR = True
                     End If
                  Else
                     If (wordlength = 5 And hasR = True) Then
 
                        Dim bufferPosition = i - 5
                        sb.Clear()
                        For j = 0 To 4
                           sb.Append(Chr(buffer(bufferPosition + j)))
                        Next
                        index.Add(New IndexEntry(sb.ToString, filePosition + bufferPosition - offset))
                     End If
                     inWord = False
                     wordlength = 0
                     hasR = False
 
                  End If
 
               Next
               offset = wordlength
               If offset > 0 Then
                  For i = 0 To offset - 1
                     buffer(i) = buffer(upper + i - offset)
                  Next
               End If
 
               filePosition += countRead
               countRead = stream.Read(buffer, offset, bufferSize - offset)
 
            End While
 
         End Using
 
      Catch ex As Exception
         Dim message = "IndexingLargeFiles.Index.CrearteIndexEntryList: " + ex.Message
         Throw New Exception(message, ex)
      End Try
 
      Return index
   End Function
 
 
   Private Const byteUpper_R = CByte(Asc("R"c))
   Private Const byteLower_r = CByte(Asc("r"c))

Private IsLetterOrDigit()As Boolean = {False,False,False,False,False,False,

False, False, False, False, False, False, False, False, False, False, False, False,
False, False, False, False, False, False, False, False, False, False, False, False,
False, False, False, False, False, False, False, False, False, False, False, False,
False, False, False, False, False, False, True, True, True, True, True, True, True,
True, True, True, False, False, False, False, False, False, False, True, True, True,
True, True, True, True, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, False, False, False, False,
False, False, True, True, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, True, True, True, True, True,
False, False, False, False, False, False, False, False, True, False, False, False,
False, True, False, True, False, True, False, True, False, False, False, False, False,
False, False, False, False, False, False, True, False, True, False, True, True, False,
False, False, False, False, False, False, False, False, False, True, False, False,
False, False, False, False, False, False, False, False, True, False, False, False,
False, True, False, False, False, False, False, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, True, True, True, True, True,
True, True, True, False, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, False, True, True, True, True, True, True,
True, True}

#End Region

Saving and transferring customisations

bill — Wed, 25 Nov 2009 03:54:10 GMT

I got an email from a reader last week asking about saving customisations in Visual Studio:

Hi Bill

I read an excellent article by you

http://visualstudiomagazine.com/Articles/2007/12/01/Customize-the-VB-IDE.aspx?Page=1

Just wondering if you know of a way to export those customisations so I can set up my computer at work restore after HDD fails and share my favorite settings with friends.

Also would like to do same for my VBIDE customisations

I have googled to no avail...... :-/

Well the good news is this is incredibly easy. On the Tools menu in Visual Studio you should see the “Import and Export Savings . . .” command. You can choose what groups of settings to import or export.

Iterators in VB 10 ?

bill — Mon, 02 Feb 2009 13:56:01 GMT

Although VB 10 won’t have a formal syntax for iterators, it will have all the necessary ingredients to easily write iterators. In VB10 you can use a generic template and multi line lambdas to create iterators.

This iterator in C# :

static public IEnumerable<String> Lines( this TextReader rdr)
{
     String line;
     while ((line = rdr.ReadLine()) != null) {
              yield return line;
     }
}

Can be written as this in VB10:

<Extension()> 
Public Function Lines(ByVal rdr as TextReader) As IEnumerable(Of String)

     Return New GenericIterator(Of String) 
          (Function(ByRef nextItem As String) As Boolean
              nextItem = rdr.ReadLine
              Return nextItem IsNot Nothing
           End Function)

End Function

The above code uses a generic iterator class that accepts a lambda function. The lambda function sets the Current item of the iterator and returns True if MoveNext should be True. The above example is written as an extension method, but you can also use the inner part of the function inline.

For more on using iterators in VB 9 today, as well as the generic class for the above example, see my latest article in Visual Studio Magazine .

Generic variance and List(Of T)

bill — Fri, 08 Aug 2008 04:55:36 GMT

This post has been sitting in my drafts for a while, so I thought I should post it, mainly because I want to talk about this and generic variance and arrays in more detail in the days ahead. The reason this post was put on hiatus was I was waiting for my article on arrays to appear in Visual Studio Magazine, as that deals with many of the details as to why this works ;)

Have you ever wanted to cast a List(Of Customer) to a List(Of BusinessBase), where Customer Inherits BusinessBase, only to find that you can't... well you can ;)

This extension will return an IList of BusinessBase for an input of a List(Of Customer). Be aware it is the underlying array, so you will need to get the actual count from the original input.

   <Runtime.CompilerServices.Extension()> _

   Function ToIList(Of T, TBase)(ByVal list As List(Of T)) As IList(Of TBase)

      Dim fi = GetType(List(Of T)).GetField("_items", Reflection.BindingFlags.Instance Or _

                                                      Reflection.BindingFlags.GetField Or _

                                                      Reflection.BindingFlags.NonPublic)

      Return CType(fi.GetValue(list), IList(Of TBase))

   End Function

And a quick test:

Module Module1

   Sub Main()

      Dim myApples As New List(Of Apple)

      myApples.Add(New Apple With {.Name = "Golden Delicious"})

      myApples.Add(New Apple With {.Name = "Red Delicious"})

      myApples.Add(New Apple With {.Name = "Granny Smith"})

      Dim fruits As IList(Of Fruit) = myApples.ToIList(Of Fruit)()

      For i = 0 To myApples.Count - 1

         fruits(i).Name = "Fruit : " & fruits(i).Name

      Next

      For Each a In myApples

         Console.WriteLine(a.Name)

      Next

      Console.WriteLine("finished")

      Console.ReadLine()

   End Sub

   <Runtime.CompilerServices.Extension()> _

   Function ToIList(Of T, TBase)(ByVal list As List(Of T)) As IList(Of TBase)

      Dim fi = GetType(List(Of T)).GetField("_items", _

                                         Reflection.BindingFlags.Instance Or _

                                         Reflection.BindingFlags.GetField Or _

                                         Reflection.BindingFlags.NonPublic)

      Return CType(fi.GetValue(list), IList(Of TBase))

   End Function

End Module

Class Fruit

   Private _Name As String

   Public Property Name() As String

Get

         Return _Name

      End Get

      Set(ByVal value As String)

         _Name = value

      End Set

   End Property

End Class

Class Apple : Inherits Fruit

End Class

Least among equals ?

bill — Tue, 25 Mar 2008 11:10:00 GMT

Patrick Meader writes on the divide between VB and C# inside Microsoft, and raises an interesting question.

My response is probably going to be lengthy; more than I have time for at present. In the meanwhile, what do you think of the issues raised in Pat's editorial ?

What's new in VB 2008

bill — Fri, 21 Dec 2007 03:23:00 GMT

Visual Studio magazine's January On VB column, by your's truly, has a quick reference guide to what's new in VB 2008. The guide includes links to earlier articles that provide more in depth information on specific features.

Errata for my January column:

The web site fails to display & properly instead showing &. The relevant part of he article should read:

XML literals are, as the name implies, the literal representation of the XML as it would appear in a file (or close to it). For example, if you wanted to name a book "War & Peace" instead of "War and Peace," you'd need to encode the & to & inside the XML literal:
' won't compile
Dim el = _
   <book>War & Peace</book>

' will compile
Dim el = _
   <book>War &amp; Peace</book>

Cleaning up your XML literal namespaces

bill — Sat, 24 Nov 2007 05:16:00 GMT

If you use XML literals in your code, adding one to another:

Dim e1 = <a:books></a:books>
dim e2 = <a:book></a:book>
e1.Add(e2)

You will have the xmlns declaration repeated in each of the elements, when really it is only needed once per the document or outer element. The problem is caused by VB adding a xmlns declaration as an attribute to the root element. It can get a bit more complex if you have duplicate namespace declarations with different prefixes. So I decided to write a CleanUpNS extension, that keeps the xml written clean by removing un-necessary namespace declarations. To use it, simply add a call to CleanUpNS to the end of your literals, e.g:

Dim e1 = <a:books></a:books>.CleanUpNS
dim e2 = <a:book></a:book>.CleanUpNS
e1.Add(e2)

   <Runtime.CompilerServices.Extension()> _
 Function CleanUpNS(ByVal el As XElement) As XElement
      Dim current = el.LastAttribute
      Do While current IsNot Nothing
         Dim temp = current.PreviousAttribute
         If current.IsNamespaceDeclaration AndAlso el.Name.NamespaceName = current.Value Then
            current.Remove()
         End If
         current = temp
      Loop
      Return el
   End Function

I go into more details about how this works and how the XML is stored and emitted in my January On VB article in Visual Studio Magazine.

Snippet Editor 2008 release

bill — Tue, 06 Nov 2007 11:49:00 GMT

I've updated the Snippet editor to work with Visual Studio 2008 and 2005 releases.

Note this release requires .NET 3.5.

Changes/fixes:

Added 2008 product range to the list of products
Fixed replacement of the install root variable for Visual Studio that was resulting in a double \ midway of file paths
Removed VB's single instancing and replaced it with named pipes messaging. This fixes various issues to do with firewalls, and the remoting VB tries to do. See Visual Studio Magazine November for details on the NamedPipes usage.
Set the required permissions to run the application as Administrator for Vista. Without this, the app would run, but snippets would be saved in the VirtualStore where Visual Studio wouldn't see them properly. The problem revolves around Visual Studio having the snippet stores in the Program Files tree.

~~The download includes the source and the release build. (in the bin\release path)~~

UPDATE: The files are now available from my web site (http://billmccarthy.com/Projects/Snippet_Editor)

Enjoy :)

Thoughts on Expression Trees

bill — Wed, 15 Aug 2007 09:04:01 GMT

I just finished writing an article about Expression Trees for Visual Studio Magazine (aka VBPJ) and there seemed to be some "holes" that I think should be plugged. An expression tree is basically a descriptive way of representing a lambda function. The standard LINQ query operators (e.g Where Group, Join et al) on an IQueryable will cause the language compilers to compile the lambda function as an expression tree. From there the expression basically allows for translation between, such as VB or C# to TSQL.

A problem with this "translation" is that it is not 100%... that is, not all things you write in a lambda can be translated. If you think about TSQL for example you can see there is a very finite limit of what can and what can't be translated. Unfortunately the way things are you don't and can't really get any design time feedback on this. For example, the extension methods in Queryable work for any IQueryable, so without a runtime analysis of the IQueryable.Provider you can't really ask for what language features it supports.

So.... this got me thinking... What about a couple of design time attributes ? The first would be on your collection/IEnumerable /data source and would specify the provider from which to query the supported features. This might take the form of <QueryProvider("MyEntityFramework")> . The "MyEntityFramework" should be the qualified named for the actual IQueryable.Provider .

The next problem is an extension method doesn't tell us if it is going to use the provider or return the same provider, so we need an attribute on them to do so. e.g <QueryProvider(UsesProvider:= True, ReturnsSameProvider:= True)> . We probably need a third property for this attribute that specifies the Provider it returns if ReturnsSameProvider is false.

Finally, a third attribute for the provider itself to indicate whether it is the design time service provider as well or the fully qualified class name for the design time service provider.

Then, it should be possible to provide a great design time experience for any query provider.

$0.02

Extension methods on VSM

bill — Wed, 30 May 2007 14:34:17 GMT

My article about Extension methods is now on the web. Unfortunately an edit I made didn't make it into the print version (and the web version is the same as the print). The problem was as I looked at the way extension methods worked in Beta 1, it was as I was told it would work form discussions I had had with members of the VB team. But as I looked at it further it dawned on me that the design of having any instance method hiding all extension methods with the same name wasn't really desirable. So I talked to some folks on the VB team about this. Meanwhile we were pushing the deadline out for print. I ended up making edits but they didn't make it into the printed release.

The last two paragraphs of the article read:

If you recall the rules around precedence, you might be wondering if methods in your collection classes might Shadow LINQ statements by mistake. The answer to that is actually rather complex. The compiler goes out of its way to let the LINQ statements work. If you add a Select method to your collection class, VB uses AsQueriable to cast your collection to an IQueriable type, which means the compile precedence is on the IQueriable type. If you also have an AsQueriable type, it tries an AsIEnumerable extension, and failing that, it tries the Cast extension method. If all of those are Shadowed then the compiler throws a compile time error.

The goal is to allow you to use LINQ statements on existing collections of all sorts. Methods inside the collection classes are viewed as being from prior to LINQ and hence having a different intent. For this reason, the compiler attempts to navigate around them. If you need to change the LINQ behavior, you must use extension methods defined in a module and implement namespace precedence to suit your needs.

That was technically correct at the time, but I believe inaccurate as to what should happen, and as to what happens in C#. The edited article replaced those two paragraphs with the following:

If you recall the rules around precedence, you might be wondering if methods in your collection classes might Shadow LINQ statements. The answer to that is instance methods will shadow by name and signature any extension methods. In the March CTP VB behaves differently: See sidebar "Out of the Shadows".

Shadowing by name and signature in this case means methods that would resolve to the same if both were instance methods. Remember extensions are Shared methods with the first parameter the instance: hence when determining if a method is shadowed by an instance method, the first parameter in the extension method is removed from the actual signature.

For example, a Select extension would be shadowed by an instance method as long as the instance method has the correct and matching signature.

' inside a module

<Extension()> _

Public Function [Select](Of TSource, TResult) _

(ByVal source As IEnumerable(Of TSource), _

ByVal selector As Func(Of TSource, TResult)) _

As IEnumerable(Of TResult)

….

End Function

' instance method inside the collection class

Public Function [Select](Of TResult)_

(ByVal selector As Func(Of T, TResult)) _

As IEnumerable(Of TResult)

….

End Function

The source parameter is removed from the signature for the extension method, generic parameters are resolved, and return types ignored to determine if the instance method shadows the extension: if they match, the instance method gets precedence.

The difficulty in using instance methods over extension methods for LINQ queries is you need to chain return types with types you have your instance methods in. Taking the earlier example of selecting a distinct list, the Distinct method has to be inside the type returned by the Select method. In that particular example you can have the Select return the same collection class and put your Distinct method in there. This becomes more complex when dealing with other projections and anonymous types. Rather than use instance methods you'll find it generally easier to import a module with your extension methods in it.

Extension methods can make creating customized LINQ queries, easier, and easier to share amongst your different libraries or collection classes. Powerful, yet incredibly simple in essence: used wisely they'll make your coding easier.

The sidebar was :

Out of the Shadows

In the March Orcas CTP, and most likely for Beta 1 of Orcas, VB shadows all extension methods by an instance method with the same name. That is, it shadows by name, not by name and signature. This has some unfortunate side effects such as the inability to add extensions with more or different parameters. A more complex issue arises around LINQ queries: if you have a Select method in your collection class that is the incorrect signature for the LINQ query, any Select extension in scope will be ignored for your collection class because they are shadowed. The compiler will then call a different extension method AsQueriable to cast the type to an IQueriable(Of T). Extension methods are then resolved for an IQueriable(Of t) rather than your collection class type. If your Select extension was written strongly typed to your collection class, it won't get called.

The good news is I've had a chat to some of the VB team, and they've promised me they'll look into. Most likely they will change it to shadows by name and signature. The bad news this change won't make it into Beta 1, you'll have to wait till Beta 2.

This highlights why we need to look at the early CTP's and betas and give Microsoft feedback. They share these early bits with us so as we can shine light on things others might not notice and give them feedback early enough to steer them clear of any rocks lurking in the shadows. J

And a special thanks to Adrian and Amanda for listening J

My sincerest apologies for not getting this in the article on time to make the print release.