search

programmatom / TreeLib

Balanced Binary Trees - Rank Augmented
http://programmatom.github.io/TreeLib/
GNU Lesser General Public License v3.0
11 stars 4 forks source link

Remove threading from AVL #6

Closed programmatom closed 8 years ago

programmatom commented 8 years ago

Remove threading from AVL tree implementation. Threading doesn't help much in dictionary case, since we get O(N) traversal using stack method of enumeration. It buys nothing in augmented cases, since offsets must be calculated on descent from root, so it's a net performance drag in those cases.

Konard commented 8 years ago

Can you compare actual performance of traversal using stack-based implementation and threads? And also can you measure degration in performance required to maintain threads? Looks like threads should be an option, not a predefined decision.

programmatom commented 8 years ago

In fact, the threading isn't being used at all right now except in the Clear() method. To make a fair comparison I will need to write a special version of the 'fast' enumerator for map/list case that uses the threads rather than the stack, and then measure.

On 7/2/2016 3:18 AM, Konstantin Dyachenko wrote:

Can you compare actual performance of traversal using stack-based implementation and threads? And also can you measure degration in performance required to maintain threads? Looks like threads should be an option, not a predefined decision.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/programmatom/TreeLib/issues/6#issuecomment-230094635, or mute the thread https://github.com/notifications/unsubscribe/AH8vqhQYGKq4MWIVnak8p9-ckzzDORfnks5qRjrjgaJpZM4JCa6m.

Konard commented 8 years ago

As a developer of Links Platform I have one place where performance should be significantly improved when using threads (iteration through a range of values from x to y in a tree, this is serves as an database index in my projects, and allows to get all the links, which reference another link). Problem with stack that it uses memory allocation, it should be always slower when a memory access. Unless you can use stackalloc, but this requires to use code generation or avoid generics.

programmatom commented 8 years ago

I measured and there was a modest performance improvement using threads instead of stack to iterate in map/list case. It doesn't appear to be due to eliminating the allocation. Instead, the improvement results from eliminating the array bounds checks on the stack element access.

programmatom commented 8 years ago

Enumeration by threading is enabled for map/list case. Threading is removed for all augmented cases.