2010-03-29-Vb20xx-Bottlenecks and traps using Linq with expensive select-expressions

Version	Description
2010-03-29 T15:51:00	Corrected formula for number of calls to new.

Description:

Implement Lazy-Load pattern for IEnumerator.Item[Get].

Problem:

If you are a linq-beginner there is something you should really be aware of before using it. Otherwise some day you may wonder about strange bugs or bad performance of your linq application.

Starting with linq some months ago I meanwhile like it very much and went deeply in using Linq-querys for various use cases. I used the select expression also to instantiate objects as shown in the below code snippet. Doing so i walked in a trap because i was not aware, that the select expression is evaluated each time the object set is enumerated. Also complex queries may be evaluated very often which increases runtime costs when the result tree is not copied.

Consider the following Vb.Net code:

 Dim aCount As Integer = (From aNum In New Integer() {1,2,3} Select New Object).Count

This query seems ok, but the problem is, that new objects are instantiated each time the list is iterated and even if one uses the Count-extension-method. This results in a number of calls to new of n * c + n * i where n is the number of items in the list, c is the number of requests to the count method and i is the number of iterations. The required number of calls to new is more less equal to n.

I now use following extension method to solve this problem and get the desired number of n calls to new:

 Module MyExtensions
  <System.Runtime.CompilerServices.Extension()>_
  Friend Function EvaluateItems(Of T)(ByVal aItems As IEnumerable(Of Func(Of T))) As IEnumerable(Of T)
   Dim aArray As T()
   Dim aCount As Integer = aItems.Count
   ReDim aArray(aCount - 1)
   Dim aIndex As Integer
   Dim aItem As Func(Of T)
   For Each aItem In aItems
    aArray(aIndex) = aItem()
    aIndex = aIndex + 1
    Next
   Return aArray
  End Function
 End Module

 Dim aQuery As IEnumerable(Of Func(Of Object)) = (From aNum In New Integer() {1,2,3} Select Function() New Object)  Dim aCount1 As Integer = aQuery.Count
 Dim aObjects As IEnumerable(Of Object) = aQuery.EvaluateItems
 Dim aCount2 As Integer = aObjects.Count

With the obove code only n constructors calls occur where n is the number of objects in the list.

However, i have one suggestions here.

Of course it is necessarry that the select expression is evaluated each time the item is requested. However, this does not apply if the list is only enumerated using IEnumerator.MoveNext without using IEnumerator.Item[Get]. The Interface design is suitable for implementing a lazy load here but (linq)-implementations of IEnumerable do not follow this.

I also wrote a extension method to (deep)-copy any IEnumerable tree for optimizing complex queries where updating is handled by the owner of the query result. The implementation quite tricky and not not so good so i don't post it here yet. Maybe Microsoft could provide a default extension method or a code snippet to do this.

Beside of this i'd like to suggest linq to implement a lazy load in IEnumerator.Item.Get to allow iteration without evaluating the select expression. For example this is done when counting items or when requesting an item at the end of the object set using ElementAt. For some use cases (for example implementing paging) this behaviour is required.

Solution:

1a. Implement lazy load in certain IEnumerator.Item[Get] implementations. (For example Linq)

Or

1b. provide extension method to create a ghost-list.

2. Provide a IEnumerable-Extension method which deep-copys items in an ienumerable (to an array) to avoid unneccesarry evaluations of the select expression.

