Question Needing actual syntactic sugar to perform iterations over arrays and lists

Hello,

I use several custom IEnumerable methods over large ILists. These are intended to simply shorten code and to do nothing better or worse than replacing them with a number of foreach or for loops. They aren't actual syntactic sugar and there is a significant performance loss though (from recent tests, close to twenty times slower).

Code (CSharp):

1. public static IEnumerable<T> AndIn<T>(this IList<T> thisIList, params IList<T>[] otherILists)
2.         {
3.             foreach (T thing in thisIList)
4.                 yield return thing;
5.  
6.             foreach (IList<T> other in otherILists)
7.                 foreach (T thing in other)
8.                     yield return thing;
9.         }

Code (CSharp):

1. public static IEnumerable<(T current, T previous)> ModuloPairs<T>(this IList<T> thisIList)
2.         {
3.             for (int i = 0, j = thisIList.Count - 1; i < thisIList.Count; i++, j = i - 1)
4.             {
5.                 yield return (thisIList[I], thisIList[j]);
6.             }      
7.         }

How to make it actual syntactic sugar (the equivalent of writing my own custom instructions)?[/I]

 

I don't think you understand what syntactic sugar is. It's just a particular bit of code that the compiler understands and can use to condense what would be a lot of code into usually a lot less.

yield return

is 100% syntax sugar as the compiler generates a whole state machine under the hood for the purpose of iterating collections.

So when you ask "how to make it actual syntactic sugar", the answer to that question is your first method is the syntax sugar method, or at least the one with the most sugar going on. Just that in a lot of cases, syntax sugar trades performance for convenience.

I feel like you want shorter code for the sake of shorter code. Sometimes less is more, and more is less. Often times performant code means you gotta write it the longhand way.

 

Are you sure about this?

Code (csharp):

1.  
2. for (int i = 0, j = thisIList.Count - 1; i < thisIList.Count; i++, j = i - 1)
3.  

It should be j-- (or j=j-1), right?

 

Well I have a few point here. First of all what we call "syntactic sugar" is part of the syntax of a language. You can not change or add anything to a language that isn't already there. "Syntactic sugar" is called a certain syntax that essentially is just translated by the compiler into more complex code that could be achieved by other language features. So you can not add or change the syntax rules of a language unless you create your own language with it's own compiler.

Your "AddIn" extension method seems to be very specific as it only works on ILists. Other than that it would be almost the same as the "Concat" Linq extension, though it allows multiple lists at once. Though the params array of course has additional overhead as it always creates an array when you use this method. That's why many extension methods actually have some overloads with one, two, maybe three explicit arguments and another one with a params array to cover the rare cases.

When you "optimise" things there are always different goals you may have in mind. One of the main points of enumerables is that they can wrap one or multiple source colliections of some sort and iterate through them "on the fly". When you're dealing with large collections, this avoids duplication of those collections. Though this is often at the expense of speed. Other solutions would just create a new collection. This may be faster but requires more memory. For example your "AddIn" extension could be written as:

Code (CSharp):

1.  
2.     public static List<T> AndIn<T>(this IList<T> thisIList, params IList<T>[] otherILists)
3.     {
4.         int count = thisIList.Count;
5.         for (int i = 0; i < otherILists.Length; i++)
6.            count += otherILists[i].Count;
7.         List<T> result = new List<T>(count);
8.         result.AddRange(thisIList);
9.         for (int i = 0; i < otherILists.Length; i++)
10.             result.AddRange(otherILists[i]);
11.         return result;
12.     }
13.  

The first part makes sure the result list is large enough to hold all elements so the result list does not need to be resized.

Such statements are kinda useless. 20 times slower compared to what? What's the reference code that does the same thing? For example over here I had my original implementation and an optimised version that was 8 times faster (at least inside the editor under debug mode). Though things can vastly differ when you actualy test it in release mode in a build. I got my speed increase from two things: inlining all those method calls in the tight loop and due to the inlining the code could be simplified and redundant parts could be removed. That means the code is actually a bit longer but much more performant.

