0

I want to know what is the fastest way to find the index of an item in a list. The reason I want to know is because I am making a XNA render but I started getting out of memory exceptions on larger models when I only used a vertex buffer, so I have now implemented an index buffer system. My problem is that I now have to continuously scan a list containing all my Vector3s for the index of the one that I want placed next in my index buffer. I am currently scanning for indices like this:

        for (int i = 1; i < circleVect.Length; i++)
        {
            indices.Add(vertices.FindIndex(v3 => v3 == circleVect[i]));
            indices.Add(vertices.FindIndex(v3 => v3 == circleVect[i - 1]));
            indices.Add(vertices.FindIndex(v3 => v3 == middle));
        }

This works fine except for the fact that it is rather slow. It takes almost 1 second for one cylinder to be calculated and I have more than 70 000 of them in my large model. I have therefore been seeing a loading screen for more than 20 minutes while loading my larger model and it still is not completed. This is unfortunately simply unacceptable. If I try loading my smaller model it takes more than 5 minutes whereas the unindexed loader took merely a second or so.

I have absolutely no formal training in C# and even less in XNA so I know this is probably a very inefficient way of calculating the indices so I would therefore appreciate it if any of you could assist me in creating a more efficient importer.

PS. If necessary I can change the list to an array but this would be a last resort option because it could potentially put strain on the system memory (causing an exception) and would mean quite a bit of coding for me.

Gerharddc
  • 3,921
  • 8
  • 45
  • 83
  • If the vertices are sorted, then the fastest way would be to use a binary search. Changing between list and array won't change anything (unless you are using a linked list). You should post what you are trying to accomplish rather than "how can i make this faster" since I don't think you can get much faster than what you have now, but what you have now isn't ideal and you likely should be looking at other data structures. – Darren Kopp Jun 07 '13 at 15:44
  • What exactly do you want to know? I am basically reading from a format that contains lots of linesegments which represent cylinders. I then calculate a quad(for now) at bot ends and four quads to connect them. The vertexes for the two squares and their centres are added to a list and the rest is then calculated as shown above by determining a Vector 3, searching for its index and adding it to the list. – Gerharddc Jun 07 '13 at 15:55
  • Have you just tried using IndexOf instead of FindIndex? There is definitely overhead involved in passing a lambda for each find. Not saying that's the answer, but I think it may help a lot. – Paul Ramsperger Jun 07 '13 at 16:20
  • I am not really sure how to implement an IndexOf for my purpose, could you possibly help? – Gerharddc Jun 07 '13 at 16:24
  • vertices.IndexOf (circleVert [i]) – Paul Ramsperger Jun 07 '13 at 16:54
  • Sorry, internet went down and commented from my phone. Replace "vertices.FindIndex(v3 => v3 == circleVert[i])" with "vertices.IndexOf(circleVert[i])" – Paul Ramsperger Jun 07 '13 at 17:04
  • Just a sanity-checking question, but you *are* loading the `VertexBuffer` only once and calling `Dispose` on it appropriately when you're done with it, *right*? The C# garbage collector doesn't know about [GPU memory](http://stackoverflow.com/a/3433209/165500), so you can't rely on it to clean up these objects for you. You must do it yourself. If you don't, you can very easily run out of GPU memory, in which case XNA will start emitting generic out-of-memory errors. – Andrew Russell Jun 07 '13 at 17:21
  • Also, the reason your existing implementation is so slow is that you're allocating a new heap object each time you use `=>`. You're churning a lot of memory, hence the slowness. – Andrew Russell Jun 07 '13 at 17:26
  • Finally, please consider that what you are doing appears to be very wrong. Most normal scenarios do not require doing this - usually you're able to generate an index buffer at the same time that you generate a vertex buffer. Please do consider the possibility that you're taking the wrong approach - consider zooming out and maybe asking another question (perhaps on [GameDev SE](http://gamedev.stackexchange.com/)) with more details of the overall problem you are trying to solve. – Andrew Russell Jun 07 '13 at 17:33
  • @AndrewRussell Thanks, I'll consider your suggestion but the problem cannot be with the buffer because the error occurs before I come even close to setting the buffer, it occurs when I try to convert a list to an array (I am assuming this is because the list is to large to be saved in consecutive memory slots) – Gerharddc Jun 07 '13 at 17:50
  • @Gerhman Please note that C#'s `List` is a contiguous block of memory (like C++'s `std::vector`, or an array). It is not a linked list (that's `LinkedList`). – Andrew Russell Jun 08 '13 at 02:27

4 Answers4

0

in your code you are looping through your vertices 3 times one for each FindIndex line. Instead use one for loop and traverse and check for all three conditions in 1 go.

Guanxi
  • 3,103
  • 21
  • 38
  • This does indeed sound like a good idea but could you possibly give me an explanation of how to do this or possibly an example of sorts? – Gerharddc Jun 07 '13 at 15:50
0
for (int i = 1; i < circleVect.Length; i++)
{
    for (int j = 0; j < vertices.Count; j++)
    {
        var v3 = vertices[j]; 
        if (v3 == circleVect[i] || v3 == circleVect[i - 1] || v3 == middle)
            indices.Add(j);
    }
}

You may want to consider adding logic to stop the inner loop from checking after all three of the indexes have been found.

JG in SD
  • 5,427
  • 3
  • 34
  • 46
0

Your main performance killer is searching in a List of 70 000 items which takes 70 000 operations. This will work a lot faster than searching in a list. 

 Dictionary<int, Vertice> vertices = new Dictionary<int, Vertice>();

            for (int i = 1; i < vertices.Length; i++)
            {
                if (vertices.ContainsKey(vertices[i]))
                {
                    indices.Add(vertices[i]);
                }
                if (vertices.ContainsKey(vertices[i - 1]))
                {
                    indices.Add(vertices[i - 1]);
                }
                if (vertices.ContainsKey(vertices[middle]))
                {
                    indices.Add(vertices[middle]);
                }
            }

edit: if searching in the list takes 2 seconds, searching in a dictionary will take 00:00:02 seconds

Georgi-it
  • 3,676
  • 1
  • 20
  • 23
0

Thanks for all the answers but none of them really worked and really appeard to be faster than what I had. I ended up having to create a structure where I could calculate the needed list index based on a given reference point.

Gerharddc
  • 3,921
  • 8
  • 45
  • 83