Author Topic: My Proposal For Optimizing LINQ  (Read 2933 times)

0 Members and 1 Guest are viewing this topic.

TheMaster

  • Guest
My Proposal For Optimizing LINQ
« on: February 08, 2012, 05:58:53 PM »
http://connect.microsoft.com/VisualStudio/feedback/details/510253/linq-optimization-with-non-generic-icollections

This was originally brought about as a result of having to deal with Autodesk's failure to implement IEnumerable<T>, ICollection<T>, and IDictionary<TKey, TValue> on many AutoCAD types that expose collections as non-generic IEnumerable, ICollection, or IDictionary.


Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: My Proposal For Optimizing LINQ
« Reply #1 on: February 08, 2012, 09:32:40 PM »

Thanks for the link Tony.

A bit over 2 years since the original posting ... Is the issue actually closed/resolved ...  can't make the time to read fully at the moment.
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

fixo

  • Guest
Re: My Proposal For Optimizing LINQ
« Reply #2 on: February 09, 2012, 01:04:42 AM »
You're really bad, Tony :)

TheMaster

  • Guest
Re: My Proposal For Optimizing LINQ
« Reply #3 on: February 09, 2012, 05:29:23 AM »

Thanks for the link Tony.

A bit over 2 years since the original posting ... Is the issue actually closed/resolved ...  can't make the time to read fully at the moment.

It's closed, but as a result they did make some changes in .NET 4.0 (they now support both the generic and non-generic ICollection at every point where they previously supported only ICollection<T>), and that was a direct result of that feedback, but I have been lobbying for more, along the lines of my prototype.

The summary of the proposal is that, with the changes I outlined implemented, the number of items that will be returned by a complex LINQ expression like what follows can be determined without having to execute the expression and iterate over the returned items (as is required today):

Code: [Select]

  ICollection items =  // assigned to non-generic ICollection
  var expr = items.Cast<TSomething>().Select( a => a.b ).OrderBy( b => b.c );

  //  here, the count is obtained without executing the LINQ expression:
  int count = expr.Count(); 


The scheme involves adding an interface to the objects returned by
Select(), OrderBy(), Cast() (and others), that would allow each of
them to query their adjacent operator/source argument for a count.

Because each of those iterator objects returned by the LINQ operators
shown in the example are often the source of another iterator object, 
the query can propagate down the calling chain until one of the objects
in it returns a count, that would then be returned back up the chain of
callers until it reaches the Count() method call and becomes its result,
and we've deduced the number of items in the result of the composite
 LINQ expression without executing it. :-o 

Today, as the design exists in all current versions of the framework, the
call to Count() in the above example triggers execution of the LINQ
expression, to produce a resulting count, and the expressions result is
unreachable, requiring the expression be executed again, in order to
make use of it.

The optimizations are not only for the sake of the Count() method.
They're also beneficial to ToArray(), ToList(), ToDictionary(), ToLookup(),
and so forth, because they must incrementally grow an array in order
to build their result when the count of items is unknown. If the count
of items is known, they can allocate the needed array capacity in one
swell foop (similar to how the List<T>(int capacity) constructor works).

So in the above example, the Count() method would ask the object
returned by OrderBy() for a count. The object returned by OrderBy()
would in-turn ask the object returned by Select() for a count, which
in-turn asks the object returned by Cast() for a count. The object
returned by Cast() would examine its source argument; see that it is
an ICollection (that knows how many elements it contains), and simply
return the value if it's ICollection.Count property.

