Sign in to follow this  

[C#] Indexing IEnumerable effeciently without allocation

This topic is 2628 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been using IEnumerable to generate collections from some data but the problem is I can't get the index of any of that data.

I've tried using IEnumerable<T>.ElementAt but that works amazingly slow unless you're using the list directly as the enumerable. As far as I can tell, that isn't possible using custom iterators.

The only method around this that I can think of, is to convert the IEnumerable to a list and work from there but I'm trying my best not to allocate memory, especially for something I'm using often.





Share this post


Link to post
Share on other sites
Just use the enumerator outside of the foreach construct. Iterate through it manually, and you get indexing.
IEnumerable<T> ev = f(...);
int index = 0;
var enumerator = ev.GetEnumerator();
while(enumerator.MoveNext())
{
doSomething(enumerator.Current,index);
index++;
}

Share this post


Link to post
Share on other sites
If you need to index something, don't pass it as IEnumerable<>. As far as I know, you can't do it efficiently with an IEnumerable and ElementAt is just iterating until a coutner reaches the index parameter.

Share this post


Link to post
Share on other sites
If you need random access to the container, IEnumerable isn't the right interface for you. IEnumerable is too generic; it represents any enumerable sequence, some of which might not even be in any given order. Try using IList<T> instead; it supports random access and better fits what you're trying to do.

Share this post


Link to post
Share on other sites
Quote:
Just use the enumerator outside of the foreach construct. Iterate through it manually, and you get indexing.


That was an idea but there are cases where I use the index directly. I could probably tweak the code but I think that would get really messy.

Quote:
As far as I know, you can't do it efficiently with an IEnumerable and ElementAt is just iterating until a coutner reaches the index parameter.


I did a a test using IEnumerable. When I generated an I enumerable and looped 1 million times using ElementAt, the program took so long I didnt' even finish but when I set the list directly as an IEnumerable it took a fraction of a second. It seems to me that collections have the ability to someway modify it that I dont' understand.

Quote:
IEnumerable is too generic; it represents any enumerable sequence, some of which might not even be in any given order. Try using IList<T> instead; it supports random access and better fits what you're trying to do.


I'd love to use IList but unfortunately I'd have to build specific lists in order to use it. Too bad there isn't some time of iterator that outputs lists

I think creating my own Enumerator that takes an IList would work but first I have to find out if structures holding classes allocate data when using the new keyword.

Share this post


Link to post
Share on other sites
Quote:

I did a a test using IEnumerable. When I generated an I enumerable and looped 1 million times using ElementAt, the program took so long I didnt' even finish but when I set the list directly as an IEnumerable it took a fraction of a second. It seems to me that collections have the ability to someway modify it that I dont' understand.

Different collections can implement the functionality of a given interface differently, some more efficiently than others. Indexing a linked list would always be slower than indexing an array, even if both types implemented an interface with GetMeElementAtIndex() or similar.

Quote:

I'd love to use IList but unfortunately I'd have to build specific lists in order to use it. Too bad there isn't some time of iterator that outputs lists

That wouldn't be an iterator. It would be a thing that returns lists. If a thing isn't already a list, something is going to need to turn it into a list. That will allocate.

Quote:

I think creating my own Enumerator that takes an IList would work but first I have to find out if structures holding classes allocate data when using the new keyword.

Using new causes allocation. Why exactly are trying to avoid allocation? You should provide a higher-level description of the problem you are trying to solve in order to get better solutions.

Share this post


Link to post
Share on other sites

Quote:

Using new causes allocation. Why exactly are trying to avoid allocation? You should provide a higher-level description of the problem you are trying to solve in order to get better solutions.


On the contrary it seems using new with structs that hold classes don't allocate data (unless of course you initialize the class data). For some odd reason I thought anything that involved classes would allocate not realizing that classes themselves are nothing more than references to actual data. Unfortunately this didn't help my little problem.

I think I'm going to go with Drigovas's idea and just try go over it manually. I can probably figure out something that'll will run smoothly without indexes.

My general problem was I was trying to find a way to take an T[] and a List<> of classes with an embedded T inside it to work within the same method.

I'm very very cautious about allocating memory because I've had some experiences where garbage collection shattered my game performance.

But anyway thanks for the speedy solutions!

Share this post


Link to post
Share on other sites
Quote:

On the contrary it seems using new with structs that hold classes don't allocate data (unless of course you initialize the class data). For some odd reason I thought anything that involved classes would allocate not realizing that classes themselves are nothing more than references to actual data. Unfortunately this didn't help my little problem.

That's incorrect. new causes allocation of memory somewhere, period, end of story. If it doesn't cause allocation it is impossible to access/use the resulting object -- even were there to be some mechanism for "delayed allocation" of the interface on first use, bookkeeping metadata would need to be allocated internally by the CLR to track this. However this is a nonissue, because that's not what happens. If you invoke 'new,' you get an allocation.

"Using new with structs" allocates the class on the stack, possibly in the locals section (which is zero-initialized when the method context is pushed to the execution stack). It does consume memory -- whether or not that is germane to your concerns about allocating memory depends on why you care about allocating memory.

On a related note, whether or not structs contain reference types is irrelevant -- structs are value types and are always zero-initialized when allocated. The references contained in those structs are thus null. What you're likely seeing there is that your "initializing of the class data" contained in those structures is allocating instances of the appropriate classes, which are reference types and thus allocated on the managed heap.

Quote:

T[] and a List<>

Indeed, unfortunately, T[] and List<T> don't share a common "indexable" interface. It's possible you could build your own wrapper type for T[] that implemented IList<T> for that array, however. That could be done with very little, to zero, new allocations beyond allocation of the wrapper instance itself (which you could reuse if you really wanted to be picky).

Mike P reminds me that System.Array does in fact implement IList.

Quote:

I'm very very cautious about allocating memory because I've had some experiences where garbage collection shattered my game performance.

You're almost certainly tuning this in the wrong fashion then. Depending on the flavor of GC you're using (in particular if you're using the XNA GC), avoiding allocations can be beneficial, but it's almost impossible to actually avoid them -- rather, you want to control them so you know exactly when they happen and why. Furthermore, allocations are not always the thing that triggers a GC.

Can you reproduce the scenario?

[Edited by - jpetrie on October 1, 2010 4:01:23 PM]

Share this post


Link to post
Share on other sites
Quote:
That's incorrect. new causes allocation of memory somewhere, period, end of story.


Perhaps I'm using the term allocation wrong. What I mean is garbage isn't created. I personally checked this by making a class and a struct and then adding a new items to a list created with a set capacity then writing GC.GetTotalMemory(true) to the console after each one was added.

Quote:
Mike P reminds me that System.Array does in fact implement IList.

True but the type I'm using is a Microsoft.XNA.Framework.Vector3, and I have no control over what interface that uses. Sorry, I seem to have a tendency to leave out details. : )

Quote:
You're almost certainly tuning this in the wrong fashion then. Depending on the flavor of GC you're using (in particular if you're using the XNA GC), avoiding allocations can be beneficial, but it's almost impossible to actually avoid them -- rather, you want to control them so you know exactly when they happen and why. Furthermore, allocations are not always the thing that triggers a GC.



I'm aware of this, but I never want to generate each frame of the garbage main loop. I read up the GC on Shawn Hargreaves blog and it a painted a pretty nasty picture of where things can go wrong. I honestly made too many mistakes to count.

Quote:
Can you reproduce the scenario?


Eh? Which scenerio?

Share this post


Link to post
Share on other sites
Quote:
Original post by AntiGuy
I've been using IEnumerable to generate collections from some data but the problem is I can't get the index of any of that data.


What exactly do you need the indices for?

Share this post


Link to post
Share on other sites
My method(s) were retrieving some data beforehand before continuing. There were also cases where I'd skip ahead one step. They're reall small problems actually, but the solution looks a bit too ugly for my tastes when there are other alternatives.

In the end, I just ditched the Vector3 struct and used a class that held a Vector3. Seems like a hassle to try and fight it.

Share this post


Link to post
Share on other sites

This topic is 2628 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this