Sign in to follow this  
SpikeViper

List.Sort() lag

Recommended Posts

Currently, I have a list that hits around 15,000 objects that is sorted using

toLoad.Sort(delegate (Vector4 first, Vector4 second) { return first.w.CompareTo(second.w); });

As expected, this generates a bit of lag. I was wondering if there are any better data types to store so much (that can still be sorted, of course). I was also wondering if the way I'm sorting it is part of the problem.

Share this post


Link to post
Share on other sites

How are you adding those objects? Perhaps something that keeps the list ordered all the time will work better. I would think that if it is possible it's probably better to insert the item int he correct position as you add it than it is to add to the end and then sort. You'd need to use a container that supports insertion like a linked list.

Edited by Nanoha

Share this post


Link to post
Share on other sites

How are you adding those objects? Perhaps something that keeps the list ordered all the time will work better. I would think that if it is possible it's probably better to insert the item int he correct position as you add it than it is to add to the end and then sort. You'd need to use a container that supports insertion like a linked list.

I'm adding them with this:

toLoad.Add(new Vector4(x, y, z, distanceSq));

I want the closest ones (ones with smallest distance) to load first, Problem with using something like a sorted dictionary is sometimes 2 objects are at the same distance, and you can't have 2 identical keys.

Share this post


Link to post
Share on other sites

Yeah, if the list of objects is "temporally coherent", then you can speed up sorting by using a sorting algorithm that can take advantage of that (one that is faster with partially sorted list).

 

The data structure you mentioned is called "multimap" I believe, there doesnt seem to be one in C# by default, but Im sure you can find an implementation (or create one yourself). Assuming that is what you actually need.

 

Then of course you can just try to find a faster sorting algorithm, or use multithreading, if nothing else works.

 

Probably if you make your vectors smaller in terms of memory, and ensure there is not some weird C# garbage collection slowing you down, that might help.

Share this post


Link to post
Share on other sites

There are sorted containers. In C# the built in sorted containers are SortedList or SortedDictionary, depending on what data you are storing.

 

You will still pay the cost of sorting, but the cost is paid at insertion time. 

 

 

If possible, organize your containers so they can be kept around and don't need to be re-sorted.  

 

As others mentioned there are also many different sorting algorithms. if you know certain useful properties of your objects there may be better sorting algorithms. For instance, if your list is mostly sorted already is probably to run the InsertionSort or similar algorithm.  By default C#'s list Sort() uses insertion sort, heapsort, or quicksort depending on the size of the container.

Share this post


Link to post
Share on other sites

Yeah, if the list of objects is "temporally coherent", then you can speed up sorting by using a sorting algorithm that can take advantage of that (one that is faster with partially sorted list).

 

The data structure you mentioned is called "multimap" I believe, there doesnt seem to be one in C# by default, but Im sure you can find an implementation (or create one yourself). Assuming that is what you actually need.

 

Then of course you can just try to find a faster sorting algorithm, or use multithreading, if nothing else works.

 

Probably if you make your vectors smaller in terms of memory, and ensure there is not some weird C# garbage collection slowing you down, that might help.

I tried a multimap implementation, and is was actually quite a bit slower than the list.

When I use the delegate to sort, is that delegate being thrown into the GC each time?

 

Frob, I'm using a loop to find all the chunks within range and adding them to the list. The problem is, since its a loop, if I don't sort it the planet will load row by row, rather than closest to the player.

Edited by SpikeViper

Share this post


Link to post
Share on other sites

 around 15,000 objects ... I'm using a loop to find all the chunks within range and adding them to the list.

 

Good to know.  So you cannot preserve the list and it is still a one-time use, so using a sorted container is probably not useful.

 

 I don't sort it the planet will load row by row, rather than closest to the player.

 

That information would have been useful up front.  Your data has natural properties that can be leveraged.

 

Then the next general advice is to use a spatial partitioning scheme (levels, zones, spatial hashes, bsp trees, quadtrees, octrees, etc) to reduce the problem set.  Instead of going through all 15000 objects in your 'planet', contain them in a structural hierarchy or other divisions. This can reduce it to closer to the number actually needed rather than 15000 each time.

Share this post


Link to post
Share on other sites

 The problem is, since its a loop, if I don't sort it the planet will load row by row, rather than closest to the player.

 

 

You could also iterate through the planet chunks in an order that corresponds to distance from the player... This might be a more "algorithimically complicated" way to address your issue, but sorting won't be needed. Off the top of my head, I feel that the Bresenham's line algorithm (or a 3d equivalent) might work for this.

Share this post


Link to post
Share on other sites

 

 The problem is, since its a loop, if I don't sort it the planet will load row by row, rather than closest to the player.

 

 

You could also iterate through the planet chunks in an order that corresponds to distance from the player... This might be a more "algorithimically complicated" way to address your issue, but sorting won't be needed. Off the top of my head, I feel that the Bresenham's line algorithm (or a 3d equivalent) might work for this.

 

That sounds like the best way to do it, but I'm not exactly a math whiz.

Share this post


Link to post
Share on other sites

I assume this is some minecraft like world as you mention chunks?

 

Are your chunks such that you can recreate them when needed, either loaded or created again when needed?

 

If so only hold the ones needed in memory then then pull them in as required, ditching ones that then fall out of scope.

 

If you need everything in ram, how about holding them in some form of spacial aware structure like a 2D or 3D array, depending on needs. Then it is easier to determine distance in relation to the player without the need of a list that long your constantly need to sort, you simply ignore anything further than some delta from the player location

Edited by WozNZ

Share this post


Link to post
Share on other sites

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