The caveat (of course there's always one or two), is that this scheme
only works with LINQ operators that return a determinant number of
items. LINQ operators whose result count is indeterminate and depend
on conditional branching (an example of which is the Where() operator)
cannot implement the interface or participate in the scheme, since they
can't determine how many items they will yield without actually executing
and producing the result.
« Last Edit: February 09, 2012, 05:36:48 AM by TheMaster »

retsameht

  • Mosquito
  • Posts: 15
Re: My Proposal For Optimizing LINQ
« Reply #4 on: February 21, 2024, 03:20:41 AM »

Thanks for the link Tony.

A bit over 2 years since the original posting ... Is the issue actually closed/resolved ...  can't make the time to read fully at the moment.

Hi Kerry.

Well, 12 years later and 14 years since I posted it, they finally got around to implementing my proposal (in .NET 6.0), in the form of TryGetNonEnumeratedCount(), and IIListProvider<T>. While their implementation is somewhat more intricate than my humble proof-of-concept, it is conceptually based on it, precisely.

Attached is the original code from that proposal, in which my TryGetCount() method materialized as TryGetNonEnumeratedCount(), and my IFixedSizedEnumerable<T> interface materialized as IIListProvider<T>.

Back when I first came up with this, it was significantly faster than the framework 4.7 Linq runtime. However, they did quite a bit of optimization since, and now the .NET 8.0 runtime's implementation of the aforementioned optimizations are roughly 2x faster than my proof-of-concept code. So, don't bother with it.  :laugh:

They also implemented my proposals for CountBy() and DistinctBy() which I may have posted about here around the same time frame, but can't remember.

« Last Edit: February 21, 2024, 03:34:35 AM by retsameht »

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2135
  • class keyThumper<T>:ILazy<T>
Re: My Proposal For Optimizing LINQ
« Reply #5 on: February 21, 2024, 03:21:48 PM »
Thank you Tony, great to see you back here . . and with most excellent news.
I'll do some study in the upcoming week.

Very clever name choice !!

Quote from: DrWhoWiki
An incarnation of the Master - seemingly one of the last of his original regeneration cycle

Stay well
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

57gmc

  • Bull Frog
  • Posts: 366
Re: My Proposal For Optimizing LINQ
« Reply #6 on: February 21, 2024, 06:11:36 PM »

Very clever name choice !!
I thought it was maybe Arabic. :-)

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2135
  • class keyThumper<T>:ILazy<T>
Re: My Proposal For Optimizing LINQ
« Reply #7 on: February 21, 2024, 07:40:11 PM »

Very clever name choice !!
I thought it was maybe Arabic. :-)


Perhaps it is that too,

. . .  but read it backwards    :-)
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

57gmc

  • Bull Frog
  • Posts: 366
Re: My Proposal For Optimizing LINQ
« Reply #8 on: February 21, 2024, 07:47:01 PM »

Very clever name choice !!
I thought it was maybe Arabic. :-)


Perhaps it is that too,

. . .  but read it backwards    :-)
I got it. It was just my attempt at humor. :0-)

JohnK

  • Administrator
  • Seagull
  • Posts: 10627
Re: My Proposal For Optimizing LINQ
« Reply #9 on: February 21, 2024, 09:59:58 PM »
Welcome back, Tony. ...As a new member (again) you are entitled to (one time) publicly call my code/idea/concept moronic; I will see if I can work up a good enough topic to start a heated discussion but if you are short on time, I have in the queue:

[0] My version is faster because error checking is not really necessary.
[1] Just integrate the whole list/array and don't worry about bounds.
[2] ALWAYS sort an array.
[3] There really isn't a difference between constant strings and string literals so just go ahead and try and modify it.
[4] "array[100]" is just SOP, don't bother counting actuals.
[5] You're a stinky-butt!     <-- That one was added my my 6 year old.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

retsameht

  • Mosquito
  • Posts: 15
Re: My Proposal For Optimizing LINQ
« Reply #10 on: February 22, 2024, 08:59:28 PM »
Hi John, and Thanks.

Perhaps we can have a heated discussion about why it's so hard to login here?  :knuppel2:

Chrome autofills the password and username fields for me, and as soon as I click the login button, the password field is cleared :tickedoff:. It took me about 10 tries to login just now.  :knuppel2:

Anyways....

For anyone interested, I'm picking a fight on GitHub over the List<T> class, and why it's wise to avoid its constructor (that takes an IEnumerable<T>), and AddRange() methods, and use Linq's ToList() instead, or at least, when initializing it with large collection.

The post is here

Code: [Select]
public static class TestListConstruction
{

   static IEnumerable<int> CreateInput(int start, int count, Func<int, int> func)
   {
      int end = start + count;
      for(int i = start; i < end; i++) yield return func(i);
   }