TestCase:

 Class C
  Public Sub New()
   InstanceCount = InstanceCount + 1
  End Sub
  Public Shared InstanceCount As Integer
 End Class

 Module Test

  Function MyCount(ByVal a As IEnumerable) As Integer
   Dim aCount As Integer
   Dim aEnumerator As IEnumerator = a.GetEnumerator
   While aEnumerator.MoveNext
    aCount = aCount + 1
   End While
   Return aCount
  End Function

  Sub Test
   Debug.Assert(3 = MyCount((From aNum In New Integer() {1,2,3} Select New C).CreateGhostList)
   Dim aSuggestionImplemented As Boolean = True
   If aSuggestionImplemented Then
    ' This will fail with Vb.Net 2010
    Debug.Assert(0 = C.InstanceCount)
   Else
    ' In Vb.Net 2010 using IEnumerator.MoveNext evaluates the Select expression of a linq-query.
    Debug.Assert(3 = C.InstanceCount)
   End If
  End Sub

  End Module

2010-02-24-Vb20xx-reflapi-Karl-Michael Beck To LW

Keywords

• Type safe reflection api.
• Inheriting from Generic-type-arguments

version: 2010-02-24T23:15

Hi L,
I would suggest to implement an extended type system for compiletime checked type safety of code generators and other code using reflection.

1. Problem: Reflection APi not type safe.

A language integrated code generator and code based on reflection may want to use a reflection-api that supports compile-time checks. Using reflection is not type safe. If you accept an type object there are very often constraints to type objects valid for specific use cases. These constraints can be checked at runtime but there is no compiletime check for it.

2. Problem: Inherit from generic-template-arguments

As in c++ a class can be inherited from template arguments users may want to inherit from generic type parameters in vb. As vb supports type constraints for generic type arguments working with base type members inherited from generic type arguments can be compile-time checked.

2. Solution: Provide a type safe reflection api.

' Begin Vb20xx
Class B
End Class
Class C
  Inherits B
End Class
Class Demo
  Sub S
   Dim ob As B = New C ' valid cast: C is kind of B
   Dim oc As C = New B ' compiler error: B is not kind of C
   Dim tc As Type = GetType(B)
   Dim tb As Type(Of B) = GetType(C) ' Valid cast: C is kind of B
   Dim tc As Type(Of C) = GetType(B) ' Compiler error: B is not kind of C
  End Sub
End Class
' End Vb20xx

2. Solution: Inherit from generic-type-arguments.

The mechanism needed to implement solution 1 has something todo with the ability to inherit from generic-type-arguments. This feature may also be public for the users. However, there must be some new layers for type-system implemented for the final type system requires to use this service.

' Begin Vb20xx
Class C
End Class
Class G(Of T As C)
  Inherits T ' inherits any member in C and any member in T.
  Sub New()
   Dim c As C = Me ' Valid cast: T is constrained to C.
  End Sub
End Class
' End Vb20xx

Note: A Problem arising here is, that each member in the generic type must be implicitely declared as shadows. But i guess, together with a homogenous naming system this case is quite strange.

2010-02-25-Vb20xx-multiinh-Karl-Michael Beck To LW

Keywords

• Use InheritNoData to use Multiple inheritance with NoData-Inheritance mode.
• Use MemberContext to extend classes in local scopes.
• Use Identifier-Mapping when overriding members.
• Use BadCast and GoodCast to separate casting-use-cases.

version: 2010-02-24T23:01

This article contains a suggestion for language extension which may be implemented in further versions of the microsoft visual basic programming language.

The article's homepage is http://karlchenscoderdasein.blogspot.com/2010/02/2010-02-24-vb20xx-karl-michael-beck-to.html

Dear Reader,

if you are a microsoft employee to categorice this content please read the solution first.
I allready have contact to vb-lead-spec but would like to use this platform to keep up your working process.
In the non-public area i have the email adress of the vb-lead-spec-employee in question.

Hi L.,

i'll come back later for your code-generator-language.
I think i have an good alternative for the code-generator-internal-type system you talked about.

For now i have another 4 issues which i think are very usefull:

1. Problem: Multiple inheritance

Using virtual inheritance may be very usefull but brings some very sophisticated rules with it, which may confuse developers and rise development costs. Refer to the c++ memory managment for multiple, virtual inheritance and the arising rules for usage of base-base-class constructor and default constructor.

This may be one reason not to support multiple inheritance in a given language like in vb.net.

For a good reason to use multiple inheritance refer to the problems in a visitor pattern arising in vb.net:

Refer to the visitor pattern introduced in Problem/solution 1-3.

In vb.net 2010 you have two alternatives:

1.1. Define a Visitor Base class

1.1.1. Pro: You may implement empty visit-methods in the base class so specific visitors may only override the visit-methods they need.

1.1.2. Contra: you can not implement a visitor in a class which allready has another base class.You need to write extra delegation code.

1.2. Define a visitor-interface:

1.1.1. Pro: You may implement the interface in any class which already has a base class.

1.1.2. Contra: You need to implement all visit-methods although if you don't need them in a specific visitor

I would like to introduce a language specification which alows to eliminate the above cons and implements a safer way of multiple inheritance.

2. Problem: Lots of Dependencies

Refer to the visitor pattern introduced in Problem/solution 1-3.

The visitor-pattern in a very fundamental way shows how you get unwanted dependencies in classes. Often the responsibilites in the visit-methods-arguments have totally nothing to do with the responsibility of the class which needs to declare the accept methods. Actually the class declaring the accept method may be a generic container-class which with the visitor pattern has a dependency to types which may be generic type-arguments. But users accept this unneccesary dependency because they are avoding bad-casts from the base class to the child class. (By using the visitor-pattern you can implement get the same results as with a bad-cast but you are not loosing compiler checks)

I would like to introduce a language specification way which allows to implement the pattern without producing such dependencies.

3. Problem: Base-Method Mapping

I have some patterns which produce naming-conflicts when overriding methods. They may also arise in the solution of Problem 2.

4. PRoblem: Bad-Cast and Good-Cast is not separated with CType, DirectCast.

Currently there is only CType or DirectCast. They are not suitable to distinguish following cases:

1. The users does a good-cast fro a child class to a base class or to the same class. This is only done to clarify code.

2. The user does a bad-cast from the base class to the child class.

In vb2010 users will use directcast or CType for both cases.

==============================================================================================================================

Dear Reader,

if you are a microsoft employee to categorice this content you may forward it to L.W. (l.w@microsoft.com)

Solutions:

Solution 1: Support 2 inheritance modes: data-inheritance and no-data-inheritance.

Refer to the visitor pattern introduced in Problem/solution 1-3.

Support declaration of no-data-classes. Inheritance can use:

0..1 Data-Classes
0..* NoData-classes

' Begin Vb20XX:
Public DataClass CMyDataBaseClass1
End Class
Public DataClass CMyDataBaseClass2
End Class
Public NoDataClass CMyNoDataClass1
End Class
Public NoDataClass CMyNoDataClass2
 Private m as Integer ' compiler-error: no data allowed in no-data-classes
End Class
Public DataClass CMyChildClass
 InheritsData CMyDataBaseClass1
 InheritsData CMyDataBaseClass2 ' Compiler error: only 1 data base class allowed.
 InheritsNoData CMyNoDataClass1
 InheritsNoData CMyNoDataClass2
 InheritsNoData CMyDataBaseClass2 ' Compiler error: data class can not be used for nodata class inheritance.
End Class
' End Vb20XX:

Applying this language specifications to the visitor pattern allows to define visit-methods in a no-data-base-class which can be used as baseclass anywhere.

Consider what the user will do if he needs to access data: HE will declare mustoverride Properties in the no-dataclasses which he will implement in child classes. Like this the user is forced to explicitely declare how memory managment is done and he has more oppertunities than in c++. Refer to solution 3 for this issue.

Following this pattern naming conflicts can arise which i would like to solve in Solution 3.

==============================================================================================================================

Solution 2. Support object-context specific extensions for classes:

Refer to the visitor pattern introduced in Problem/solution 1-3.

Consider implementations of the Visitor pattern. You will notice that you may have a lot of dependency in the class which provides the base methods for the Accept routine.

I could imagine a mechanism that solves this problem.

I would like to define members for a class which only are visible in a specific "member-context". Such a membercontext is very similar to a namespace. So it may result in each membercontext having an own v-table and an own type-descriptor.

I would like to dynamically attach these members to allready compiled clr-code.

Imagine:

' Begin Vb20XX:
MemberContext MC1
  Namespace N1
   Class Ag
    ' this class will be extended with a visitor-pattern in another member-context
    ' you can not access/see the visitor pattern here.
   End Class
   Class B
    Inherits A
   End Class
  End Namespace
End MemberContext

' this member context implements the visitor pattern (maybe in another assembly)
MemberContext MC2
  Namespace N2 ' this namespace matches to the above namespace in MC1
    Friend Partial Class A
      Friend Overridable Sub Accept(ByVal aVisitor As CVisitor) ' member only valid in MC2.
        Throw New NotImplementedException("Method should be overridden.") ' MustOverride seems not to be applicable here.
      End Sub
    End Class
  End Namespace
   Friend Partial Class B
    Friend Overrides Sub Accept(ByVAl aVisitor As CVisitor)
     aVisitor.VisitB(Me)
    End Sub
   End Class
   Friend Class C ' This class only exists in MC2
    Inherits A
    Friend Overrides Sub Accept(ByVAl aVisitor As CVisitor)
     aVisitor.VisitC(Me)
    End Sub
   End Class
  Friend NoDataClass CVisitor
   Public Overridable Sub VisitB(ByVAl b As B)
   End Sub
   Public Overridable Sub VisitC(ByVAl c As C)
   End Sub
  End Class
  Partial Class A
   Friend Mustoverride Sub Accept(ByVAl aVisitor As CVisitor)
  End Class
End MemberContext
' End Vb20XX:

Using this language specifiication any user may define additional dependencies which only apply in his member context. Other users can not see/access the members defined in a member context unless they are declared public rather than friend.

==============================================================================================================================

Solution 3. OVerride-Name-Mapping

I would like to map implementations of base-class members similar to the interface-implemenation mapping supported in vb 2008

' Begin Vb2010:
  Interface I
    Sub F()
  End Interface
  Class C
   Implements I
   Protected Sub FImpl() Implements I.F
   End SUb
  End Class
' End Vb2010:
' Begin Vb20XX:
  Class B
   Public MustOverride Sub F()
  End Class
  Class C
    Inherits B
    Private Sub FOverride() As CBaseType OVerrides MyBaseClass.F
    End Sub
    Public Shadows Sub F() As CChildType
    End Sub
' End Vb20XX:

Refer to the no-data-inheritance in solution 2:

Several No-Data-Base-Classes may define MustOverride-data-accessors which have the same name but in the child class implementing the data the abstraction level is lowered and the identifiers may become more concrete. A use case of this pattern is described in solution 1.

For example:

' Begin Vb20XX:
Public NoDataClass Nd1
  Public MustOverride ReadOnly Property O As Object
End Class
Public NoDataClass Nd2
  Public MustOverride ReadOnly Property O As Object
End Class
Public DataClass D1
  Inherits NoData Nd1
  Inherits NoData Nd2
  Public Mustinherit ReadOnly Property O1 As OBject Overrides Nd1.O
  Public Mustinherit ReadOnly Property O2 As OBject Overrides Nd2.O
End Class
' compiler error when referencing D1.O: member is not accessable: the identifier is ambiguous.
' End Vb20XX:

4. BadCast/Good Cast keywords

I'd like to introduce a language specification which defines keywords to clearly separate cast-use-cases.

' Begin Vb20XX:
Class B
End Class
Class C
  Inherits B
End Class

Class Test
  Shared Sub Execute()
   Call GoodCast(New C, B)
   Call GoodCast(New B, C) ' Compiler error
   Call BadCast(New C, B) ' compiler error
   Call BadCast(New B, C)
  End Sub
End Class
' End Vb20XX