This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC] Offloading Support in libgomp

> No.  If you insert 1 to 100 into a splay tree in ascending order (that will
> give you a totally unbalanced tree), and then lookup 1 to 100 in the
> ascending order again, then the lookup of 1 will be expensive (100
> comparisons), but then for each following lookup it
> will cost just 2 comparisons, so for the 100 lookups you'll need 298
> comparisons, i.e. ~ 3 comparisons per lookup on average (rather than the 6-7
> lookups you'd get for balanced AVL tree or similar).  Splay trees
> actually behave very nicely if the lookups are done in sorted orders or
> if you usually look up similar addresses in sequence (which is quite likely,
> usually the splay tree will contain addresses of #pragma omp declare target
> vars (and selected functions) and typically lookups for #pragma omp target
> will be usually for function local variables which will have similar
> addresses), and if what you lookup is completely random, then you wouldn't
> end up with an unbalanced tree.
Maybe you are right, so splay trees might be the best choice here indeed.

> 	Jakub

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]