   static int count = 100000;

   public static void Run()
   {
      var seq = Enumerable.Range(0, count).Select(i => i / 2);
      var seq2 = CreateInput(0, count, i => i / 2);

      /// JIT code
      List<int> list = new List<int>();
      List<int> list2 = new List<int>();
      List<int> list3 = new List<int>();
      list.AddRange(seq);
      new List<int>(seq);
      seq.ToList();
      list = new List<int>();
      list2 = new List<int>();
      list2.AddRange(seq2);
      list3.AddRange2(seq);
      new List<int>(seq2);
      seq2.ToList();

      for(int i = 0; i < 4; i++)
      {
         list = new List<int>();
         list2 = new List<int>();
         list3 = new List<int>();
         Write("  list.AddRange(seq): ", () => list.AddRange(seq));
         Write("list2.AddRange(seq2): ", () => list2.AddRange(seq2));
         Write("list3.AddRange2(seq): ", () => list3.AddRange2(seq));
         Write("  new List<int>(seq): ", () => new List<int>(seq));
         Write(" new List<int>(seq2): ", () => new List<int>(seq2));
         Write("        seq.ToList(): ", () => seq.ToList());
         Write("       seq2.ToList(): ", () => seq2.ToList());
         Console.WriteLine("");
      }
   }

   public static void Write(string label, Action action)
   {
      long result = Time(action);
      Console.WriteLine("{0} {1,8}", label, result);
   }

   public static long Time(Action action)
   {
      GC.Collect();
      GC.WaitForFullGCComplete();
      Stopwatch stopwatch = Stopwatch.StartNew();
      action();
      stopwatch.Stop();
      return stopwatch.ElapsedTicks;
   }

}

public static class ListExtension
{
   /// <summary>
   /// Surrogate for List<T>.AddRange()
   ///
   /// Attempts to deduce the number of elements needed
   /// to hold the result, and if successful, increases
   /// the list's capacity to same.
   ///
   /// Unfortunately, this doesn't seem to gain much in
   /// contrast to the more extensive optimizations that
   /// Enumerable.ToList() has undergone.
   /// </summary>


   public static void AddRange2<T>(this List<T> list, IEnumerable<T> items)
   {
      if(items == null)
         throw new ArgumentNullException(nameof(items));
      if(list == null)
         throw new ArgumentNullException(nameof(list));
      int count = 0;
      if(items.TryGetNonEnumeratedCount(out count))
         list.EnsureCapacity(list.Count + count);
      list.AddRange(items);
   }
}


JohnK

  • Administrator
  • Seagull
  • Posts: 10627
Re: My Proposal For Optimizing LINQ
« Reply #11 on: February 23, 2024, 12:45:15 PM »
log in: I'll try to reproduce and dig in a bit but try the login boxes in the upper left corner instead of the other one.

