Re: switched sparse format to binary trees

[Patrick Alken <patrick dot alken at Colorado dot EDU>]

On 04/28/2014 04:35 PM, Gerard Jungman wrote:
> 
> On 04/27/2014 07:32 PM, Patrick Alken wrote:
> 
>> This actually makes a huge speed improvement in duplicate detection and
>> element retrieval for large sparse matrices. There may however be a
>> performance hit since a new tree node must be allocated each time an
>> element is added to the matrix. But I believe the tradeoff is worth it.
> 
> 
> For what it's worth, the right thing to do is probably
> to expose the avl allocation strategy to the GSL client
> in some way. It could be as simple as an extra argument
> to gsl_spmatrix_alloc(), which could be a pointer to a
> generic allocator strategy struct (similar or identical
> to 'struct libavl_allocator'). This is the most general
> solution, which requires that clients who care be able
> to write their own allocator.

Interesting idea...I'll think a bit more on it. Unfortunately I don't
think there is any easy way to preallocate a binary tree. Even if the
user knows ahead of time how many elements they want to add to the
sparse matrix, its not so easy to preallocate the whole tree, since
after each insertion, the tree rebalances itself to minimize its height.

I did do some tests on my own machine, inserting 2.5M elements into a
sparse matrix and profiling the code. I found that the avl allocation of
a new node was insignificant, compared to searching the tree each time
to check for duplicate elements.

I also found a study online where people benchmarked various sparse
matrix storage strategies. The other main contender is to use a hash
table, which is what matlab does for its sparse matrices. For that
approach you need to develop a strategy to deal with hash collisions,
which can happen frequently for huge matrices.

Anyway the study found that AVL trees were much superior to hash tables
in terms of speed. The study is here:

http://link.springer.com/chapter/10.1007%2F978-3-540-25944-2_135

Anyway, its a good idea to give the user more control over the
allocation, so I will think some more on how to do this elegantly.

Patrick