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 11:15:16 +0400
- Subject: Re: [RFC] Offloading Support in libgomp
- Authentication-results: sourceware.org; auth=none
- References: <20130913112930 dot GC30181 at msticlxl57 dot ims dot intel dot com> <20130913123614 dot GB1817 at tucnak dot redhat dot com> <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>
> Yes, splay tree can get totally unbalanced and you can have a linear lookup
> time, the O(log n) lookup time is amortized. But, if you e.g. really do
> lookup sorted keys (which is not given, the compiler puts vars into the
> clauses based on the user order or in the order references to those vars are
> discovered, plus for array sections pointer kinds which usually have
> different addresses go immediately after the data ones), you really can have
> one O(n) lookup if you've looked e.g. the highest address last time and now
> you're looking up the lowest and the tree is totally unbalanced, but then
> won't the following lookups be all O(1), because the keys you are looking up
> will be always immediately in the right child?
If the first time the lookup was in increasing keys order, and then we are
looking up in decreasing keys order, then yes, there is no problem and at the
beginning the element we are looking for would be very close to root, so it
would be fast (at the end I guess there would be still O(log N)). The problem
would be if the order of the 2nd lookup is the same as the order of the 1st
lookup.
> Anyway, if the splay trees ever cause issues in real-world, it is not hard
> to just replace them by something else (R-B trees, AVL trees or similar).
Yes, agreed.
Michael
> Jakub