Finally "ModuloPairs" seems to be a strange name. After actually reading the code I now understand the idea behind the name. Though I don't think that a user would understand what this does from just the name. It's hard to find proper names for methods, especially when they have a very specific usecase. This concept of creating pairs of "consecutive elements" also has many different potential implementations. For example your first element is already the "wrapped" pair which is often the last one. Also your pairs are always connecting "backwards" and don't hand out pairs as they appear in the array. It may fit your usecase and in other cases it might not matter. Though it's hard to reason about code if the exact behaviour is not clear.

 

No, I think he actually wanted to create chain-pairs of consecutive elements but have it "wrap around" at the end. That's why he called it "Modulo". Though he does the "wrapping" essentially with the first element which wraps to the last in the first step. From that point on he always wraps "i" and "i-1" into a pair. As I explained in my answer, not an intuitive method for sure

 

I think "syntactic sugar" implies, per definition, that is it compiled as the longer version of the code, and that there is no performance gain or loss compared to said longer version of the code. And especially not that is it orders of magnitude slower.

This might not be intuitive, but it is orders of magnitude faster than than the naive :

Code (CSharp):

1.             int count = thisIList.Count;
2.  
3.             for (int i = 0; i < thisIList.Count; i++)
4.             {
5.                 yield return (thisIList[i], thisIList[(i - 1) % count]);
6.             }

(Which if my memory's correct doesn't even work because of the %'s limitation in negatives.)

 

Well you're probably alone in that thought. Syntax Sugar just makes things shorter. It makes no promises about performance.

There's lots of situations in C# where syntax sugar can create additional overhead.

 

You might have a point with overloads, but writing each overload separately would result in several hundreds of extension methods. If there is no other way around it to preserve performance though ... Ideally it's not even methods that I need, but rather generic "compiler instructions". "Such code should be compiled as such other code."

This is performance suicide. The problem that some of you don't understand is that, if you spend twice the time doing an iteration with a IEnumerable method that it takes by doing a long sequence of loops or a thrice-nested loop, although it might not seem like a big deal, the fact is it chained with plenty of other such losses of performance, makes it exponentially low-performance. For instance, you might have to retrieve an array of 10 millions Vector2 in a single frame, then perform a bunch of mudulo operations, then project it to polar coordinates, then to world coordinates, etc. You cannot afford exponential loss of performance in these cases.

The code example you provided in the other thread, that iterates over a Color32[] is absolute performance suicide as well. Color32 is an extremely inefficient struct, and no collection operations should be directly performed on them. You better treat each Color32 as an int32 and convert them back with bit shifting after performing the wanted operations.

 

I can't possibly be the only one to not have misconceptions about it.

Code (CSharp):

1. var annoyingOne = new List<List<Dictionary<short, (Vector3, Vector3)>>>();

That is syntactic sugar. Is it compiled exactly the same as the longer definition.

Although I admit a shorter code piece compiled differently can be syntactic sugar through abuse of language if the performance impact is negligible.

Anyway, I think I might have found the beginning of a solution in the use of :

Code (CSharp):

1. [MethodImpl(MethodImplOptions.AggressiveInlining)]

Although this might not work for methods that have a params parameter. I don't know.

 

Syntatic sugar are normally said to be a feature of a programming language, so you can't create a function as an syntatic sugar. (It's just a handy function)
However the definition of syntatic sugar is not so important here. The reason why your code slow down is that you are using the "yield" syntax, which will create extra objects, and do extra things.
How about something like this?

Code (CSharp):

1.  
2.     public static void DoSomthingTo<T>(this Action<T> process, params IList<T>[] otherILists)
3.     {
4.         var outerCount = otherILists.Length;
5.         for (var i = 0; i < outerCount; i++) {
6.             var list = otherILists[i];
7.             var innerCount = list.Count;
8.             for (var j = 0; j < innerCount; j++) {
9.                 process(list[j]);
10.             }
11.         }
12.     }
13.  

you can compare the equivalent compile result of the original yield code and the above for code, apparently the later one do less things, hence would be faster.
(Be ware of Inlining, in some situation it would make the code become slower; let the compi)

 

Your fixation on "syntactic sugar" is inhibiting you from understanding the basics of why we write software.

I quote from Mike Action:

"The purpose of all programs, and all parts of those programs, is to transform data from one form to another."

That's it. There is NO OTHER PURPOSE.

At the end of the day, EVERY computer language (including assembly language!) is simply "syntactic sugar" for the ultimate 1s and 0s that constitute the underlying executable code. That's why we use computer languages: we don't think in 1s and 0s so we need the help.

