Comparing locking strategies in large highly mutable loose quadtrees

Abstract: Using a quadtree to store points or geometrical shapes in two dimensional environments is a well tried-out approach shown to be able to provide both fast updates of the carried data as well as fast intersect-checks for a specified area. These are all useful abilities for a data structure when tracking, for instance, emergency vehicles for operator centrals. Tweaking this data structure to achieve even better performance can only get you that far and sooner or later other measures will be needed in order to reach higher capacity. For instance it could be the case that the flow of information needs to move quicker to supply the operators with the information they need. One such measure commonly used in the field is the act of making the data structure concurrent. On a multithreaded machine a program that has been made concurrent can gain a speed up of up to the number of cores used, meaning the total running time can be improved plentiful. In this thesis the loose quadtree with buckets is evaluated when different kinds of common parallelism approaches are applied. Batching in the form of bunchingup incoming calls are done in two different lines of action, simply going through the queue of operations as well as rebuilding the tree with the changes applied to create a new tree. Other approaches build upon the strategy of handover-hand-locking to try out how the tree works with node-coupled locks as well as to fully lock the data structure upon every interaction. These tactics are compared in different scenarios matching real-world appearances and evaluated both as a whole as well as for each individual scenario. The results show that the best approach, the one with the highest average total throughput, is the one where there is only one lock used for access to the datastructure, performing especially well in comparison for grouped up objects. One interesting feature which is shown to create faster execution in the parallel context is the use of something called dummy-layers. Adding these to the data structure allowed it to become more concurrent on the cost of putting a tighter constraint on object size. The main contribution made in this thesis is the foundation it creates for further work in this specific area. Due to the lack of previous work there was little to go on except for translating solutions for different structures and thus restricted the amount of work that could be done. So with this work simple solutions are provided with different main strategies in mind, allowing future work to compare themselves to these solutions or even develop them further if this is deemed gaining. A secondary contribution is also some results on how performance for the loose quadtree becomes when used with four writing threads and two reading threads.