This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [RFC] Offloading Support in libgomp
- From: "Michael V. Zolotukhin" <michael dot v dot zolotukhin at gmail dot com>
- To: Jakub Jelinek <jakub at redhat dot com>
- Cc: Marek Polacek <polacek at redhat dot com>, Kirill Yukhin <kirill dot yukhin at gmail dot com>, Richard Henderson <rth at redhat dot com>, gcc-patches at gcc dot gnu dot org, triegel at redhat dot com
- Date: Mon, 16 Sep 2013 12:07:20 +0400
- Subject: Re: [RFC] Offloading Support in libgomp
- Authentication-results: sourceware.org; auth=none
- References: <20130913131109 dot GD30181 at msticlxl57 dot ims dot intel dot com> <20130913131556 dot GD1817 at tucnak dot redhat dot com> <20130913153527 dot GH1817 at tucnak dot redhat dot com> <20130913154103 dot GT23899 at redhat dot com> <20130914192956 dot GI1817 at tucnak dot redhat dot com> <20130915093007 dot GA60139 at msticlxl57 dot ims dot intel dot com> <20130915154124 dot GB60139 at msticlxl57 dot ims dot intel dot com> <20130916064444 dot GK1817 at tucnak dot redhat dot com> <20130916071516 dot GC60139 at msticlxl57 dot ims dot intel dot com> <20130916073114 dot GL1817 at tucnak dot redhat dot com>
> 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.
Michael
> Jakub