Take a moment to understand your actual data rather than your theoretical "For instance, you might have" data and how you need to transform it, and the select and engineer an appropriate solution.

After all, O(n^3) is absolutely fine when n == 3 (like tic-tac-toe), but probably not so much when n == 3000000

 

If you need to generate a ton of similar code, it's time to wield some SourceGenerators. Pro: as performant as the underlying method, you can generate hundreds of "overload" methods, con: separate class library project.

 

Syntactic Sugar & Performance
As spiney199 and tsukimi have mentioned, syntactic sugar does not guarantee equivalent performance to other syntax. In fact, it can often be quite the opposite. I agree that you are surely not the only one to have a similar misconception, but hopefully that is what we are doing here in the forums, disabusing one another of misconceptions and helping each other grow day by day.

Iterator Methods
As you can see from tsukimi's links and this link, https://learn.microsoft.com/en-us/a...ustom-iterators-with-yield#how-iterators-work, the syntactic sugar of writing a simple iterator method that returns an IEnumerable and contains yield return statements is compiled into a hidden class that implements the IEnumerable<T>, IEnumerable, IEnumerator<T>, IEnumerator, and IDisposable interfaces. When the method is called, it returns a new instance of that class. Creating new instances of a class will add some overhead, not to mention the pressure added to the garbage collector to clean up that discarded instance later. When you use that new IEnumerable in a foreach loop, IEnumerable.GetEnumerator() will be called, which is the main method of the IEnumerable interface. Depending on some conditions there concerning state and threading it may return itself as the IEnumerator to be used in the foreach loop, or it may return another new instance of that class. (It's difficult to read these automatically compiled, hidden classes because their member names are not human readable.) The class contains members that reference all of the IList arguments that were passed into the iterator method. As the foreach loop iterates the IEnumerator it calls IEnumerator.Current to get the current element which the hidden class is keeping track of, and IEnumerator.MoveNext() to perform the logic of determining what the next Current element is. This is how it is able to iterate through multiple, separate collections without allocating new memory or copying the contents of those collections. It uses an instance of a hidden, automatically compiled class to hold references to all of the separate objects and state variables, and automatically generated logic for how to to iterate through them one by one, inferred by the compiler based on how you wrote the iterator method. If you called the iterator method with a particular set of lists, I imagine you could even cache and re-use the returned IEnumerable, or perhaps the IEnumerator by manually calling IEnumerator.Reset(), to iterate over those same lists in the future. However, I wouldn't recommend that as it seems unnecessarily advanced to me. I just wanted to point out the way these iterator methods work, and that one of the benefits is that they avoid allocating a new collection or copying the contents, but you mustn't forget that they still cause allocation of a new IEnumerator object instance each time the method is called. You also take on all of the performance overhead of the nested instances of this pattern. The compiler generated IEnumerator contains other nested IEnumerators. Furthermore, we can see that there are a lot of interfaces being used here. So, we are taking on the inherent performance overhead of calling virtual methods via interfaces. I am not opposed to using interfaces, but as you yourself pointed out, doing something even fractionally less performant in a large loop can add up. So, iterator methods are obviously not going to automatically deliver equivalent performance as the compiler generates completely different code.

Why IList?
You are iterating over implementations of the IList interface, and I must ask, why? There is an inherent performance cost with using interfaces and with iterating via foreach, as opposed to using a for loop. (Arrays are the exception here. Iterating an array with a foreach loop is the fastest way to iterate. However, I suspect that is a compiler optimization only afforded to actual arrays, not any other type like custom IEnumerator objects. Outside of iterating an array, a for loop becomes more performant than a foreach.) Perhaps you have a legitimate reason for using the IList type. I'm not trying to imply that you don't, but if so, what is the reason? If it is so that you can iterate both lists and arrays, I would just write out separate methods for each. Then you can code each type directly and iterate in the most performant way. It will result in more code, but that code should be hidden away in the methods that we will ultimately call anyway. So, once it's written, the boilerplate is taken care of, has ideal performance, and is hidden away from needing to know anything about it or see it ever again.

