1

I'm writing a 2D infinite Terrain Editor with focus on performance. Each time the user paints, he creates Nodes which at the moment are assigned to Dictionaries in "Layer" classes. Since the user can paint over existing nodes while he's on a different Layer, I want to find those nodes and destroy them. With my current setup this would involve looping through all the Layers and getting the necessary nodes one by one from the dictionaries.

Obviously, this is way too expensive if done tens of thousands of times per frame. So now I thought I could create just one Dictionary with all the nodes in lists. However, this turns out to use almost as much performance as the previous setup, because now I have to perform a check for whether a Key already exists when instantiating new Nodes :

before:

public Node(){ dic.Add(key,this); }

now:

public Node(){ List<Node> nodes; if(dic.TryGetValue(key,out nodes)) nodes.Add(this); else{ list = new List<Node>(); dic.Add(key,list); } }

As you can see, while the current setup saves some performance when checking for nodes, it completely ruins the effect by inflating the instantiation time by the dictionary lookup time.

So now I'm looking for some way to get the same effect as Dictionary<Key,List<Node>> , but without the cost of looking up the list in the dictionary. Is there perhaps a different type of dictionary that lets one stack an infinite (or if necessary a limited) number of Values per Key?

Alternatively, is it possible to somehow order the values in the dictionary so I could use a normal Dictionary<key, Node> and then look up the first key and loop from there through all the values until I hit some Node which no longer fits the search criteria?

In pseudo code, my instantiation functions would look like this :

public Node(){ dic.Add(key+LayerIndex,this); }

and my lookup function would look something like this

public LookUpAll(key, out list){ var o = dic[key]; // looking up just one node list.Add(o); var keyPosition = o.keyPosition; while(o.position == keyPosition){ // then looping through all other nodes at that position until one comes that has a different position. o = dic.NextValue(); list.Add(o); } }

Now, this does not work as is on the unsorted dictionary, but since I was hoping that someone here could maybe get some inspiration from it and work out a working solution.

How do I reduce the number of lookups in my scenario, or add multiple values per key without looking up the key first?

Improve this question
4
  • Are you sure that the dictionary lookup is the bottleneck of this procedure? Commented Jan 14, 2014 at 14:26
  • I've run some benchmarks now, if I instantiate 500^2 nodes, then the performance cost addition of the check makes up something between 1/2 and 1 % . To be honest, I expected it to be greater since it used to be a major bottleneck in the past until I overwrote the hash function, but even so it would be nice to get rid of it, especially since I hope to further increase the performance and I don't want for this thing to become a real bottleneck in the future. Commented Jan 14, 2014 at 15:07
  • For your alternate solution, consider using a SortedDictionary<TKey, TValue>. You would then pass your own implementation of IComparer for the key so that the dictionary will be properly sorted to suit your lookup requirements. I cannot speak to whether this will be more or less performant. Commented Jan 14, 2014 at 15:40
  • @aaron Thanks, I will try it, I had already resigned myself to hit the bench again and write some sort of n-tree solution,but a properly sorted dictionary would be so much easier. Commented Jan 14, 2014 at 15:49

2 Answers 2

Reset to default
1

Since the user can paint over existing nodes while he's on a different Layer,

I'm going to assume that this is so that you do not end up persisting data that you don't need. But what if the user doesn't intend on deleting data on that layer? He just wants to "see" how something looks. Then he undoes his change and blammo, you have no data on the change he just did so you can't undo it.

Why not just keep all the nodes unless the user explicitly tries to delete them? The end user can always choose what is frustum culled in his end result.

You could also try using a tree-like structure.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

You're raising a very good point, I hadn't thought of reversibility yet. However, a major reason for all this microoptimisation is the need for the script to also run during gameplay. I want it to be able to generate terrain in realtime without having to rely on a multithreading to hide the performance cost.
saying you don't want to rely on multithreading to "hide the performance cost" is confusing me because multithreading is a tool that is there to be used. Either way dictionary lookup is very fast. As someone mentioned, are you sure the dictionary is the bottleneck? In addition, have you even benchmarked this or is it just premature optimization (evil)?
Yeah, I was evil... But I still would like to save performance anywhere I can. So can you please elaborate your tree-like structure? Did you mean something along the lines of what Bas Brekelmans posted?
0

If you only care about the topmost node related to a certain key, and on occasion need to iterate over all nodes you could construct a linked list from your nodes. This allows you to iterate over nodes and retrieve the relevant node by key. However it increases the memory consumption of your nodes. You could minimize this by creating a subclass of Node that holds a Next property while leaving the normal nodes without the possibility of an underlying node. This might slow down iteration though.

public Node Next { get; set; } public Node() { Node next; if (dic.TryGetValue(key, out next)) this.Next = next; dic[key] = this; }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.