Warning: POSIX C based information follows; grain of salt (I'm not good with C# so chances are these statements could be just gibberish)!

On time:
Typical `start clock`/`stop clock` time functions we tend to build measure actual clock-time (like a stopwatch). But multiple processes share the CPU so real-clock-time isn't an accurate measurement. In POSIX I have to create a virtual timer to find out how long a process spends in a running state to get an "accurate" time (and this is something I have yet to do myself so...).

Can you disable JIT to hopefully get "more optimized code"?

That `Fill()` reduction stephentoub posted is interesting. I would have thought it would have been more optimized than that. For example, I was playing around the other day--in C--with a theory and I pinned myself up against a std lib function. My approach was over-simplistic and doomed to fail (obviously) but the point of my testing was really about how much can be packed into just a line of code like: do { if (*p1++ != *p2++) vs a  for(unsigned i = 0...){ if *p1 != *p2... construct and to see if I could even come close.

But if I pull on that thread a bit to see if I can offer any sort of help: I was going up against the `memcmp()` with a simple FOR loop.

The reason the below code will ALWAYS win is because of the pointer array postfix operator which returns the value BEFORE the operation. So, the statement *p1++ != *p2++ is comparing the value THEN incrementing the array position, and that little optimization puts it one step ahead of my FOR(; ; p1++, p2++) loop.

Code - C++: [Select]
  1. int memcmp(const void *s1, const void *s2, size_t n)
  2. {
  3.         if (n != 0) {
  4.                 const unsigned char *p1 = s1, *p2 = s2;
  5.  
  6.                 do {
  7.                         if (*p1++ != *p2++)
  8.                                 return (*--p1 - *--p2);
  9.                 } while (--n != 0);
  10.         }
  11.         return (0);
  12. }

I'd like to read a bit more on arrays, loops and operators in C# but it might be a fun little distraction for myself trying to create a `Fill()` function.
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8693
  • AKA Daniel
Re: My Proposal For Optimizing LINQ
« Reply #12 on: February 23, 2024, 08:08:39 PM »

JohnK

  • Administrator
  • Seagull
  • Posts: 10627
Re: My Proposal For Optimizing LINQ
« Reply #13 on: February 23, 2024, 10:05:18 PM »
Warning:
how its done these days https://xoranth.net/memcmp-avx2/

stephentoub said the code reduced to Fill().

I supposed I should have framed my ramblings this way (but I was so rudely interrupted by actual work all day):

Questions about Fill():
  1. Why is there an iterator (i) when you already have the start?
  2. Why get the length every iteration?
  3. If you accepted a size_t you could have iterated backwards to zero and answered #1 and #2.
Code - C#: [Select]
  1. private static void Fill(Span<TResult> results, int start, Func<int, TResult> func) {
  2.   for (int i = 0; i < results.Length; i++, start++) {
  3.     results[i] = func(start);
  4.   }
  5. }

I would have expected something like (not sure how the compiler would react to the sequence for modification and access to that size var because I'm sure most compilers would toss a wobbly, but you get my concept and it could be moved down):
Code - C#: [Select]
  1. do {
  2.   results[size--] = func(size);
  3. } while (size > 0);

---
EDIT: checked theory.
All of these compile (shocked the first one did, to be honest), but they should be faster than the `fill()`'s for loop stephentoub provided.

Code - C++: [Select]
  1. // Compiles but tosses a warning.
  2. do {
  3.   results[size--] = func[size];                         // Here be dragons?
  4. } while (size > 0);
  5.  
  6. do {
  7.   results[size] = func[size];
  8.   size = size - 1;
  9. } while (size > 0;
  10.  
  11. for (; size > 0;) {
  12.   results[size] = func[size];
  13.   size = size - 1;
  14. }

« Last Edit: February 23, 2024, 11:00:58 PM by JohnK »
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

retsameht

  • Mosquito
  • Posts: 15
Re: My Proposal For Optimizing LINQ
« Reply #14 on: February 24, 2024, 07:30:59 AM »


Can you disable JIT to hopefully get "more optimized code"?

Now you can deploy a .NET app as a native APP without any JIT whatsoever. It's called
Native AOT

Quote

That `Fill()` reduction stephentoub posted is interesting. I would have thought it would have been more optimized than that.


The latest .NET has some nifty optimizations for ToArray() and ToList(). But they didn't propagate them to the List<T> constructor or AddRange().

Here's the same/similar optimization applied to the latter. The Span<T> class allows direct access to the list's internal storage, which is where the biggest improvement comes from:

Code: [Select]
public static void FastAddRange<T>(this List<T> list, IEnumerable<T> items)
{
   if(items == null)
      throw new ArgumentNullException(nameof(items));
   if(list == null)
      throw new ArgumentNullException(nameof(list));
   if(items.TryGetNonEnumeratedCount(out int count) && count > 0)
   {
      int current = list.Count;
      CollectionsMarshal.SetCount(list, current + count);
      Span<T> span = CollectionsMarshal.AsSpan(list);
      int i = current;
      int end = current + count;
      using(IEnumerator<T> enumerator = items.GetEnumerator())
      {
         while(enumerator.MoveNext())
         {
            Debug.Assert(i < end, "Count mismatch");
            span[i++] = enumerator.Current;
         }
         Debug.Assert(i == end, "Count mismatch");
      }
   }
   else
   {
      list.AddRange(items);
   }
}