AggressiveInlining
This will almost certainly not provide the silver bullet solution you're looking for. This is merely a hint to the compiler. At best, you're begging the compiler to consider inlining the contents of a method, which the compiler is already trying to do to the best of its ability in a release build. There are more sure fire ways to attempt to guarantee that the compiler can inline a method, but they don't involve just slapping an attribute on the method and calling it a day. They are more related to not throwing exceptions directly from the method, the size of the method, and other things that are over my head. I leave those kinds of optimizations to the compiler wizards. If something can be inlined, the compiler is probably already doing its best to ensure that happens. The other major issue here is that, as we have seen, the iterator method is not really a method! It's a class definition. You can't throw that attribute on an entire class and all of its methods, which are called repeatedly in a loop, and expect it to be able to inline everything (moreso than it already was), and unroll the entire loop, etc.

My Suggestion
As tsukimi suggested, I would define methods that accept the collections you want to iterate, as well as a delegate that defines what you want to do during iteration. As Bunny83 pointed out, using a params array means new arrays will be allocated, so I would avoid those as well. If defining a preset number of overloads to accept multiple collections is not enough, then I would imagine you ought to be able to have all of the separate collections in some other collection, iterate them one at a time and call the appropriate method on each one. If that collection of collections is sufficiently abstract you can also write more methods to encapsulate that functionality as well.

Code (CSharp):

