0
  • I will use C# here as an example, but my question is about any language.
  • My question is from framework to compiler perspective (i.e the solution can be by implementing given idea inside compiler)

Consider such code:

if (sequence.Any()) ...

and let's say the sequence "holds" 1 million items. This condition will be executed pretty fast nevertheless (with single check -- either iterator moves or not). Now, slight change:

if (sequence.Count() > 1) ...

now the sequence will be iterated over 1 million items and after that the result will be "oh yes, we have at least 1 item".

Question: how it could be optimized in such way, that the excessive iterations will not be made. On the other hand I would like to avoid polluting framework with plethora of "optimized" methods -- CountAtMost, CountAtLeast -- and so on.

Of source Count is just example, another aggregation queries come to mind -- consider expression (wrong example I am keeping it for historical reasons) collection.Sum() > 1000.

I am not asking about C#-specific optimizations, the question is completely general -- iterable sequences are present in a lot of languages. Iterable sequences can come from generators as well, so the question is how to optimize aggregation query with external (comparing to query) arguments.

  • 2
    Just a note about your Sum() example: You can't really optimize this. You will always need to iterate over every item because your collection could contain negative numbers. For example, if you're testing collection.Sum() > 1000 and the values in collection are 2000, -3000, -1, -1 then quitting early after the first item is clearly a bad idea. – MetaFight Jan 21 '16 at 20:08
  • You might actually know beforehand that your collection contains no negative numbers. Say for instance people.Sum(p => p.NumberOfBoats);. – die maus Jan 21 '16 at 20:42
3

I think I found the solution -- the key is to follow deferred execution of sequences (iterables). Count should not return int type, but some Counted type which would keep reference to the sequence. With implicit conversion to int it would integrate smoothly, but having overloaded some operators it could process even infinite sequences.

  • Good idea. I'd like to see a collection framework that uses this. – Jules Jan 22 '16 at 9:39
1

Do you absolutely need these huge collections in your business layer?

Where do these huge collections come from? If for instance, they come from a database, then it might be a good idea to filter/count/sum the result on the database-side of things. This will save loads of processing-power and memory.

Is your program absolutely required to handle these enormous collections? If not, then try to optimize the sizes of your collections before they enter your business-layer.

Either way...


A somewhat C#-specific answer:

If performance is of enormous concern then you will have to implement some of these methods, if it's just a "one-time"-thing, just use foreach with a local count-variable. However; just calling .Count() on a large collection is not an enormously heavy operation in itself, as long as the enumeration of each item doesn't take enormous amount of processing-power/time, in which case, you should probably be careful of how many items you enumerate (i.e. use Take). So creating methods like these might in the end be considered micro-optimization, that is if the collection will always contain 1 million items or less.

Another way to tackle the problem is to enumerate the IEnumerable<T> to a collection of some sort – List<T>, for example.

This requires just one enumeration, which will yield you information about the collection, such as .Count and indexed access to items within it.

This of course depends on whether or not you are going to perform multiple operations on the collection, since it must be enumerated at least once.

Try to be pragmatic, ask yourself the simple questions. Will I need indexed access to the items? Do I need the count? Do I need to make sure there are at least fifteen items? Will i need to perform multiple enumerations of the collection? Will this collection be enormous? Then simply work from there, there is no magical correct way that always works, you absolutely must do trade-offs.

At one point in the code, it might be a good idea to iterate just 10 items, just to check if it contains 10 items or more, at another place; calling Count() might be a better idea.
At one point in the code, enumerating your collection to a List<T> might be a great idea, at other points – it might not.

Also, C# already has some great built in "i only want X"-items within Linq, for instance Take.

Code example:

if (hugeCollection.Take(4).Count() == 4)
{
    Foo();
}

This will not enumerate the entire collection, just the first 4 items, twice. Which for small collections might not be that great, but for larger collections, sure.


A C# tidbit:

Whether .Any() or .Count() is faster depends on whether the call is being made on an ICollection<T> or not. For ICollection<T>, Microsoft went ahead and optimized it, looking at the .Count-property; which is marginally faster than calling .Any(), regardless of the collections size – since the collection will never have to be enumerated.

  • I had to write the example in some language, I am not asking how to optimize C# code, iterable collections are present in C#, Scala, Swift, Haskell, you name it. So your example with Take works (thank you for that), but I am still looking for something general (without discussing if my iterable comes from database or not -- it is completely irrelevant here). – greenoldman Jan 21 '16 at 20:13
  • 2
    *However; just calling .Count() on a large collection is not an enormously heavy operation in itself. * We only know that this is an IEnumerable - he hasn't said it's, for instance, a List. Certain collection types, like a LINQ result, could take a very long time. The Count property on certain collection types is different, and of course should be used if it's readily available. – Katana314 Jan 21 '16 at 20:16
  • I thought it was worth at least mentioning that keeping huge collections out of the business-layer, generally is a good idea. Regardless, the answer is "Somewhat C#-specific", not entirely C#-specfic. I'm sure that most of the thinking-process can be applied to any language that carries some similarities to C# (and probably many that don't)... – die maus Jan 21 '16 at 20:17
  • @Katana314 all Count() does is iterate over the collection and count up a value, it's not an extremely heavy operation, regardless if it's a ICollection or just an IEnumerable. In most scenarios enumerating an item doesn't take an enormous amout of processing power. But i will edit my answer accordingly. – die maus Jan 21 '16 at 20:20
  • 3
    @diemaus This is perhaps an eye-rolling example, but if your IEnumerable is a LINQ "SelectMany()" that returns the name of an element, plus the entire works of Shakespeare, that yields individual spoken lines, then yeah, it could take quite a while. IEnumerable is an interface, not a specific implementation, and there is no absolute guarantee that that implementation has its own "length" variable or that iterating through all of them is fast. – Katana314 Jan 21 '16 at 20:24
0

Ok so the code for Count() in C# would be:

public static int Count<T>(this IEnumerable<T> enumerable)
{
    var count = 0;

    using (var enumerator = enumerable.GetEnumerator())
    {
        while (enumerator.MoveNext())
            count += 1;
    }
}

It's pretty easy to imagine that if this gets inlined, the predicate is pushed into the while condition:

var result = false;
{
    var count = 0;

    using (var enumerator = enumerable.GetEnumerator())
    {
        while (!result && enumerator.MoveNext())
        {
            count += 1;
            result = count > x;
        }
    }
}

if (result) // the original condition featuring Count() > x

EDIT: This is not possible though unless the compiler/optimizer can devirtualize the IEnumerator<T> as it can have side effects and the loop cannot be cut short unless the compiler can be sure that nothing changes by that.</edit>

Besides, I'm afraid the optimization options are limited to the given language runtime - JITed can hope for the inline, compiled can get this optimization through whole-program analysis after linkage and functional - no idea there...

But I'm afraid that the compiler won't be able to do much since this will usually be used from external binaries. And those see the implementation only in link-time.

If you're doing a framework and want this, these are some ideas:

  • Put as much compiler-inline-this-please attributes as you can
  • Create two versions: Count() and CountUntil(Predicate<int>)
  • Have higher hopes about your users :)

Or possibly

  • Don't implement the Count() at all - make the users explicitly create a collection and .Count it or use foreach. Not very friendly though...
  • Thank you, but I doubt inlining work this way -- condition > is external for count, so why would compiler decide to change the inlined body of a Count and merge it? – greenoldman Jan 22 '16 at 6:40
  • @greenoldman I have realized that the inlining is impossible anyway due to the virtual dispatch on the IEnumerator. Besides, the compiler will not generate this code, this is just how it would look if you decompiled it back from assembly. C++ compiler does things like this often - even removing whole functions and modifying their bodies at the points of usage. – Zdeněk Jelínek Jan 22 '16 at 9:22
  • The optimization of terminating the loop early is, unfortunately, only available to the compiler if it is able to guarantee that the call to MoveNext is free from side effects, which is unlikely to be achievable in most languages other than pure functional ones. – Jules Jan 22 '16 at 9:31
  • Virtual dispatch may not be necessary, however, if the call to GetEnumerator is also inlined, which would allow the compiler to know the exact type of the enumerator. – Jules Jan 22 '16 at 9:33
  • @Jules But the GetEnumerator cannot be inlined because it is again virtual. You'd need to devirtualize the IEnumerable in the first place. And then you'd need to make sure the MoveNext is pure, as you said, which could work for collections, but since we're concerned mostly with other sources of data here, it seems that this is no way to go except for functional languages, like you've said. – Zdeněk Jelínek Jan 22 '16 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.