Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In the past, I've had alot of success just using a .NET Dictionary, with a TKey consisting of the X,Y coordinates merged together. However its read performance, despite being amortized constant time, is a bottleneck in a design of mine.

My application needs to perform alot of reads, and would benefit greatly if the performance of the read was similar to that of an array. My data has a very high degree of spatial locality; attached is an image showing two graphs of the distribution of some sample data on a 2D plane (sorry for the lack of labels); on the left is data with low spatial locality, and on the right is how my data looks (it's always a single connected mass, and blocky in form).

enter image description here

I could use an array (by computing a bounding rectangle (bRect) around the data and then doing data=array[(y-bRect.Top)*bRect.Height+x-bRect.Left]) but then I'd have to rebuild the entire array each time bRect.Height changed, or bRect.Width increased.

And so my question is, given the high degree of spatial locality, is Dictionary really the best choice here? Is there another approach I could take where I could get near array like read performance, yet not have to rebuild the array when data is added? (I don't need to ever remove data)

share|improve this question
    
The performance of the dictionary will heavily depend on how you calculate hash based on X and Y value. Can you show us how you do it? –  Euphoric Dec 14 '13 at 10:50
    
@Euphoric (x<<16)|y where x and y are both 16 bits and hash codes are 32 bits. –  Mr. Smith Dec 14 '13 at 10:53
    
“but then I'd have to rebuild the entire array each time I inserted data” Does that mean that the size of the grid changes? –  svick Dec 14 '13 at 15:18
2  
You appear to be describing a sparse matrix - currently you are using a DOK approach, but there are 5 other approaches to the general problem that have different trade offs. –  MichaelT Dec 14 '13 at 18:00
3  
How much memory can you afford? You can decrease the number of table rebuilds you have to do by over-allocating space in the first place. So if you insert insert a new point with height x > current table height, you rebuild the table with height=x*1.5, or whatever gives you the best performance. –  MikeFHay Dec 14 '13 at 20:11

3 Answers 3

up vote 3 down vote accepted

I don't really think there is way to make it quicker. According to MSDN, the retrieval time of Dictionary is close to O(1), which is as fast as you can get. And the way you calculate the hash value has no room for hash collisions.

Only thing you can do right now is to change the algorithm to minimize number of reads.

So, I tried to do some quick benchmarking. I used 3 algorithms: HashSet, Dictonary and simple Quadtree implementation. I made 2 datasets, first with completely random distribution. Second was made by creating random boxes and filling them up. The read dataset was random distribution. HashSet and Dictionary are pretty similar. Results are in ticks:

  • HashSet
    • Even distribution : 350000
    • Box distribution : 430000
  • Quadtree
    • Even distribution : 1510000
    • Box distribution : 490000

You can get my source here: http://www.mediafire.com/download/4bcrc41my23k9ef/PerfTest.zip

Your test makes little sense. First, why are you saving points? Shouldn't you save booleans or ints or something? Also, if you are filling the whole space, then dictionary is not going to make much sense. Second, the way your read the data has huge memory locality. Are you sure you are going to read the data in such sequential manner? This is reason why I'm randomizing the order of access in my benchmark. Next thing is that rectangle of yours. Are you sure you are going to have only one? Your algorithm is going to break down if you are going to have multiple. And are you sure you are able to rebuild such bounding box from the data you have on the input? Is this algorithm you can directly use in your problem or is it something you need to change? If later, then the results are useless and non-informative.

share|improve this answer
4  
You might be right, but keep in mind O(1) doesn't mean fast. O(n) can be faster than O(1) on many occasions. And an array's O(1) is much faster than a Dictionary's O(1). –  Mr. Smith Dec 14 '13 at 10:59
    
@Mr.Smith The point of O(1) is that it is always same speed no matter how big or complex your data is. With O(n), the more data you have, the slower it gets. In your case, you can't really have so few data that O(n) becomes faster than O(1). –  Euphoric Dec 14 '13 at 11:02
2  
@Euphoric:O(1) may be constant time no matter the size, but if that constant time is 100 ms but another approach that is O(n) only takes 100 us (except for very high n), then the 1,000 times difference in speed will make a huge impact in the algorithms performance, despite O(1) being a theoretically better algorithm. –  Dunk Dec 14 '13 at 17:00
    
@Dunk If that was the case, then it would be said in structure's description. But knowing it is using a hash table, then only operations is is doing is hashing the value and accessing the array. So the constant time is extremely low. And cases where O(n) with reasonable n is faster than O(1) are few. –  Euphoric Dec 14 '13 at 17:03
1  
Good call on the memory locality; instead of for(y)for(x) I switched it to for(x)for(y) (causing y*h+x to be effectively random) and performance went from 1012% to 270%. At that low of difference, it's not worth the effort. You were right all along. –  Mr. Smith Dec 16 '13 at 22:53

If the blocks are relatively big and there is a relatively small number of them, then I can see two approaches that could help you:

  1. Decompose each block into rectangles and then store them in an R-tree.
  2. Split the plane evenly into quadrants. For each quadrant that is not homogeneous (either completely empty or completely filled), continue splitting recursively. This structure is called quadtree.
share|improve this answer
    
Those are the two things I thought of on seeing that data too. –  Donal Fellows Dec 15 '13 at 7:33
1  
I did think of this too at first. But I'm willing to bet dictionary is still going to be faster when he benchmarks it. –  Euphoric Dec 15 '13 at 7:37
    
@Euphoric: True, unless his grid plane is too large to fit in RAM. –  Brian Mar 14 at 19:41

I could use an array (by computing a bounding rectangle (bRect) around the data and then doing data=array[(y-bRect.Top)*bRect.Height+x-bRect.Left]) but then I'd have to rebuild the entire array each time bRect.Height changed, or bRect.Width increased.

Utilize the Cantor pairing function as your hash function. I would also assume that using the cantor pairing function to index in a plain array is somewhat faster than an hash table because the overhead of checking for an collision and modulo operations can be avoided.

How big is your array? If it doesn't fit in L2 cache, you may want to consider Z-order curves to help with spatial locality. It is also possible to use hilbert curves with the same result, but that seems quite expensive compared to Z-order curves.

I should also note that when you have a single connected mass, storing data per pixel may not be the best approach. It might be possible to speed up your algorithm by generating mipmaps (lower resolution versions of your data) and reading from that to help keeping everything in cache.

Since you mentioned reading is the bottleneck, moving the computation to the GPU may lead to some degree of success.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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