1. using System;
2. using System.Collections.Generic;
3. using System.Text;
4. using Switchboard;
5. using UnityEngine;
6. using ILogger = Switchboard.ILogger;
7.  
8. public static class CollectionUtility
9. {
10.     // ForEach is an established naming pattern in .NET, as in List<T>.ForEach(Action<T>), so we align somewhat with that pre-existing naming pattern.
11.  
12.     public static void ForEachPair<T>(this T[] collection, Action<T, T> action)
13.     {
14.         // Note that I would handle each null check separately, this is just to be concise.
15.         if(collection == null || action == null)
16.         {
17.             // Throw ArgumentNullException? This is what .NET System classes would do here, but it will prevent this method from being inlined.
18.             // .NET often uses an exception helper to throw exceptions from another method so that the rest of this method can still inline.
19.             // I did that for a long time, but then when I finished my public facing class library, every single .dll required the exception helper, so I stopped. :/
20.         }
21.  
22.         int last = collection.Length - 1;
23.         if(last > 0)
24.         {
25.             for(int i = 0, j = 1; i < last; i++, j++)
26.             {
27.                 action(collection[i], collection[j]);
28.             }
29.             action(collection[last], collection[0]);
30.         }
31.         else
32.         {
33.             // Handle invalid operation.
34.         }
35.     }
36.  
37.     // Overloads that explicitly handle more parameters. .NET does this all the time.
38.     public static void ForEachPair<T>(T[] collection1, T[] collection2, Action<T, T> action)
39.     {
40.         ForEachPair(collection1, action);
41.         ForEachPair(collection2, action);
42.     }
43.  
44.     public static void ForEachPair<T>(T[] collection1, T[] collection2, T[] collection3, Action<T, T> action)
45.     {
46.         ForEachPair(collection1, action);
47.         ForEachPair(collection2, action);
48.         ForEachPair(collection3, action);
49.         // etc.
50.     }
51.  
52.  
53.     public static void ForEachPair<T>(this List<T> collection, Action<T, T> action)
54.     {
55.         if(collection == null || action == null)
56.         {
57.             // Exception handling
58.         }
59.  
60.         int last = collection.Count - 1;
61.         if(last > 0)
62.         {
63.             for(int i = 0, j = 1; i < last; i++, j++)
64.             {
65.                 action(collection[i], collection[j]);
66.             }
67.             action(collection[last], collection[0]);
68.         }
69.         else
70.         {
71.             // Handle invalid operation.
72.         }
73.     }
74.  
75.     public static void ForEachPair<T>(List<T> collection1, List<T> collection2, Action<T, T> action)
76.     {
77.         ForEachPair(collection1, action);
78.         ForEachPair(collection2, action);
79.         // etc.
80.     }
81.  
82.  
83.     // If you need some additional state object passed in to perform the operation, you can do that like this:
84.  
85.     public static void ForEachPair<T, TArg>(this T[] collection, Action<T, T, TArg> action, TArg state)
86.     {
87.         if(collection == null || action == null)
88.         {
89.             // Exception handling
90.         }
91.  
92.         // You can perform null checks on state as well, but you need to apply a generic type constraint, like class, to the method for TArg state.
93.  
94.         int last = collection.Length - 1;
95.         if(last > 0)
96.         {
97.             for(int i = 0, j = 1; i < last; i++, j++)
98.             {
99.                 action(collection[i], collection[j], state);
100.             }
101.             action(collection[last], collection[0], state);
102.         }
103.         else
104.         {
105.             // Handle invalid operation.
106.         }
107.     }
108.  
109.     public static void ForEachPair<T, TArg>(T[] collection1, T[] collection2, Action<T, T, TArg> action, TArg state)
110.     {
111.         ForEachPair(collection1, action, state);
112.         ForEachPair(collection2, action, state);
113.         // etc.
114.     }
115.  
116.  
117.     public static void ForEachPair<T, TArg>(this List<T> collection, Action<T, T, TArg> action, TArg state)
118.     {
119.         if(collection == null || action == null)
120.         {
121.             // Exception handling
122.         }
123.  
124.         // You can perform null checks on state as well, but you need to apply a generic type constraint, like class, to the method for TArg state.
125.  
126.         int last = collection.Count - 1;
127.         if(last > 0)
128.         {
129.             for(int i = 0, j = 1; i < last; i++, j++)
130.             {
131.                 action(collection[i], collection[j], state);
132.             }
133.             action(collection[last], collection[0], state);
134.         }
135.         else
136.         {
137.             // Handle invalid operation.
138.         }
139.     }
140.  
141.     public static void ForEachPair<T, TArg>(List<T> collection1, List<T> collection2, Action<T, T, TArg> action, TArg state)
142.     {
143.         ForEachPair(collection1, action, state);
144.         ForEachPair(collection2, action, state);
145.         // etc.
146.     }
147.  
148.  
149.     public static void ForEach<T>(this T[] collection, Action<T> action)
150.     {
151.         Array.ForEach(collection, action);
152.     }
153.  
154.     public static void ForEach<T>(T[] collection1, T[] collection2, Action<T> action)
155.     {
156.         Array.ForEach(collection1, action);
157.         Array.ForEach(collection2, action);
158.         // etc.
159.     }
160.  
161.     public static void ForEach<T, TArg>(this T[] collection, Action<T, TArg> action, TArg state)
162.     {
163.         if(collection == null || action == null) // state == null
164.         {
165.             // Exception handling
166.         }
167.  
168.         // Arrays iterate the fastest with a foreach loop.
169.         foreach(T item in collection)
170.         {
171.             action(item, state);
172.         }
173.     }
174.  
175.     public static void ForEach<T, TArg>(T[] collection1, T[] collection2, Action<T, TArg> action, TArg state)
176.     {
177.         if(collection1 == null || collection2 == null || action == null) // state == null
178.         {
179.             // Exception handling
180.         }
181.  
182.         foreach(T item in collection1)
183.         {
184.             action(item, state);
185.         }
186.  
187.         foreach(T item in collection2)
188.         {
189.             action(item, state);
190.         }
191.  
192.         // etc.
193.     }
194.  
195.  
196.     // List<T>.ForEach(Action<T> action) already exists.
197.  
198.     public static void ForEach<T>(List<T> collection1, List<T> collection2, Action<T> action)
199.     {
200.         collection1.ForEach(action);
201.         collection2.ForEach(action);
202.         // etc.
203.     }
204.  
205.     public static void ForEach<T, TArg>(this List<T> collection, Action<T, TArg> action, TArg state)
206.     {
207.         if(collection == null || action == null) // state == null
208.         {
209.             // Exception handling.
210.         }
211.  
212.         // Lists iterate the fastest with a for loop.
213.         for(int i = 0, count = collection.Count; i < count; i++)
214.         {
215.             action(collection[i], state);
216.         }
217.     }
218.  
219.     public static void ForEach<T, TArg>(List<T> collection1, List<T> collection2, Action<T, TArg> action, TArg state)
220.     {
221.         if(collection1 == null || collection2 == null || action == null) // state == null
222.         {
223.             // Exception handling.
224.         }
225.  
226.         for(int i = 0, count = collection1.Count; i < count; i++)
227.         {
228.             action(collection1[i], state);
229.         }
230.  
231.         for(int i = 0, count = collection2.Count; i < count; i++)
232.         {
233.             action(collection2[i], state);
234.         }
235.  
236.         // etc.
237.     }
238.  
239.     // Now, you could also add methods to handle List<List<T>>, List<T[]>, T[][], and List<T>[],
240.     // for the times when explicitly overloading the number of collections is not enough.
241.     // However, I hope you get the point because that's a lot more example code for me to write,
242.     // but I'll write one as an example.
243.  
244.     public static void ForEach<T, TArg>(this List<List<T>> collection, Action<T, TArg> action, TArg state)
245.     {
246.         if(collection == null || action == null) // state == null
247.         {
248.             // Exception handling.
249.         }
250.  
251.         // Lists iterate the fastest with a for loop.
252.         for(int i = 0, count = collection.Count; i < count; i++)
253.         {
254.             List<T> innerCollection = collection[i];
255.             if(innerCollection == null)
256.             {
257.                 // How do you want to handle it? Would you rather null check all of the inner collections at the start of the method?
258.             }
259.             // Do you want to just let this inner method handle the null checks?
260.             innerCollection.ForEach(action, state);
261.         }
262.     }
263.  
264.  
265.     // Now, for an example of using all of this to do something specific, but also saving that specific functionality in a utility class.
266.     // I would probably move these type of methods to another file, as everything above is UnityEngine agnostic.
267.  
268.     private static StringBuilder StringBuilder => _stringBuilder ?? new StringBuilder();
269.     [ThreadStatic] private static StringBuilder _stringBuilder;
270.  
271.     public static void LogEach(this List<List<MonoBehaviour>> collection, ILogger logger)
272.     {
273.         if(collection == null)
274.             throw new ArgumentNullException(nameof(collection));
275.  
276.         if(logger == null)
277.             throw new ArgumentNullException(nameof(logger));
278.  
279.         StringBuilder stringBuilder = StringBuilder;
280.         stringBuilder.Length = 0;
281.  
282.         collection.ForEach((MonoBehaviour monoBehaviour, StringBuilder sb) =>
283.         {
284.             // Be careful with lambdas. This could accidentally become a closure if we referenced stringBuilder instead of sb, for example.
285.             if(monoBehaviour == null)
286.                 sb.AppendLine("Null reference!");
287.             else
288.                 sb.Append("GameObject: ").Append(monoBehaviour.gameObject.name)
289.                     .Append("Type: ").Append(monoBehaviour.GetType().Name)
290.                     .Append("Enabled: ").Append(monoBehaviour.enabled)
291.                     .Append('\n');
292.         }, stringBuilder);
293.  
294.         string message = stringBuilder.ToString();
295.         stringBuilder.Length = 0;
296.         logger.LogInformation(message);
297.     }
298. }

And then you can operate on every item in multiple collections as easy as this:

Code (CSharp):

1. List<List<MonoBehaviour>> myList = new List<List<MonoBehaviour>>();
2. // Fill the collection somehow.
3. myList.LogEach(Logger);

Voila! Custom syntactic sugar with minimal performance impact!

 

Its best apparently isn't anything to get very excited about though

From Unity Manual's section Understanding optimization in Unity.

I don't know if MethodImplOptions.AggressiveInlining helps avoid this situation or not. I've been using it every now and then just in case it does happen to help.

 

That's very interesting to know. Thank you! I admit that I do not consider myself an expert on inlining or what happens at the compiler level, but every time I have looked into the matter and that attribute on Stack Overflow or elsewhere I seem to remember the answer being along the lines of what I said about the attribute being more of a compiler hint or request. Now, I have seen the attribute applied when reading through some .NET source code, but I've always felt like I personally wouldn't know when to appropriately apply that attribute and what conditions would make it have a different outcome over the default behavior. In any case I feel relatively confident that attempting to inline an iterator method, which is really hiding an entire class, would likely have no result here. I wouldn't criticize anyone for using the attribute if they have a reason to believe it could have an impact, but I would caution people just coming across the attribute to not think of it as something you should now be putting on every method in your code base.

 

Man, that is so interesting to know about the total lack of inlining, particularly as it relates to using property getters vs local variables. It certainly makes me second guess some of the assumptions I've taken from micro-optimization benchmarks I've run outside of Unity in BenchmarkDotNet. I hope that is fixed by them moving to CoreCLR.

 

Thank to you both for these quality answers.